ASM - Hilfe bei Optimierung, x64?

Für allgemeine Fragen zur Programmierung mit PureBasic.
Benutzeravatar
cxAlex
Beiträge: 2111
Registriert: 26.06.2008 10:42

ASM - Hilfe bei Optimierung, x64?

Beitrag von 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
Projekte: IO.pbi, vcpu
Pausierte Projekte: Easy Network Manager, µC Emulator
Aufgegebene Projekte: ECluster

Bild

PB 5.1 x64/x86; OS: Win7 x64/Ubuntu 10.x x86
Marvin
Beiträge: 497
Registriert: 17.07.2005 14:42
Wohnort: Krikkit

Re: ASM - Hilfe bei Optimierung, x64?

Beitrag von 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
Beiträge: 6291
Registriert: 29.08.2004 08:37
Computerausstattung: Hoffentlich bald keine mehr
Kontaktdaten:

Re: ASM - Hilfe bei Optimierung, x64?

Beitrag von DarkDragon »

Marvin hat geschrieben: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.
Angenommen es gäbe einen Algorithmus mit imaginärer Laufzeit O(i * n), dann gilt O((i * n)^2) = O(-1 * n^2) d.h. wenn man diesen Algorithmus verschachtelt ist er fertig, bevor er angefangen hat.
Benutzeravatar
Helle
Beiträge: 566
Registriert: 11.11.2004 16:13
Wohnort: Magdeburg

Re: ASM - Hilfe bei Optimierung, x64?

Beitrag von Helle »

Hättest ´ne gute Chance, wenn Du den zu konvertierenden Original-Code zeigst.
Gruß
Helle
Kevin
Beiträge: 236
Registriert: 11.06.2007 12:55

Re: ASM - Hilfe bei Optimierung, x64?

Beitrag von Kevin »

Helle hat geschrieben: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
Beiträge: 497
Registriert: 17.07.2005 14:42
Wohnort: Krikkit

Re: ASM - Hilfe bei Optimierung, x64?

Beitrag von Marvin »

DarkDragon hat geschrieben:
Marvin hat geschrieben: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.
Benutzeravatar
cxAlex
Beiträge: 2111
Registriert: 26.06.2008 10:42

Re: ASM - Hilfe bei Optimierung, x64?

Beitrag von 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
Projekte: IO.pbi, vcpu
Pausierte Projekte: Easy Network Manager, µC Emulator
Aufgegebene Projekte: ECluster

Bild

PB 5.1 x64/x86; OS: Win7 x64/Ubuntu 10.x x86
Marvin
Beiträge: 497
Registriert: 17.07.2005 14:42
Wohnort: Krikkit

Re: ASM - Hilfe bei Optimierung, x64?

Beitrag von Marvin »

Ah, ich hab übersehen, dass „mapsize = *hMap\mapsize“ gar kein Kommentar ist. :D
Benutzeravatar
Helle
Beiträge: 566
Registriert: 11.11.2004 16:13
Wohnort: Magdeburg

Re: ASM - Hilfe bei Optimierung, x64?

Beitrag von 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.
Zuletzt geändert von Helle am 29.07.2010 18:10, insgesamt 1-mal geändert.
DarkDragon
Beiträge: 6291
Registriert: 29.08.2004 08:37
Computerausstattung: Hoffentlich bald keine mehr
Kontaktdaten:

Re: ASM - Hilfe bei Optimierung, x64?

Beitrag von DarkDragon »

cxAlex hat geschrieben: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.
cxAlex hat geschrieben: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.
Angenommen es gäbe einen Algorithmus mit imaginärer Laufzeit O(i * n), dann gilt O((i * n)^2) = O(-1 * n^2) d.h. wenn man diesen Algorithmus verschachtelt ist er fertig, bevor er angefangen hat.
Antworten