Quicksort in ASM

Fiete · Beiträge: 617 Erhaltene Danke: 364 W7 Delphi 6 pro

Die Quicksortprocedure hab ich in Assembler umgesetzt, die fünf lokalen Variablen ließen sich gut mit dem Stack verarbeiten. Der Geschwindigkeitszuwachs hält sich in Grenzen

alte Prozedur

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

PROCEDURE QuickSort(VON,BIS:INTEGER);
  VAR I,J,M:Integer;
  BEGIN
   I:=VON;J:=BIS;M:=LISTE[(I+J) DIV 2];
   WHILE I<J DO
    BEGIN
     WHILE LISTE[I]<M DO INC(I);
     WHILE M<LISTE[J] DO DEC(J);
     IF I<=J THEN BEGIN Tausch(LISTE[I],LISTE[J]);INC(I);DEC(J) END
    END;
   IF I<BIS THEN QUICKSORT(I,BIS);
   IF VON<J THEN QUICKSORT(VON,J)
  END;

neue Prozedur

markieren

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:

PROCEDURE AsmQuickSort(VON,BIS:INTEGER);
  BEGIN
   ASM                  // EDI - I   EBP - VON   ESI - J   ECX - BIS   EDX - M
         PUSHAD                         // alle Register auf den Stapel
         MOV EDI,VON                    // EDI:=VON
         MOV ESI,BIS                    // ESI:=BIS
         MOV EBP,EDI                    // EBP:=EDI
         MOV ECX,ESI                    // ECX:=ESI
         CALL @QUICK                    // Prozedur QUICK aufrufen
         JMP @ENDE                      // springe zu @ENDE
@QUICK:  MOV EDI,EBP                    // EDI:=EBP
         MOV ESI,ECX                    // ESI:=ECX
         MOV EBX,EDI                    // EBX:=EDI
         ADD EBX,ESI                    // EBX:=EBX+ESI
         SHR EBX,1                      // (J+I) DIV 2
         SHL EBX,2                      // EBX:=EBX*4 wegen Datentyp Integer
         MOV EDX,[Offset[Liste-4+EBX]]  // M:=LISTE[(I+J) DIV 2]
@ANFANG: CMP EDI,ESI                    // I>=J
         JGE @UNTEN                     // falls ja zu @UNTEN
         MOV EBX,EDI                    // EBX:=EDI
         SHL EBX,2                      // EBX:=EBX*4 wegen Datentyp Integer
@WHILE1: MOV EAX,[Offset[Liste-4+EBX]]  // EAX:=LISTE[I]
         CMP EAX,EDX                    // LISTE[I]>=M
         JGE @WHILWE                    // falls ja zu @WHILE2
         INC EDI                        // INC(I)
         ADD EBX,4                      // EBX:=EBX+4 nächste Listenelement
         JMP @WHILE1                    // springe zu @WHILE1
@WHILWE: MOV EBX,ESI                    // EBX:=ESI
         SHL EBX,2                      // EBX:=EBX*4 wegen Datentyp Integer
@WHILE2: MOV EAX,[Offset[Liste-4+EBX]]  // EAX:=LISTE[J]
         CMP EDX,EAX                    // M>=LISTE[J]
         JGE @SWAP                      // falls ja zu @SWAP
         DEC ESI                        // DEC(J)
         SUB EBX,4                      // EBX:=EBX-4 vorherige Listenelement
         JMP @WHILE2                    // springe zu @WHILE2
@SWAP:   CMP EDI,ESI                    // I>J
         JG @UNTEN                      // falls ja zu @UNTEN
         MOV EBX,EDI                    // EBX:=EDI
         SHL EBX,2                      // EBX:=EBX*4 wegen Datentyp Integer
         MOV EBX,[Offset[Liste-4+EBX]]  // EBX:=LISTE[I]                  
         PUSH EBX                       // EBX auf den Stapel
         MOV EBX,EDI                    // EBX:=I
         SHL EBX,2                      // EBX:=EBX*4 wegen Datentyp Integer
         MOV [Offset[Liste-4+EBX]],EAX  // LISTE[I]:=LISTE[J]
         POP EAX                        // EAX:=LISTE[I]
         MOV EBX,ESI                    // EBX:=J
         SHL EBX,2                      // EBX:=EBX*4 wegen Datentyp Integer
         MOV [Offset[Liste-4+EBX]],EAX  // LISTE[J]:=LISTE[I]
         INC EDI                        // INC(I)
         DEC ESI                        // DEC(J)
         JMP @ANFANG                    // springe zu @ANFANG
@UNTEN:  CMP EDI,ECX                    // I>=BIS
         JGE @WEITER                    // falls ja zu @WEITER
         PUSH EDI                       // lokale Variable I auf den Stapel
         PUSH ESI                       // lokale Variable J auf den Stapel
         PUSH EBP                       // lokale Variable VON auf den Stapel
         PUSH ECX                       // lokale Variable BIS auf den Stapel
         MOV EBP,EDI                    // VON:=I
         CALL @QUICK                    // Prozedur QUICK aufrufen
         POP ECX                        // lokale Variable BIS vom den Stapel
         POP EBP                        // lokale Variable VON vom den Stapel
         POP ESI                        // lokale Variable J vom den Stapel
         POP EDI                        // lokale Variable I vom den Stapel
