Optimizer

[Stefan]

Hallo Remi_Meier
Hast du eigentlich schon die Optimierungen für multiplikation
mit negativen Zahlen eingebaut ?
Hier noch ein Ersatz für den Int-Befehl:

Code: Alles auswählen

_PB_Int@4

!FISTP dword[esp-4]
!MOV Eax,[esp-4]

P.S.: Mein fünfzigster Beitrag
Gruß
Stefan

[remi_meier]

Ah hallo!
Negative Zahlen hab ich noch nicht (frag mich nicht wieso.., habs verges-
sen). Int() werd ich noch einbauen, danke!

Im Moment komme ich aber zu gar nix... Ist echt stressig hier! Schon nur
das Problem mit den Assemblerfehlern ist noch nicht gelöst

greetz
Remi

Gratuliere!

[Ynnus]

Ist es nicht eigentlich Freds Aufgabe, die Funktionen soweit per ASM zu optimieren, dass es nicht besser geht? Vielleicht solltest du ihm deine Methoden offenlegen, dass er sie in den Compiler direkt übernehmen kann und dann ein Zwischentool nicht mehr nötig ist. Das würde PB nur zu Gute kommen. Eventuell könnte man PB ja in den Compileroptionen eine Option "Optimieren" verpassen, welches dann eben etwas länger dauert aber dafür optimiert mit deinen Routinen. Bisher bietet PB ja nur eine Art der Kompilierung und die ist scheinbar noch ausbaufähig.

[Helle]

Hier ein Vorschlag um vorzeichenlose Division mit konstanten Divisor (etwas) zu beschleunigen:

Code: Alles auswählen

;------- Unsigned Division mit konstanten Divisor; Dividend und Divisor jeweils kleiner 65336 ------
;----------- Die Division (DIV) wird ersetzt durch eine schnellere Multiplikationsroutine ----------
;----------------------------------- Helle, PB3.93, 12.6.2005 --------------------------------------
   
   divisor.l=23     ;für Test frei gewählt
   shiftwert.b=0
   dividend.l=0
   faktor.l=0 
   quotient.l=0     ;zur Korrektur von faktor

;----- Diese Routine dient zur Ermittlung von faktor und shiftwert für einen konstanten Divisor ----
MOV [v_shiftwert],16
BSR EAX,[v_divisor]
;JZ l_error         ;kein gesetztes Bit gefunden, wäre Division durch Null!
ADD [v_shiftwert],AL
MOV CL,[v_shiftwert]
MOV EAX,1
SHL EAX,cl
MOV ECX,[v_divisor]
XOR EDX,EDX
DIV ECX

MOV EBX,[v_divisor]
PUSHAD
MOV EAX,[v_dividend]
XOR EDX,EDX
DIV EBX
MOV [v_quotient],EDX
POPAD
CMP [v_quotient],0
JE l_plus

SHR EBX,1
CMP EDX,EBX
JB l_noplus
PLUS:
INC EAX
NOPLUS:
MOV [v_faktor],EAX
;faktor und shiftwert für divisor 1-65335 können auch in eine Tabelle geschrieben werden, ähnlich
;wie Remi´s IMULOptimierungen.txt
 
;-------------------------------------- Test für Division durch 23 ---------------------------------
a1.l=0
a2.l=0

;---------------------------------------- Test mit Multiplikation ----------------------------------
  StartTime = ElapsedMilliseconds() 
 For i=1 To 1000 
  For dividend = 0 To 65000
   
   MOV EAX,[v_dividend]
   
   IMUL EAX,45591     ;ermittelter faktor für Divisor=23
   SHR EAX,20         ;ermittelter shiftwert für Divisor=23

   MOV [v_a1],EAX     ;zeigt hier nur den Endwert an: 65000/23=2826
   
  Next dividend 
 Next i 
  
  Debug = ElapsedMilliseconds()-StartTime 
  Debug a1 
;---------------------------------------------------------------------------------------------------

  Debug "########"

;-------------------------------------- Test mit herkömmlicher Division ----------------------------
  StartTime = ElapsedMilliseconds() 
 For i=1 To 1000 
  For dividend = 0 To 65000
   
   MOV EAX,[v_dividend]
   
   XOR EDX,EDX
   DIV [v_divisor]

   MOV [v_a2],EAX     ;zeigt hier nur den Endwert an: 65000/23=2826
    
  Next dividend 
 Next i 

  Debug = ElapsedMilliseconds()-StartTime 
  Debug a2 
