Dotaz: rychlost kodu

[secido]

Porovnaval som rychlost programu (napisany v C) pod roznymi operacnymi systemami a nestihal som sa divit. HW je Turion@1.8. Vo win32/gcc3 bezal 40s, linux/gcc3 aj gcc4 amd64 90s (!) a nakoniec freebsd/gcc3 amd64 28s. Mam niekde problem alebo je ten linux taky pomaly?

Odpovědi

[VícNežNic]

To je bez toho programu těžko posoudit (z kolika měření jsou ty výsledky?)

[secido]

Z dvoch-troch behov. Linux sa mi podarilo stiahnut na 76s v single user s vypnutym throttlingom. Ale aj tak je to vela, nechapem. Preco bez programu tazko posudit? gcc je ine na bsd ako v linuxe? Optimalizacia bola zapnuta -O2.

[_]

cpufreq v jadre mas nastaveny na powersave governor, ze?

jaky parametry jsi pouzil pri kompilaci?

jaky parametry se doplnily ze specs z gcc?

na kolika mistech provadis dlopen/fork?

[secido]

Ked mi napises ako tieto veci zistim, mozem ich doplnit.

[secido]

Skusil som aj na inom 64bitovom linuxe - konkretne Ubuntu 6.06 TLS x86_64, gcc 4.0.3, procesor AMD Athlon(tm) 64 Processor 3500+ (2.2GHz), kernel 2.6.15.7. Priemerny cas 1m, z toho 99% user. dlopen() a fork() vobec nepouzivam, je to ansi C (snad . Parametre pri kompilacii gcc -O2 -Wall -g.

[*]

No ja to nepouzivam, takze jen po pameti, kdyz jsem to pred par lety objevil a vypnul... tusim /proc/cpufreq - jestli neexistuje ten soubor a existuje radek proc v /proc/filesystem tak to nepouzivas.

parametry si sem napsal.

cat /usr/lib/gcc-lib/*/*/specs

a fork a dlopen si nepouzil.

a jeste maji knihovny premapovany adresni prostory na nahodny mista prelinkem?

pouzivas knihovny s debug symbolama? jak casto se volaji knihovni funkce? (ltrace)

[secido]

Pridavam kus kodu, ktory sa toci v slucke. Boli to moje programatorske zaciatky, tak sa nesmejte . Pozeram, ze sa pouziva viac globalnych premmenych ako by bolo zdrave.

void PridajRiadokNovy(void) {
  int i, j, tmp, tmp2, xx=dlzka;

  tmp = dalsi * c_tz;
  for(i=0;i<c_tz;i++) {
    if(znacka2[pole[tmp+i]]) continue;
    for(j=0;j<c_max;j++) {
      if(!znacka[tmp2 = pole2[pole[tmp+i]*c_max+j]]) {
        znacka[tmp2]++;
        dlzka++;
      }
    }
    znacka2[pole[tmp+i]]++;
  }
  predch=dlzka-xx;
  if(!dalsi) for(i=0;i<c_rt;i++) zrychli[i]=predch;
  riadok[dalsi]++;
  cnt++;
}

void DalsiRiadokNovy(void) {
  int i, j, k, tmp, tmp2;
  mini = 0;

  for(k=0;k<c_rt;k++){
    if(!riadok[k]) {
      if(zrychli[k]<=mini) continue;
      tmp = k * c_tz;
      teraz = 0;
      memset(znacka3, 0, c_ru);
      for(i=0;i<c_tz;i++) {
        if(znacka2[pole[tmp+i]]) continue;
        for(j=0;j<c_max;j++)
          if(!znacka[tmp2 = pole2[pole[tmp+i]*c_max+j]] && !znacka3[tmp2]) {
            teraz++;
            znacka3[tmp2]++;
          }
      }
      zrychli[k]=teraz;
      if(teraz > mini) {
        dalsi = k;
        mini = teraz;
      }
      if(predch==teraz) break;
    }
  }
}

[VícNežNic]

Právě proto. Když máme gcc víceméně stejný, tak z něho vyleze víceméně stejný kód a ten se těžko bude vykonávat různě rychle. Takže problém by měl být někde mimo program, v tom co volá, ne?

Co vypisuje time na FreeBSD a Linux, nejsou tam třeba nějaké radikální rozdíly v poměrech jednotlivých složek?

[_]

> Právě proto. Když máme gcc víceméně stejný, tak z něho vyleze víceméně stejný kód a ten se těžko bude vykonávat různě rychle.

ne. rozdil muze byt i sto nasobny.

[_]

> rozdil muze byt i sto nasobny.

samozrejme s tim samym kompilatorem na tom samem systemu s tim samym kodem. opravdu zalezi na tom, jak se to prelozi.

[secido]

Kod je rovnaky samozrejme, kompilator nie uplne rovnaky. Na win32 som pouzil mingw gcc 3.4.2. Linux gcc 4.0.3, 3.3 aj 3.4 s priblizne rovnakym vysledkom na urovni cca 2x windows. Nieco asi bude v tom systeme rozbite, skusim pozriet co vsetko tam bezi. FreeBSD 7.0 current s distribucnym gcc (tusim 3.4) sa javi ako uplne eso co sa tyka rychlosti a aj napr. pri kompilacii akehokolvek kodu je rychle ako blesk.

[Michal Kubeček]

Pokud jsem něco zásadního nepřehlédl, ten fragment kódu, který jste tu ukázal, nevolá žádný syscall, přímo ani nepřímo. Takže mi není moc jasné, jak z rychlosti jeho provádění chcete vyvozovat závěry o rychlosti Linuxu…

[secido]

Jednoducho skompilovany program bezi na linuxe pomalsie ako na inom systeme, ja sa len pytam preco resp. ako je take nieco mozne. Lebo ked sa takto sprava jeden program, mozu sa aj ine.

[secido]

Nemoze to byt rozdielnymi libc, kedze volam memset?

[Michal Kubeček]

U aktuálních verzí gcc by AFAIK měly funkce typu memset() být implementovány přímo překladačem, takže by ani na volání knihovny nemělo dojít. Ale to byste se asi musel podívat do výsledného kódu (např. si to nechat přeložit jen do assembleru).

[secido]

Kazdopadne libc implementacia vo freebsd pre amd64 sa lisi od implementacie linuxovej glibc a pre i386 je tiez uplne ina. Skusil som tento kod:

$ cat memset.c
int main() {
  int num = 1;
  memset(&num, 0, sizeof(num));
}
$ gcc -S memset.c
$ cat memset.s
        .file   "memset.c"
        .text
.globl main
        .type   main, @function
main:
        pushl   %ebp
        movl    %esp, %ebp
        subl    $24, %esp
        andl    $-16, %esp
        movl    $0, %eax
        subl    %eax, %esp
        movl    $1, -4(%ebp)
        movl    $4, 8(%esp)
        movl    $0, 4(%esp)
        leal    -4(%ebp), %eax
        movl    %eax, (%esp)
        call    memset
        leave
        ret
        .size   main, .-main
        .section        .note.GNU-stack,"",@progbits
        .ident  "GCC: (GNU) 3.3.5 (Debian 1:3.3.5-13)"

Co z toho vidim?

[AraxoN]

Toto je dôležité

call    memset

a znamená to, že memset() je spracovaný ako každá iná funkcia. T.j. že sa na stack nahádžu jej parametre a potom sa zavolá nejaký ďalší kód od inokiaľ, ktorý podľa tých parametrov niečo robí. Ak by to bolo nadrôtované v GCC, tak by tam nebolo volanie funkcie ale nejaká asm inštrukcia s prefixom "rep", alebo "loop".

[AraxoN]

hehe, odpovedám sám na seba...

Pozeral som ako sa to kompiluje u mňa v GCC 4.1, a vo výsledku nikdy nie je call, a dokonca ani rep alebo loop. Záhada?

[michich]

Žádná záhada. V tomto případě překladač ví, že má vynulovat pamět o délce sizeof(int), což jde udělat jedinou instrukcí bez jakéhokoliv cyklu.

[AraxoN]

Njn, ale secidovi vyššie to vygenerovalo "call memset"... Skúšal som rôzne stupne optimalizácie, ale nikdy z toho u mňa nebol call, rep či loop.

[Michal Kubeček]

Jenže on použil gcc 3.3.5 (nebo něco, co se za něj vydává :-) ).

