Doppelte for schleife: performance optimierung

G

Greenberet

0
Hi!
Das problem einer doppelten for Schleife liegt daran, dass sie sehr langsam ist. Es ist jedoch leicht möglich eine doppelte in eine einfache umzuwandeln.
Einige meinen vl, dass es keinen großen unterschied macht, aber der Unterschied ist ENORM.

Ich hab diese variante in den Sprachen C, C++(native), c#, java und pawn getestet. Das Ergebnis war überall gleich, die einfache ist schneller :P

Beispiel: Ich hab vor ca. nem jahr eine ShaderApi geschrieben und hab um jedes Pixel zu benutzen eine doppelte for-schleife gehabt.
Code: 
for( int y = 0; x < max_y; y++ )
{
     for( int x = 0; y < max_x; x++ )
     {
           //PAAR OPERATIONEN
     }
}
Diese schreibweise ist leider weit verbreitet.
Bei dem Sobel - Operator hat diese Schreibweise bei einem Bild( 1024X768 ) ca 6-7 sekunden gedauert

Hier die Umwandlung in eine einfache for-schleife
Code: 
int size = max_x * max_y;
for( int i = 0; i < size; i++ )
{
      int x = i % max_x;
      int y = i / max_x;

     //PAAR OPERATIONEN
}
Allein durch diese Änderung hat die ganze Operation beim Sobel-Filter gerade mal < 1 sec gedauert^^.
Zu beachten ist die Schreibweise der Berechnungen.

x wäre in beiden Fällen die innere Schleife und y die Äußere.

Hier ist jetzt der genaue Code was ihr wie ersetzen müsst:
Code: 
for( int var_aussen; var_aussen < aussen_max; var_aussen++ )
{
     for( int var_innen; var_innen < innen_max; var_innen++ )
     {

     //...

     }
}

//die gesammtgröße in eine variable speichern, da sie sonst jedes mal neu ausgerechnet werden würde.
int size = aussen_max * innen_max;
for( int i = 0; i < size; i++ )
{
     int var_innen = i % innen_max;
     int var_aussen = i / innen_max;

     //...
}


Also ihr seht schön eine einfache for-schleife benutzen :P
Wenn ich mein altes Programm gefunden hab, uploade ich es mal.

-- Greenberet
 
wenn ich das jetzt richtig verstanden habe, bezieht sich das nur auf render-engines? denn wenn die innere schleife inkrementel und die äußere dekrementel zälht, dann sollte doch eigentlich keine optimierung möglich sein. nur um auf nummer sicher zu gehen...

weiß eigentlich jemand, wie die performance mit zwei while-schleifen aussieht? bin grad dabei meinen laptop neu aufzusetzen...
 
also das ganze geht nur wenn beide dekrement oder inrement sind
wie die berechnung bei unterschiedlichen ist muss ich mir erst anschauen XD
Ich glaube das ganze müsste man dann mit einer wertinvertierung gehen.

und nein das ist nicht nur bei rendering, ich hab rendering nur als beispiel genommen weil das viel zeit in anspruch nimmt und man dort die zeit aber braucht. Bei anderen dingen ist die einfache auch schneller^^

mit while schleifen sieht das ganze im großen und ganzen gleich aus wie mit den for schleifen.
 
Ich denke das hängt SEHR vom compiler ab ;)
//die gesammtgröße in eine variable speichern, da sie sonst jedes mal neu ausgerechnet werden würde.
Zum Vergrößern anklicken....

Ein ordentlicher compiler macht es natürlich weg ;). Z.B auch
Code: 
for(int i=0;i<MAX;i++)
{
ergebnis=i*20;
}
sollte ein "neuerer" Compiler vorberechnen und die Schleife aus dem fertigen Code wegoptimieren.
Was Du vergleichst, ist ohne den "weitere Codeeinsicht" nicht wirklich vergleichsam: denn normalerweise ist eine Division zumindest auf einem Pentium/AMD immer noch langsamer als ein Vergleich - und davon hast Du gleich zwei.Ein "vernünftiger" Compiler würde es hier bei einer belassen (denn bei einer Division wird gleichzeitig auch der Rest festgehalten - so braucht man eigentlich nur eine, eventuell also die Reihenfolge % und / vertauschen - um dem Compiler bei der optimierung zu helfen) . Was ich vermute, warum bei Dir soviel mehr leistung rausgekommen ist: bessere Cache"hits", auch wenn solche Sachen auf einem P4 schwer vorherzusagen sind. Jedenfalls denke ich dass besonders bei Speicherzugriffen diese Zählvariablen alleine keine allzugroße Rolle spielen ;)




