Optimaliseren van code (if statements)

quote:

prometheus345479 schreef op zondag 18 mei 2008 @ 13:03:
Ik gebruik de standaard IDL FFT, dus die zal wel geheel geoptimaliseerd zijn.

Dat is een erg gevaarlijke aanname, die al onderuit gehaald wordt door de resultaten van de profiler. Waarom probeer je niet de FFTW library in je code je hangen? Zoals ik al eerder aangaf is die wel echt goed geoptimaliseerd. Of kan je die niet vanuit IDL aanroepen?

En verder heeft MSalters natuurlijk gelijk dat de grootste winst gehaald kan worden door je matrix te verkleinen indien mogelijk. Standaard geldt: hoe hoger het niveau van optimalisatie/versimpeling, hoe groter de winst. Dus op algoritmisch niveau kun je bijvoorbeeld een factor 1-10 winnen (hier: door een kleinere matrix te gebruiken), waar je met optimalisaties in de implementatie vaak maar een veel kleinere factor (<2) kunt winnen (hier: betere FFT implementatie door bijv. een lookup tabel te gebruiken i.p.v. steeds de Sin/Cos waardes te berekenen).

quote:

prometheus345479 schreef op woensdag 21 mei 2008 @ 10:42:
Ik zal even posten wat de code profiler aangaf. (uitleg onderaan)
[code]
Module Type Count Only(s) Avg.(s) Time(s) Avg.(s)
ABS (S) 1002 2.264961 0.002260 2.264961 0.002260
...
[/list]

(...)

offtopic:
Waar komt deze lijst uit, welke profiler, en ander welk platform/IDE?

Wat mij opvalt, is dat de COS() zoveel sneller is dan de SIN(). Ik zou verwachten dat deze operaties ongeveer gelijk zijn

quote:

Knutselsmurf schreef op woensdag 21 mei 2008 @ 16:49:
Wat mij opvalt, is dat de COS() zoveel sneller is dan de SIN(). Ik zou verwachten dat deze operaties ongeveer gelijk zijn

De gemiddelde tijd ligt inderdaad lager. Zou dit betekenen dat een aanroep naar SIN() simpelweg geredirect wordt naar COS() met een faseverschuiving? Want een extra functioncall zou dat tijdsverschil wel kunnen verklaren.

quote:

Stamgastje schreef op woensdag 21 mei 2008 @ 11:53:
[...]

Dat is een erg gevaarlijke aanname, die al onderuit gehaald wordt door de resultaten van de profiler. Waarom probeer je niet de FFTW library in je code je hangen? Zoals ik al eerder aangaf is die wel echt goed geoptimaliseerd. Of kan je die niet vanuit IDL aanroepen?

Ik heb even gekeken naar FFTW, maar het is nogal ingewikkeld om te implementeren. Het is mogelijk om IDL en C samen te laten werken, maar dit werkt weer niet met de IDL versie die ik thuis heb. (dat is de demo versie, waarbij calls naar externe code niet zijn toegestaan).

Het liefst wil ik alles volledig cross platform houden, zodat ik mijn pc thuis ook kan gebruiken voor rekenwerk. (die is sneller dan de computers op de universiteit) Thuis heb ik vista 64-bit met een core 2 Quad. en op de faculteit heb ik 64 bit linux met AMD X2's.

@JeRa
Wat je zegt klopt niet helemaal. COS en SIN in mijn code evenvaak aangeroepen. Dus als een call naar COS SIN zou aanroepen, dan zou de count van SIN 2 maal de count van COS moeten zijn. Dat is dus niet zo. Ik blijf het vreemd vinden...

@Zeroxcool
De output is de output van de ingebouwde profiler van IDL. (zoek op: IDL profiler )

prometheus345479 wijzigde dit bericht 22-05-2008 10:27 (5%)

Klein experiment in matlab, hier is de cos 10x langzamer dan de sin.
Er staat me wel bij dat een cos functie geimplementeerd is met iets met convergentieslagen, maar helemaal zeker weet ik dat niet meer.
matlab:

>> a = rand(100,100)*.001;
>> tic ; c = cos(a); toc
elapsed_time =
    0.0154