[michich]

Jo, to je tím. Teď jsem si ověřil, že gcc 3.3.6-13 a 3.4.6-4 generují call memset, kdežto 4.1.1-13 ne.

[Michal Kubeček]

Neviděl bych v tom záhadu, odpovídá to tomu, co jsem psal: že některé funkce typu memset() nebo memcpy() mají novější verze gcc jako builtin. To naznačuje už fakt, že když zkusíte zkompilovat to, co zde bylo uvedeno, pomocí gcc 4.1, dostanete tuto chybu:

  mike@lion:~/tmp> gcc -S memset.c
  memset.c: In function ‘main’:
  memset.c:3: warning: incompatible implicit declaration of built-in function ‘memset’

[secido]

V poriadku, ale preco potom:

$ gcc --version|grep gcc
gcc (GCC) 4.0.3 (Ubuntu 4.0.3-1ubuntu5)
$ gcc -O2 -S gext.c
$ grep memset gext.s
        call    memset
        call    memset
        call    memset
        call    memset
        call    memset
$ grep memset gext.c
      memset(znacka3, 0, c_ru);
  memset(riadok, 0, c_rt);
  memset(znacka, 0, c_ru);
  memset(sucet, 0, sizeof(int)*c_rz);
  memset(znacka2, 0, c_rz);

