ASM - Hilfe bei Optimierung, x64?

[cxAlex]

Ich optimiere gerade ein bisschen am Speed meines Hashtable-Includes und übersetzte einige Teile von Hand in Assembler da mir der PB - Compiler nicht genug optimiert. Nun hab ich aber irgendwie einen Fehler in meiner Übersetzung, sieht einer der ASM - Gurus wo ich danebenhaue, bzw. kenn jemand noch ein paar Tricks das ganze unter x64 zu beschleunigen?

Code: Alles auswählen

Macro _DoQuad()
  CompilerIf #True
    counter + 1
    hash + ((counter/2)*(counter/2))*(-1 + (r*2))
    hash%*hMap\Mapsize
    If hash<0 : hash + *hMap\Mapsize : EndIf
  CompilerElse
    mapsize = *hMap\mapsize
    !INC dword[p.v_counter]
    !MOV EAX,dword[p.v_counter]
    !MOV EBX, dword[p.v_mapsize]
    !MOV ECX,2
    !CDQ
    !DIV ECX ; counter/2
    !IMUL EAX,EAX ; ((counter/2)*(counter/2))
    !MOV ESI, dword[p.v_r]
    !ADD ESI, ESI ; r*2
    !DEC ESI ; -1
    !IMUL EAX,ESI
    !ADD EAX, dword[p.v_hash] ; hash + rest
    !CDQ
    !DIV EBX ;hash%*hMap\mapsize
    !MOV EAX, EDX
    ; If hash<0 : hash + *hMap\Mapsize : EndIf
    !AND EAX,EAX
    !JGE @f
    !ADD EDX,EBX
    !@@:
    !MOV dword[p.v_hash], EDX
    ; r ! 1
    !XOR dword[p.v_r], 1
  CompilerEndIf
EndMacro

Gruß, Alex

[Marvin]

So auf die Schnelle sehe ich erstmal, dass man /2 mittels shr 1 schneller darstellen kann, für *2 kann man shl 1 nehmen (obwohl ich nicht weiß, ob das schneller als add edi,edi ist). Außerdem ist inc/dec AFAIK langsamer als add 1/sub 1.

Das mit dem if < 0 funktioniert so nicht. Du müsstest da ein jns (statt jge) nehmen (and eax,eax ist nicht gleich cmp eax,0).

Wie genau du auf *hMap\mapsize zugreifst, kann ich jetzt auch nicht wirklich erkennen (denn in [p.v_mapsize] steht das eher nicht, würde ich behaupten)…

Insgesamt wüsste ich jetzt nicht, wo genau das Problem ist (außer den beiden genannten), ich kenne aber z. B. die Variablentypen nicht. Wenn das .i ist, dann müsste das auf x64 ja 64 Bit sein, also qword (und somit rax statt eax, etc.).

[DarkDragon]

Das mit dem if < 0 funktioniert so nicht. Du müsstest da ein jns (statt jge) nehmen (and eax,eax ist nicht gleich cmp eax,0).

Doch das funktioniert so, denn der Compiler macht aus

Code: Alles auswählen

If hash < 0
  Blabla
End

ja sowas hier:

Code: Alles auswählen

JGE @f ; springe vorwärts, falls nicht < 0, ansonsten führe folgendes aus:
Blabla
@@:

was dem hier gleichkommt:

Code: Alles auswählen

If Not hash >= 0
  Goto EndOfIf ; überspringe den fall, dass hash < 0 ist
EndIf
Blabla
EndOfIf:

Btw.: Du hast da counter / 2 zweimal drin, mach das bitte nur einmal. Und das moduloergebnis wird ja nie negativ sofern hash und *hMap\Mapsize positiv sind.

[Helle]

Hättest ´ne gute Chance, wenn Du den zu konvertierenden Original-Code zeigst.
Gruß
Helle

[Kevin]

Hättest ´ne gute Chance, wenn Du den zu konvertierenden Original-Code zeigst.
Gruß
Helle

ich bin mir nicht sicher aber der orginal code ist doch das am anfang:

Code: Alles auswählen

 Macro _DoQuad()
CompilerIf #True
    counter + 1
    hash + ((counter/2)*(counter/2))*(-1 + (r*2))
    hash%*hMap\Mapsize
    If hash<0 : hash + *hMap\Mapsize : EndIf
  CompilerElse
 ...

[Marvin]

Das mit dem if < 0 funktioniert so nicht. Du müsstest da ein jns (statt jge) nehmen (and eax,eax ist nicht gleich cmp eax,0).

Doch das funktioniert so, denn der Compiler macht aus

Code: Alles auswählen

If hash < 0
  Blabla
End

ja sowas hier:

Code: Alles auswählen

JGE @f ; springe vorwärts, falls nicht < 0, ansonsten führe folgendes aus:
Blabla
@@:

Aber and eax,eax ist nicht cmp eax,0.
Und das jge macht er dort nur hin, nachdem er da ein cmp hatte, oder?

Wobei ich erstmal nachsehen müsste, ob jge nicht am Ende doch ein Alias für jns ist…

EDIT: Na ja, jge springt, wenn ZF=1 oder SF=OF. Da das OF hier wohl immer 0 ist (und das SF bei ZF=1 automatisch 1 ist), entspricht das wohl (in diesem Fall) einem jns.

[cxAlex]

Jop, das im oberen Compilerif ist der Orginalcode.

Wie ich hab counter/2 2 mal drin? ich rechne counter durch 2 (EAX durch ECX, das Ergebniss ist wieder in EAX) und multipliziere das ganze mit sich selbst (IMUL EAX, EAX) entspricht doch (counter/2)*(counter/2), oder? Das ist schon so gewollt :P

Das mit dem mapsize = *hMap\mapsize ist nur dazu da das ich auf den Wert in *hMap\mapsize zugreifen kann (dword[p.v_mapsize]), ich hab keinen Plan wie ich PB Strukturelemente in ASM direkt ansprechen kann, das klappt schon so.

Sieht irgendwer was was ich übersehe?

Gruß, Alex

[Marvin]

Ah, ich hab übersehen, dass „mapsize = *hMap\mapsize“ gar kein Kommentar ist.

[Helle]

Ohne Testmöglichkeit, nur so als Idee:

Code: Alles auswählen

;Pseudo-Code 32-Bit; Variablen anpassen
r.b=1                        ;oder 0 (Remi) 
mapsize = *hMap\mapsize      ;oder *object\Mapsize (Original inc)

;Else ; // quadratic probe
 ;counter + 1
 !inc [v_counter]            ;Variable wird noch ausgewertet
 ;hash + ((counter/2)*(counter/2))*(-1 + (r*2))
 !mov eax,[v_counter]
 !shr eax,1                  ;div 2
 !mul eax
 !mov edx,[v_hash]
 !xor [v_r],1                ;Toggle r 0-1-0...; ist aber nicht das Schnellste...
 !jz @f                      ;also r=0
 !add edx,eax                ;r=1, also Addition
 !jmp X
 !@@:
 !sub edx,eax                ;r=0, also Subtraktion
 !X:
 !mov eax,edx                ;eax=hash
 ;hash % *hMap\Mapsize
 !mov ecx,[v_mapsize]
 !cdq                        ;alle Bits von edx erhalten Wert des Vorzeichens (MSB) von eax  
 !idiv ecx                   ;in edx steht Modulo = hash; interessant wäre Modulo ohne Division
 ;If hash < 0 : hash + *hMap\Mapsize : EndIf
 !test edx,80000000h         ;negativ?
 !jz @f                      ;nein
 !add edx,[v_mapsize]
 !@@:
 !mov [v_hash],edx
;EndIf

Gruß
Helle

Edit: 29.07.2010 Code überarbeitet.

[DarkDragon]

Jop, das im oberen Compilerif ist der Orginalcode.

Wie ich hab counter/2 2 mal drin? ich rechne counter durch 2 (EAX durch ECX, das Ergebniss ist wieder in EAX) und multipliziere das ganze mit sich selbst (IMUL EAX, EAX) entspricht doch (counter/2)*(counter/2), oder? Das ist schon so gewollt :P

Ja im oberen Code hast du es 2 mal drin. Und der ist ja der default-code momentan.

Das mit dem mapsize = *hMap\mapsize ist nur dazu da das ich auf den Wert in *hMap\mapsize zugreifen kann (dword[p.v_mapsize]), ich hab keinen Plan wie ich PB Strukturelemente in ASM direkt ansprechen kann, das klappt schon so.

Mit einem Offset geht das. Aber dann musst du das jedes mal ändern, wenn du das Offset in der Struktur änderst.