Kurze Beschreibungshilfe für Array-Zugriffe

Hallo beisammen,

ich will/soll einen report zu einem implementierten Algorithmus schreiben.
Dabei habe ich eine Routine die innerhalb doppelter schleife auf mehreren Arrays (C-Arrays) operationen ausführt.

Ich habe ein profiling der implementierung gemacht und festgestellt dass es schneller ist innerhalb dieser routine berechnnungen zu machen und diese in ein weiteres array zu speichern. Das profiling zeigte, dass es günstiger ist mehr (unnötige) berechnung zu machen als benötigt werden im gegensatz zu einer version wo man if-abfragen einbaut in die routine.

Ich habe schwierigkeiten den grund dafür technisch anzugeben. Jetzt wollte ich fagen ob folgende überlegungen dazu sinnvoll sein könnten:

Da unnötigen Berechnungen scheinen günstiger zu sein als die irre-oft aufrufenden if-statements. Zusätzlich ist man bei den array-zugriffen im speicher ohnehin schon in der nähe von array-elementen die zu dieser berechnung (nötig+unnötig) gebraucht werden.

Stimmt vor allem letzteres? Kann man sagen dass wenn man auf ein array zugreift mit arr[7] z.B. und dann ein paar code-zeilen später nochmal auf arr[7] zugreift dass dann der zugriff schneller geht als ein if-statement sozusagen?

Danke für eure Hilfe
Gruß

SeppJ

if-Abfragen sind auf modernen Prozessoren elend langsam. Naja, nicht direkt langsam, aber viel langsamer als einfache Rechnungen. Du verstehst, was ich meine. Speicherzugriffe sind an sich auch langsam, aber wenn man einen Wert mehrmals benutzt (oder schon absehbar ist, dass man ihn bald benutzen wird), dann kann er zwischengespeichert werden und der Zugriff ist dann quasi instantan.

Th69

Das eigentliche Stichwort lautet: Cache-Misses
Eine if-Abfrage besteht auf Assembler-Ebene ja eigentlich aus 2 Vorgängen:
- Testen der Bedingung
- Springe zum nächsten Block (bzw. else-Zweig), wenn die Bedingung nicht erfüllt ist

Und gerade der Sprung kann (je nach Größe des Blocks) zu groß für den Cache sein, so daß wieder die neue Page nachgeladen werden muß. Und bei einer Schleife dann wieder an den Anfang zurück (also evtl. wieder alte Page laden etc.)...

Und bei einem Arrayzugriff wird ausgenutzt, daß die Daten alle nahe beisammen sind (außer du hast ein großes Array und greifst zufällig auf die Indizes zu).

SeppJ

@Th69: Deine Erklärung ist falsch. Cache-Misses sind nicht, was if-Abfragen teuer macht. Erstens steht schon im vorhinein fest, wohin man springt und zweitens springt man meistens nur wenige Anweisungen weiter. Und es ist sowieso praktisch das ganze Programm im Cache. Für Cachemisses im Code muss man sich schon sehr anstrengen (exzessives Inlining und Unrolling kann dazu führen).

Was if-Anweisungen so teuer macht ist ein Pipelinemiss. Prozessoren führen eine ganze Reihe von Anweisungen gleichzeitig aus, wie an einem Fließband. Bei if-Anweisungen teilt sich die Reihe in zwei Stränge. Dann muss die Logik im Prozessor abschätzen, welcher Strang wohl genommen wird. Wenn sie falsch liegt, muss der gesamte verarbeitete Strang verworfen werden und nochmal von vorne an der richtigen Stelle angefangen werden. Und so hat man dann ungefähr 2x die Fließbandlänge an Takten verloren.

Das gilt nicht für if-Anweisungen, die ein gut vorhersehbares Ergebnis haben. Bei der Abbruchbedingung einer Schleife, die fast immer das gleiche Ergebnis hat, außer nach dem letzten Durchlauf, lässt sich gut vorhersagen, wie das Ergebnis aussehen wird. Da verliert man dann nix, wenn die Logik im Prozessor den Sprung korrekt vorausgesagt hat.

