Hab noch etwas tiefer gegraben und die Kompilate verschiedener Varianten verglichen.
Zunächst: Das "
asm nop end;" am Ende der Funktion ist offenbar ein schlechtes Beispiel. Tatsächlich übersetzt der Compiler die Funktion vollkommen anders (und umständlicher), sobald ein asm-Block innerhalb des Quelltextes auftaucht. Und zwar von der ersten Zeile an, nicht erst ab der Position des Blocks. Das gilt auch dann, wenn man die veränderten Register dem Compiler anzeigt, also z.B. so:
Man kann daraus aber nicht den Schluß ziehen, daß dieser asm-Block quasi vorsorglich alle Optimierung komplett ausschalten würde, denn auch dann enthält das Kompilat eingesprengte Alignments.
Anstelle des asm-Blocks habe ich es dann einmal mit einem zusätzlichen "
inc(i)" versucht, am Ende der Funktion, wobei das i eine lokale und später nicht mehr gebrauchte Integer-Variable ist. Auch damit läßt sich der Laufzeitunterschied nachfolgender Prozeduren reproduzieren.
Was also ändert sich durch das Vertauschen der Reihenfolge zweier Prozeduren im Quelltext oder das geringfügige Ändern irgendeiner vorhergehenden Prozudur? Es ist nicht so, daß der Compiler überhaupt kein Alignment der Prozedur-Startpositionen vornehmen würde (die Startposition also um lediglich 1 Byte verschoben wäre). Das voreingestellte Alignment basiert vielmehr auf 8, die nachfolgende Prozedur läuft (in meinem Fall!) schneller, wenn sie auf 0 beginnt, und 10 % langsamer, wenn sie auf einer 8 startet. Der Effekt ist verschwunden, sobald ich die Compileranweisung "
{$CODEALIGN PROC=16}" hinzufüge.
Das läßt sich aber keineswegs generalisieren! Denn der
Startpunkt der Funktion ist meistens ziemlich unwichtig, er wird pro Durchgang nur einmal angesprungen. Befinden sich innerhalb der Funktion Loops, also etwa beim Durchsuchen eines Strings nach einem Treffer mit einem Vergleichsstring (z.B. bei System.Pos) - und nur solche Prozeduren lohnt es, zu optimieren - werden die
Startpositionen der Loops zum entscheidenden Merkmal. Das funktioniert im meinem Fall also nur
zufällig dann besser, wenn die Funktion auf der 0 beginnt, es könnte genausogut umgekehrt sein.
Deshalb habe ich es auch einmal mit
versucht. Der Effekt war durchwachsen berauschend! Meine Funktion ("
ShortPosSensitive", oben als "
Func3" bezeichnet), an deren Optimierung ich arbeite und die ohnehin schon ziemlich gut war (25 % schneller als ihr RTL-Pendant), hat sich damit schlagartig um nochmal 12 % verbessert. Die Vergleichsfunktionen allerdings (u.a. eine 1:1-Kopie der ShortString-Variante von System.Pos) konnten davon nicht profitieren und blieben gleich schnell. Ein Aufstocken auf
{$CODEALIGN LOOP=32} hat übrigens dann keine Veränderungen mehr bewirkt.
mschnell hat geschrieben:Der Prozessor greift auf den Cache (oder z.B. der Layer 1 Cache auf den Layer 2 Cache) vermutlich in einer ziemlich großen Wortbreite zu, die natürlich vom jeweiligen Prozessor-Typ abhängt. Ich schätze z.B. 256 Bit = 64 Byte. Da macht es sicher etwas aus, wie viele solche Worte eine Funktion belegt. Bei einer sehr kleinen Funktion also eines oder zwei. Schlechtes Alignment würde die Anzahl dieser Zugriffe also verdoppeln. Aber wer macht "vorsorglich" schon ein align auf 64 Byte ?
NOPs einfügen würde nur dann ein reproduzierbares Ergebnis bringen, wenn man sich sein kann, dass der gesamte Programm-Code überhaupt in immer derselben Alignment geladen wird. Kann man das ?
Da bin ich mir nicht sicher, ob das wirklich ein entscheidender Punkt ist. Soweit ich es mir aus den verschiedenen Quellen zusammengereimt habe, arbeitet der AMD64 (nur mit dem habe ich mich eingehender beschäftigt) etwa folgendermaßen: Die als nächstes abzuarbeitenden Instruktionen werden in den Prozessor-Cache geladen und danach bewertet, welche Schritte von vorhergehenden (noch abzuarbeitenden) Entscheidungen abhängig sind und welche nicht. Die unabhängigen Aktionen (z.B. das Laden einer neuen Variablen in ein Register) werden dann in einer Art Hintergrundprozeß parallel abgearbeitet und stehen dann schon zur Verfügung, wenn ihr Ergebnis gebraucht wird - das macht die Sache superschnell (der Fachausdruck dafür ist "
Superskalarität"). Verzweigungen infolge von Entscheidungen (z.B. ob die Zählvariable eines Loops ihre Abbruchgröße erreicht hat) stellen dann insofern Stolpersteine dar, als der Prozessor vorab nicht wissen kann, wie die Entscheidung ausfällt und welchem Pfad er demnächst zu folgen hat. Auf sagenhaft schlaue Weise stellt er deshalb "
branch prediction"-Vermutungen an, welche Entscheidung wohl wahrscheinlicher sein dürfte und arbeitet sich an diesem Pfad schon mal vorsorglich ab. Fällt die Entscheidung nun anders aus, war die Vorarbeit für die Katz' und der Prozessor muß erstmal sein Zeug aufräumen und umorganisieren - das kostet dann wiederum Laufzeit. Das ist wohl (zumindest teilweise) der Grund, weshalb man - in Pascal - sagt "
Wähle If-then-else-Anweisungen so, daß der wahrscheinlichere Pfad im If-Zweig steht". Ich bin mir aber nicht sicher, ob das so stimmt! Vom Prozessor her gesehen, ist es eher umgekehrt, da lautet die
Faustregel "
Bedingte Sprünge nach unten sollten zum unwahrscheinlicheren Zweig führen, solche nach oben zum wahrscheinlicheren". Das ist dann allerdings erst der Anfang, innerhalb von Loops lernt der Prozessor hinzu und korrigiert seine Voraussagen. Hochkompliziert, faszinierend und saumäßig schwer zu durchdringen das alles...
Um auf das Alignment zurückzukommen: Soweit ich es verstehe, sind die 16/32/64 oder was auch immer Byte sozusagen die Blockgrenzen für das Bestücken des Prozessor-Caches. Innerhalb dieses Cache-Blocks kann der Prozessor aber nur
eine Verzweigungsstelle im Auge behalten (siehe
hier und
hier). Wenn ich das richtig verstehe, könnten also vermeintlich so elegante Konstrukte wie
Code: Alles auswählen
asm
cmpw %dx, %ax // Vergleich zweier Word-Registerinhalte
ja .L1 // Wenn AX > DX, dann springe zu L1
je .L2 // Wenn AX = DX, dann springe zu L2
... // Wenn AX < DX, dann weiter im Text
end;
den Prozessor unverhofft ausbremsen, während ein paar nop's zwischen den Sprungentscheidungen L1 und L2 Wunder wirken könnten.
Socke hat geschrieben:Ich habe gelesen, dass der Open64-Compiler wesentlich (30 %) effizienteren Binärcode für die AMD-Bulldozer-Architektur erzeugen kann als z.B. der GCC. Seit dem bezweilfe ich, dass einige Optimierungen überhaupt sinnvoll sind bzw. eigentlich für jede Prozessorarchitektur individuell ausgetestet werden müssen. Sobald man damit jedoch fertig ist, wird die getestete Prozessorarchitektur nicht mehr hergestellt.
Das hat der Teufel gesehen!
Man kann aber auch nicht sagen, daß die Optimierungen wenig wirksam wären. Mir ist da was ziemlich Verrücktes passiert: Ich hatte mich vor Monaten damit beschäftigt, (ShortString-) Compare-Funktionen (die von Sortieralgorithmen exzessiv genutzt werden) zu optimieren (und die Ergebnisse auch
hier eingestellt, seither konnte ich sie nochmals um etwa 10% bzw. 20 % verbessern). Da war es so, daß die Assembler-Varianten phänomenal schnell waren und meine Pascal-Pendants keine Chance hatten, diese zu toppen. Was mich damals nicht verwundert hat, außerdem hat das auch ziemlich Spaß gemacht. Als ich mich jetzt an die (case-sensitiven und -insensitiven) ShortString-Pos-Funktionen gesetzt habe, ist es mir ziemlich mühelos gelungen, eine Pascal-Alternative zu System.Pos zu schreiben, die 25 % (bzw. seit heute früh ca. 36 %...) schneller war als ihr RTL-Gegenstück. Dann habe ich es für X86-64 in Assembler versucht und erwartet, nochmal 10-20 % rausholen zu können. Pustekuchen! Es gelingt mir partout nicht, näher als 10 % (jetzt etwa 20 %) an die vom FPC-Compiler optimierte Pascal-Variante heranzukommen. Einen Teil davon kann ich mir erklären (Übergabe von Parametern in den Registern statt auf dem Stack), aber das kann nur ein kleiner Teil sein. Die Assembler-Version sieht perfekt aus, schlank, trickreich, sparsam, elegant, fehlerfrei - aber sie fetzt nicht. Wahrscheinlich sind es genau solche Konstrukte wie oben, die den Flaschenhals ausmachen. Jedenfalls habe ich die FPC-Optimierung auf diese Weise trotz manchen Stirnrunzelns schätzen gelernt!
Socke hat geschrieben:Es gibt im Bugtracker auch ein Ticket in dem das zufällige Einfügen von 10 % nops diskutiert wird, da dies auf einigen Prozessoren Leistungssteigerungen mit sich bringt.
Ja, das habe ich auch gelesen. Wobei ich mich an dem "
zufällig" störe. Mag sein, daß schon zufällig gestreute nop's was bringen, aber es muß schon mehr System dahinterstecken. Soweit ich das verfolgen konnte, herrscht da immer noch gewaltiges Rätselraten. Es ist aber auch ein verrücktes Zeugs... Und ich bin mir keineswegs sicher, das Ganze auch nur annähernd korrekt verstanden zu haben.
Nochmal kurz zu den No-Operations:
Hier bzw.
hier auf Seite 94 werden zeitsparende Multi-Byte-NOP's beschrieben, mit denen man sich das Alignment nachfolgender Anweisungen von Hand zurechtschieben kann. Ich habe aber noch nicht herausgefunden, wie ich diese Macros/Opcodes in FreePascal umsetzen kann, die Dokumentationen (sowohl FPC-seitig als auch die des GNU Assemblers) geben da nichts her. Ist es möglich, in asm-Blöcke auch reine Opcodes einzufügen (das wäre das Einfachste)? Vielleicht kann mir da jemand weiterhelfen?
Gruß Rüdiger
Verein
Links
