Fragen? Antworten! Siehe auch: Alternativlos
Also, wenn ich zwei 1024-Bit-Zahlen addieren will, dann sind das auf AMD64 16 Additionen. Mein Code braucht ca 640 Zyklen, der gcc-Code braucht ca 440 Zyklen, der schnellste Code (tomfastmath) braucht immer noch 390 Zyklen. Auf meinem Athlon 64 braucht der Code 84 Zyklen. Es ist bekannt, daß Addition mit Carry auf dem Pentium 4 unglaublich langsam ist, aber auf dem Core hieß es hätten sie das gefixt. Wenn man 16 Mal "adc %%rdx,%%rax" macht, braucht das auf dem Athlon 64 16 Zyklen, auf dem Core 2 aber 48. Das ist enttäuschend, aber das ist immer noch nur ein Zehntel der Gesamtzeit. Wo geht die ganze Zeit hin? Ich habe dann mal in mehreren Schritten geguckt, aber schaut euch den Code selber an (nur den 64-bit-Teil). Ich habe da mehrere Verfahren getestet, wie man die Addition machen kann. Es stellt sich raus, daß das pure Laden, Addieren und Schreiben bloß 72 Zyklen braucht, wenn man die Offsets als Konstanten hinschreibt und das nicht als Schleife macht. Dabei spielt es keine Rolle, ob man das Ergebnis des adc direkt schreibt oder in einem Register hält und später schreibt (immer vier adds, vier stores habe ich getestet). Allerdings: wenn man immer direkt schreibt, und immer das selbe Register für den Wert nimmt, dann wird es langsamer. Für genau diesen Fall ist Register Renaming da, das können x86-CPUs an sich seit Pentium 2 oder so. Offenbar hat Core 2 da Defizite, den dann kostet das einen Cycle mehr pro Addition.
Damit wären wir bei 84 Cycles insgesamt, immer noch weit von den 480 entfernt. Wenn man das als Schleife schreibt, und die Offsets in den Arrays dynamisch ausrechnet (über einen Schleifenzähler und die erweiterten Adressierungsmodi von x86), ist man plötzlich bei 480 Cycles. Ja, richtig gelesen! Die selbe Arbeit, als Schleife geschrieben, braucht mehr als 6 Mal so lange. Schlimmer noch, wenn man das nicht über die erweiterte Adressierung sondern per Zeigerarithmetik macht, braucht der Code sogar 504 Zyklen! Kurz gesagt: das ist ein Desaster. Ich bin völlig überrascht, daß das das Bottleneck ist. Das heißt für mich, daß ich da jetzt für typische Werte wie 1024, 2048 ausgerollte Routinen vorhalten werde. Übrigens ergibt sich beim Athlon 64 eine ähnliche Progression, aber statt von 72 zu 504 geht es dort nur von 42 zu 160. Man sieht also: auch dort ist noch deutlich was rauszuholen.
Übrigens: auf dem Athlon ist es schneller, zwischen das add und das Rausschreiben des Ergebnisses andere Instruktionen zu schedulen. Das ist auch überraschend, das hätte danke Reordering kostenlos sein sollen.
Kurzzusammenfassung für Nicht-Assemblerhacker: normalerweise optimiert man Schleifen, indem man den Inhalt der Schleife optimiert, und sich Gedanken macht, ob man die Parallelität erhöhen kann, indem man den Schleifeninhalt möglichst so formuliert, daß verschiedene Durchläufe unabhängig voneinander sind. Conventional Wisdom ist, daß man sich eine alte Optimierung namens Unrolling heute sparen kann, ja es sogar kontraproduktiv ist, weil der eigentliche Schleifenteil wegen CPU-Features wie Register Renaming, Multiskalarität, Pipelining und Result Forwarding quasi kostenlos ist, und die CPU intern quasi unsichtbar eh Unrolling betreibt. In meinem Code kommen jetzt aber 80% der Laufzeit vom Schleifenmanagement selbst, nicht vom Code in der Schleife. Diese Erkenntnis ist besonders krass, weil die plötzlich denkbare Ersparnis deutlich über das hinaus geht, was man von krassen Spezialoptimierungen wie Vektorinstruktionen o.ä. hätte erwarten können.