C - ++i sebesség

Eddig mindig úgy gondoltam, hogy a legoptimálisabb inkrementálást a ++i nyújtja, mert ugye neki nem kell először lementeni az eredeti értéket.

De kíváncsiságból gondoltam, hogy letesztelem a dolgot:


int main(int argc, char** argv) {
clock_t start, end;
double cpu_time_used_1, cpu_time_used_2, cpu_time_used_3;
long i;
long x=1;

start = clock();
for (i=0; i<FOR_END; i=i+1) {
x=x*2;
x=x/2;
}

end = clock();
cpu_time_used_1 = ((double) (end - start)) / CLOCKS_PER_SEC;

start = clock();
for (i=0; i<FOR_END; i++) {
x=x*2;
x=x/2;
}

end = clock();
cpu_time_used_2 = ((double) (end - start)) / CLOCKS_PER_SEC;

start = clock();
for (i=0; i<FOR_END; ++i) {
x=x*2;
x=x/2;
}

end = clock();
cpu_time_used_3 = ((double) (end - start)) / CLOCKS_PER_SEC;

printf("x:%ld\ni=i+1:%lf\ni++:%lf\n++i:%lf\n",x,cpu_time_used_1,cpu_time_used_2,cpu_time_used_3);

return 0;
}

És az eredmény kicsit meglepett:

spica@spica-dev:~/projektek$ gcc -o proba proba.c
spica@spica-dev:~/projektek$ ./proba
x:1
i=i+1:6.250000
i++:6.170000
++i:6.650000
spica@spica-dev:~/projektek$ ./proba
x:1
i=i+1:6.730000
i++:6.260000
++i:6.490000
spica@spica-dev:~/projektek$

Az első esetben még a i=i+1 is gyorsabb volt...vagy van pontosabb mérés erre?

( saxus | 2010. 11. 20., szo – 01:35 )

Jo lenne a kodot a break moge rakni, hogy ne vagja szet az egesz blog oldalt. Koszi.

Amugy, legegyszerubb lenne megnezni, hogy mit fordit be ASM-be. Na meg az optimalizalasokat is erdemes megnezni.

----------------
Lvl86 Troll

( anr | 2010. 11. 20., szo – 06:54 )

andrej@o:/tmp$ ./i;./i2;./i3
x:1
i=i+1:7.660000
x:1
i++:7.660000
x:1
++i:7.660000

nem tul meglepo, de ugyanarra optimalizalja a kodot :)

andrej@o:/tmp$ gcc -O3 -S i3.c
andrej@o:/tmp$ diff i.s i2.s
1c1
< .file "i.c"
---
> .file "i2.c"
4c4
< .string "x:%ld\ni=i+1:%lf\n"
---
> .string "x:%ld\ni++:%lf\n"
andrej@opata:/tmp$ diff i.s i3.s
1c1
< .file "i.c"
---
> .file "i3.c"
4c4
< .string "x:%ld\ni=i+1:%lf\n"
---
> .string "x:%ld\n\n++i:%lf\n"

( turul16 v | 2010. 11. 20., szo – 08:58 )

-O0 nal van kulombseg, az osszes tobbi modnal (O1) a gcc eldobja ciklust, es nulla lesz az eredmeny. Tul okos a gcc :)

gcc --version
gcc (Gentoo 4.4.5 p1.0, pie-0.4.5) 4.4.5
Copyright (C) 2010 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Amit nem lehet megirni assemblyben, azt nem lehet megirni.

-O0-val nem dobja el a ciklust, de a generált asm kód megegyezik (, kivéve a printf formátum stringjét).
Ha for helyett while ciklussal csináljuk meg, akkor is ugyanazt a kódot generálja. 


i = 0;
while (i < FOR_END) {
    x=x*2;
    x=x/2;
    ++i;
}

-----
"Ha javulni látod a dolgokat, akkor valami fölött elsiklottál."

O0 ket callq kozotti resz: 


  400673:	e8 10 fe ff ff       	callq  400488 <clock@plt>
  400678:	48 89 45 c8          	mov    %rax,-0x38(%rbp)
  40067c:	48 c7 45 f0 00 00 00 	movq   $0x0,-0x10(%rbp)
  400683:	00 
  400684:	eb 1f                	jmp    4006a5 <main+0x121>
  400686:	48 d1 65 f8          	shlq   -0x8(%rbp)
  40068a:	48 8b 45 f8          	mov    -0x8(%rbp),%rax
  40068e:	48 89 c2             	mov    %rax,%rdx
  400691:	48 c1 ea 3f          	shr    $0x3f,%rdx
  400695:	48 8d 04 02          	lea    (%rdx,%rax,1),%rax
  400699:	48 d1 f8             	sar    %rax
  40069c:	48 89 45 f8          	mov    %rax,-0x8(%rbp)
  4006a0:	48 83 45 f0 01       	addq   $0x1,-0x10(%rbp)
  4006a5:	48 81 7d f0 ff ff ff 	cmpq   $0x3ffffff,-0x10(%rbp)
  4006ac:	03 
  4006ad:	7e d7                	jle    400686 <main+0x102>
  4006af:	e8 d4 fd ff ff       	callq  400488 <clock@plt>

