Seite 5 von 10
Verfasst: 10.06.2005 19:13
von 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:
P.S.: Mein fünfzigster Beitrag 
Gruß
Stefan
Verfasst: 10.06.2005 19:29
von 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!
Verfasst: 10.06.2005 19:41
von 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.
Verfasst: 12.06.2005 11:56
von 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
Verfasst: 12.06.2005 13:36
von 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
Verfasst: 12.06.2005 14:15
von 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
Verfasst: 12.06.2005 14:33
von 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
Verfasst: 12.06.2005 16:29
von 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
Verfasst: 12.06.2005 17:01
von 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.
Verfasst: 12.06.2005 18:30
von Stefan
Freds Antwort:
Fred hat geschrieben:it seems like a very good trick, i think i will impelement it