;---------------------------------------------------------------------------------------------------
;Werte auf Athlon64,3200+:  Multiplikation: 5,3s
;                           Division:       6,3s
;nicht umwerfend, aber besser als garnichts

End

Mit einer Testroutine habe ich meinen Rechner schon zig-Stunden zwecks Überprüfung gequält und bisher keinen Fehler (Abweichung) gefunden (Vorgängerversionen hatten schon mal +-1 Unterschied zur DIV-Routine).

Gruss
Helle

[remi_meier]

@Sunny:
Fred hat schon davon erfahren und der SourceCode wird ja auch mitgeliefert.
Ich wäre auch glücklich, wenn das alles schon vom Compiler erledigt würde,
aber Fred scheint im Moment Wichtigeres zu tun haben..

@Helle:
Bei mir komme ich sogar manchmal auf einen Faktor von 10x schneller!
(ohne Debugger)
Aber um das anwenden zu können, müsste ich sicher sein, dass Dividend
und Divisor unsigned sind, oder? Eine Überprüfung würde das Resultat aber
wieder etwa umkehren. (kann ich dann machen, wenn PB endlich unsigned
Support hat)
Oder habe ich einen Denkfehler?

PB hatte ja mal die Divisionsoptimierung durch SAR drinne, das verursachte
aber irgendwie Probleme und deshalb ists wieder draussen..
Aber wenn du etwas herausfinden könntest, dass keine Probleme verursacht
bei vorzeichenbehafteten Zahlen, wäre ich sehr glücklich! (und Fred bestimmt
auch)

greetz
Remi

[Helle]

Hallo Remi,
es soll ein "Ersatz" für DIV sein, nicht für IDIV! Die Verwendung von IMUL irritiert möglicherweise etwas, hat aber den Grund, das man "faktor" direkt angeben kann (ohne über Extra-Register oder -Variable).

Gruss
Helle

[remi_meier]

Dann habe ich es richtig verstanden.
Also kann ich es im jetzigen PB nicht verwenden, da dort ja immer IDIV
verwendet wird

greetz
Remi

[Stefan]

Hallo Remi
Ich hab eine sehr schnelle Optimierung für IDIV gefunden für Zahlen die aus 2er Potenzen bestehen.(Auch negative Zahlen).
Der Nachteil dabei ist nur, dass diese Methode fast doppel soviel
Speicher frisst, wie IDIV.

Code: Alles auswählen

SetPriorityClass_(GetCurrentProcess_(),#REALTIME_PRIORITY_CLASS)

M1Start=GetTickCount_()
For C=-100000000 To 100000000
!MOV EAX,[v_C]
!CDQ
!MOV EBX,2
!IDIV EBX
Next
M1Ende=GetTickCount_()

Delay(1000)

M2Start=GetTickCount_()
For C=-100000000 To 100000000
!MOV EAX,[v_C]
!CMP EAX,0
!JGE NoNeg
!NEG EAX
!SAR Eax,1
!NEG EAX
!JMP EndShift
!NoNeg:
!SAR Eax,1
!EndShift:
Next
M2Ende=GetTickCount_()

Delay(1000)

M3Start=GetTickCount_()
For C=-100000000 To 100000000
!MOV EAX,[v_C]
Next
M3Ende=GetTickCount_()


TSchleife=M3Ende-M3Start
TMethod1=M1Ende-M1Start-TSchleife
TMethod2=M2Ende-M2Start-TSchleife

A$="Method 1(IDIV) "+Str(TMethod1)+" ms"+Chr(13)
A$+"Method 2       "+Str(TMethod2)+" ms"+Chr(13)

SetPriorityClass_(GetCurrentProcess_(),#NORMAL_PRIORITY_CLASS)

MessageRequester("Result",A$)

Sollte ich vieleicht auch Fred schicken, da er die SAR-Optimierung immerhin wegen mir herausgenommen hat.

//Edit:
Hab einen Bug im Speedtest behoben.
Meine Ergebnisse:
Methode1: 8782 ms
Methode2: 688 ms
Methode 2 ist also fast 13 mal so schnell wie Methode 1.

Gruß
Stefan

[remi_meier]

@Stefan: Sieht sehr interessant aus!
Ja schicks mal Fred und sag mir dann, ob ers einbaut, sonst mach ich es
irgendwie! Aber halt leider noch nicht jetzt... Kann noch dauern.

[Stefan]

Freds Antwort:

it seems like a very good trick, i think i will impelement it