@WEITER: CMP EBP,ESI                    // VON>=J
         JGE @PROCEND                   // falls ja zu @PROCEND
         PUSH EDI                       // lokale Variable I auf den Stapel
         PUSH ESI                       // lokale Variable J auf den Stapel
         PUSH EBP                       // lokale Variable VON auf den Stapel
         PUSH ECX                       // lokale Variable BIS auf den Stapel
         MOV ECX,ESI                    // BIS:=J
         CALL @QUICK                    // Prozedur QUICK aufrufen
         POP ECX                        // lokale Variable BIS vom den Stapel
         POP EBP                        // lokale Variable VON vom den Stapel
         POP ESI                        // lokale Variable J vom den Stapel
         POP EDI                        // lokale Variable I vom den Stapel
@PROCEND:RET                            // Prozedur QUICK beenden
@ENDE:   POPAD                          // alle Register restaurieren
   End
  END;

Viel Spaß beim studieren
Gruß Fiete

Einloggen, um Attachments anzusehen!

_________________
Fietes Gesetz: use your brain (THINK)

BenBE · Verfasst: Mo 20.06.11 11:24

Du kannst deine SHL EBX,2 gefolgt von nem Displacement durch

markieren

Delphi-Quelltext

1:
2:
3:

asm
    MOV [Liste-4+4*EBX],Wert
end;

ersetzen. Außerdem kannst Du das begin/end der Methode an sich weg lassen, wenn Du die Stack-Behandlung eh selber machst. Das spart auch noch mal zyklen.

Deine Stack-Frames sind übrigens absolut unsauber. Pfui! Außerdem: So viel, wie Du auf dem Stack rumwurschtelst, ist das absolut klar, dass das nicht schneller wird ;-)

Außerdem gibt's zum Tauschen von Speicherzellen mit Register ne Anweisung XCHG, die recht gut funktioniert, wenn Du das inline machen willst.

Insgesamt ist da also noch einiges zu verbessern; hab leider nur grad wenig Zeit für's Optimieren.

Und Edith meint, du solltest nicht mit den Offsets arbeiten (SUB EBX, 4), sondern die Indizes nutzen und die Displacements dann entsprechend Multiplizieren; das macht die CPU dann nämlich intern und brauch keinen zusätzlichen Zyklus.

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

herr-master · Beiträge: 34

Hm allso ich hab mir das mal im debugger angeschaut du solltest es veleicht so lösen.

markieren

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:

procedure QuickSort(VON,BIS:INTEGER);assembler;
asm
PUSHAD
push ebp
mov ebp,esp
add esp,-$14 
mov [ebp-$08],edx 
mov [ebp-$04],eax 
mov eax,[ebp-$04]
mov [ebp-$0c],eax
mov eax,[ebp-$08]
mov eax,[ebp-$0c]
add eax,[ebp-$10]
jno label
call @label
sar eax,1
jns label
adc eax,$00
dec eax
cmp eax,$05f5e0fe
jbe label
call @BoundErr
inc eax
mov eax,[eax*4+$4cc2a4]
mov [ebp-$14],eax
POPAD
end;

Das ist nur ein teil des optiermierten codes.
Da mir der code sonst zu lang wird und ich nicht genau weiß wieviel zeilen man hier zu verfügung hat zum schreiben.

jaenicke · Verfasst: Mo 27.06.11 17:35

herr-master hat folgendes geschrieben :

und ich nicht genau weiß wieviel zeilen man hier zu verfügung hat zum schreiben.

Genügend, keine Sorge, es wurden auch schon deutlich längere komplette Units gepostet. Außerdem kannst du sehr lange Quelltexte auch anhängen ;-)

Horst_H · Verfasst: Di 28.06.11 08:46

Hallo,

was ist wo optimiert?
EAX wird "von" sein und EDX ist dann "bis"

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:

mov ebp,esp
add esp,-$14      // Schaffe Platz für 20 byte oder 5 LongInt-Werte mit ebp als Zeiger auf die erste Stelle 0
mov [ebp-$08],edx // Speichere "bis"
mov [ebp-$04],eax // Speichere "von"
mov eax,[ebp-$04] // Lade "von" in Register EAX, das schon mit "von" belegt ist
mov [ebp-$0c],eax // Speichere es noch woanders
mov eax,[ebp-$08] // Lade EAX mit "bis" was aber schon in EDX ist
mov eax,[ebp-$0c] // Lade EAX mit dem Wert "von" siehe 2 Zeilen zuvor, wozu wurde vorher "bis" geladen 
add eax,[ebp-$10] // Was steht in [ebp-$10], ist doch nicht belegt.

Es wird statisch gegen $05f5e0fe = 99999998 verglichen, was irgendwie merkwürdig ist für etwas universelles.
Da fehlt wo Label steht, es sieht nach einer procedure außerhalb aus.
Es ist zuwenig Code um etwas damit anfangen zu können.

