Optimaliseren van code (if statements)

[prometheus345479]

Hoi,

Ik heb eigenlijk wat hele algemene vragen over de manier hoe CPUs met intructies omgaan, maar ik heb niet echt een antwoord kunnen vinden op wikipedia of howstuffworks etc.

Ik ben op dit moment bezig met een numeriek model om turbulentie te simuleren. Op dit moment doet dit model er 120 uur over om de berekeningen te doen die nodig zijn. (op één core van een Core 2 Quad) Dit kan ik spreiden over alle cores, maar dan nog steeds duurt het erg lang om alles te simuleren.

Ik wil graag weten hoe ik dit kan versnellen. Ik heb eigenlijk alleen wat informatie van mijn oude programmeer lessen in C++, die af en toe vaag over efficientie van processoren gingen. Zoals: vermijd for loops, en if statements zijn traag.

Van wat ik heb gelezen (maar niet zeker of ik het helemaal begrijp) is het vermijden van for loops handig, omdat branch prediction ~dan beter werkt. En ik weet niet of met huidige processors een if statement veel trager verloopt dan een andere rekenkundige bewerking.

Nog even terug naar waarom ik dit wil weten:

In mijn model worden in de orde van vele miljarden double floating points bewerkingen gedaan (double precision is nodig), en honderden miljoenen if statements uitgevoerd. Stel dat ik het aantal if statements halveer, levert dit dan een significante snelheidswinst op? (als if statements gelijk zijn aan rekenkundige operaties levert het zo'n 1% snelheidswinst op, als if statements veel langer duren een rekenkundige operatie, dan levert het dus veel meer snelheidswinst op)

En als je dubbele if statements gebruikt zoals

if a == 1 || b ==2

Wordt dan in alle gevallen zowel de check a==1 en b==2 uitgevoerd? Of gaat de code al door als 1 van de twee waar is? Dus stel dat a==1 meestal waar is, is het dan nuttig om a==1 eerder te laten checken dan b == 2? En hoe werkt dat in de syntax (wat natuurlijk per taal verschillend is waarschijnlijk)

Het model is geschreven in IDL, dat zeer snel is met matrix vermenigvuldigen, maar langzaam met uitlezen van waarden uit vectors (waarom zou ik graag willen weten).

Ik vind dit allemaal erg interessant om te weten, dus als jullie websites kunnen geven waar dit duidelijk uitgelegd wordt(of zelf de moeite nemen om een heel verhaal te typem) dan erg bedankt!

[Verwijderd]

In z'n algemeenheid moet je altijd eerst kijken naar de programmaflow zelf voordat je op if of for-nivo gaat optimaliseren. Heb je al een profiler gedraaid om te zien waar de meeste executietijd in gaat zitten?

prometheus345479 schreef op zaterdag 17 mei 2008 @ 10:03:
En als je dubbele if statements gebruikt zoals

if a == 1 || b ==2

Wordt dan in alle gevallen zowel de check a==1 en b==2 uitgevoerd?

De 2e check wordt alleen uitgevoerd als de 1e niet slaagt, vziw.

[prometheus345479]

De programmaflow op zich is goed, daar heb ik goed over nagedacht, en geprobeerd alles zo optimaal mogelijk te laten verlopen.

De grootste vertraging treedt op vanwege twee discrete fourier transformaties op twee 256*256 matrices. Dit zijn de traagste stappen.

[Boss]

Heb je al eens gekeken of je met een code profiler kan uitzoeken waar nu echt de bottlenecks in je code zitten? Daar kunnen misschien ook heel verassende dingen uitkomen.

[Stamgastje]

prometheus345479 schreef op zaterdag 17 mei 2008 @ 10:14:
De grootste vertraging treedt op vanwege twee discrete fourier transformaties op twee 256*256 matrices. Dit zijn de traagste stappen.

Heb je dit zelf geprogrammeerd? En zo ja, doe je het in O(N log N) stappen (als Fast Fourier Transform dus) of in O(N^2) stappen? In het tweede geval is er dan nog heel veel winst te behalen.

Verder zou ik je aan willen raden om eens naar de FFTW library te kijken: deze bevat allerlei geoptimaliseerde routines om de DFT/DCT/DST te berekenen.

[ Voor 9% gewijzigd door Stamgastje op 17-05-2008 11:16 ]

[prometheus345479]

Bedankt voor de snelle reacties!

Helaas gebruik ik al fast fourier transform. En ik ben ook vrij zeker dat de vertragingen in de functies zitten met de fourier transformaties.

Ik zal maandag eens kijken naar een code profiler voor IDL.

Maar weet iemand nu, gewoon uit interesse, of if statements heel veel langzamer zijn dan andere operaties. En of er meer van dat soort performance argumenten zijn om iets wel of niet te doen...

[Stamgastje]

prometheus345479 schreef op zaterdag 17 mei 2008 @ 11:34:
Helaas gebruik ik al fast fourier transform. En ik ben ook vrij zeker dat de vertragingen in de functies zitten met de fourier transformaties.

Als je vooral geïnteresseerd bent in de resultaten van je berekening, zou ik je nogmaals willen aanraden de FFTW library te gebruiken. Deze bevat door-en-door geoptimaliseerde code. Ben je echter vooral geïnteresseerd in het optimaal leren programmeren, dan moet je natuurlijk met je eigen code verder gaan.

Maar weet iemand nu, gewoon uit interesse, of if statements heel veel langzamer zijn dan andere operaties. En of er meer van dat soort performance argumenten zijn om iets wel of niet te doen...

Dat hangt heel erg af van de processor. En specifieker: van de lengte van de instruction pipeline en van de branch predictor. Op een Pentium 4 bijvoorbeeld zal een IF statement gemiddeld gezien veel meer pijn doen dan op een AMD Athlon XP, aangezien de eerste een veel langere pipeline heeft (grofweg twee keer zo lang).

Maar verder hangt de performance nog van veel meer zaken af. Loops hoeven helemaal niet slecht te zijn, de code voor de loop bevindt zich na de eerste iteratie in de cache en hoeft dus niet steeds opnieuw uit het RAM gehaald te worden (dat relatief zeer traag is). Dit is dus een geval van locality of reference. Wat in jouw voorbeeld heel erg kan helpen, is om het Cooley-Tukey FFT algoritme te gebruiken. Dit deelt de FFT op in losse 1D transforms (van 1x256 waardes). Dit heeft twee voordelen:

1. alle waardes voor zo'n kleine FFT kunnen zich in de locale cache van de processor (of specifieker: de core) bevinden
2. de verschillende cores (in jouw geval 4) kunnen tegelijkertijd verschillende stukken van de 2D FFT berekenen zonder dat ze hiervoor elkaars resultaten nodig hebben

Kortom, een eenduidig antwoord op jouw vraag is niet mogelijk. Op micro-niveau geldt dat de efficiëntie van een bepaalde instructie erg af hangt van de processor. En op macro-niveau geldt bijv. dat andere zaken (de mate van communicatie tussen verschillende cores, locality of reference etc) een grote rol spelen.

[Verwijderd]

Verwijderd schreef op zaterdag 17 mei 2008 @ 10:10:
[...]
De 2e check wordt alleen uitgevoerd als de 1e niet slaagt, vziw.

Dat is alleen relevant als er functies worden aangeroepen of er side-effects zijn. In dit geval maakt het niets uit. Dus de compiler kan de jump penalty vermijden door ze allebei uit te voeren. Als je echt wil weten wat de compiler doet, dan moet je kijken naar de machinecode die de compiler produceert.

Hoe snel het dan op een processor draait, daarvoor moet je profilen. De huidige processoren hebben zoveel optimalisaties en caches dat het heel moeilijk is om goed te redeneren over hoeveel tijd een instructie kost.

[TheWickedD]

prometheus345479 schreef op zaterdag 17 mei 2008 @ 10:03:
En als je dubbele if statements gebruikt zoals

if a == 1 || b ==2

Wordt dan in alle gevallen zowel de check a==1 en b==2 uitgevoerd?

Dit hangt van de programmeertaal en compiler af denk ik. Ik werk veel met MATLAB en daar kun je beide doen.

voor MATLAB:
a == 1 | b ==2 Evalueert beide en kijkt dan of minstens eentje waar is
a == 1 || b ==2 Evalueert eerst a==1 en als die niet waar is pas b==2

Met IDL heb ik geen ervaring, dus kan ik je dit niet vertellen. Moet wel ergens in een goeie reference ofzo terug te vinden zijn?

[MSalters]

prometheus345479 schreef op zaterdag 17 mei 2008 @ 11:34:
Bedankt voor de snelle reacties!

Helaas gebruik ik al fast fourier transform. En ik ben ook vrij zeker dat de vertragingen in de functies zitten met de fourier transformaties.

Ik zal maandag eens kijken naar een code profiler voor IDL.

Maar weet iemand nu, gewoon uit interesse, of if statements heel veel langzamer zijn dan andere operaties. En of er meer van dat soort performance argumenten zijn om iets wel of niet te doen...

Een redelijke stelling is dat if-statements geen bijzonder grote penalty geven in naief geschreven programma's. Ongeveer de enige plek waar ze belangrijk zouden kunnen zijn is binnen in je FFT. Maar die heb je zelf niet geschreven, dus daar hoef je je niet druk om te maken.

Aan de andere kant wil je het liefst de FFTs in de SSE unit draaien; die is veel beter in dat soort dingen. Kan je IDL compiler dat?

[pkuppens]

prometheus345479 schreef op zaterdag 17 mei 2008 @ 11:34:
Bedankt voor de snelle reacties!

Helaas gebruik ik al fast fourier transform. En ik ben ook vrij zeker dat de vertragingen in de functies zitten met de fourier transformaties.

Ik zal maandag eens kijken naar een code profiler voor IDL.

Maar weet iemand nu, gewoon uit interesse, of if statements heel veel langzamer zijn dan andere operaties. En of er meer van dat soort performance argumenten zijn om iets wel of niet te doen...

FFT2D zelf bedacht? Leuk om de details van te begrijpen, maar er hebben veel andere mensen ook al naar gekeken, die vast al genoeg verstand hebben van het parallelliseren en andere compiler optimalisaties. En of het nu handiger is om alvast wat cosinus en butterfly tabellen in het geheugen te hebben, of steeds uit te rekenen.

Verder is met 99.97% zekerheid je compiler slimmer in het (weg-)optimaliseren van IF statements, tenzij er wat in je probleemdomein mogelijk is, mathematische eigenschappen van de matrix (zuiver reeel, e.d.).

Die profiler is een goede suggestie waar ik niet aan gedacht heb. Doen die alleen rekentijd of ook geheugengebruik/diskgebruik (swappen)?

Mijn echte suggestie is om terug te gaan naar 128x128. Dat is denk ik 8x sneller.
Van double naar float heeft denk ik geen zin meer op een 64 bit processor, maar daar zou je ook nog naar kunnen kijken. Als het scheelt, dan scheelt het meteen 100%!
Als je je probleem genormaliseerd hebt, valt het wel mee met het precisie verlies.

Nyquist kan je vertellen of dat bij jouw probleem allemaal kan..
[Edit: ik herlees je originele mail en daarin zeg je dat het nodig is, die dubbele precisie. Dan is je 256x256 vast ook nodig :/] Ik geloof dat niet helemaal, wat is jouw Nyquist sommetje?

[Ir. Technische Wiskunde TU/e - 1993]

[ Voor 5% gewijzigd door pkuppens op 18-05-2008 09:07 ]

[RemcoDelft]

prometheus345479 schreef op zaterdag 17 mei 2008 @ 10:03:
Stel dat ik het aantal if statements halveer, levert dit dan een significante snelheidswinst op?

Kan je dit niet simpelweg even testen? Maak een test-progje, laat hem 10M if-statements doorlopen, en vergelijk de runtime met het doen van 10M andere bewerkingen...

[Voutloos]

En opzoeken/testen of er bij if condities short circuiting gebruikt wordt is ook maar 5 seconden werk...

[prometheus345479]

MSalters schreef op zondag 18 mei 2008 @ 00:53:
[...]
Een redelijke stelling is dat if-statements geen bijzonder grote penalty geven in naief geschreven programma's. Ongeveer de enige plek waar ze belangrijk zouden kunnen zijn is binnen in je FFT. Maar die heb je zelf niet geschreven, dus daar hoef je je niet druk om te maken.

Goed, dan laat ik het hele if statements gebeuren varen. Ik dacht dat het veel tijd zou schelen door de error handling (die met if statements wordt afgehandeld) uit mijn meest aangeroepen standaard functies te halen. Maar kennelijk is een if statement niet zo traag als ik dacht, oude informatie ofzo...

pkuppens schreef op zondag 18 mei 2008 @ 08:59:
[...]
Mijn echte suggestie is om terug te gaan naar 128x128. Dat is denk ik 8x sneller.
Van double naar float heeft denk ik geen zin meer op een 64 bit processor, maar daar zou je ook nog naar kunnen kijken. Als het scheelt, dan scheelt het meteen 100%!
Als je je probleem genormaliseerd hebt, valt het wel mee met het precisie verlies.

Nyquist kan je vertellen of dat bij jouw probleem allemaal kan..
[Edit: ik herlees je originele mail en daarin zeg je dat het nodig is, die dubbele precisie. Dan is je 256x256 vast ook nodig :/] Ik geloof dat niet helemaal, wat is jouw Nyquist sommetje?

[Ir. Technische Wiskunde TU/e - 1993]

Bedankt voor je uitgebreide reactie, mocht je geinteresseerd zijn, ik ben optica en turbulentie aan het simuleren. En met Fourier transformaties gaat dat heel makkelijk. Ik gebruik de standaard IDL FFT, dus die zal wel geheel geoptimaliseerd zijn.

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.

[MSalters]

Tja, ik ben toch geneigd om te suggereren dat je snelheidswinst het makkelijkste te halen is door een slimmer algoritme. Om een oplossingsrichting te suggereren: gebruik eerst lage precisie (128x128) om vervolgens in deelgebieden met hogere resolutie eeen foutcorrectie toe te passen. Dat werkt als/omdat je nu grote gebieden met hoge precisie uitrekent terwijl ze niet wezenlijk bijdrage aan de foutterm.

[prometheus345479]

MSalters schreef op maandag 19 mei 2008 @ 00:11:
Tja, ik ben toch geneigd om te suggereren dat je snelheidswinst het makkelijkste te halen is door een slimmer algoritme. Om een oplossingsrichting te suggereren: gebruik eerst lage precisie (128x128) om vervolgens in deelgebieden met hogere resolutie eeen foutcorrectie toe te passen. Dat werkt als/omdat je nu grote gebieden met hoge precisie uitrekent terwijl ze niet wezenlijk bijdrage aan de foutterm.

Het probleem is dat er niet valt te voorspellen wat de fout is. Ik genereer een willekeurig golffront, en doe daar een fouriertransformatie op.

Inmiddels heb ik zelf al iets bedacht wat ongeveer 25% snelheidswinst op moet leveren. (beetje te ingewikkeld om op een programmeer forum op in te gaan). Maar dan nog duurt het erg lang.

[pkuppens]

prometheus345479 schreef op maandag 19 mei 2008 @ 09:21:
[...]


Het probleem is dat er niet valt te voorspellen wat de fout is. Ik genereer een willekeurig golffront, en doe daar een fouriertransformatie op.

Inmiddels heb ik zelf al iets bedacht wat ongeveer 25% snelheidswinst op moet leveren. (beetje te ingewikkeld om op een programmeer forum op in te gaan). Maar dan nog duurt het erg lang.

Wat doe je allemaal nog meer dan dat? Want mijn matlab op een trage SUN had maar orde grootte milliseconden nodig om een 256x256 FFT uit te rekenen.

En wat gaf de code profiler aan?

[prometheus345479]

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
ACOS            (S)       2    0.007523  0.003761    0.007523  0.003761
ARG_PRESENT     (S)       2    0.000006  0.000003    0.000006  0.000003
BYTE            (S)    6004    0.021434  0.000004    0.021434  0.000004
COOGRID         (U)    6002    7.138946  0.001189   11.613055  0.001935
COS             (S)    5000   11.494399  0.002299   11.494399  0.002299
CREATE_STRUCT   (S)    6003    2.087533  0.000348    2.087533  0.000348
DBLARR          (S)    9014    1.022593  0.000113    1.022593  0.000113
DCOMPLEX        (S)    8000    6.051644  0.000756    6.051644  0.000756
DINDGEN         (S)   12004    0.065636  0.000005    0.065636  0.000005
DOUBLE          (S)   10000    1.872647  0.000187    1.872647  0.000187
ECLAT           (U)    4000    0.128123  0.000032    4.221070  0.001055
EXP             (S)    3000   15.977381  0.005326   15.977381  0.005326
FFT             (S)    4000   55.418734  0.013855   55.418734  0.013855
FIX             (S)       3    0.000248  0.000083    0.000248  0.000083
FLOAT           (S)       2    0.000006  0.000003    0.000006  0.000003
GENERATE_IMAGE  (U)    1000    5.626188  0.005626  154.693842  0.154694
GENSHIFT        (U)    1000    4.322913  0.004323   64.514111  0.064514
IMAGINARY       (S)    3000    1.522926  0.000508    1.522926  0.000508
KEYWORD_SET     (S)  169044    0.395062  0.000002    0.395062  0.000002
LONG            (S)    1000    0.002499  0.000002    0.002499  0.000002
MATHFT          (U)    4000   16.434584  0.004109  196.604006  0.049151
MIN             (S)    4000    1.054041  0.000264    1.054041  0.000264
MOMENT          (U)       2    0.000098  0.000049    0.000185  0.000093
N_ELEMENTS      (S)    6006    0.014832  0.000002    0.014832  0.000002
N_PARAMS        (S)   22002    0.050284  0.000002    0.050284  0.000002
ON_ERROR        (S)    4004    0.015306  0.000004    0.015306  0.000004
PRINT           (S)      12    0.000314  0.000026    0.000314  0.000026
PROFILER        (S)       4    0.000175  0.000044    0.000175  0.000044
RANDOMN         (S)    1000    5.908828  0.005909    5.908828  0.005909
RANDOMU         (S)    1000    1.368500  0.001368    1.368500  0.001368
ROTATE          (S)    8000    4.265221  0.000533    4.265221  0.000533
SHIFT           (S)    4000    4.033640  0.001008    4.033640  0.001008
SIN             (S)    5000  101.880558  0.020376  101.880558  0.020376
SIZE            (S)  227060    0.600929  0.000003    0.600929  0.000003
SQRT            (S)    3006    1.353392  0.000450    1.353392  0.000450
STDDEV          (U)       2    0.000030  0.000015    0.000223  0.000111
SYSTIME         (S)       1    0.000005  0.000005    0.000005  0.000005
TOTAL           (S)    4006    0.036819  0.000009    0.036819  0.000009
WAVE            (U)    1000   20.994102  0.020994  118.914418  0.118914
WFSSIM          (U)       1    1.194888  1.194888  274.870050274.870050
WHERE           (S)    5002    0.242422  0.000048    0.242422  0.000048

• De colom module geeft de naam van de module aan.
• Type geeft het type van de module aan. U is zelf gemaakt, S is een system variabele
• count is het aantal keer dat een functie wordt aangeroepen.
• only is de tijd die besteed wordt in de functie zelf (dus zonder de tijd meegerekend van calls naar externe functies)
• time is de tijd besteed in de functies in totaal

Dit is het resultaat van 1000 iteraties. In totaal moeten er 9*9*5=405 maal 1000 ieteraties uitgevoerd worden. En dit moet in totaal voor 5 verschillende waarden worden uitgevoerd, maar dat kan gespreid worden over 5 cores.

Het beste kun je kijken naar de only time, waar te zien is dat de meeste vertraging zit in de sinus functie, en in de fast fourier transform functie. Sin wordt per iteratie 5 maal aangeroepen, fft 4 maal.

De grote verassing is dus dat de vertraging in de sinus functie optreed, en niet zozeer in de fft. Toch wel nuttig zoiets.

Ik ga nu uitzoeken of ik calls naar sin kan vervangen door iets anders, snellers.

Bedankt voor de hulp, en als iemand nog suggesties heeft dan graag!

[JeRa]

De standaard methode om aanroepen naar sin() te versnellen is vantevoren een cache te maken met input -> output waarden. Afhankelijk van hoeveel waarden je cachet en het bereik van deze waarden gaat dit ten koste van de nauwkeurigheid van je model, of van het geheugengebruik.

[ Voor 11% gewijzigd door JeRa op 21-05-2008 10:58 ]

[Stamgastje]

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).