[secido]

Stiahol som si gcc-core-4.1.1.tar.bz2 ale nevidim tam ziadnu asm implementaciu memset, len toto:

$ find . -name '*memset*'
./gcc/config/memset.c
./libiberty/memset.c
./libssp/memset-chk.c

co je v skutocnosti trivialny cyklus:

$ cat gcc/config/memset.c
/* Public domain.  */
#include <stddef.h>

void *
memset (void *dest, int val, size_t len)
{
  unsigned char *ptr = dest;
  while (len-- > 0)
    *ptr++ = val;
  return dest;
}

[secido]

Asm implementacie vo freebsd a linuxe. Hladajte rozdiel .

[secido]

Este maly navrat, memset() asi nie je dovod. Skompiloval som staticku binarku (ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), for GNU/Linux 2.2.0, statically linked, for GNU/Linux 2.2.0, stripped) a tato bezi na spominanom athlone (jadro 2.6.15-27-k7 z ubuntu) rychlejsie ako na duron 1600 (jadro 2.6.15.3 kompilovane pre i386).

[Michal Kubeček]

To o ničem nevypovídá, i když to slinkujete staticky, používá se pořád stejná implementace té funkce.

[secido]

Ano, pouziva sa rovnaka tak by aj rychlost mala byt rovnaka resp. zodpovedajuca rozdielu vo vykone hw, alebo sa mylim?

[Michal Kubeček]

Snažíme se vám od začátku vysvětlit, že rozdíl bude nejspíš v tom, že nespouštíte v obou případech totéž.

[secido]

Ak potom spustit to iste, ked ten isty skopirovany staticky linkovany spustitelny subor to iste nie je?

[Michal Kubeček]

On je to snad jediný proces, který vám v tom systému běží?

[secido]

Pochopitelne, ze nie, ale nebezi tam nic co by zatazovalo CPU tak, aby mohli vzniknut taketo rozdiely.

[Michal Kubeček]

To ale těžko můžeme posoudit, pokud jste jediný, kdo ví, o jakém programu je to vlastně řeč…

[secido]