Gruß Horst

Delphi-Laie · Verfasst: Di 28.06.11 18:01

Fiete hat folgendes geschrieben :

Die Quicksortprocedure hab ich in Assembler umgesetzt, die fünf lokalen Variablen ließen sich gut mit dem Stack verarbeiten. Der Geschwindigkeitszuwachs hält sich in Grenzen

Das ist zwangsläufig, denn Quicksort gehört bereits zu den (asymptotisch) optimalen Sortieralgorithmen. Mithin kann auch eine Assemblerimplementierung keinen nennenswerten Geschwindigkeitsvorteil mehr bewirken. Nichtdestoweniger ist eine solche Mühe bemerkens- und lobenswert.

Für welchen Datentyp und welche Datenmenge ist Dein Algorithmus möglich? Ich sehe in der Menge der zu übergebenden Variablen nur zwei Integer. Wie wird die eigentliche, nämlich die zu sortierende Datenmenge übergeben oder sonstwie adressiert?

herr-master · Beiträge: 34

Hier ist der gesammte code:

markieren

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:

Arraytest.pas.62: BEGIN
004BDC14 55               push ebp
004BDC15 8BEC             mov ebp,esp
004BDC17 83C4EC           add esp,-$14
004BDC1A 8955F8           mov [ebp-$08],edx
004BDC1D 8945FC           mov [ebp-$04],eax
Arraytest.pas.63: I:=VON;
004BDC20 8B45FC           mov eax,[ebp-$04]
004BDC23 8945F4           mov [ebp-$0c],eax
Arraytest.pas.64: J:=BIS;
004BDC26 8B45F8           mov eax,[ebp-$08]
004BDC29 8945F0           mov [ebp-$10],eax
Arraytest.pas.65: M:=LISTE[(I+J) DIV 2];
004BDC2C 8B45F4           mov eax,[ebp-$0c]
004BDC2F 0345F0           add eax,[ebp-$10]
004BDC32 7105             jno $004bdc39
004BDC34 E85771F4FF       call @IntOver
004BDC39 D1F8             sar eax,1
004BDC3B 7903             jns $004bdc40
004BDC3D 83D000           adc eax,$00
004BDC40 48               dec eax
004BDC41 3DFEE0F505       cmp eax,$05f5e0fe
004BDC46 7605             jbe $004bdc4d
004BDC48 E83B71F4FF       call @BoundErr
004BDC4D 40               inc eax
004BDC4E 8B0485A4C24C00   mov eax,[eax*4+$4cc2a4]
004BDC55 8945EC           mov [ebp-$14],eax
Arraytest.pas.66: WHILE I<J DO
004BDC58 8B45F4           mov eax,[ebp-$0c]
004BDC5B 3B45F0           cmp eax,[ebp-$10]
004BDC5E 0F8DB3000000     jnl $004bdd17
004BDC64 EB0B             jmp $004bdc71
Arraytest.pas.68: WHILE LISTE[I]<M DO INC(I);
004BDC66 8345F401         add dword ptr [ebp-$0c],$01
004BDC6A 7105             jno $004bdc71
004BDC6C E81F71F4FF       call @IntOver
004BDC71 8B45F4           mov eax,[ebp-$0c]
004BDC74 48               dec eax
004BDC75 3DFEE0F505       cmp eax,$05f5e0fe
004BDC7A 7605             jbe $004bdc81
004BDC7C E80771F4FF       call @BoundErr
004BDC81 40               inc eax
004BDC82 8B0485A4C24C00   mov eax,[eax*4+$4cc2a4]
004BDC89 3B45EC           cmp eax,[ebp-$14]
004BDC8C 7CD8             jl $004bdc66
004BDC8E EB0B             jmp $004bdc9b
Arraytest.pas.69: WHILE M<LISTE[J] DO DEC(J);
004BDC90 836DF001         sub dword ptr [ebp-$10],$01
004BDC94 7105             jno $004bdc9b
004BDC96 E8F570F4FF       call @IntOver
004BDC9B 8B45F0           mov eax,[ebp-$10]
004BDC9E 48               dec eax
004BDC9F 3DFEE0F505       cmp eax,$05f5e0fe
004BDCA4 7605             jbe $004bdcab
004BDCA6 E8DD70F4FF       call @BoundErr
004BDCAB 40               inc eax
004BDCAC 8B0485A4C24C00   mov eax,[eax*4+$4cc2a4]
004BDCB3 3B45EC           cmp eax,[ebp-$14]
004BDCB6 7FD8             jnle $004bdc90
Arraytest.pas.70: IF I<=J THEN BEGIN Tausch_asm(LISTE[I],LISTE[J]);
004BDCB8 8B45F4           mov eax,[ebp-$0c]
004BDCBB 3B45F0           cmp eax,[ebp-$10]
004BDCBE 7F4B             jnle $004bdd0b
004BDCC0 8B45F0           mov eax,[ebp-$10]
004BDCC3 48               dec eax
004BDCC4 3DFEE0F505       cmp eax,$05f5e0fe
004BDCC9 7605             jbe $004bdcd0
004BDCCB E8B870F4FF       call @BoundErr
004BDCD0 40               inc eax
004BDCD1 8B1485A4C24C00   mov edx,[eax*4+$4cc2a4]
004BDCD8 8B45F4           mov eax,[ebp-$0c]
004BDCDB 48               dec eax
004BDCDC 3DFEE0F505       cmp eax,$05f5e0fe
004BDCE1 7605             jbe $004bdce8
004BDCE3 E8A070F4FF       call @BoundErr
004BDCE8 40               inc eax
004BDCE9 8B0485A4C24C00   mov eax,[eax*4+$4cc2a4]
004BDCF0 E81BFFFFFF       call Tausch_asm
Arraytest.pas.71: INC(I);
004BDCF5 8345F401         add dword ptr [ebp-$0c],$01
004BDCF9 7105             jno $004bdd00
004BDCFB E89070F4FF       call @IntOver
Arraytest.pas.72: DEC(J) END
004BDD00 836DF001         sub dword ptr [ebp-$10],$01
004BDD04 7105             jno $004bdd0b
004BDD06 E88570F4FF       call @IntOver
Arraytest.pas.66: WHILE I<J DO
004BDD0B 8B45F4           mov eax,[ebp-$0c]
004BDD0E 3B45F0           cmp eax,[ebp-$10]
004BDD11 0F8C5AFFFFFF     jl $004bdc71
Arraytest.pas.74: IF I<BIS THEN QUICKSORT(I,BIS);
004BDD17 8B45F4           mov eax,[ebp-$0c]
004BDD1A 3B45F8           cmp eax,[ebp-$08]
004BDD1D 7D0B             jnl $004bdd2a
004BDD1F 8B55F8           mov edx,[ebp-$08]
004BDD22 8B45F4           mov eax,[ebp-$0c]
004BDD25 E8EAFEFFFF       call QuickSort
Arraytest.pas.75: IF VON<J THEN QUICKSORT(VON,J)
004BDD2A 8B45FC           mov eax,[ebp-$04]
004BDD2D 3B45F0           cmp eax,[ebp-$10]
004BDD30 7D0B             jnl $004bdd3d
004BDD32 8B55F0           mov edx,[ebp-$10]
004BDD35 8B45FC           mov eax,[ebp-$04]
004BDD38 E8D7FEFFFF       call QuickSort
Arraytest.pas.76: END;
004BDD3D 8BE5             mov esp,ebp
004BDD3F 5D               pop ebp
004BDD40 C3               ret 
004BDD41 8D4000           lea eax,[eax+$00]