rapso

eine branch missprediction kostet 1x die pipeline, weil die 'richtige' instruction gleich am anfang der pipeline (+4 cycle latenz wegen icache zugriff) anliegt, ist somit quasi am ende der pipelien mit der verzoegerung der pipelienlaenge (z.b. 16cycles beim nahalem, z.b. i7 920).

gastxxl, wenn du den kritischen teil vom code zeigst, bzw das assembly mit den countern, kann man dir vermutlich genauer antworten, ohne das zu sehen, kann es sowohl am icache wie auch am branch an sich liegen.
( am besten beide assemblies )

ein micro-op miss hat eine wahrscheinlichkeit von ca 20%, ein icache miss bei ca 10%, static branch miss ist bei ca 15% und dynamic (local+global) hat eine chance von 2% bis 12%) beim sandy bridge.
ein branch miss kostet 14 auf sandy bridge + 4cycles cache zugriff beim hit oder 4+12 beim miss, bei einem branch ueber 4kb gibt es noch extra 24cycles (obwohl es im Icache liegt), ich glaube das war weil es ein TLB lookup gibt.

ein einfacher grund weshalb dein code mit if abfrage langsammer ist, kann sein, dass der compiler einfach nicht ueber diese grenze hinweg optimiert (beim gcc ist das meines wissens nach eine optimization barrier, instructions werden also nicht drueber hinweg verschoben), wenn du also sowas wie:

a=b^c;
if(a&1)
 foo[1]=b+c;
else
 foo[0]=b+c;

hast, wuerde die if zeile auf das ergebnis von a&1 warten, wobei erst auf b&c gewartet wird. Erst dann wuerde je branch b+c berechnet werden, dann wuerde das foo[...] schreiben auf b+c warten.
wenn du

a=b^c;
foo[a&1]=b+c;

hinschreibst, wird b^c parallel zu b+c berechnet und nur a&1 wartet auf b^c;

deswegen ist es ohne code nicht so sehr sinnvoll zu sagen ob es am cache, oder branch, oder scheduling vom instructions durch den compiler, oder RAW dependancy, oder was ganz anderem liegt.

SeppJ

rapso schrieb:

ein micro-op miss hat eine wahrscheinlichkeit von ca 20%, ein icache miss bei ca 10%, static branch miss ist bei ca 15% und dynamic (local+global) hat eine chance von 2% bis 12%) beim sandy bridge.

Woher hast du diese Zahlen? So etwas hängt doch höchst empfindlich vom Code ab. Man kann leicht Code erzeugen, der zu 50% Branch Miss oder zu 100% Op Miss hat.

rapso

von intel, es ist ein average den sie errechnen (bzw median wird es wohl eher treffen). bevor intel eine hardware optimierung macht, untersuchen sie analytisch wieviel es bei der meisten zeitkritischen software bringt.
anderesrum ist natuerlich zeitkritische software so aufgebaut, dass sie moeglichst in diese cache areas passt.

falls du nach einem speziellen paper/link fragst, sorry, das war nur aus dem kopf, ich habe kein spezielles paper zittiert. aber kurz googlen bringt dieselben zahlen hervor z.b. micro-op cache hit rate:
http://www.legitreviews.com/article/1501/2/

natuerlich kannst du eine software machen die 0% hitrate hat, genau so wie du eine schreiben kannst, die 100% hitrate hat, daran zweifelte ich nicht.

SeppJ

nein, spezielles Paper ist nicht nötig, ich wollte nur wissen, wie die Zahlen zustande kommen. Und dies sagt mir nun, dass diese Zahlen wichtig sind bei der Optimierung des Prozessors, nicht aber bei der Optimierung von Software. Denn die konkrete Software hat ganz eigene Raten, da sie sich nicht an den Durchschnitt aller Software hält. Diese Raten klein zu halten ist Teil der Optimierung.

puh...also danke erstmal für eure Hilfe/Antworten. Sehr interessant alles.
Assembler wäre mit sicherheit ein nächster schritt den ich leider aus zeitgründen jetzt net hinbekomm.