>> tic ; c = sin(a); toc
elapsed_time =
    0.0015
>>

Overigens reproduceert dit experiment totaal niet bij mij, dus het zegt niks

Zie bijvoorbeeld dit:
matlab:

>> a=randn(1000,1000)*.001;
>> tic ; c = cos(a); toc
elapsed_time =
   0.27571800000000
>> tic ; c = cos(a); toc
elapsed_time =
   0.20404700000000
>> tic ; c = cos(a); toc
elapsed_time =
   0.25817500000000
>> 
>> tic ; s = sin(a); toc
elapsed_time =
   0.15150000000000
>> tic ; s = sin(a); toc
elapsed_time =
   0.12732000000000
>> tic ; s = sin(a); toc
elapsed_time =
   0.15823100000000
>>

Ik stop er maar mee, je zou er wijzer van moeten worden

quote:

prometheus345479 schreef op donderdag 22 mei 2008 @ 10:15:
Verder worden COS en SIN in mijn code evenvaak aangeroepen. Dus als een call naar COS sin zou aanroepen, dan zou de count van SIN 2 maal de count van COS moeten zijn.

Als sin direct cos zou aanroepen ja. Waarschijnlijker is het dan echter dat sin en cos beide proxies zijn die uiteindelijk een implementatie van een cosinusfunctie aanroepen, waarbij sin dus meer overhead heeft dan cos. Ik beweer niet dat het zo is, ik zeg alleen dat het zou kunnen. Maar het lijkt me raar dat sin daardoor 9x zo duur is als cos. In mijn eigen arbitrary precision implementatie van sin en cos verschillen ze niet zoveel van elkaar, en ook op de FPU van m'n CPU (2.4 GHz Core 2 Quad) performen ze gelijkwaardig (0.38 sec voor 10 miljoen aanroepen)

Als je over low-level optimalisaties wil gaan kun je er ook deze eens op na slaan:
http://lwn.net/Articles/250967/

Bovendien denk ik dat een goeie for-lus net wel bevorderlijk is voor de prestaties. De compiler kan namelijk aannames maken:
C++:

1 2 3

for (int i = 0; i < size; ++i) { }