jaenicke · Verfasst: Di 28.06.11 19:18

herr-master hat folgendes geschrieben :

Hier ist der gesammte code:

Das ist doch nur der disassemblierte Code, den Delphi generiert. Und was soll das jetzt bringen im Hinblick auf das Thema? :gruebel:

herr-master · Beiträge: 34

Das ist doch nur der disassemblierte Code, den Delphi generiert. Und was soll das jetzt bringen im Hinblick auf das Thema?
Damit wollte ich drauf hindeuten das es nicht überall notwendig ist den code zu optimiren.
Da delphi von sich aus den code in asm schon optimiert.
Hier ist der pure asm code:

markieren

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:

004BDC10  /$  89EC             MOV ESP,EBP  //tausch_asm
004BDC12  |?  C3               RETN
004BDC13  |.  90               NOP
004BDC14  |?  55               PUSH EBP //begin
004BDC15  |?  8BEC             MOV EBP,ESP //mov
004BDC17  |?  83C4 EC          ADD ESP,-14
004BDC1A  |?  8955 F8          MOV DWORD PTR SS:[EBP-8],EDX
004BDC1D  |?  8945 FC          MOV DWORD PTR SS:[EBP-4],EAX
004BDC20  |?  8B45 FC          MOV EAX,DWORD PTR SS:[EBP-4]
004BDC23  |?  8945 F4          MOV DWORD PTR SS:[EBP-C],EAX
004BDC26  |?  8B45 F8          MOV EAX,DWORD PTR SS:[EBP-8]
004BDC29  |.  8945 F0          MOV DWORD PTR SS:[EBP-10],EAX
004BDC2C  |.  8B45 F4          MOV EAX,DWORD PTR SS:[EBP-C]
004BDC2F  |?  0345 F0          ADD EAX,DWORD PTR SS:[EBP-10]
004BDC32  |?  71 05            JNO SHORT 004BDC39                                 ;  ATest.004BDC39
004BDC34  |.  E8 5771F4FF      CALL 00404D90                                      ;  ATest.00404D90
004BDC39  \.  D1F8             SAR EAX,1
004BDC3B   ?  79 03            JNS SHORT 004BDC40                                 ;  ATest.004BDC40
004BDC3D  |.  83D0 00          ADC EAX,0
004BDC40  |?  48               DEC EAX
004BDC41  |?  3D FEE0F505      CMP EAX,5F5E0FE
004BDC46  |?  76 05            JBE SHORT 004BDC4D                                 ;  ATest.004BDC4D
004BDC48  |.  E8 3B71F4FF      CALL 00404D88                                      ;  ATest.00404D88
004BDC4D  |?  40               INC EAX
004BDC4E  |.  8B0485 A4C24C00  MOV EAX,DWORD PTR DS:[EAX*4+4CC2A4]
004BDC55  |?  8945 EC          MOV DWORD PTR SS:[EBP-14],EAX  //an der stelle ist in eax=bc4c4
004BDC58  |?  8B45 F4          MOV EAX,DWORD PTR SS:[EBP-C]   //was glaubt ihr woll ist jetzt im register eax?
004BDC5B  |?  3B45 F0          CMP EAX,DWORD PTR SS:[EBP-10]  //stimmt der vergleich ja oder nein was glaubt ihr?
004BDC5E  |?  0F8D B3000000    JGE 004BDD17                                       ;  ATest.004BDD17 //springt er ja oder nein?
004BDC64  |?  EB 0B            JMP SHORT 004BDC71                                 ;  ATest.004BDC71
004BDC66  |?  8345 F4 01       ADD DWORD PTR SS:[EBP-C],1
004BDC6A  |?  71 05            JNO SHORT 004BDC71                                 ;  ATest.004BDC71
004BDC6C  |?  E8 1F71F4FF      CALL 00404D90                                      ;  ATest.00404D90
004BDC71  |?  8B45 F4          MOV EAX,DWORD PTR SS:[EBP-C]
004BDC74  |?  48               DEC EAX
004BDC75  |>  3D FEE0F505      CMP EAX,5F5E0FE
004BDC7A  |?  76 05            JBE SHORT 004BDC81                                 ;  ATest.004BDC81
004BDC7C  |?  E8 0771F4FF      CALL 00404D88                                      ;  ATest.00404D88
004BDC81  |?  40               INC EAX
004BDC82  |?  8B0485 A4C24C00  MOV EAX,DWORD PTR DS:[EAX*4+4CC2A4]
004BDC89  |?  3B45 EC          CMP EAX,DWORD PTR SS:[EBP-14]
004BDC8C  |.^ 7C D8            /JL SHORT 004BDC66                                 ;  ATest.004BDC66
004BDC8E  |>  EB 0B            |/JMP SHORT 004BDC9B                               ;  ATest.004BDC9B
004BDC90  |?  836D F0 01       SUB DWORD PTR SS:[EBP-10],1
004BDC94  |.  71 05            ||JNO SHORT 004BDC9B                               ;  ATest.004BDC9B
004BDC96  |?  E8 F570F4FF      CALL 00404D90                                      ;  ATest.00404D90
004BDC9B  |?  8B45 F0          MOV EAX,DWORD PTR SS:[EBP-10]
004BDC9E  |?  48               DEC EAX
004BDC9F  |?  3D FEE0F505      CMP EAX,5F5E0FE
004BDCA4  |.  76 05            ||JBE SHORT 004BDCAB                               ;  ATest.004BDCAB
004BDCA6  |?  E8 DD70F4FF      CALL 00404D88                                      ;  ATest.00404D88
004BDCAB  |?  40               INC EAX
004BDCAC  |?  8B0485 A4C24C00  MOV EAX,DWORD PTR DS:[EAX*4+4CC2A4]
004BDCB3  |?  3B45 EC          CMP EAX,DWORD PTR SS:[EBP-14]
004BDCB6  |.^ 7F D8            |JG SHORT 004BDC90                                 ;  ATest.004BDC90
004BDCB8  |>  8B45 F4          |/MOV EAX,DWORD PTR SS:[EBP-C]
004BDCBB  |?  3B45 F0          CMP EAX,DWORD PTR SS:[EBP-10]
004BDCBE  |.  7F 4B            ||JG SHORT 004BDD0B                                ;  ATest.004BDD0B
004BDCC0  |?  8B45 F0          MOV EAX,DWORD PTR SS:[EBP-10]
004BDCC3  |>  48               | DEC EAX
004BDCC4  |?  3D FEE0F505      CMP EAX,5F5E0FE
004BDCC9  |?  76 05            JBE SHORT 004BDCD0                                 ;  ATest.004BDCD0
004BDCCB  |?  E8 B870F4FF      CALL 00404D88                                      ;  ATest.00404D88
004BDCD0  |?  40               INC EAX
004BDCD1  |?  8B1485 A4C24C00  MOV EDX,DWORD PTR DS:[EAX*4+4CC2A4]
004BDCD8  |?  8B45 F4          MOV EAX,DWORD PTR SS:[EBP-C]
004BDCDB  |.  48               ||DEC EAX
004BDCDC  |?  3D FEE0F505      CMP EAX,5F5E0FE
004BDCE1  |?  76 05            JBE SHORT 004BDCE8                                 ;  ATest.004BDCE8
004BDCE3  |.  E8 A070F4FF      |CALL 00404D88                                     ;  ATest.00404D88
004BDCE8  |.  40               |INC EAX
004BDCE9  |?  8B0485 A4C24C00  MOV EAX,DWORD PTR DS:[EAX*4+4CC2A4]
004BDCF0  |?  E8 1BFFFFFF      CALL 004BDC10                                      ;  ATest.004BDC10
004BDCF5  |?  8345 F4 01       ADD DWORD PTR SS:[EBP-C],1
004BDCF9  |.  71 05            |JNO SHORT 004BDD00                                ;  ATest.004BDD00
004BDCFB  |?  E8 9070F4FF      CALL 00404D90                                      ;  ATest.00404D90
004BDD00  |.  836D F0 01       |SUB DWORD PTR SS:[EBP-10],1
004BDD04  |.  71 05            |JNO SHORT 004BDD0B                                ;  ATest.004BDD0B
004BDD06  |?  E8 8570F4FF      CALL 00404D90                                      ;  ATest.00404D90
004BDD0B  |.  8B45 F4          |MOV EAX,DWORD PTR SS:[EBP-C]
004BDD0E  |?  3B45 F0          CMP EAX,DWORD PTR SS:[EBP-10]
004BDD11  |.^ 0F8C 5AFFFFFF    |JL 004BDC71                                       ;  ATest.004BDC71
004BDD17  |?  8B45 F4          MOV EAX,DWORD PTR SS:[EBP-C]
004BDD1A  |?  3B45 F8          CMP EAX,DWORD PTR SS:[EBP-8]
004BDD1D  |.  7D 0B            |JGE SHORT 004BDD2A                                ;  ATest.004BDD2A
004BDD1F  |?  8B55 F8          MOV EDX,DWORD PTR SS:[EBP-8]
004BDD22  |?  8B45 F4          MOV EAX,DWORD PTR SS:[EBP-C]
004BDD25  |?  E8 EAFEFFFF      CALL 004BDC14                                      ;  ATest.004BDC14
004BDD2A  |?  8B45 FC          MOV EAX,DWORD PTR SS:[EBP-4]
004BDD2D  |?  3B45 F0          CMP EAX,DWORD PTR SS:[EBP-10]
004BDD30  |?  7D 0B            JGE SHORT 004BDD3D                                 ;  ATest.004BDD3D
004BDD32  |?  8B55 F0          MOV EDX,DWORD PTR SS:[EBP-10]
004BDD35  |?  8B45 FC          MOV EAX,DWORD PTR SS:[EBP-4]
004BDD38  |?  E8 D7FEFFFF      CALL 004BDC14                                      ;  ATest.004BDC14
004BDD3D  |?  8BE5             MOV ESP,EBP
004BDD3F  |>  5D               POP EBP
004BDD40  |?  C3               RETN
004BDD41  |?  8D40 00          LEA EAX,DWORD PTR DS:[EAX]