O1: 


  4005c9:       e8 e2 fe ff ff          callq  4004b0 <clock@plt>
  4005ce:       49 89 c5                mov    %rax,%r13
  4005d1:       e8 da fe ff ff          callq  4004b0 <clock@plt>

objdump -al neztem.

O0 meg kit erdekel? Ez a teszt igy nem meri azt amit kene neki, O1 -nal mar 0 db merendo muveletet csinal.

Amit nem lehet megirni assemblyben, azt nem lehet megirni.

"O0 meg kit erdekel?" Téged? <- "-O0 nal van kulombseg,..."

A -O0-nál sincs különbség a három változat között. Mindhárom változat ugyanazt a kódot eredményezi.
Ez a teszt két dologra jó:
- ha a generált kódot megnézzük, akkor látható, hogy mindegy hogyan növeljük a ciklusváltozó értékét.
- ennek ellenére a mért értékek kissé eltérhetnek, de ez a clock() függvénnyel történő mérésre vezethető vissza.

Kieg:
Valóban jobb lenne, ha a ciklusban az x értékét ténylegesen módosítanánk, és a mindegyik ciklus után kiíratnánk az eredményt. De ez nem befolyásolná a végső következtetést.

-----
"Ha javulni látod a dolgokat, akkor valami fölött elsiklottál."

Akkor egyszerubben fogalmazok:Az O1 eseteben SEMMIT SEM CSINAL! Eldobja kodot es megmeri a semmi idejet. Az oszes magasabb O -nal szinten megmeri a SEMMIT.
O0 -nal marad valami, ami abszulute nem relevans a valos vilagban.

Ciklust ha jol emlekszem nem szokta eldobni, ha mondjuk y+=y; van a magjaban es a vegen kiirod az y -t.

szerk: kevesbe write only modban rajottem mit akarsz modnai. 3 valtozatot ugy ertettem 3 kulonbozo O, te meg ugy, hogy ugyan azt az asm-et generalja 3 noveles resz O0 -val...

Amit nem lehet megirni assemblyben, azt nem lehet megirni.

-O0-nál nem dob el semmit, azt csinálja, amit a programozó kért. Hogy ez nem releváns, arról a programozó tehet.

Ciklus eldobása -O1-nél és felette: A ciklustörzsbe csak az x +=3; szerepeljen. Mivel az x-et kiíratjuk, így -- elvileg -- nem dobhatja el a ciklust. Gyakorlatilag már -O1-nél is, a fordító kiszámolja az x értékét (jelen esetben 1 + x * FOR_END) és ez kerül a kódba. Tehát ami fordítási időben egyszerűen kiszámolható, azt ki fogja számolni a fordítási időben.
Ha x += x-et (vagy x = sin(x)-et) teszünk a ciklustörzsbe, akkor már nem tudja kihagyni a ciklust a fordító.

Kieg.: A három változat a háromféle ciklusváltozó növelésre vonatkozik. A problémát egyszerűbb úgy vizsgálni, hogy a három esetet külön-külön forrásban helyezzük el (mint azt anr is tette), és az így kapott három kódot hasonlítjuk össze. Mind a három változat esetén (++i, i++, i=i+1) ugyanazt a kódot kapjuk.

-----
"Ha javulni látod a dolgokat, akkor valami fölött elsiklottál."

( bocs | 2010. 11. 20., szo – 16:08 )

ma amelyik fordító nem ugyanarra optimalizálja a fenti kódokat, az nem elég jó fordító, de a lényeg nem itt van.

A fenti esetek közt a különbség saját iterátoroknál jön elő.
Élő példa: mi dolgoztunk egy 3dimenziós tömb kezelő könyvtárral, ahol 2Ds, 1Ds szeleteket is bejáró iterátorok is megtalálhatóak voltak.
No itt a futásidők 2x 3x akkorák voltak, ha ++i helyett i++ -t írt az ember, hiszen az egyik csupán növelést jelent (pl átlépést a 3Ds tömb következő elemére egy adott síkban), míg a másiknál pl
- az iterátor copy konstruálását
- a tömbben hivatkozást leíró mutatók bejegyzését, thread-safe refcount növelést
- iterátor növelést
- a tömbben hivatkozást leíró mutatók kitörlését, thread-safe refcount csökkentést
- iterátor destruálás

Előfordult, hogy egy lusta programozó által írt kódot háromszorosára, ötszörösére lehetett gyorsítani egy i++ -> ++i cserével

( hrgy84 | 2010. 11. 20., szo – 20:19 )

Pont most olvastam errol Stephen Dewhurst konyveben, primitiv tipusoknal nincs kulonbseg, de osztalyok eseteben mar jelentos elteresek lehetnek.
-- 

Ki oda vagyik, hol szall a galamb, elszalasztja a kincset itt alant. | Gentoo Portal