[zeroxcool]

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?

[Knutselsmurf]

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

[JeRa]

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.

[prometheus345479]

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 )

[ Voor 5% gewijzigd door prometheus345479 op 22-05-2008 10:27 ]

[pkuppens]

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

[.oisyn]

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)

[H!GHGuY]

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++:

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++:

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

deze

C++:

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++:

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.

[YopY]

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

C++:

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

deze

C++:

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++:

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.

[.oisyn]

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++:

bool ok = true;

if (!a)
{
    if (!b)
    {
        if (!c)
            ok = false;
    }
}

if (ok)
{
    // doeIets
}

[ Voor 94% gewijzigd door .oisyn op 26-05-2008 11:45 . Reden: goto weggewerkt ;) ]

[H!GHGuY]

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

[Spiked]

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).

[Voutloos]

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.

[.oisyn]

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)

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'.

[ Voor 20% gewijzigd door .oisyn op 23-06-2008 17:58 ]

[MSalters]

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.

[Hydra]

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.

[.oisyn]

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.

[ Voor 72% gewijzigd door .oisyn op 23-06-2008 22:33 ]

[zoxzo]

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.

[apyss]

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

[Peter]

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++:

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;
.

code:

    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.
.

code:

    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++:

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++:

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.

[ Voor 13% gewijzigd door Peter op 24-07-2008 12:41 ]

[.oisyn]

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++:

if (b > 5)
    a = 10;

kan dan worden vertaald naar

GAS:

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)

[Peter]

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

[.oisyn]

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++:

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

[ Voor 26% gewijzigd door .oisyn op 26-07-2008 15:06 ]

[igmar]

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.

[.oisyn]

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.

[ Voor 24% gewijzigd door .oisyn op 28-07-2008 13:04 ]