Der code kommt direckt aus dem debugger(ollydbg)

BenBE · Verfasst: Mi 29.06.11 11:01

@Herr_master: Und was ist an dem Code vom Delphi-Compiler bitte optimiert? So viele Speicherzugriffe da drin sind, ist das weder optimal noch guter ASM-Code.

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Fiete · Beiträge: 617 Erhaltene Danke: 364 W7 Delphi 6 pro

@BenBE: habe einiges geändert - hoffentlich verbessert

markieren

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:

PROCEDURE AsmQuickSort(VON,BIS:INTEGER);
   ASM                  // EDI - I   EBP - VON   ESI - J   ECX - BIS   EDX - M
         PUSHAD                         // alle Register auf den Stapel
         MOV EDI,VON                    // EDI:=VON
         MOV ESI,BIS                    // ESI:=BIS
         MOV EBP,EDI                    // EBP:=EDI
         MOV ECX,ESI                    // ECX:=ESI
         CALL @QUICK                    // Prozedur QUICK aufrufen
         JMP @ENDE                      // springe zu @ENDE
@QUICK:  MOV EDI,EBP                    // EDI:=EBP
         MOV ESI,ECX                    // ESI:=ECX
         MOV EBX,EDI                    // EBX:=EDI
         ADD EBX,ESI                    // EBX:=EBX+ESI
         SHR EBX,1                      // (J+I) DIV 2
         MOV EDX,[Offset[Liste-4+4*EBX]]// M:=LISTE[(I+J) DIV 2]