kann mir jemand noch erklären was ein icache ist? google spuckt mir nur seltsame geld-transfer links aus....

danke euch

eine kurze frage noch:
wo könnte ich sowas nachlesen mit sinnvoller literatur. ich meine jetzt euch beide -> SeppJ und rapso -> also in bezug auf eure erklärungen...

rapso

SeppJ schrieb:

...nicht aber bei der Optimierung von Software.

damit widersprichst du:

SeppJ schrieb:

Man kann leicht Code erzeugen, der zu 50% Branch Miss oder zu 100% Op Miss hat.

Denn wenn du die hardware kennst, kannst du einen algorithm waehlen, der am besten fuer die hardware ist.
simples beispiel ist z.b. dass viele gute quicksort implementierungen nach einiger zeit in ein insert sort uebergehen, weil das vergleichen von werten mit immer dem selben ergebnis gut predicted wird, ein quicksort ist zwar akademisch schneller, aber praktisch langsammer.
wieviele elemente du per insertsort sortierst, ist dann wieder sehr architektur abhaengig.
Bei manchen architekturen (GPU ;)) ist branching an sich derart teuer, dass man dann lieber eine bitonic sort einbaut.
Wenn du am ende eine Software geschrieben hast, die nicht 50% (ala quicksort), sondern 90% (ala insertsort) branch hitrate hat, hast du deinen software teil gemacht (Das ist mein widerspruch zu deiner behauptung :D)

Denn die konkrete Software hat ganz eigene Raten, da sie sich nicht an den Durchschnitt aller Software hält. Diese Raten klein zu halten ist Teil der Optimierung.

der kritische teil einer software ist normalerweise ein sehr kleiner teil, den wird man vermutlich sehr bewust designen und kann dann algorithmen waehlen die fuer die hardware spezialisiert sind.
Ein grund weshalb intel IPP anbietet, die je nach cpu eine andere dll laedt, selbst der intel compiler waehlt je nach cpu andere pfade innerhalb deines compilierten binaries, das liegt nicht nur an prozessorfeatures, manchmal auf dem P4 hat intel mmx benutzt, wofuer auf dem P3 SSE benutzt wurde (ich glaube das waren spezielle memcpy usw.)

es gibt aber auch cross-cpu ein paar dinge die man ueber branch prediction wissen kann, z.b. dass ein vorwaerts branch nicht genommen wird, ein rueckwaerts branch wird genommen, entsprechend kann man seinen code versuchen anzupassen, z.b. indem man einen binary tree aus der balanz bringt und so vermutlich etwas mehr branches springt (also tiefere rekursion), aber durch den predicted code path doch schneller ist.

@GastXXL
icache ist "instruction cache" im gegensatz zu dcache "data cache", ein intel atom hat z.b. 24kb dcache und 32kb icache, sie nehmen dieselbe silizium flaeche ein, die 24kb sind mit 8transistoren gebaut um energie zu sparen, die 32kb mit 6transistoren und auf kurze latenz ausgelegt.

SeppJ

rapso schrieb:

SeppJ schrieb:

...nicht aber bei der Optimierung von Software.

damit widersprichst du:

SeppJ schrieb:

Man kann leicht Code erzeugen, der zu 50% Branch Miss oder zu 100% Op Miss hat.

Nein tue ich nicht, denn:

Denn wenn du die hardware kennst, kannst du einen algorithm waehlen, der am besten fuer die hardware ist.

Die Zahlen verraten mir nichts über die Hardware, sondern darüber, was der Durchschnitt in irgendwelcher Testsoftware ist, die Intel genommen hat um auszumessen, ob und in welchen Bereichen sie ihre Hardware optimieren sollten.

Was wichtig zu wissen ist, wieviel ein Miss (egal von welcher Sorte) kostet. Dann kann man abwägen, ob man lieber rechnet oder lieber einen möglichen Miss in Kauf nimmt (siehe Beispiel des Threaderstellers). Diese Zahlen stehen daher auch in den gängigen Optimierungshandbüchern.