ASM - Hilfe bei Optimierung, x64?

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

Re: ASM - Hilfe bei Optimierung, x64?

Beitrag von cxAlex »

Danke helle :D Nur r ist leider nicht der Rest, sondern einfach eine eigenständige Variable und ich versteh deinen Code leider nicht genug um es selbst anzupassen :oops:

@DD:

Code: Alles auswählen

counter + 1
hash + ((counter/2)*(counter/2))*(-1 + (r*2))
hash%*hMap\Mapsize
If hash<0 : hash + *hMap\Mapsize : EndIf
Ich quadriere hier einfach counter/2 ( (counter/2)² ), wo ist da ein counter/2 zu viel?

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
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:Danke helle :D Nur r ist leider nicht der Rest, sondern einfach eine eigenständige Variable und ich versteh deinen Code leider nicht genug um es selbst anzupassen :oops:

@DD:

Code: Alles auswählen

counter + 1
hash + ((counter/2)*(counter/2))*(-1 + (r*2))
hash%*hMap\Mapsize
If hash<0 : hash + *hMap\Mapsize : EndIf
Ich quadriere hier einfach counter/2 ( (counter/2)² ), wo ist da ein counter/2 zu viel?

Gruß, Alex
Des gibts doch it, mach die Augen auf!! Langsam regts mich auf >_< . Des Counter/2 optimiert PB ja schließlich nicht weg glaube ich. Und wenn doch muss man sicher gehen, dass sich das nie ändert in PB.

Code: Alles auswählen

counter + 1
hash + ((counter/2)*(counter/2))*(-1 + (r*2)) ; HIER STEHT 2 MAL (counter/2) !! VORHER ZWISCHENSPEICHERN UND DANN ERST QUADRIEREN, DAMIT SICHER NICHT 2 MAL COUNTER/2 GEMACHT WIRD!!
hash%*hMap\Mapsize
If hash<0 : hash + *hMap\Mapsize : EndIf
Und das letzte If kannst du komplett weglassen ... die Mapsize ist doch nie negativ und der Hash denke ich auch nicht oder?
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
cxAlex
Beiträge: 2111
Registriert: 26.06.2008 10:42

Re: ASM - Hilfe bei Optimierung, x64?

Beitrag von cxAlex »

Ah, du meinst ich soll das ganze nur 1* berechnen und das ganze in einer Temp-Variable quadrieren, stimmt natürlich.
Aber es geht mir grade nicht drum den PB - Source zu optimieren, es geht mir grade nur um den ASM - Code.

Doch der Hash kann negativ werden wenn der Long (oder Quad auf x64) überläuft. Kommt durchaus öfter vor.

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
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 »

Ein Bit macht da doch nicht soviel aus würde ich sagen. Hast du ernsthaft vor mehr als 2^31 Datensätze und deren Schlüssel zu speichern? Wem willst du damit Konkurrenz machen?
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
cxAlex
Beiträge: 2111
Registriert: 26.06.2008 10:42

Re: ASM - Hilfe bei Optimierung, x64?

Beitrag von cxAlex »

Es müssen nicht 2^31 Datensätze sein. Der Hashing-Algo (DJB2) erzeugt schon mal so hohe Werte, das If hat schon seinen Sinn.

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
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:Es müssen nicht 2^31 Datensätze sein. Der Hashing-Algo (DJB2) erzeugt schon mal so hohe Werte, das If hat schon seinen Sinn.
:lol: Und du musst ja auch unbedingt die original DJB2 Hashfunktion verwenden, was? Wenns dir doch so auf Geschwindigkeit ankommt würd ich das dann trotzdem auf 31 bits reduzieren.
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
NicTheQuick
Ein Admin
Beiträge: 8807
Registriert: 29.08.2004 20:20
Computerausstattung: Ryzen 7 5800X, 64 GB DDR4-3200
Ubuntu 24.04.2 LTS
GeForce RTX 3080 Ti
Wohnort: Saarbrücken