@ANFANG: CMP EDI,ESI                    // I>=J
         JGE @UNTEN                     // falls ja zu @UNTEN
@WHILE1: MOV EAX,[Offset[Liste-4+4*EDI]]// EAX:=LISTE[I]
         CMP EAX,EDX                    // LISTE[I]>=M
         JGE @WHILE2                    // falls ja zu @WHILE2
         INC EDI                        // INC(I)
         JMP @WHILE1                    // springe zu @WHILE1
@WHILE2: MOV EAX,[Offset[Liste-4+4*ESI]]// EAX:=LISTE[J]
         CMP EDX,EAX                    // M>=LISTE[J]
         JGE @SWAP                      // falls ja zu @SWAP
         DEC ESI                        // DEC(J)
         JMP @WHILE2                    // springe zu @WHILE2
@SWAP:   CMP EDI,ESI                    // I>J
         JG @UNTEN                      // falls ja zu @UNTEN
         MOV EBX,[Offset[Liste-4+4*EDI]]// EBX:=LISTE[I]
         MOV [Offset[Liste-4+4*EDI]],EAX// LISTE[I]:=EAX = LISTE[J]
         MOV [Offset[Liste-4+4*ESI]],EBX// LISTE[J]:=EBX = LISTE[I]
         INC EDI                        // INC(I)
         DEC ESI                        // DEC(J)
         JMP @ANFANG                    // springe zu @ANFANG
