Testprogramm zur prozessorspezifischen X86-Codeoptimierung

[martin_frb]

Die 40 minuten waren uebrigens anders bedingt.

Mein Lazarus fuegt ALLEN Projekten -Criot bei. Na ja, das ist schon langsamer.

[mschnell]

Wo sollte denn da der Nachteil sein?

Weniger Arbeit für Deine Hilfe.

Ein Kommandozeilen-Programm (Windows und/oder Linux) hätte ich gestartet und Dir das ausgegebenen Text geschickt. Dieses Verfahren war mir zu aufwändig.

Ich habe bei weitem nicht auf allen Rechnern, auf denen ich hätte testen können Lazarus installiert.

Dieser Test wird keine unverrückbaren Wahrheiten ergeben,

Doch ein Test testet genau das was er testet.

Deshalb sollte man zunächst ganz exakte Test-Bedingungen schaffen. (Hier exakt dieselben Funktionen mit exakt denselben Daten (die damit auch alle dasselbe Ergebnis liefern) auf verschiedenen Rechnern starten und für jeden Rechner eine Matrix der relativen Ausführungszeiten aller Implementierungen sammeln. Dann kann man vergleichen welche Funktions-Implementierung auf welcher CPU ideal oder besonders schlecht ist und sich dann Gedanken machen, warum das so sein könnte.

Ein "Praxistext" ist weit weniger aussagekräftig, könnte aber zur Kontrolle ob der wissenschaftliche Ansatz nicht vielleicht doch voll daneben gegangen ist (weil die Fragestellung nicht relevant oder die Durchführung nicht umfassend genug war), nachgeschoben werden. Aber ein Praxistest testet nur eine sich zufällig ergebende "Praxis" (=Auswahl von Test-Fällen) und nicht jede.

etwas dazuzulernen.

Ernsthaft "Lernen" kann man nur wenn nachvollziehbare Bedingungen vorliegen. Ein "Praxistext" produziert nur Vorurteile. Das ist durchaus nicht negativ, wir arbeiten ständig sehr erfolgreich mit Vorurteilen. Aber man sollte sich darüber klar sein. Und hier wäre es m.A. einfacher, zunächst einmal einen exakten Test zu machen.

-Michael

[mschnell]

Und das, obwohl diese Sprunganweisung in weniger als 3 % aller Loopdurchläufe überhaupt erreicht wird!

Bedingte Sprünge sind in modernen Prozessor-Architekturen (mit langer Queue) sehr "teuer". Das ist bekannt und deshalb machen Compiler bei entsprechender Oprimierungsstufe ein "loop enrolling". Ich weiß nicht, ob FPC das auch tut.

Die unterschiedlichen "Jump prediction" Strategien der verschiedenen CPU-Architekturen machen sich hier bemerkbar. Das ist zu erwarten. Welcher Chip unter welchen Bedingungen hier besser arbeitet ist wirklich eine interessante Fragestellung. Ein solcher Test müsste relativ viele bedingte Sprünge machen und exakte Bedingungen herstellen, auf die verschiedene Chips unterschiedlich reagieren könnten. Nicht nur das Alignment ist wesentlich, sondern auch die Fragestellung wie oft und entsprechend welcher Statistik eine Verzweigung in eine bestimmte Richtung genommen worden ist, bevor sich ein "stabiler" Vorhersage-Zustand einstellt.

Ich meine gelesen zu haben, dass bestimmte Prozessoren z.B. eine Situation wie "jedes vierte mal wird gesprungen" (oder auch noch komplexer) korrekt vorhersagen können.

-Michael

[Horst_h]

Hallo,

um die Sprungvorhersage auszuschalten mische ich ja den Teststring sMix immer wieder mal.Natürlich hätte man auch vorab eine Liste mit xxx gemischten Strings vorab erstellen können und darüber suchen lassen.XXX passend für Level I Cache, damit es schneller geht.
Meine 40% bezogen sich auf System.pos, wie ruewa es auch macht 100%-40% -> 60 % aka 58%.
Bei mir war keine Assemblerversion so schnell, aber AMD CPU's sind wohl wesentlich empfindlicher.
Ruewa braucht viele verschiedene CPU. i3 und i5 sind sich zu ähnlich, wegen +-1% Unterschied braucht es die lange Liste nicht.Es fehlt jetzt ATOM, FX 8150, Pentium IV und so etwas.
DIe 9407 Dateien sind es bei mir auch die Lazarus 1.2.6 unter Wine32.

Gruß Horst

[ruewa]

Ein Kommandozeilen-Programm (Windows und/oder Linux) hätte ich gestartet und Dir das ausgegebenen Text geschickt. Dieses Verfahren war mir zu aufwändig.

Ich habe bei weitem nicht auf allen Rechnern, auf denen ich hätte testen können Lazarus installiert.

Dann freue ich mich auf Deine Ergebnisfiles von den Rechnern, auf denen Du Lazarus installiert hast! Denn auf denen ist das, von zwei zusätzlichen Mausklicks abgesehen, kein bißchen aufwändiger als ein Kommandozeilenprogramm.

Michael, wenn Du Dir einen solchen Test ausgedacht hättest, hättest Du es anders gemacht, ist doch völlig klar! Jeder hätte das, auf seine Weise. Entwertet das jedwede Aussage, die dieser reale, nicht-ideale Test, so wie er ist, ergeben könnte?

Und wenn es so läuft, wie ich hoffe, und sich aus den gewonnenen Erkenntnisse eine klarere Fragestellung für weitere Nachforschungen ergibt, wäre es ohnehin schön, wenn sich dafür eine Arbeitsgruppe bilden würde. Dann könnte man im Vorhinein das Für und Wider verschiedener Testdesigns diskutieren und sich auf ein gemeinsames Konzept einigen, anstatt im Nachhinein alles zu bekritteln, was ein Einzelner gemacht hat.

Was misst denn der Test, so wie jetzt ist?

1. Er vergleicht Funktionen auf dem jeweiligen Rechner unter exakt gleichen Bedingungen - abgesehen vom Rauschen des Betriebssystems.
2. Er sucht das Rauschen bzw. Störimpulse des Betriebssystems durch Wiederholungen der Tests zu überwachen.
3. Er vergleicht Rechner bzw. CPUs unter statistisch hinreichend ähnlichen Bedingungen (ich glaube nicht, daß exakt gleiche Bedingungen, also ein künstlich geschaffener Datensatz, auch nur an der ersten Prozent-Nachkommastelle etwas ändern würde).
4. Er untersucht die Reaktion verschiedener CPUs auf geringfügige Variationen eines 6-zeiligen Assembler-Codeabschnitts innerhalb eines Loops. Die Amplitude dieser Reaktion liegt im Bereich von 1-2.
5. Er untersucht quer dazu den Einfluß des Alignments auf verschiedene CPUs. Auch hier liegen die Ausschläge bei > 1:1,6.
6. Er erfaßt die CPUs nach Hersteller/Typ/Modell/Stepping und ermöglicht daher ggfls. Zusammenhänge zwischen z.B. Hersteller oder Architektur und Verhalten zu erkennen.
7. Er versucht einen kleinen Ausschnitt der CPU-Charakteristik mit einem großen Signal zu erfassen, anstatt einen großen Bereich mit schwer zu analysierendem Signalsalat.

Unter großem Vorbehalt (denn erstens ist die Datenbasis immer noch viel zu dünn, und zweitens konnte ich die Ergebnisse bisher nur optisch durchsehen) zeichnen sich folgende Tendenzen ab:

1. Es scheint mit einer signifikanten Ausnahme eine deutliche Korrelation zwischen Hersteller und Verhalten zu geben:
   • Die meisten Intel-Prozessoren zeigen dasselbe Verhalten, das ich schon für den Celeron beschrieben habe: Die Variante 3b ist die einzige, die richtig gut funktioniert. Diese Prozessoren reagieren also mit Leistungssteigerungen um größenordnungsmäßig den Faktor 1,8 auf den Austausch einer SUB-Anweisung durch ein DEC. Alle anderen Varianten sind dort großteils langsamer als die (Pascal-) Referenzfunktion System.Pos.
   • AMD-Prozessoren scheinen heftiger auf Alignment-Variationen zu reagieren als Intel-Prozessoren. Alignment spielt bei AMD-Prozessoren also wahrscheinlich eine größere Rolle als bei Intel-CPUs.
   • Die Ausnahme betrifft Intel Core Prozessoren. Die scheinen insgesamt eher unempfindlich auf sowohl Code- wie Alignment-Variationen zu reagieren.
2. Die Variante 3b scheint auf allen CPUs mit die beste Performance zu erreichen. Sie ist damit die Einzige, die auf bislang allen Rechnern gut funktioniert.
   .
3. Es scheint überlagernde Alignment-Effekte zu geben:
   • Intel-Prozessoren oszillieren deutlich, wenn auch nicht dramatisch auf gerade/ungerade Sprungstellen.
   • AMD-Prozessoren zeigen sich davon relativ wenig beeindruckt, mit der signifikanten Ausnahme des leeren Rücksprungs (Version 4a), den einige, aber nicht alle AMD-CPUs ebenfalls zeigen.
   • AMD-CPUs weisen in stärkerem Maß Alignment-Bereiche auf, die signifikant besser laufen. Diese Bereiche sind gleichbedeutend mit der Auftrennung des Loops in verschiedene 16-Byte-Cacheblöcke.
4. Die Streuungen sind insgesamt erfreulich gering, es gibt wenige, klar identifizierbare Ausreißer, die ich bisher allerdings nur unter Windows feststellen konnte.
   .
5. Einige weitverbreitete Lehrmeinungen scheinen auf tönernen Füßen zu stehen und sind es offenbar wert, infrage gestellt zu werden:
   • SUB ist besser als DEC, wenn es um Geschwindigkeit geht.
   • Entscheidungen sollten so angelegt werden, daß sie zumeist verworfen werden.
   • Kompakte Blöcke sind besser als eine Aufteilung zwischen Blöcken.
   • Unkonditionale Sprünge sind besser als konditionale.

Also, Leute, ich kann mir nicht helfen: Wenn sich diese Aussagen bestätigen, dann wird das ein verdammt großer Erkenntnisbrocken für so ein kleines, spontan entstandenes, viel zu "unwissenschaftliches" Testprogramm sein! Der Test wird uns ganz sicher keine Erklärungen dafür liefern, warum es z.B. für eine stattliche Anzahl von Intel-CPUs so entscheidend ist, statt eines SUB ein DEC vorzufinden. Aber wer würde das denn erwarten?

Doch wie gesagt, die Datenbasis ist bislang noch viel zu klein, um belastbare Aussagen treffen zu können.

Deshalb nochmals die Bitte an alle Leser: Macht mit, gebt die Ergebnisse hier herein oder sendet sie mir per Email zu. Und seht Euch das ruhig mal genauer an: Ihr könnt dabei einiges Erstaunliche über Euren eigenen Computer lernen. Keine Bange, wenn Ihr das "nicht versteht": Keiner von uns tut das wirklich...

Und an diejenigen Leser, die es vorziehen, von außen zuzuschauen und sich nicht gerne in einem solchen Forum registrieren: Wenn Ihr gerne mittesten würdet, aber mangels Registrierung nicht an den Download herankommt, sendet mir einfach eine kurze Email, dann schicke ich Euch die zip-Datei: rue/Punkt/walter/ät/web/Punkt/Deh-Ehh...

Gruß Rüdiger

[Dragon]

Hier einmal meine ergebnisse von einem Intel Core 2 Duo E8400 ich hoffe die ergebnisse sind hilfreich

[Horst_h]

Hallo,

die Daten sind ja grauselig ungleichmässig liegt das an 64-Bit??

Code: Alles auswählen

Function CharPos_Asm3b_LoopStart_5
                                             Verified   138.7 ms (125.2 %)  =    61 ns / Call  =    56 ns Loop time / Call
    Run 2                                    Verified   134.3 ms (121.2 %)  =    59 ns / Call  =    54 ns Loop time / Call
    Run 3                                    Verified   88.38 ms ( 79.8 %)  =    39 ns / Call  =    34 ns Loop time / Call
    Run 4                                    Verified   101.7 ms ( 91.8 %)  =..  

Gruß Horst

[Dragon]

die Daten sind ja grauselig ungleichmässig liegt das an 64-Bit??

Das weiß ich leider nicht!

[mschnell]

Leistungssteigerungen um größenordnungsmäßig den Faktor 1,8 auf den Austausch einer SUB-Anweisung durch ein DEC.

Es gibt da auch noch die "loop" Instruktion. Die scheint ideal für solche zwecke. Ich habe aber mal gelesen, dass sie langsamer sein soll als sub/dec plus bedingtem Sprung.

Eigentlich unverständlich, aber anscheinend ist hier ja einiges merkwürdig.

-Michael

[mschnell]

Was misst denn der Test, so wie jetzt ist?

Gar nichts, da das Ergebnis von zufälligen Faktoren abhängt.

(Das heißt nicht, dass man an den Ergebnissen nicht durchaus einige interessante Vermutungen aufstellen kann.)

-Michael

[mschnell]

es gibt wenige, klar identifizierbare Ausreißer, die ich bisher allerdings nur unter Windows feststellen konnte.

Dann kann das ja nichts mit dem Prozessor-Chip zu tun haben, sondern liegt an den unsauber definierten Testbedingungen.

-Michael

[mschnell]

SUB ist besser als DEC, wenn es um Geschwindigkeit geht.

Interessant wäre Loop. Da wird ein Befehl weniger gebraucht.

Entscheidungen sollten so angelegt werden, daß sie zumeist verworfen werden.

Das ist bei oft durchlaufenden Befehlsfolgen bei Jump-Prediction natürlich Unsinn. Bei gcc kann man zur Optimierung "likely" angeben

Kompakte Blöcke sind besser als eine Aufteilung zwischen Blöcken.

Das Gegenteil ist schon erstaunlich, sofern es nicht der Optimierung des Alignments dient

Unkonditionale Sprünge sind besser als konditionale.

Das ist sicher richtig. Bedingte Sprünge sind aber einfach unvermeidbar.

-Michael

[ruewa]

Gar nichts...

Was man halt so als moderner Charakterkopf vom Rest der Welt hält...

es gibt wenige, klar identifizierbare Ausreißer, die ich bisher allerdings nur unter Windows feststellen konnte.

Dann kann das ja nichts mit dem Prozessor-Chip zu tun haben, sondern liegt an den unsauber definierten Testbedingungen.

Da würde ich jetzt am ehesten auf die Existenz eines Betriebssystems tippen. Vielleicht kann Dir das bei Gelegenheit mal jemand genauer erläutern... Im Ernst: Wären Versuche nur unter teutonisch-prinzipienhaftem Ausschluß jedweder Störeinflüsse erlaubt, hätten wir es bis heute noch nicht von den Bäumen herunter geschafft! Als könnte man Störungen, Peaks und Rauschen nicht kontrollieren, Fehlergrößen und Rauschabstände nicht einschätzen. Sorry - aber auf dieser Ballaballa-Ebene diskutiere ich diesen Mist nicht länger! Wenn Du eine profund begründete Fehlerabschätzung vorzubringen hast, dann bring sie bitte vor - aber doch nicht auf diesem vor Verächtlichkeit strotzenden Biertischniveau!

Es gibt da auch noch die "loop" Instruktion. Die scheint ideal für solche zwecke. Ich habe aber mal gelesen, dass ...

Alles längst durchgespielt, Michael. Die Loop-Instruktion eignet sich für bestimmte Fälle, indem sie den Zähler dekrementiert (der in ECX liegen muß, was aber weiter kein Problem ist), dabei aber das Zero-Flag unangetastet läßt und von einer vorherigen Registeroperation durchschleußt. LOOP(N)Z/E wertet also zwei Bedingungen aus: Einmal, ob ECX nach dem dekrementieren Null ist, und zweitens ob das Zero-Flag von der vorherigen Operation her gesetzt ist oder nicht. Wenn beide Abbruch-Bedingungen denselben Weg nehmen, ist LOOPcc möglicherweise das Mittel der Wahl (auf meinem AMD64 ist das so), ansonsten (wenn sie verschiedene Wege nehmen, was bei den CharPos-Funktionen der Fall ist) wird es ineffizient, weil man weitere Verzweigungsentscheidungen nachschieben muß, die man auch gleich hätte durchführen können.

Die reine LOOP-Anweisung ohne Zero-Flag-Auswertung bildet ein ordinäres

Code: Alles auswählen

    decl   %ecx
    jnz    .LoopAnfang               // Jump if Not Zero

nach, was zwar eine Zeile weniger ist, aber intern nicht weniger Aufwand: Es wird eine Operation durchgeführt, und wenn deren Ergebnis vorliegt, wird eine Sprungentscheidung getroffen. Da der LOOP-Befehl zudem jedoch die Flag-Behandlung einerseits ausschalten muß, um die Flags unverändert durchzuleiten, andererseits aber sehr wohl einen Zero-Flag-Ersatz für das Dekrementieren von ECX auswerten muß (vielleicht via Flags kopieren / rückkopieren, wie auch immer), ist damit tatsächlich mehr interner Aufwand verbunden als bei dem Zweizeiler. Deshalb ist das reine LOOP ineffizienter - keineswegs so viel, wie einem die Phalanx erhobener Zeigefinger im Internet einreden möchte, aber doch so in der Größenordnung von gemessenen 4 % (bezogen auf den Zeitbedarf der gesamten Funktion), wenn ich das recht erinnere. Bei dieser CharPos-Funktion macht der Einsatz von LOOP einfach keinen Sinn, bei anderen Funktionen kann er durchaus Sinn machen (dann aber nur in der Variante LOOPcc).

Was Deinen letzten Beitrag angeht: Vielleicht hast Du es nicht bemerkt, aber das waren Zitate urbaner Mythen der Assembler-Programmierung, Lehrbuchweisheiten. Genau die sind es wert, überprüft zu werden (ebenso wie vielleicht später mal die angebliche Ineffizienz von LOOPcc - dort, wo's hinpaßt). Deswegen machen wir das ja, anstatt bloß autoritative Überzeugungen a la "das ist sicher richtig" kundzutun. Und was bitte ist jetzt "wissenschaftlicher": Ein Versuch, der, pffffft, "gar nichts misst", oder Glaubensbekenntnisse wie dieses?

Aber klar - wie Georg Kreisler das einstmals auf den Punkt gebracht hat: "Ändern loßt'se goar nix, weil sonst hätt ma's ja scho gmacht"...

Okay - genug geärgert...

@Dragon:

Deine Listen - vielen Dank! - sind tatsächlich die ersten, die fortlaufend heftige Streuungen aufweisen, bei beiden Datensätzen. Mit 64-bit hat das definitiv nichts zu tun, andere Rechner machen das nicht. Hier sieht es wirklich so aus, was MartinFrb ausgeführt hat, als würde da ein heftiges Cache-Swapping im Hintergrund stattfinden. Ich kann nur ins Blaue hinein spekulieren, was die Ursache dafür sein könnte.

• Laufen / liefen auf dem Rechner Speicher- bzw. CPU-intensive Hintergrundprozesse? Falls ja, könnte man den Test nochmal unter ruhigeren Bedingungen starten.
• Zweite Idee: Du arbeitest mit CodeTyphoon. Hast Du das Programm aus der IDE heraus gestartet? Vielleicht hat deren IDE die Griffel allzu tief im Programm, solange es dort eingebettet läuft. Bei Lazarus macht das keinen Unterschied (da ist bei mir die gesamte Testzeit von ca. 12 Minuten auf die Sekunde genau diesselbe), aber was CT da macht, weiß ich nicht. Du könntest AlignTest also auch nochmal als Executable starten und sehen, ob es dann besser wird (ruhig mit den kleinen Daten).
• Dritte Möglichkeit: Du kannst auch mal tiefer in den Verzeichnisbaum reingehen, bis nur noch ein paar hundert Dateien zum Einlesen übrigbleiben (pi * Daumen 100.000 Strings), und schauen, ob es sich dann beruhigt. Wenn ja, könnte man schrittweise die Daten vergrößern und die Hausnummer feststellen, ab welcher Größe es dann kippt.

Gruß Rüdiger

[mschnell]

Wären Versuche nur unter teutonisch-prinzipienhaftem Ausschluß jedweder Störeinflüsse erlaubt, hätten wir es bis heute noch nicht von den Bäumen herunter geschafft! Als könnte man Störungen, Peaks und Rauschen nicht kontrollieren, Fehlergrößen und Rauschabstände nicht einschätzen.

Ich möchte nur, dass technische Begriffe richtig benutzt werden. "Versuch" ist völlig in Ordnung und natürlich sinnvoll. Er gibt Hinweise, wie man weiter vorgehen kann.

Um das Ergebnis als "Messung" zu kommunizieren, muss die Mess-Anordnung definiert sein. Ergibt die relative Laufzeit-Messung von Schleifen ohne Betriebssystem-Aufrufe unter Windows ein signifikant anderes Ergebnis als unter Linux ist es eben keine Messung und kann nicht zur Beurteilung von Prozessor-Eigenschaften dienen und legt nahe, dass auch bei Ergebnissen ähnlicher Mess-Anordnungen die Störeinflüsse des Betriebssystem (oder was auch immer) so groß sind, dass das Messergebnis eben ein Versuchs-Hinweis ist. Um ein signifikantes Ergebnis einer Messung unter Störeinflüssen zu bestimmen muss die Messanordnung (inklusive statistischer Auswertung) so geartet sein dass der Einfluss der Störfaktoren als klein genug (statistisch "nicht signifikant") bewertet werden kann. Dazu ist es sinnvoll zunächst einmal die Störeinflüsse zu minimieren (möglichst nur genau das messen, was erwartungsgemäß in das Ergebnis einfließt, Zufälle so weit wie möglich ausschließen). Und dann - wenn eine Streuung der Messergebnisse erkannt wird, weil unvermeidbare Störgrößen vorliegen - eine entsprechende Statistik machen (Signifikanz bestimmen).

Trotzdem ist ein "Praxistest" natürlich immer sinnvoll. Erfahrungsgemäß kann sich trotz gründlicher Versuchs-Vorbereitung herausstellen, dass die Messung zwar "sauber" ist, aber etwas anderes misst, was man eigentlich messen wollte.

-Michael

[mschnell]

Okay - genug geärgert...

Hier leider nicht.

Ich finde das Thema sehr interessant und würde mich freuen wenn belastbare (also von Störgrößen wie "Betriebssystem" und "Daten-Lage der von der Loop bearbeiteten Strings") Messergebnisse unabhängige (d.h. statistisch befreite) Messergebnisse sichtbar würden wie verschiedene Prozessor-Chips auf unterschiedliche Programmier-"Stile" ("DEC oder SUB oder Loop(*)", verschieden Alignment-Varianten mit NOPs, ... ) bei Schleifen mit (verschiedenen) vorgegebenen Funktionalitäten (z.B. "CharPos", "CharLength", "Stringcompare", ...) reagieren. Und das am besten sowohl im 32 als auch im 64 Bit Mode.

-Michael (zum Selber-Programmieren einer solchen Diplom-Arbeit leider momentan keine Zeit)

(*) Bei Loop muss die Schleife natürlich entsprechend der Doppel-Abfrage Funktion der Instruktion optimiert geschrieben werden. Dafür ist Loop ja da. Ob das bei modernen Prozessoren ein Vor oder Nachteil ist, ist durchaus fraglich und wäre eben ein interessantes Ergebnis.