Entwickler-Ecke
Delphi Tutorials - Optimierung von Code am Beispiel von SpeculationSort
I.MacLeod - Fr 01.04.05 10:52
Titel: Optimierung von Code am Beispiel von SpeculationSort
Schnelles Sortieren / Optimierung von Code
(Aprilscherz)
In diesem Tutorial werde ich einen schnellen, aber nicht-stabilen Sortieralgorithmus (Speculation-Sort) vorstellen und die Optimierung ebendieses ansatzweise beschreiben. (Eine vollständige Beschreibung wird in den nächsten Monaten in Buchform erscheinen)
Der Algorithmus funktioniert folgendermaßen:
- Es werden Ausgabedaten generiert
- Es wird sichergestellt, dass diese sortiert sind
- Es wird überprüft, ob es sich um eine Permutation der Eingabedaten handelt
Durch diese Vorgehensweise ergeben sich folgende Vorteile:
- Die Sortierung kann bereits beginnen, bevor alle Daten vorhanden sind, solange die Datengröße bekannt ist - egal um welche Daten es sich handelt. (Schritte 1 und 2)
Beim Advanced-Speculation-Sort kann auch der dritte Schritt bereits früher stattfinden, dieser lässt sich aber bisher noch nicht effizient implementieren.
- Auf die Daten muss erst relativ spät zugegriffen werden. Dies lässt dem Prozessor und dem Programmierer Zeit, erweitertes Caching durchzuführen
Hier der Algorithmus als Pseudocode:
Delphi-Quelltext
1: 2: 3:
| repeat Result := CreateOutputData; until Result.Sorted and Result.IsPermutationOf(Input); |
Offensichtlich wird erst im letzten Schritt auf die Daten zugegriffen.
Zur Optimierung werden wir folgende Techniken einsetzen:
- Stack-Shadowing:
Dank Stack-Shadowing kann teilweise auf den Zugriff auf eine oder mehrere Variablen verzichtet werden. Dies kann über 50% Geschwindigkeitsunterschied ausmachen. (Laut Borland soll dies in folgenden Delphiversionen automatisch vom Compiler unterstützt werden. Da dies allerdings nur für Delphi-Code gilt, lohnt es sich trotzdem die Funktionsweise zu verstehen, um den eigenen Assembler-Code optimieren zu können)
- Constant-Splitting:
Der Einsatz von Constant-Splitting hat nur indirekt einen Performance-Grund, da es hier viel mehr um die größe der Anwendung geht. Dazu eine Beispiel:
Es soll die Konstante "3" in das Register cl geschrieben werden. Das Register ist ein 8-Bit Register, demnach muss auch die Konstante in 8 Bits vorliegen:
(Leerzeichen zur besseren Lesbarkeit eingefügt)
Da der Computer im Binärmodus arbeitet, werden für die Darstellung dieser Konstante also 8 Bytes benötigt. (Der Delphi-Compiler beherrscht Constant-Splitting bereits seit Version 3, in Assembler-Bereichen muss sich der Programmierer jedoch selbst darum kümmern.)
Constant-Splitting setzt hier an:
- Es werden nur die Bits gespeichert, die auch wirklich benötigt werden. (In diesem Fall also die letzten beiden)
- Konstanten werden so umgeformt, dass sie durch andere Instruktionen dargestellt werden können. Dies hat sowohl Vorteile bei der Geschwindigkeit als auch bei der Größe des Codes.
Beispiel:
Um die Codegröße drastisch zu verringern, wird der Befehl
Quelltext
1:
| mov cl, 3 (9 bytes Daten (opcode + 8 bytes für die Darstellung der Zahl "3") |
per (in diesem Beispiel nur einfachem) Constant-Splitting umgewandelt:
Quelltext
1: 2: 3: 4:
| xor cl, cl (2 bytes) inc cl (2 bytes) shl cl, cl (2 bytes) inc cl (2 bytes) |
Wie zu erkennen ist, haben wir die Codegröße um 1 byte verringert. Mit erweiterten Splitting-Techniken lassen sich auch Verringerungen von 4 oder mehr Bytes erzielen, was jedoch den Umfang dieses Tutorials sprengen würde. (Ein generell guter Tipp ist, beim Constant-Splitting auch von bereits vorhandenen Daten auszugehen)
Des weiteren ist der Erfolg des Splittings bei größeren Konsanten oft sehr viel größer.
Hinweis: Auf modernen Prozessoren der 64er-Generation kann man mit Constant-Splitting nur noch weniger starke Erfolge erzielen, da diese 6bit (=64) als Basis verwenden. Dennoch ist es empfehlenswert, da Konsantenin der RISC/CISC-Architektur generell langsamer geladen werden, als einfacher Code)
- Variable-Switching:
Diese Technik ist schwer kurz zu erklären. Sie basiert im Prinzip darauf, im Code Referenzen auf Variablen so anzuordnen, dass sie in anderen Teilen leicht ausgetauscht werden. Dies wird im folgenden Beispiel deutlich.
(Auch dies soll in folgenden Compiler-Versionen unterstützt werden)
Ich werde jetzt nur auf eine Funktion zum schnellen Vergleichen von zwei Werten unter Berücksichtigung der oberen Techniken (mit Ausnahme von Constant-Splitting, das würde dieses Tutorial zu stark aufblähen) eingehen.
Beginnen wir mit der Grundfunktion:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9:
| function Compare(a, b: DWORD): integer; stdcall; begin if a < b then result := 1 else if a > b then result := -1 else result := 0; end; |
Wir haben insgesamt 2 Vergleiche und 4 Zugriffe auf Variablen (und somit den Stack!). Offensichtlich nicht sehr schnell. Da Delphi kein Stack-Shadowing unterstützt, müssen wir also schon zu Assembler wechseln, um den ersten Teil zu implementieren. Um Stack-Shadowing durchzuführen, laden wir zunächst B:
Und greifen dann von daraus ausgehend auf A zu: (wobei eax zu beginn -4 ist)
-4 wurde hier in eax ausgelagert, um Variable-Switching zu ermöglichen. Beim Variable-Switching werden ebx und eax so verändert, dass ebx auf A zeigt, und ebx+eax auf B - ein klarer Vorteil.
Quelltext
1: 2:
| add eax, 8 sub ebx, eax |
In SpeculationSort wurden die Geschwindigkeitskritischen Teile mit den oben genannten Methoden optimiert. Anhand dieser Erklärung sollte der Code aber leicht verständlich sein.
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123: 124: 125: 126: 127: 128: 129: 130: 131: 132: 133: 134: 135: 136: 137: 138: 139: 140: 141: 142: 143:
| type TByteArray = array of byte;
function FastCompare(a, b: dword): integer; stdcall; asm push ebx push edx push ecx lea ebx, [b] mov eax, -4 mov edx, -1 @@loop: mov ecx, [ebx] sub ecx, [ebx+eax] cmovc ecx, edx cmp ecx, edx je @@end add eax, 8 sub ebx, eax add edx, 2 cmp eax, 12 jne @@loop @@end: mov eax, ecx pop ecx pop edx pop ebx end;
function SpeculationSort(var input: TByteArray): TByteArray; var count, i: integer; invalidresult: boolean; LUT: array[0..511] of integer; begin count := Length(input); SetLength(result, count); asm push eax push ecx push ebx push edx lea eax, LUT xor ecx, ecx xor dl, dl inc cl lea ebx, [ecx] shl cl, cl shl cl, cl lea ecx, [ecx + ebx] shl ebx, cl shr ecx, cl mov edx, ecx @@1: test ebx, ebx jz @@2 dec ebx mov [eax+ecx], edx inc dl lea edx, [edx + edx] imul edx, edx add ecx, edx xor dl, dl jmp @@1 @@2: xchg cl, ch inc bl mov edx, [input] mov edx, [edx] shl ebx, cl xor ch, ch inc ch xchg cl, ch inc cl shr ch, cl xchg ch, cl shl ebx, cl mov ecx, count lea ebx, [eax + ebx] xor eax, eax @@3: test ecx, ecx jz @@4 dec ecx push cx mov al, byte ptr [edx+ecx] xor cx, cx inc ecx shl cx, cl shl ax, cl inc [ebx + eax] pop cx xor ah, ah jmp @@3 @@4: pop edx pop ebx pop ecx pop eax mov invalidresult, 1 end;
while invalidresult do begin asm mov invalidresult, 0 push eax push edx push ecx mov edx, [result] mov edx, [edx] mov ecx, count @@6: test ecx, ecx jz @@7 dec ecx mov eax, $100 mov byte ptr [edx + ecx], 0 jmp @@6 @@7: pop ecx pop edx pop eax end;
result[0] := random(256); for i := 1 to count-1 do begin result[i] := random(256); if FastCompare(result[i], result[i-1]) > 0 then begin invalidresult := true; break; end; end;
if not invalidresult then begin for i := 0 to 255 do LUT[i] := 0; for i := 0 to count - 1 do inc(LUT[result[i]]); for i := 0 to 255 do if LUT[i] <> LUT[i+256] then begin invalidresult := true; break; end; end; end end; |
Ich hoffe ich konnte durch dieses kurze Tutorial einige neuartige Methoden zur Optimierung von Code etwas näherbringen.
Wahrscheinlich haben sich ein paar kleine Fehler eingeschlichen, dafür entschuldige ich mich :mrgreen:. Leider ist heute der einzige Tag in der nächsten Zeit an dem es mir möglich ist ein derartiges Tutorial zu veröffentlichen, was natürlich zu Zeitdruck geführt hat.)
Moderiert von Motzi: Aprilscherz-Hinweis hinzugefügt.
MrSaint - Fr 01.04.05 11:22
Titel: Re: Optimierung von Code am Beispiel von SpeculationSort
I.MacLeod hat folgendes geschrieben: |
Leider ist heute der einzige Tag in der nächsten Zeit an dem es mir möglich ist ein derartiges Tutorial zu veröffentlichen, was natürlich zu Zeitdruck geführt hat.) |
:lol:
EDIT:
Wenn man sich das durchliest kringelt man sich, echt super :!: :rofl:
opfer.der.genauigkeit - Fr 01.04.05 11:38
Feine Sache, sieht gut aus das Tutorial. :twisted:
//Edit: Da ich leider keineswegs fit in Assembler bin, kann ich das Tut nicht auf Richtigkeit prüfen. N Aprilscherz ist das aber nicht oder? :mrgreen:
fvolk - Fr 01.04.05 11:49
Werde ich gleich mal in eines meiner Programme einbauen, das noch die veralteten - sehr langsamen - Soriteralgorithmen verwendet. :lol:
delfiphan - Fr 01.04.05 12:57
Der Text über die Optimierung mag gut sein, aber das Speculationsort... Kann mir echt nicht vorstellen, dass das was taugt. Die Hälfte ist zwar Assembler, aber mal ehrlich: Dein FastCompare ist eine sehr, sehr ineffiziente Art, um herauszufinden ob a grösser als b ist.
Vor allem brauchst du ja nicht das Vorzeichen, sondern willst lediglich wissen, ob der einte Wert grösser als der andere ist. Da reicht ein einfaches "b-a" (>0 falls b grösser, <0 falls a grösser und =0 falls gleich). Und überhaupt: Dein FastCompare(result[i], result[i-1]) > 0 ist äquivalent zu result[i-1]) > result[i]. Das zweitere ist wohl zig mal schneller.
Respect, aber so wie es jetzt implementiert ist, ist das ganze wohl mehr oder weniger unbrauchbar.
I.MacLeod - Fr 01.04.05 13:10
delfiphan hat folgendes geschrieben: |
Der Text über die Optimierung mag gut sein, aber das Speculationsort... Kann mir echt nicht vorstellen, dass das was taugt. Die Hälfte ist zwar Assembler, aber mal ehrlich: Dein FastCompare ist eine sehr, sehr ineffiziente Art, um herauszufinden ob a grösser als b ist.
...
Und überhaupt: Dein FastCompare(result[i], result[i-1]) > 0 ist äquivalent zu result[i-1]) > result[i]. Das zweitere ist wohl zig mal schneller. |
Hier was der Delphi-Compiler aus result[i-1] < result[i] macht:
Quelltext
1: 2: 3: 4: 5:
| mov eax, [edi] mov al, [eax+ebx] mov edx, [edi] cmp al, [edx+ebx-$01] jnb +$09 |
Offensichtlich werden weder Variable-Switching noch Stack-Shadowing verwendet. Das führt - kombiniert mit dem nötigen Overhead durch die Änderung der Register eax und edx - zu einem enormen Geschwindigkeitsverlust. FastCompare ist optimal auf die x86-Architektur angepasst und kann eben durch die oben genannten Methoden die 1. Arithmetik-Pipeline und die RISC-Integer-Laufzeitoptimierung des Prozessors voll ausnutzen. Einzig schneller wäre vielleicht noch LSort oder nWay-Mergesort, die machen aber nur für einige Spezialfälle wirklich Sinn. (Die werd ich vielleicht nächstes Jahr mal genauer unter die Lupe nehmen, wenn ich endlich wieder Zeit hab.)
delfiphan - Fr 01.04.05 13:19
Ein Vergleich Speculationsort vs. Quicksort bei einer nicht-sortierten Array wär mal was, wenn jemand Zeit dafür hat.
uall@ogc - Fr 01.04.05 13:24
ausserdem benutzt du nicht alle register, z.b. kannst ja zusätzlich noch esi oder ebp benuutzen und warum ist FastCompare ne stdcall fuktion, variablen über register übergeben geht viel schneller und das du beim fastcompare alle register pushed ist auch nicht unbedingt notwendig, nur die aufn stack ablegen die in der funktion die diese aufruft danach noch gebraucht werden.
delfiphan - Fr 01.04.05 13:27
Vor allem wär der Functioncall auch unnötig. Vielleicht kannst du mir ja das erklären:
Test1: 400ms
Test2: 90ms
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43:
| Procedure Test1; Var I, J : Integer; A : Array[0..1] of DWOrd; begin a[0] := 1; a[1] := 0; For I := 0 to 10000000 do if FastCompare(a[0],a[1])>0 then asm nop end; a[0] := 0; a[1] := 1; For I := 0 to 10000000 do if FastCompare(a[0],a[1])>0 then asm nop end; a[0] := 0; a[1] := 0; For I := 0 to 10000000 do if FastCompare(a[0],a[1])>0 then asm nop end; end;
Procedure Test2; Var I, J : Integer; A : Array[0..1] of DWOrd; begin a[0] := 1; a[1] := 0; For I := 0 to 10000000 do if a[0]>a[1] then asm nop end; a[0] := 0; a[1] := 1; For I := 0 to 10000000 do if a[0]>a[1] then asm nop end; a[0] := 0; a[1] := 0; For I := 0 to 10000000 do if a[0]>a[1] then asm nop end; end; |
I.MacLeod - Fr 01.04.05 13:29
Im Anhang eine Statistik die ich im Rahmen meiner Untersuchungen erstellt habe.
StackShadowing ist aufgrund der zugrundeliegenden Theorie nur mit StdCall-Funktionen verwendbar. StackShadowing erreicht dabei allerdings wesentlich bessere Performance beim Zugriff auf den Stack als normale Registeroperationen.
EDIT:
Deine Ergebnisse sind sehr interessant. Was für einen Prozessor verwendest du?
delfiphan - Fr 01.04.05 13:37
Einheiten in der Graphik?
PS: Hast du denn Quicksort an einer bereits sortierten Liste durchgeführt (evtl. weil du es mehrere Male hintereinander ausgeführt hast)? Bei Quicksort tritt der Worst-Case ein, wenn die Liste bereits sortiert ist (wenn ich mich nicht täusche). Du solltest auch die genaue Testumgebung angeben, zwei Zahlen alleine sagen so gut wie nichts.
I.MacLeod - Fr 01.04.05 13:47
Die Einheiten sind wie oben bereits erwähnt von der 1. Arithmetik-Pipeline (AP) und der RISC-Integer-Laufzeitoptimierung (RIL) abhängig, dafür bräuchte ich also deinen genauen Prozessortyp. (Informationen über Leckströme, Integrationsdichte und Seriennummer wären auch hilfreich)
Die Arrays bestanden natürlich bei jedem Test aus Datenquellen mit echtem Zufall. (Aufnahme einer Schafherde aus Nordirland)
Spaceguide - Fr 01.04.05 13:52
Ist das nur bei mir so, dass FastCompare doppelt so langsam ist wie Compare?
I.MacLeod - Fr 01.04.05 14:16
Ich schlage euch vor, meine Postings noch einmal genau durchzulesen, dann sollte euch euer Denkfehler klar werden.
uall@ogc - Fr 01.04.05 14:51
und noch was:
anzahl bytes der instruction <> geschwindigkeit:
(besteht übrigens nicht 9 byte sondern 2 (B1 03))
nen
Quelltext
1: 2: 3: 4:
| xor cl, cl (2 bytes) inc cl (2 bytes) shl cl, cl (2 bytes) inc cl (2 bytes) |
wie gesagt 8 bytes
es sind aber die taktzyklen entscheidend für die geschwindigkeit
http://homepages.compuserve.de/fmatth01/8086Assembler/Asm.htm
laut der tabelle braucht nen
genau 8 zyklen
Quelltext
1: 2: 3: 4:
| xor cl, cl (3 zyklen) inc cl (3 zyklen) shl cl, cl (8 +4 pro bit zyklen) (nen shl cl, 1) wäre sogar schneller mit 2 zyklen inc cl (3 zyklen) |
also bestenfalls 11 zyklen, somit ist das direkte schreiben ins register immer noch schneller
(übrigens kannste mit so nem April scherz tutorial wirklich noch leute durcheinander bringen die das jetzt wirklich machen, hoffe ich hab wenigstens bisl erklärt wie man wirklich testet wie schnell etwas ist)
retnyg - Fr 01.04.05 15:34
I.MacLeod hat folgendes geschrieben: |
Die Einheiten sind wie oben bereits erwähnt von der 1. Arithmetik-Pipeline (AP) und der RISC-Integer-Laufzeitoptimierung (RIL) abhängig, dafür bräuchte ich also deinen genauen Prozessortyp. |
schön, dass du deinen code für RISC prozessoren optimierst. da freuen sich vielleicht die user von Macs oder Sun-Systemen, aber keine delphi-programmierer, die in der regel eine x86 cpu verwenden.
I.MacLeod - Fr 01.04.05 15:40
Schön, dass du weißt dass heutige CISC-Prozessoren alle einen RISC-Kern haben.
Schön, dass dir die Abkürzungen aufgefallen sind.
@uall: Na endlich, ich dachte ich müsste mir noch mehr Blödsinn einfallen lassen... :mrgreen:
retnyg - Fr 01.04.05 15:44
I.MacLeod hat folgendes geschrieben: |
Schön, dass du weißt dass heutige CISC-Prozessoren alle einen RISC-Kern haben.
Schön, dass dir die Abkürzungen aufgefallen sind. |
ich habe mir das alles nicht im detail durchgelesen, aber es würde zu dem unsinn passen den du sonst postet. deine aprilscherze kannst du woanders treiben aber nicht im tutorial-bereich.
uall@ogc - Fr 01.04.05 15:48
ganz so extrem würd ichs net sagen, aber ich hasse auch aprilscherze die zum nachahmen aufrufen...
was wenn jemand behauptet man kann strom sparen indem man nen schraubenzieher in die steckdoste steckt, will nicht iwssen wieviele so blöde sind und das testen oO
da finde ich die scherze wo nur etwas behauptet wird (delphi 2006, dvdplayer zum aufnehmen etc.) besser da denkt man sich nur cool will ich haben oder so...
I.MacLeod - Fr 01.04.05 15:56
retnyg hat folgendes geschrieben: |
..., aber es würde zu dem unsinn passen den du sonst postet. deine aprilscherze kannst du woanders treiben aber nicht im tutorial-bereich. |
es wird OT... Warten wir mal einfach ab was ein Mod/Admin dazu sagt (gelöscht/verschoben wird es ja so oder so). Und was ich angeblich "sonst" für Unsinn poste kann ich auch nicht ganz nachvollziehen. (Du kannst mir auch gerne per PM Antworten)
@uall: nja, ehrlich gesagt hätte ich nicht wirklich damit gerechnet dass jemand so einen Blödsinn ernst nehmen könnte. Außerdem waren meine Formulierungen schwammig genug, damit man selbst Ahnung von Assembler haben müsste, um überhaupt in der Lage zu sein das nachzuahmen. Und wenn man Ahnung davon hat, macht man es nicht nach, weil es offensichtlich Schwachsinn ist. :mrgreen:
delfiphan - Fr 01.04.05 18:00
Ich finde es ein wenig undankbar - ich geb mir Mühe eine Antwort zu schreiben. Ich mein, einige Behauptungen von dir waren auch völlig korrekt.
In einem Forum, wo man viele "schlecht programmierte" Sachen sieht, sollte man vielleicht nicht als Scherz einen schlecht programmierten Algorithmus posten. Etwas unoriginell; aber wenn's dich befriedigt, dann konnte ich dir ja wenigstens ein bisschen Freude machen.
*gähn
wdbee - Fr 01.04.05 18:10
Man kann es halt nicht allen recht machen. An anderer Stelle im Forum haben sich viel beklagt, das es keine wirklich originellen Aprilscherze mehr gäbe, alles sei so offensichtlich. Nun macht sich einer die Mühe und erfindet etwas so gut, dass man tatsächlich zweimal hinsehen muss, und nun ist es auch nicht allen recht.
Mir hat es gefallen, weil es mehr Niveau hat, als so maches andere, was hier so rumgeistert!
Danke an alle Beteiligten für diesen schönen Beitrag.
Motzi - Sa 02.04.05 15:59
Also ich hab ihn auch nicht schlecht gefunden..! Für mich war nicht von Anfang an ganz offensichtlich, dass es ein Aprilscherz war. Ich hab zwar nicht daran geglaubt, dass hier wirklich jemand den ultimativen neuen Sortieralgo vorstellt, aber ich war mir nicht ganz sicher, ob das wirklich ernst gemeint ist, oder I.MacLeod uns doch nur alle auf den Arm nehmen will! ;) Und @uall@ogc - mal ernsthaft, selbst wenn das jemand ausprobiert, was sollte er dadurch für einen Schaden nehmen? Außer höchstens sein Ego, wenn er merkt, dass er nach allen Regeln der Kunst reingelegt wurde..! ;)
Da aber der erste April inzwischen vorbei ist und um weitere Diskussionen über guten/schlechten Aprilscherz vorzubeugen mach ich hier mal dicht. Weitere persönliche Probleme (@retnyg und I.MacLeod) bitte per PN zu klären!
Gruß, Motzi
* C L O S E D *
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!