@UNTEN:  CMP EDI,ECX                    // I>=BIS
         JGE @WEITER                    // falls ja zu @WEITER
         PUSH EDI                       // lokale Variable I auf den Stapel
         PUSH ESI                       // lokale Variable J auf den Stapel
         PUSH EBP                       // lokale Variable VON auf den Stapel
         PUSH ECX                       // lokale Variable BIS auf den Stapel
         MOV EBP,EDI                    // VON:=I
         CALL @QUICK                    // Prozedur QUICK aufrufen
         POP ECX                        // lokale Variable BIS vom den Stapel
         POP EBP                        // lokale Variable VON vom den Stapel
         POP ESI                        // lokale Variable J vom den Stapel
         POP EDI                        // lokale Variable I vom den Stapel
@WEITER: CMP EBP,ESI                    // VON>=J
         JGE @PROCEND                   // falls ja zu @PROCEND
         PUSH EDI                       // lokale Variable I auf den Stapel
         PUSH ESI                       // lokale Variable J auf den Stapel
         PUSH EBP                       // lokale Variable VON auf den Stapel
         PUSH ECX                       // lokale Variable BIS auf den Stapel
         MOV ECX,ESI                    // BIS:=J
         CALL @QUICK                    // Prozedur QUICK aufrufen
         POP ECX                        // lokale Variable BIS vom den Stapel
         POP EBP                        // lokale Variable VON vom den Stapel
         POP ESI                        // lokale Variable J vom den Stapel
         POP EDI                        // lokale Variable I vom den Stapel
@PROCEND:RET                            // Prozedur QUICK beenden
@ENDE:   POPAD                          // alle Register restaurieren
  END;

Gruß Fiete

_________________
Fietes Gesetz: use your brain (THINK)

Horst_H · Verfasst: Mi 29.06.11 12:01

Hallo,

Es wäre schön, die Startadresse von Liste zu übergeben

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

type 
  TIntliste = array of Integer;
var
  Liste : TIntListe;
PROCEDURE AsmQuickSort(VON,BIS:INTEGER;p0:pInteger);
...
Procedure myQuicksort(var L: TIntListe);
begin
  AsmQuickSort(low(L),High(L),@Liste[Low(L)]);
end;


begin
setlength(Liste,1000000);
// Füllen
myQuicksort(Liste);

Nebenbei bemerkt:
Ist es schneller?

Gruß Horst

herr-master · Beiträge: 34

Allso leut google und einigen seiten ist der code den delphi generiert in asm schon zimlich gut optiermiert zwar nicht bei allen functionen aber bei den meisten.@Horst_H so eine version gibt es schon für delphi :

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:

 procedure QuickSort(var A: array of Integer; iLo, iHi: Integer) ;
 var
   Lo, Hi, Pivot, T: Integer;
 begin
   Lo := iLo;
   Hi := iHi;
   Pivot := A[(Lo + Hi) div 2];
   repeat
     while A[Lo] < Pivot do Inc(Lo) ;
     while A[Hi] > Pivot do Dec(Hi) ;
     if Lo <= Hi then
     begin
       T := A[Lo];
       A[Lo] := A[Hi];
       A[Hi] := T;
       Inc(Lo) ;
       Dec(Hi) ;
     end;
   until Lo > Hi;
   if Hi > iLo then QuickSort(A, iLo, Hi) ;
   if Lo < iHi then QuickSort(A, Lo, iHi) ;
 end;

Auf dieser seite gefunden:
delphi.about.com/od/...lide/a/quicksort.htm

jaenicke · Verfasst: Mi 29.06.11 17:32

herr-master hat folgendes geschrieben :

Allso leut google und einigen seiten ist der code den delphi generiert in asm schon zimlich gut optiermiert

Man merkt, dass du nicht viel Ahnung von Assembler hast...
Manchmal kommen da so viele unnötige Befehle heraus... Nur hat eine solche Optimierung in Assembler eben auch gravierende Nachteile, so dass ich es meistens eben akzeptiere...

BenBE · Verfasst: Do 30.06.11 02:25

@Fiete: Das End; von nem ASM-Block ist bereits ein RET-Befehl. Du kannst also

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:

asm
//...
@ENDE:
    POPAD
@PROCEND:
end;

machen und bekommst auch den richtigen Code raus. ist 1 Byte sogar kleiner ;-)

Das ist auch der Hintergrund, warum ich gesagt hab, dass man ohne das begin/end arbeiten sollte, weil Delphi dann kein eigenes Stackframe schreibt.