Ok, ein wenig von meiner Seite:
Code: 
    align 4
        timer_begin 1000, REALTIME_PRIORITY_CLASS ;die schleife wird insgesamt 1000 000 000 durchlaufen
        mov ebx,0 ;mov 0 ist schneller als XOR -> inteldoku +eigene tests
        LOOP1:
          mov ecx,0
          LOOP2:
            add ecx,1
            cmp ecx,1000
            jbe LOOP2
          add ebx,1
          cmp ebx,1000
          jbe LOOP1  
 

    timer_end
    print ustr$(eax)
    print chr$(" ms, 'primitiver Loop'",13,10)

    align 4
    timer_begin 1000, REALTIME_PRIORITY_CLASS

        mov ebx,1000
        LOOP3:
          mov ecx,1000
          LOOP4:
            sub ecx,1 ;auf Pentium4 schneller als dec ecx
            jns LOOP4
          sub ebx,1
          jns LOOP3  
 

    timer_end
    print ustr$(eax)
    print chr$(" ms, 'verbesserter Loop'",13,10)

    
align 4
    timer_begin 1000, REALTIME_PRIORITY_CLASS
        
        mov edi,1000; unsere MAX Konstante, Optimierung die ein "älterer" Compiler nicht vornimmt!            
        mov ebx,0
        LOOP5:
           mov eax,ebx
           mov edx,0
           div edi
           ;jetzt ist in edx X wert und in EAX Y             
           add ebx,1 ;auf Pentium4 schneller als dec ecx
        cmp ebx,1000000
        jbe LOOP5
         

    timer_end
    print ustr$(eax)
    print chr$(" ms, nur 'eine' schleife, leicht optmiert",13,10)

    align 4
    timer_begin 1000, REALTIME_PRIORITY_CLASS
       
        mov edi,1000; unsere MAX Konstante, Optimierung die ein "älterer" Compiler nicht vornimmt!            
        mov ebx,1000000
        LOOP6:
           mov eax,ebx
           mov edx,0
           div edi
           ;jetzt ist in edx X wert und in EAX Y             
           sub ebx,1 ;auf Pentium4 schneller als dec ecx
        jns LOOP6
         

    timer_end
    print ustr$(eax)
    print chr$(" ms, nur 'eine' schleife, etwas besser optimiert",13,10)


mov   eax, input(13,10,"Press enter to exit...")
exit

; ??????????????????????????????????????????????????????????????
end start

Ich bin zwar alles andere als ein guter Optimierer, nicht desto trotz glaube ich einen Compiler überbieten zu können, der nicht mal
e speichern, da sie sonst jedes mal neu ausgerechnet werden würde.
int size = aussen_max * innen_max;
Zum Vergrößern anklicken....
optimieren kann ;)

und zwar wird jede Schleife 1000 000 000 mal asugeführt (die forschleifen jeweils 1000 mal und die funktion selber auch 1000 mal, damit man halbwegs was messen kann).
alle schleifen sind gleich - sie laufen immer die gleiche Anzahl an Loops durch. Die ersten beiden sind jeweils: eine "naive" Schleife, dann eine "optimierete" (zählt rückwärts und erspart sich damit einen Vergleich) die anderen beiden sind jeweils zu einer zusammengefasst worden (nach Deiner Methode - also auch das Modulo/Teilen um X,Y Werte herauszufinden), wobei ich die erste nur "ein wenig" optimiert habe: sprich sie kommt nur mit einer Division aus (das wird ein "älterer" Compiler nicht berücksichtigen und fast mit sicherheit zwei daraus machen) und auch die Konstante lasse ich im Register (wiederum: bei älteren C/Delphi compilern kann man davon ausgehen, dass sie sie Lokal abspeichern und gleich wieder laden :rolleyes: )
die zweite Schleife ist wieder "rückwärts" und erspart sich dadurch einen Vergleich. Das ganze ist auf einen P4 ausgelegt (deswegen auch mov ecx,0 und nicht XOR - denn mov ist schneller, genauso ADD ECX,1 und nicht INC ECX). Meine Zahlen sind (P4, 3.0 GHz, HT):

Durchlauf 1:
525 ms, 'primitiver Loop'
418 ms, 'verbesserter Loop'
9586 ms, nur 'eine' schleife, leicht optmiert
9210 ms, nur 'eine' schleife, etwas besser optimiert

Durchlauf2:
526 ms, 'primitiver Loop'
446 ms, 'verbesserter Loop'
9613 ms, nur 'eine' schleife, leicht optmiert
9435 ms, nur 'eine' schleife, etwas besser optimiert

Durchlauf3:
528 ms, 'primitiver Loop'
440 ms, 'verbesserter Loop'
9586 ms, nur 'eine' schleife, leicht optmiert
9110 ms, nur 'eine' schleife, etwas besser optimiert

Wie man sieht, bringt die jeweilige "Minioptimierung" (sprich das rückwärtslaufenlassen) bei den "normalen" Schleifen am meisten. Die jeweiligen unteren Werte sind übrigens kein Fehler (wie auch ich anfangs dachte) ;)
wenn man die Division weglässt, sind die Werte z.T sogar besser als bei den oberen Schleifen (da weniger Instruktionen).
Und wenn man bedenkt, dass ein "älterer" Compiler hier gar zwei Divisionen und ein paar unnötige Speicherzugriffe hätte - damit untermauere ich meine These, dass bei Dir andere Gründe für den Leistungszuwachs gesorgt haben ;).

Im Anhang ist eine Test.exe samt Quelltext und Includes. Damit kann jeder, der MASM32 v8 hat, damit rumspielen.
 
8o

member of honour bzw mod ist das mindeste, was cdw werden kann: sein altruismus in ehren auf ewiglich (oder so) *thumbsup*

nun aber wirklich gute nacht ;)
 
@CDW: wenns aber nur um die division geht, die braucht man natürlich nicht. und das eine einzelne schleife weniger overhead produziert sollte eigtl. klar sein.
 
Original von CDW
Ich denke das hängt SEHR vom compiler ab ;)
//die gesammtgröße in eine variable speichern, da sie sonst jedes mal neu ausgerechnet werden würde.
Zum Vergrößern anklicken....
Ein ordentlicher compiler macht es natürlich weg ;).
Zum Vergrößern anklicken....

Bei Konstanten wirds nicht neu ausgerechnet, allerdings bei normalen variablen schon, da sich die Wärte ändern könnten

Was Du vergleichst, ist ohne den "weitere Codeeinsicht" nicht wirklich vergleichsam: denn normalerweise ist eine Division zumindest auf einem Pentium/AMD immer noch langsamer als ein Vergleich - und davon hast Du gleich zwei.
Zum Vergrößern anklicken....
Weiter codeeinsicht: Also Shapderoperationen bestehen aus additionen und multiplikationen von mindestens 9 werten^^( Ausnahme bei multiplikationen mit 0 die hab ich weggelassen, ist aber abhängig vom Shader )

Ein "vernünftiger" Compiler würde es hier bei einer belassen (denn bei einer Division wird gleichzeitig auch der Rest festgehalten - so braucht man eigentlich nur eine, eventuell also die Reihenfolge % und / vertauschen - um dem Compiler bei der optimierung zu helfen) .
Zum Vergrößern anklicken....
jain, wäre möglich das es ein wenig was nützt, allerdings darfst du nicht vergessen, dass diese 2 anweisungen unabhängig von einander sind und deswegen höchst wahrscheinlich gleichzeitig verarbeitet werden.

Was ich vermute, warum bei Dir soviel mehr leistung rausgekommen ist: bessere Cache"hits", auch wenn solche Sachen auf einem P4 schwer vorherzusagen sind. Jedenfalls denke ich dass besonders bei Speicherzugriffen diese Zählvariablen alleine keine allzugroße Rolle spielen
Zum Vergrößern anklicken....
Ähm ich hab meine variablen nicht im register^^( zumindest nich vom code her ;) )

DEIN CODE+erklärung
Zum Vergrößern anklicken....
  • du speicherst alles in registern, ich nicht( hat auch gründe )
  • du machst alles direkt in asm und springst hin und her. In anderen Programmiersprachen ist die übersetzung nicht so simple wie bei dir :P


Und wenn man bedenkt, dass ein "älterer" Compiler hier gar zwei Divisionen und ein paar unnötige Speicherzugriffe hätte - damit untermauere ich meine These, dass bei Dir andere Gründe für den Leistungszuwachs gesorgt haben ;).
Zum Vergrößern anklicken....
Wüsst keine anderen Gründe, da ich nur das umgestellt hab^^