Als de compiler hier redeneert dat i < size altijd waar is (en dus een instructie genereert waarin altijd de "true" code geprefereerd wordt, dan heb je altijd:
- 1 enkele pipeline flush door een foute branch
- size - 1 goeie branches.
Dit rendeert vanaf size = 2.

Je kan in veel gevallen de compiler bij if-statements ook een beetje helpen met dit soort aanwijzingen.
Bij gcc kun je bvb __likely() en __unlikely() gebruiken.

Ook kan het in veel gevallen een voordeel zijn om ipv
C++:

1 2 3

if (a || b || c) { }

deze
C++:

1 2 3

if (a | b | c) { }

te gaan gebruiken (tenzij evaluatie van b en c 'duur' is)

De reden is dat de eerste code gelijk is aan
C++:

1 2 3 4 5 6 7 8 9

if (a) {   if (b)   {     if (c)     {     }   } }

Het zijn van die micro-optimalisatie die in hotspots wel wat kunnen opleveren.
Maar zoals anderen al aangaven, roer eerst eens maar eens met de pollepel in de pot voor je met een koffie-lepel begint. Die sinus-berekening is al een goeie eerste start.

quote:

H!GHGuY schreef op vrijdag 23 mei 2008 @ 22:35:
Ook kan het in veel gevallen een voordeel zijn om ipv
C++:

1 2 3

if (a || b || c) { }

deze
C++:

1 2 3

if (a | b | c) { }

te gaan gebruiken (tenzij evaluatie van b en c 'duur' is)

De reden is dat de eerste code gelijk is aan
C++:

1 2 3 4 5 6 7 8 9

if (a) {   if (b)   {     if (c)     {     }   } }

euh, nee? Het onderste stukje code is gelijkwaardig aan &&, niet || - bij de || wordt immers de code uitgevoerd als ook maar een van de drie statements true zijn, niet als a, b en c true zijn. Of ik begrijp je redenering niet helemaal.

Dus hij bedoelt && en & ipv || en |, waarbij het bij de || en | ook wel opgaat maar het equivalent in if-statements iets anders is. Dat maakt z'n punt toch niet minder valide?

Bij de || zou het zoiets zijn:
C++:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

bool ok = true; if (!a) {     if (!b)     {         if (!c)             ok = false;     } } if (ok) {     // doeIets }

.oisyn wijzigde dit bericht 26-05-2008 11:45 (94%)
Reden: goto weggewerkt ;)

juist ja, klein foutje van mijn kant. er moet idd && staan waar nu || staat

Welke van de volgende 2 snippets zou het snelste zijn?
code:

if(statement) {
    x = 1;
} else {
    x = 2;
}

of
code:

x = 2;
if(statement) {
    x = 1;
}

Ik heb gelezen dat optie 2 sneller is, maar maakt die extra toewijzing of een else veel uit? (In het kader van optimalisatie).

Tja, tenzij dit in een loop met gruwelijk veel iteraties zit is het nog niets 2s denkwerk waard. Bovendien zal menig compiler dezelfde output geven voor beide inputs.

quote:

Spiked schreef op maandag 23 juni 2008 @ 16:29:
Welke van de volgende 2 snippets zou het snelste zijn?

[...code...]

Ik heb gelezen dat optie 2 sneller is, maar maakt die extra toewijzing of een else veel uit? (In het kader van optimalisatie).

Waar heb je dat gelezen dan? En voor welke taal?
Wat machinecode betreft kan het feitelijk beide kanten op, en in een taal met complexe typen kan het afhangen van de kosten van de assignment. Maar over het algemeen is het een totaal oninteressante vraag (zoals de meeste vragen in de topic trouwens)

quote:

Voutloos schreef op maandag 23 juni 2008 @ 16:40:
Bovendien zal menig compiler dezelfde output geven voor beide inputs.

Daar kun je feitelijk geen zinnig woord over zeggen zonder meer informatie te hebben over bijv. taal en het type van 'x'.

.oisyn wijzigde dit bericht 23-06-2008 17:58 (20%)

Op de ARM is het antwoord simpel: De eerste kost je twee conditional moves (MOVEQ/MOVNE) terwijl de tweede je een conditional en een unconditional move kost (MOV/MOVEQ). De MOVNE is niet duurder dan de MOV, en soms goedkoper. Dus op ARM is de eerste sneller.

quote:

MSalters schreef op maandag 23 juni 2008 @ 20:51:
Op de ARM is het antwoord simpel: De eerste kost je twee conditional moves (MOVEQ/MOVNE) terwijl de tweede je een conditional en een unconditional move kost (MOV/MOVEQ). De MOVNE is niet duurder dan de MOV, en soms goedkoper. Dus op ARM is de eerste sneller.

Lijkt me dan meer aan je compiler liggen. De eerste kun je prima optimizen naar een enkele Jump-if-equal. Als 'ie niet matched krijg je een fallthrough naar de else case.

Optimizen naar een conditional jump? Are you mad?

Instructies als conditional moves e.d. bestaan niet voor niets. Die hebben namelijk geen last van branch mispredictions en complete pipeline flushes als gevolg daarvan.

.oisyn wijzigde dit bericht 23-06-2008 22:33 (72%)

quote:

prometheus345479 schreef op zondag 18 mei 2008 @ 13:03:
[...]

Het probleem is dat bij Fourier optics, je lens een blokfunctie is (waar een turbulent golffront doorheen gestuurd kan worden). De benodigde nyquist sampling is dus eigenlijk oneindig, om de blokfunctie te kunnen sampelen. Het bleek dat de fouten die optraden vanwege het samplen te groot waren bij een kleine matrix. De fout neemt toe naarmate je dichter bij de rand van de matrix zit. (hoge spatial frequencies). Dit probleem is gewoon inherrent aan de discrete fourier transformatie.

Dus nu simuleren we een grote matrix (256x256) en zoomen daarna in op het centrale gedeelte (32x32), dat voldoende nauwkeurig is. Ook de double precisie is nodig, om de grote range aan waarden allemaal mee te kunnen nemen.

Feitelijk heb je last van het Gibbs fenomeen. Nu las ik laatst dat er variaties op de fourier transformatie zijn die het probleem van die oscilaties kunnen onderdrukken. Ze zullen allicht duurder zijn dan een DFT, maar als je dan wel met kleinere matrices kan werken kan het uiteindelijk wel voordeliger zijn. Ik zou zeggen zoek daar eens naar.

Als je if-statements vooral bedoeld zijn om fout-codes af te vangen dan zou je hier nog een kleine snelheidswinst kunnen maken door ze om te zetten naar switch()-statements.

Voor referentie: http://www.blackwasp.co.uk/SpeedTestIfElseSwitch.aspx

Ja en nee. Een if-statement in pure ASM is niets meer dan een "cmp" (compare) instructie gevolgd door een jump instructie, bijvoorbeeld "je" (jump equal). Bij een jump wordt de "locatie register" aangepast aan het nieuwe adres, zijnde EIP, wat vrij weinig overhead heeft. Bij een switch statement wordt er gebruik gemaakt van een zogenaamde jump-tabel, wat in principe een serie addressen is (in sommige gevallen zelfs absolute addressen). Bij meer complexe switch-statements zijn er zelfs twee vertaal-tabellen, ééntje om de eigenlijke case uit te vinden, en de tweede om het adres van deze case te achterhalen. Een voorbeeld hiervan is;
.
C++:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

unsigned char ucWaarde = 123; switch (ucWaarde) {     case 1, 5, 6, 10:         printf ("Case 1");         break;     case 15, 19, 25:         printf ("Case 2");         break;        case 99, 123:         printf ("Case 3");     default:         printf ("Default");         break; }

.
In dat geval wordt er eerst een array gemaakt met de waardes, een array die in totaal 123 (hoogste waarde) bytes zal bevatten. De inhoud zal beginnen met [0,1,0,0,0,1,1,0...], waarbij index 0 de default-switch is, index 1 de eerste case, enzovoorts. De assembly code die hierbij gemaakt wordt moet rekening houden met een aantal dingen: als de waarde hoger dan 123 of lager dan 1 is, zal sowieso de default switch uitgevoerd moeten worden. Verder moet de case-index uit deze eerste translation array opgehaald worden waarna een 2e array gelezen kan worden om het adres van de case uit te vinden. In Assembly zal dit ongeveer gelijk zijn aan;
.
assembly:

    mov eax, 123 ; de case index
    cmp eax, 0
    jbe _default
    cmp eax, 124
    jae _default
    movsx al, __caseIndex[eax]
    jmp __caseAddress[al*4]

_case1:
    ....
    jmp _end
_case2:
    ....
    jmp _end
_case3:
    ....
_default:
    ....

_end
    ; rest van je code

Dit, samen met de nodige jump en compare instructies, heeft veel meer overhead dan de standaard if-constructie, welke in Assembly taal vrijwel gelijk zal staan aan het volgende. Hierbij wil ik opmerken dat bij echt hele "complexe" switch tabellen, waarbij de waardes meer dan 1000-2000 uit elkaar liggen, de assembler er vaak een grote serie if-compares van maakt.
.
assembly:

    cmp eax, 123
    jne _false
    .... ; Code gedeelte voor true
_false:
    .... ; Rest van je code

Uiteindelijk wil ik nog toevoegen dat simpele switches wel degelijk sneller zijn; als je switch goede aaneensluitende waardes bevat, 1-8 bijvoorbeeld, dan wordt er maar één jump gedaan. Dit is ook het geval als het opvolgende waardes zijn, bijvoorbeeld 1,2,4,8,16 etcetera, daar kennen compilers vaak handige trucjes voor. Wat sneller is heeft echt heel veel te maken met de situatie waarin je het gebruikt, gezien een switch naar drie verschillende dingen kan assembleren. Als je echt voor snelheid wilt gaan kan je nog gaan nadenken over inline Assembly, het is moeilijker, maar je kan code wel zeer veel efficienter maken. Eén van de redenen dat de eerste Rollercoaster Tycoon vrij veel tegelijk kon doen op de oudere systemen; het spel bestond voor 99% uit handgeschreven Assembly.

Sorry als m'n verhaal hier en daar wat onduidelijk is, ben nogal bezig met WOGgen op het moment

Edit;
Nog wat algemene tips voor optimalisatie; een belangrijk punt zijn for-loops en de vergelijkwaarde in het tweede deel. Iets wat vaak gedaan wordt is het volgende:
.
C++:

1 2 3 4 5 6 7 8

std::list <int> listCijfers; listCijfers.push_back (5); listCijfers.push_back (10); for (int i = 0; i < listCijfers.size(); i++) { ... }

Sommige assemblers (let op: niet allemaal meer) hebben de neiging om na iedere run van de loop opnieuw de size() methode van de list aan te roepen, wat echt veel tijd in beslag kan nemen bij grotere loops. In gevallen als deze, zet de waarde van de size() functie in een tweede locale variable:
C++:

1 2 3 4

for (int i = 0, j = listCijfers.size (); i < j; i++) { }

In het meest efficiente geval zal de assembler de "j" in het EDI register zetten, waardoor je inplaats van een collectie calls, mov's en hertellingen van de lijst enkel één compare instructie hebt, met lijsten van miljoenen cijfertjes kan dat echt seconden gaan schelen.

Peter wijzigde dit bericht 24-07-2008 12:41 (13%)

quote:

Peter schreef op donderdag 24 juli 2008 @ 12:30:
Ja en nee. Een if-statement in pure ASM is niets meer dan een "cmp" (compare) instructie gevolgd door een jump instructie, bijvoorbeeld "je" (jump equal). Bij een jump wordt de "locatie register" aangepast aan het nieuwe adres, zijnde EIP, wat vrij weinig overhead heeft.

Het spijt me, maar met die laatst gequootte zin aan het begin van je post kan ik niet anders dan je hele post in twijfel trekken - het geeft namelijk aan dat je niet echt ervaring hebt met "moderne" (zeg vanaf de 386) x86 architectuur.

Een gewone jump naar een vast adres is idd vrij goedkoop. Een conditionele jump echter niet. Instructies worden namelijk niet een voor een afgerond, maar gaan door verschillende fases (fetch, decode, execute, etc) die parallel worden uitgevoerd. Dat betekent dat als de conditional jump gedecode en geexecute wordt, mogelijk nog niet bekend is wat het resultaat van de compare is omdat het flags register nog niet is geüpdate. De CPU gaat dan maar "gokken" (branch prediction adhv resultaten uit het verleden) of hij wel moet springen of niet, zodat hij wel alvast nieuwe instructies kan fetchen, decoden, etc. terwijl hij degene die momenteel in de pipeline zitten kan afronden. Gokt hij mis, dan betekent dat dat op het moment hij erachter komt alle nieuwe instructies die al in de pipeline zitten gecanceled moeten worden, en moet hij de hele pipeline weer vullen met instructies vanaf het andere adres. Op CPU's met een lange pipeline (zoals de P4) is dit érg kostbaar.

Met dit verhaal in je achterhoofd kun je ook wel bedenken dat jump tables niet zo heel erg optimaal meer zijn als op die oude simpele CPU's. Hij moet namelijk het adres uitrekenen aan de hand van een aantal condities en daarnaartoe jumpen. Als dat adres nog niet volledig achterhaald is op het moment van de jump instruction heb je hetzelfde verhaal, maar dan nog erger - in feite is dit altijd een branch misprediction met een pipeline flush als resultaat, omdat hij simpelweg niets heeft om te predicten.

Beide gevallen zijn natuurlijk te voorkomen door te zorgen dat de instructies die zorgen voor de flags danwel het adres al lang en breed zijn uitgevoerd voordat de jump plaats vindt, en de compiler zal je hierbij helpen. Dit is echter lang niet altijd mogelijk - er moet natuurlijk wel werk te doen zijn .

En daarom bestaan er dus ook instructies zoals conditional moves, die geen invloed hebben op de instruction flow waardoor de CPU gewoon zo efficient mogelijk door kan gaan met het uitvoeren van instructies. Een stukje code als
C++:

1 2	if (b > 5)     a = 10;

kan dan worden vertaald naar
asm:

cmp b, 5    ; vergelijk b met 5
cmovg a, 10     ; als groter, dan schrijf 10 naar a

Je ziet ook steeds vaker gebeuren dat bij het doen van veel berekeningen (met SSE bijvoorbeeld) if-statements helemaal niet als zodanig worden geassembleerd. De compiler genereert code die beide takken altijd uitvoert en vervolgens combineert door de een te vermenigvuldigen met 0 en de ander met 1, afhankelijk van een bepaalde conditie. Door het streaming karakter van SSE is dit veel voordeliger dan bijvoorbeeld in een algoritme vroeg bepaalde condities te controleren waardoor de berekening niet plaats zou hoeven vinden (de zgn. early-outs) - ze kosten namelijk op zich weinig cycles, maar hebben wel een lange pipeline.

(leesvoer)

Dergelijke conditional moves zijn een prima oplossing, het grote probleem hierbij is dat er maar amper assemblers zijn dit dit goed aankunnen - mogelijkerwijs dat de platform specifieke high-performance compilers van Intel hier mee om kunnen gaan, maar de gebruikelijke cl.exe kan dit zeer zeker niet. Vanuit dat opzicht is inline assembly gebruiken gewoon een hele goede optie als je dat efficient kan.

Meestal werk ik met x86 asm, vrij recent, ondanks dat nog niet de nieuwere instruction sets er bij mij goed inzitten. Verder komt daarbij dat moderne asm ook niet niet zo heel veel voorkomt, veel productiegames/applicaties worden nog steeds gemaakt met Visual Studio 2003, gezien niet iedereen even blij is met de extra requirements voor 2005 en verder. Toch bedankt voor je verhaal

VS doet dat idd niet helaas. Waarom weet ik niet precies, in het voorbeeld dat ik gaf zou het prima kunnen. Echter, als de cmov een memory operand heeft dan haalt hij dat geheugen op ongeacht de conditie, waardoor het in een constructie als de volgende al niet meer gebruikt kan worden:
C++:

1 2 3 4 5

int * p; int a; // ... if (p)     a = *p;

Als hier een cmov gebruikt zou worden, dan zou je een exception krijgen als de pointer null is. gcc en de intel compiler maken vziw wel gebruik van de cmov instructie (maar dan uiteraard niet in dit geval).

Wij zijn tijdens de ontwikkeling van Tomb Raider: Underworld overigens overgestapt naar VS 2005. Temeer omdat dat ook een requirement is voor de Xbox 360 SDK

.oisyn wijzigde dit bericht 26-07-2008 15:06 (26%)

Indien je zelf kan voorspellen dat code een bepaald pad volgt (bv een null check op een pointer die eigenlijk nooit true kan zijn), en je werkt / kan werken met gcc kun je __builtin_expect() gebruiken. Op die manier zet gcc hetgeen wat het minst waarschijnlijk is in een branch blok, en de rest is sequentieel.

Indien je berekeningen gebruikt met de zelfde input (en dus ook output), zou je kunnen overwegen dit tegaan cachen. Floating point + context switches waren in het verleden altijd een slechte combinatie. Zaken zoals het gebruik van SSE kan ook een rol spelen, desnoods via een implementatie van bepaalde delen in assembler.

Dat kan met VC++ ook, met __assume(). Maar dan zal hij niet eens branchen - van de pointer wordt dan immers aangenomen dat hij niet 0 is, dus hoeft hij ook niets te controleren. Het is wel handig om het in een macro te wrappen zodat je in debug builds ook assert op dezelfde expressie (en eigenlijk zou je alle asserts dan zo moeten maken, want het is een win-win situatie: extra controle in debug builds, en betere performance in release builds)

De oude x87 FP stack mag sowieso wel sterven. Wij targetten CPU's met minstens SSE2 - alle floating point operaties kunnen dan middels SSE code gerealiseerd worden, die een stuk rapper zijn en minder last hebben van allerlei stalls.

.oisyn wijzigde dit bericht 28-07-2008 13:04 (24%)