Irgendwie kann ich mich mit deinem pushad/popad noch nicht so recht anfreunden. Ist zwar wegen dem call @Quick nur einmal für den gesamten Sortier-Vorgang, aber sieht trotzdem unschön aus.

Noch ne kleine Schönheitssache:

markieren

Delphi-Quelltext

1:
2:
3:

asm
    LEA EAX, DWORD PTR [Liste-4+4*EDI]
end;

statt

markieren

Delphi-Quelltext

1:
2:
3:

asm
    MOV EAX, [Offset[Liste-4+4*EDI]]
end;

ist zwar paar Zeichen mehr zu tippen, ist aber schon anhand des Mnemonic etwas eindeutiger (LEA = Load Effective Address). Wird aber intern auch nur in ein MOV übersetzt. Hintergrund ist der, dass ältere Delphi-Versionen mit der Offset-Syntax nichts anfangen können; mit LEA aber schon. Damit wird der Code etwas portabler.

Ein anderer Trick zum Tauschen von Speicherinhalten ist:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:

asm
    XCHG EAX, DWORD PTR [PtrExpr1]
    XCHG EAX, DWORD PTR [PtrExpr2]
    XCHG EAX, DWORD PTR [PtrExpr1]
end;

Wenn man den Wert von PtrExpr1 oder PtrExpr2 bereits im Speicher hat, entfällt eine der XCHG-Anweisungen entsprechend. Wäre bei @Swap der Fall, weil Du durch den Vergleich eh bereits in EAX einen der beiden Werte hast.

Wenn man Platz sparen möchte, kann man sogar das

markieren

Delphi-Quelltext

1:
2:
3:

asm
    MOV DWORD PTR [4*EDI+PtrExpr], EAX
    INC EDI

umbauen zu

markieren

Delphi-Quelltext

1:
2:

asm
    STOSD

Was auf aktuellen Superskalaren CPUs (also allen ^^) zwar kleineren Code erzeugt, aber langsamer ist und zudem den Nachteil hat, dass in EDI der fertig berechnete Pointer stehen muss. Analog ginge das Lesen mit

markieren

Delphi-Quelltext

1:
2:
3:

asm
    MOV EAX, DWORD PTR [4*ESI+PtrExpr]
    INC ESI

mit

markieren

Delphi-Quelltext

1:
2:

asm
    LODSD

zu vereinfachen, wobei aber die gleichen Nachteile gelten. Die Variante mit 2 Befehlen ist hier also in beiden Fällen trotz des längeren Codes zu bevorzugen.

Ach ja: In deiner Konstruktion ab Zeile 38 solltest Du ggf. schauen, dass Du EDI (Zeile 47 und 50) direkt auf dem Stack lässt und ESI/EBP umordnest, so dass Du nur eines von beiden vom Stack holen musst:

markieren

Delphi-Quelltext

 
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:

{ ... }
asm
         PUSH EDI                       // lokale Variable I auf den Stapel
         PUSH ECX                       // lokale Variable BIS auf den Stapel
         PUSH EBP                       // lokale Variable VON auf den Stapel
         PUSH ESI                       // lokale Variable J auf den Stapel
         MOV EBP,EDI                    // VON:=I
         CALL @QUICK                    // Prozedur QUICK aufrufen
         POP ESI                        // lokale Variable J vom den Stapel
@WEITER: CMP EBP,ESI                    // VON>=J ([ESP]=EBP, da EBP von @Quick nicht geändert wird, entfällt der Speicherzugriff aber)
         JGE @PROCEND                   // falls ja zu @PROCEND
         PUSH ESI                       // lokale Variable J auf den Stapel
         MOV ECX,ESI                    // BIS:=J
         CALL @QUICK                    // Prozedur QUICK aufrufen
         POP ESI                        // lokale Variable J vom den Stapel
@PROCEND:POP EBP                        // lokale Variable VON vom den Stapel
         POP ECX                        // lokale Variable BIS vom den Stapel
         POP EDI                        // lokale Variable I vom den Stapel
         RET
@ENDE:   POPAD

Ja, es gehen auch Displacements über den Stack-Pointer ;-)

Und durch dein Wiederherstellen der ganzen Register beim Verlassen von Quick könnte man sogar das POP ESI/PUSH ESI weglassen und EBP als beibehalten annehmen. Da EBP nie geschrieben wird in @Quick, könnte man sich sogar das PUSH EBP/POP EBP sparen. Den CMP bei Weiter hatte ich zuerst mit

markieren

Delphi-Quelltext

1:
2:

asm
    CMP DWORD PTR [ESP],ESI

was das gleiche ist. Man kann aber, wenn man sich einen Speicherzugriff sparen möchte:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:

asm
    MOV ESI, DWORD PTR [ESP]
    CMP EBP, ESI
    JGE @ProcEnd
    MOV ECX, ESI

machen. Das dürfte aber unter Nutzung des L1 Data-Cache eher wenig ausmachen.

Mehr seh ich jetzt grad erstmal nicht mehr. Erstens zu müde und zweitens keinen Debugger da zum Durchsteppen.

HTH.

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme