Entwickler-Ecke :: Thema anzeigen - Optimierung von Code am Beispiel von SpeculationSort

I.MacLeod - Fr 01.04.05 09: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:

Quelltext

1:

0000 0011

(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:

Quelltext

1:	lea ebx, [b]

Und greifen dann von daraus ausgehend auf A zu: (wobei eax zu beginn -4 ist)

Quelltext

1:	sub ecx, [ebx+eax]

-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 10: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 10: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 10:49

Werde ich gleich mal in eines meiner Programme einbauen, das noch die veralteten - sehr langsamen - Soriteralgorithmen verwendet. :lol:

delfiphan - Fr 01.04.05 11: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 12:10

delfiphan hat folgendes geschrieben:

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 12: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 12: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 12: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 12: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 12: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 12: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 12:52

Ist das nur bei mir so, dass FastCompare doppelt so langsam ist wie Compare?

I.MacLeod - Fr 01.04.05 13:16

Ich schlage euch vor, meine Postings noch einmal genau durchzulesen, dann sollte euch euer Denkfehler klar werden.

uall@ogc - Fr 01.04.05 13:51

und noch was:

anzahl bytes der instruction <> geschwindigkeit:

Quelltext

1:

mov cl, 3

(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

Quelltext

1:	mov reg, mem

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 14: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 14: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 14: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 14: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 14: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 17: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 17: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 14: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 *