Takze pomocou vynikajuceho nastroja menom profiler som definitivne vylucil memset. Dalsou skvelou utilitkou gcov som zistil kolko krat sa ktory riadok vykona, snad pomoze:

     2931:   46:void DalsiRiadokNovy(void) {
        -:   47:  int i, j, k, tmp, tmp2;
     2931:   48:  mini = 0;
        -:   49:
218359778:   50:  for(k=0;k<c_rt;k++){
218359667:   51:    if(!riadok[k]) {
216130000:   52:      if(zrychli[k]<=mini) continue;
  1236087:   53:      tmp = k * c_tz;
  1236087:   54:      teraz = 0;
  1236087:   55:      memset(znacka3, 0, c_ru);
  7416522:   56:      for(i=0;i<c_tz;i++) {
  6180435:   57:        if(znacka2[pole[tmp+i]]) continue;
135608850:   58:        for(j=0;j<c_max;j++)
130586300:   59:          if(!znacka[tmp2 = pole2[pole[tmp+i]*c_max+j]] && !znacka3[tmp2]) {
 55771154:   60:            teraz++;
 55771154:   61:            znacka3[tmp2]++;
        -:   62:          }
        -:   63:      }
  1236087:   64:      zrychli[k]=teraz;
  1236087:   65:      if(teraz > mini) {
    27552:   66:        dalsi = k;
    27552:   67:        mini = teraz;
        -:   68:      }
  1236087:   69:      if(predch==teraz) break;
        -:   70:    }
        -:   71:  }
      111:   72:}

[secido]

Az tak definitivne som ho nevylucil , je to fakt memset(). Mojim nespravnym pouzivanim profilera na dynamicky linkovanu binarku som dostaval skreslene vysledky, staticka ukazuje v com je problem. Casy su trochu dlhsie kvoli zapnutemu profileru.

athlon@750 (116.04 s)

  %   cumulative   self              self     total
 time   seconds   seconds    calls   s/call   s/call  name
 83.83    242.63   242.63                             memset
 15.50    287.48    44.85     2931     0.02     0.02  DalsiRiadokNovy

duron@1600 (268.35 s)

  %   cumulative   self              self     total
 time   seconds   seconds    calls   s/call   s/call  name
 93.79    628.86   628.86                             memset
  6.07    669.56    40.70     2931     0.01     0.01  DalsiRiadokNovy

athlon64@2200 (61.91 s)

  %   cumulative   self              self     total
 time   seconds   seconds    calls   s/call   s/call  name
 92.94    143.58   143.58                             memset
  6.75    154.01    10.43     2931     0.00     0.00  DalsiRiadokNovy

Pricina je jasna, teraz uz len ako vyriesit problem.

[machr]

Pastni sem celej ten program, ja to otestuju na svym pocitaci.

Zajimalo by me proc tam pouzivas -g ????

[secido]

Pravdepodobne kvoli debugeru, ale aj stripnuty bezi rovnako dlho.

[cynik]

Podle pomeru casu to vypada tak, ze jsi pri kompilaci toho programu na linuxu nepouzil direktivy pro specifikaci procesoru a je to tedy prelozene na tu uplne nejbeznejsi 386ku. Pokud tam das svuj processor, casy pod ruznymi OS se pravdepodobne budou lisit jen minimalne.

[secido]

Mam taky pocit, ze problem bude v jadre i ked to znie zvlastne. Prave som trochu otestoval moje stare PC k7@750Mhz a cuduj sa svete, casy sa lisili tak +/- 5 sekund od priemeru. Priemer 112s na PC minimalne 3x pomalsom je slusny. Testoval som vo win, linux a opensolaris. Potom som binarku skompilovanu na linuxe bez specifikacie CPU (cize 386 ak sa nemylim) preniesol na system duron@1.6GHz - vysledok 260s. Na systeme bolo jadro kompilovane na 386ku. Cize vychadza mi z toho jadro. Ale 10 sekundovy rozdiel medzi win32 a freebsd64 je stale zahada.

[Michal Kubeček]

Už jsem vás na to upozorňoval jednou: v tom kódu nevoláte naprosto žádný syscall. Tak jak může, proboha, být problém v jádře?

[secido]

Ano? Tak potom preco binarka bezi na pomalsom hw rychlejsie, ked to nie je v jadre?

[VícNežNic]