Original von blueflash
@CDW: wenns aber nur um die division geht, die braucht man natürlich nicht. und das eine einzelne schleife weniger overhead produziert sollte eigtl. klar sein.[/quote
da geb ich dir vollkommen Recht.
Zum Vergrößern anklicken....
 
@CDW: wenns aber nur um die division geht, die braucht man natürlich nicht. und das eine einzelne schleife weniger overhead produziert sollte eigtl. klar sein.
Zum Vergrößern anklicken....
Naja, es ging ja egentlich nicht um Shader sondern einfach um "doppelte" schleifen - nichts mehr und nichts weniger, und da so ein "einzelding" eigentlich weniger Overhead verursacht und damit schneller läuft, ist irgendwie logisch ;)

allerdings darfst du nicht vergessen, dass diese 2 anweisungen unabhängig von einander sind und deswegen höchst wahrscheinlich gleichzeitig verarbeitet werden.
Zum Vergrößern anklicken....
Das hängt ja wiederum von der CPU ab und nicht zuletzt was der Compiler daraus bastelt - im schlimmsten Fall hat man nacher zwei Divisionen und der Compiler verwendet bei beiden den EAX Register (was er bei StandardDIV nicht anders machen kann) - so dass sie wiederum abhängig sind und nicht "parallel" ausgeführt werden können. Wobei das ein heikles Thema ist und ich zugegebenermaßen noch nicht wirklich die dicke Intel-Dokumentation unter meinem Schreibtisch durchgelesen habe ;)

Ähm ich hab meine variablen nicht im register^^( zumindest nich vom code her Augenzwinkern )
....
du machst alles direkt in asm und springst hin und her. In anderen Programmiersprachen ist die übersetzung nicht so simple wie bei dir
Zum Vergrößern anklicken....
Naja, das war die "möglichst" optimale Annahme, was so ein Compiler eigentlch daraus basteln können sollte (eventuell gehts auch noch besser).
Und ein Forschleife sollte doch auch in etwa so übersetzt werden - zumindest Schablonenmäßig als Label mit einem Jump. Ob aber mit oder ohne ausgiebige Registernutzung - Div bleibt Div.

Wüsst keine anderen Gründe, da ich nur das umgestellt hab^^
Zum Vergrößern anklicken....
Was ich meinte war ja eben, dass man nicht pauschal das sagen kann - rein logisch müsste es langsamer werden ;) , auch wenn es vom Schleifenoverhead nicht wirklich auffallen sollte. Was ich mit Chachehits meinte:
ein einfaches Beispiel.
Code 1:
Code: 
for (int y=0;y<BILD_Y;y++)
  for(int x=0;x<BIDL_X;x++)
   {
    ReadPixel(x,y);
   }
Code 2:
Code: 
for (int x=0;x<BILD_X;x++)
  for(int y=0;y<BIDL_Y;y++)
   {
      ReadPixel(x,y,blue);
   }
Rein formell ist es das gleiche - allerdings wird i.R Code1 auf einem Pentium/AMD
viel schneller laufen als Code2 - denn die Daten liegen linear im Speicher

pixel1,pixel2, ... , pixel2000

und werden auch in Blöcken beim Zugriff "gecacht". Der erste Code geht sequentiell durch, der zweite dagegen "hüpft" durch den Speicherraum durch (zugriff: y*Y_MAX+x) und macht dadurch Caching zurnichte - so dass man als Folge langsame Speicherzugriffe hat und insgesamt eine sehr schlechtere Perfomance. Und vielleicht hattest Du "Glück" mit der Umstellung und hast dadurch z.B die "magische" Cachegrenzengröße erreicht - so dass der Code komplett gecacht werden konnte.
Die Wege des Compilers sind unergründlich ;)

Wäre aber interessant, wenn jemand das ganze mit einem "hochoptimierenden" Compler testet (z.B dem von Intel).
 
einigen wir uns darauf, dass es teilweise schneller und teilweise langsamer ist( osnt artet das hier noch aus )^^

zugriff: y*Y_MAX+x
Zum Vergrößern anklicken....
falsch
y*X_MAX+x

deswegen ist die formel ja auch

Code: 
int x = i % X_MAX;
int y = i / X_MAX;

wenn man hier jetzt Y_MAX genommen hätte wäre es dein code 2 gewesen^^
 