Re: ASM - Hilfe bei Optimierung, x64?

Beitrag von NicTheQuick »

Im Übrigen kann man auch statt (counter / 2) * (counter / 2) einfach (counter * counter) >> 2 schreiben. Der Nachteil dabei ist nur, dass das Zwischenergebnis counter * counter überlaufen kann. Aber ich weiß auch nicht wie groß counter werden kann.
Benutzeravatar
NicknameFJ
Beiträge: 324
Registriert: 03.06.2007 14:36
Wohnort: Von der Sonne aus gesehen der dritte Planet

Re: ASM - Hilfe bei Optimierung, x64?

Beitrag von NicknameFJ »

Hi cxAlex,

meine Assemblerkenntnisse sind schon etwas eingerostet, daher vorab mal sorry für den Fall dass ich jetzt einen Schmarn erzählen:

Code: Alles auswählen

  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

Mit dem !CDQ erweiterst Du den Wert in EAX auf 64 Bit unter Beibehaltung des Vorzeichens. Anschließend (mit !DIV ECX) teilst Du diesen Wert - !DIV ist aber ohne Berücksichtigung des Vorzeichens! Müsste das hier dann nicht !IDIV sein? Weiter unten im Code rechnest Du ja auch mit IMUL

Wenn die obige Annahme mit den Vorzeichen von mir falsch ist, d.h. in EAX, sprich Counter immer nur positiv sein kann, dann würde ich die Division durch 2 mit einer Rechtsschiebeoperation durchführen SHR EAX,1, dies ist schneller sein als eine Division.

Auch könnte man dann anstatt
!CDQ
!MOV EDX,0 oder !XOR EDX,EDX schreiben, das spart einen Zyklus braucht aber wohl mehr Platz im Speicher (hier sollte der Mr Green sein, geht aber grad irgendwie nicht?!)


Aber wieder im Ernst:
!ADD EDX,EBX - ziemlich am Ende Deines Codes

müsste glaube ich !ADD EAX,EBX sein, da der Modulo-Wert (Rest der Division) vorher von Dir nach EAX geschoben wurde.


Grüße

NicknameFJ
PS: Alle im Text enthaltenen Schreibfehler sind beabsichtigt und dienen der Belustigung aller

Bild
Benutzeravatar
NicknameFJ
Beiträge: 324
Registriert: 03.06.2007 14:36
Wohnort: Von der Sonne aus gesehen der dritte Planet

Re: ASM - Hilfe bei Optimierung, x64?

Beitrag von NicknameFJ »

Dein Code nachmals ganz und gar

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
    !SHL EAX,1        !;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       - Wert wird in EDX belassen, da unten mit EDX weitergerechnet wird, und nicht mit EAX
    ; If hash<0 : hash + *hMap\Mapsize : EndIf
     !AND EDX,EDX       ;!AND EAX,EAX     , Prüfung ob kleiner Null wird auf EDX geändert, da steht der Wert
    !JGE @f
    !ADD EDX,EBX
    !@@:
    !MOV dword[p.v_hash], EDX
    ; r ! 1
    !XOR dword[p.v_r], 1
  CompilerEndIf
EndMacro
Bitte mal testen

Grüße NicknameFJ

Sry für Doppelpost
PS: Alle im Text enthaltenen Schreibfehler sind beabsichtigt und dienen der Belustigung aller

Bild
Benutzeravatar
Thorium
Beiträge: 1722
Registriert: 12.06.2005 11:15
Wohnort: Germany
Kontaktdaten:

Re: ASM - Hilfe bei Optimierung, x64?

Beitrag von Thorium »

Wieso eigentlich "wenn der quad überläuft bei x64"?
Du arbeitest garnicht mit quads wurde aber auch schon erwähnt dein assemblercode ist reiner 32bit code. du nutzt nicht ein einziges 64bit register.
Zu mir kommen behinderte Delphine um mit mir zu schwimmen.

Wir fordern mehr Aufmerksamkeit für umfallende Reissäcke! Bild
Antworten