Když to nestráví v jádře vůbec žádný čas, protože to tam nic nevolá, jak by mohl kód jádra zdržovat?

[Kníže Ignor]

To není pravda, že Třeba může mít linux naprosto debilní plánovač...

Ale problém bych hledal někde jinde, rozhodně si nepoběžím nainstalovat freebsd :-P

[Michal Kubeček]

Pravda… Ale něco mi říká, že kdyby na tom byl linuxový scheduler tak špatně, aby kvůli němu běžel na víceméně nezatíženém stroji (předpokládám, že tazatel to nebenchmarkoval na systému se stovkou dalších aktivních procesů) dvakrát až třikrát déle, někdo by si toho všiml a něco s tím udělal… :-)

[*]

...treba si toho prave nekdo vsiml?

[VícNežNic]

Což je taky možnost, pravda. Právě proto by bylo hezké vidět výstup time…

[secido]

FreeBSD (pustane v X)

real    0m32.367s
user    0m29.428s
sys     0m0.118s

[VícNežNic]

A srovnání s tím Linuxem?

[secido]

real    1m20.233s
user    1m15.656s
sys     0m0.800s

[secido]

Dobre beriem, lenze stale som sa nedozvedel v com je chyba. Nejaky dalsi napad?

[Michal Kubeček]

Pravděpodobně špatná optimalizace - buď je to rukama nebo překladačem. Ale s jádrem to nemá nic společného.

[secido]

Binarka je rovnaka (386) a na athlone@750 bezi 2x rychlejsie ako na durone@1600?

[VícNežNic]

Tak zkus tu linuxovou (pomalou) binárku spustit v tom FreeBSD.

[Michal Kubeček]

Tím spíš by bylo užitečné vědět, co všechno vám tam běží kromě ní.

[secido]

load average: 0.00, 0.02, 0.00 takze vela tam toho nie je, je to gw do netu pre par ludi.
Spustil som 386kovu linuxovu binarku vo freebsd/amd64 a dostal som vysledok 41s cize podobny ako 32 bitovy kod vo win. Zial 64bitovu binarku z linuxu nedokazem spustit.

[AraxoN]

Ten program len tak beží, alebo aj niečo vypisuje?

Ak vypisuje, a je spúšťaný v grafike, tak je to jasné - antialiasing, rendering fontu, plus nejaký neoptimalizovaný ovládač grafiky, ktorý nestíha texty tak rýchlo scrollovať.

A na tom Duronovom routri to asi ide cez ssh, takže sa na ňom nič nevykresľuje... Hádam dobre?

[secido]

Hadas dobre, na routri cez ssh v screene, lokalne je rozdiel medzi konzolou a X asi 1 sekunda cize zanedbatelny.

[AraxoN]

Windows má ovládače na 2D grafiku vcelku vychytané. Skús to s presmerovaním výstupu do súboru - rozdiel v rýchlosti filesystémov bude asi menší. Alebo v textovej konzole - a tým myslím naozaj textovej konzole, 80 znakov, 25 riadkov, nie framebuffer.

[secido]

Spustal som aj na textovej konzole, bez zmeny. Uz ma nic nenapada.

[secido]

Dalsi novy poznatok, rozdiel v rychlosti zavisi od vstupnych parametrov programu. Znamena to, ze program nie je vo vseobecnosti pomalsi na linuxe, ale len v niektorych pripadoch. Tak toto je uz na mna vela .

[machr]

v tom kodu, cos tady psal je dvakrat tento radek:

if(znacka2[pole[tmp+i]]) continue;

ale nikde tam neni inicializace znacka2. To muze byt jeden z duvodu. Kdybys sem hodil celej ten program, tak uz by ti urcite nekdo rek, co tam mas spatne...

[secido]

Je prilis dlhy aby som ho sem daval cely, ale ak chces testnut mozem ti ho poslat na mail.

[machr]

x303 AT email DOT cz

[secido]

Poslal som.

[David Jaša]

pastebin.com, rafb.net/paste, pastey.net jsou na toto mnohem lepší než mail