/Neunmalkluger-Modus on

Das was hier diskutiert wird ist unter dem Begriff "Big O Notation" bekannt. Eine einzelne Schleife hat die Komplexität von O(N), eine verschachtelte von O(N?).

/Neunmalkluger-Modus off ;)
 
/Neunmalklügerer Modus an

Grundsätzlich richtig. Aber wenn man aus zwei verschachtelten schleifen die jeweils eine Komplexität von O(n) haben eine macht die die gleiche Funktionalität bietet, hat man i.d.R. eine neue Schranke
m = n * n also ändert sich an der Komplexität gar nüscht. ;)

/Neunmalklügerer Modus aus
 
Da in der Äusseren Schleife nun "drinnen" keine weitere Schleife mehr abläuft, verringert dies die Komplexität von O(N?) zu O(N log N) wenn ich mich noch recht daran erinnere. Auf jeden Fall ist die Komplexität kleiner geworden (auch wenns nur ein bischen ist).

So genug über Big-O gelabert 8)
 
re

Hi!
Ich habe mir das Ganze mal angeschaut und stelle fest: Es funktioniert nicht.
Das Problem ist, dass wir in der Mathematik mit einem Dezimalsystem rechnen, wie der Code hier ja auch.
Code: 
int size = max_x * max_y;
for( int i = 0; i < size; i++ )
{
      int x = i % max_x;
      int y = i / max_x;

     //PAAR OPERATIONEN
}
Soweit so gut. Aber wenn wir jetzt wollen, dass die Null auch immer mitzählt
for( int y =0; x < max_y; y++ )

for( int x = 0; y < max_x; x++ )
Zum Vergrößern anklicken....
, dann funktioniert der Code nicht mehr und man muss folgendes machen:
----------------------------------------------------------------
int size = max_x * max_y + max_x + max_y;
for( int i = 0; i < size; i++ )
{
int x = i % (max_x+1);
int y = i / (max_x+1);

//PAAR OPERATIONEN
}
---------------------------------------------------------------
Ich hoffe, ich habe den C++-Code richtig geschrieben, kann kaum C++. ;)
cu gabriel
 
Mein Code stimmt schon.
deiner ist falsch.
du vergisst dass man mit 0 zu zählen beginnt und nicht mit 1
sprich max_x = 5
mögliche pos. für x: 0, 1, 2, 3, 4
 
re

Hi!
Kann sein, dass ich das falsch verstanden habe. Wenn du also sagst Maximum=5, dann willst du 5 gar nicht erreichen, sondern nur bis 4 gehen? Da macht zwar die Bezeichnung MAX keinen Sinn, aber dann stimmt dein Code natürlich, aber wenn du wirklich bis einschließlich zum Maximum gehen willst, wirst du meinen nehmen müssen.

cu Gabriel

PS: Jetzt sehe ich es gerade: Du hast als Bedingung gestellt: x < max_x. Sorry, habe ich wegen der verwirrenden Bezeichnung "max_x" übersehen.
 
Ich fütchte, ich muss das noch mal klarstellen.

In den simplen Fällen, die ihr hier beschreibt (sprich: Zählschleifen), bringt es keinerlei performance oder laufzeitvorteile, aus zwei schleifen eine zu machen. Beweis: Es geht euch darum, für ein Rechteck, das aus sagen wir A = n*m Pixeln besteht, auf jedem Pixel eine bestimmte Operation mit konstantem Aufwand durchzuführen. Also programmiert man intuitiv zwei Schleifen, zB Zeilen- und Spaltendurchlauf um damit auf jedem Pixel die Operation durchzuführen. Der Aufwand beträgt dann:
c (== Aufwand der Operation) * A (== Anzahl der Pixel) oder eben O(A) in der Big-O Notation. Wenn man diese jetzt umschreibt, kann man auch O(n?) schreiben (angenommen n>m).
Genaueres dazu findet ihr auch in meinem habo-wiki Artikel.
Man hat zwar nun scheinbar quadratischen Aufwand, aber da man eine wesentlich kleinere Variable betrachtet ist das auch ok.

Wenn ihr das ganze nun mit einer Schleife beschreibt, aber trotzdem pro Pixel genau eine Operation durchführen wollt. WIe viele Operationen habt ihr dann? Richtig! Immer noch genau A Operationen also immer noch einen Aufwand von O(A) ihr habt nur die Pixel anders nummeriert.
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben