Optimizer

Helle · Beitrag von **Helle** » 19.02.2005 14:08

Nachdem bisher die Multiplikation optimiert wurde nachfolgend ein Beispiel für die Division durch 5 bzw.10, basierend auf der Multiplikation
mit dem Reziprok-Wert. Ist fast doppelt so schnell!
Code:
;-------------------- Test Division ------------
!ALIGN 4

#N = 49999999

;-------------- herkömmliche Division durch 5 -----------------
a = 123450
b = 5
c = 0
time1 = ElapsedMilliseconds()
For z = 1 To #N
!MOV Eax,dword [v_a]
!MOV Edi,dword [v_b]
!CDQ
!IDIV Edi
!MOV dword [v_c],Eax
Next
time1 = ElapsedMilliseconds() - time1

;--------------------- optimierte Divison durch 5 ---------------
a = 123450
d = 0
time2 = ElapsedMilliseconds()
For z = 1 To #N
!MOV Eax,dword [v_a]
!MOV Edx,0cccccccdh
!MUL Edx
!SHR Edx,2
!MOV dword [v_d],Edx
Next
time2 = ElapsedMilliseconds() - time2

;---------------------- optimierte Divison durch 10 --------------
a = 123450
e = 0
time3 = ElapsedMilliseconds()
For z = 1 To #N
!MOV Eax,dword [v_a]
!MOV Edx,0cccccccdh
!MUL Edx
!SHR Edx,3
!MOV dword [v_e],Edx
Next
time3 = ElapsedMilliseconds() - time3

MessageRequester("", Str(time1)+" "+Str(time2)+" "+Str(time3))
Debug c
Debug d
Debug e

Stefan · Beitrag von **Stefan** » 19.02.2005 15:03

Hallo

@remi_meier

EDIT: ist das normal, dass LEA auch mit eax*3 also a*4 geht?

Der Code

Code: Alles auswählen

!LEA Eax,[Eax+Eax*3]

wird von FASM in

Code: Alles auswählen

!LEA Eax,[Eax*4]

übersetzt

Außerdem könnte man LEA noch mit einem shift kombinieren.
Beispiel:

Code: Alles auswählen

!LEA Eax,[Eax+Eax*4] ;\
!LEA Eax,[Eax+Eax*4] ; } Eax*100
!SHL Eax,2           ;/

@Helle
Wenn du willst, dass es mit negativen Zahlen auch funktioniert solltest du
IMUL anstatt von MUL und SAR anstatt von SHR benutzen.

Gruß
Stefan

Helle · Beitrag von **Helle** » 20.02.2005 09:43

@Stefan: Da ich in Assembler grundsätzlich nur unsign verwende habe ich mir hier keine weitere Gedanken gemacht (mein Fehler!). Nachdem ich mich eine geschlagene Stunde dann mit IMUL herumgeschlagen habe musste ich feststellen, das dies hier wohl nicht (sinnvoll) möglich ist. In der Erläuterung dieses Verfahrens wird auch ausdrücklich von unsign ge-
sprochen. Je nach verwendeten Zahlen treten bei sign Rundungsfehler
auf (es gibt hier keinen "Rest"!), die zeitaufwendig korrigiert werden müssten und damit den Vorteil dieser Routine wieder schmälern.
Solltest du eine Routine ohne diese Nachteile haben wäre ich sehr daran
interessiert!

Gruss
Helle

remi_meier · Beitrag von **remi_meier** » 20.02.2005 10:48

Danke Helle und Stefan!
Die Autooptimierung von /2 nach SAR 1 wurde früher vom PBCompiler gemacht, da das eben zu Problemen geführt hat, hat Fred es für die neue Beta entfernt. Nebenbei ist jetzt auch DEC drinne

Ich werd mal alles ausprobieren was ihr geschrieben habt!

bis bald
remi

remi_meier · Beitrag von **remi_meier** » 20.02.2005 11:20

Sry für den Doppelpost!
Das !ALIGN 4 hat bei mir irgendwie überhaupt keine Wirkung und macht auch keine Probleme

.
Und um es nochmals klar zu stellen, was soll ich jetzt reintun? Im Moment sind *3, *5, *9 drinn. Wenn jetzt das SAL auch draussen ist (habs nicht getestet), dann könnte vielleicht auch *4 mit LEA gemacht werden, denn irgendwie habe ich bei der Multiplikation keine Rundungsprobleme.

Tjo das wars
cu, remi

Helle · Beitrag von **Helle** » 26.04.2005 20:05

Hallo,
um dieses interessante Thema weiterzuführen stelle ich mal (in Absprache mit remi) nachfolgenden Code hier rein.
Sollte es jemand testen wäre eine Rückmeldung super

!

Code: Alles auswählen

;-------------------------- Setzen Alignment, K.Helbing, PureBasic 3.93, 26.04.2005 ---------------------------
;- Compilieren als FASM3.EXE, danach die Original-FASM.EXE (im Verzeichnis LW:\Programme\PureBasic\Compilers) - 
;----------- umbenennen in FASM2.EXE und FASM3.EXE umbenennen in FASM.EXE (alles im o.g.Verzeichnis) ----------
;- Alignment: Das Legen von CPU-Instruktionen (und auch Daten!) auf Speicheradressen, die ohne Rest durch 4 teilbar
;- sind (oder anderer Wert, der eine Zweier-Potenz sein muss; bei einem 32-Bit Betriebssystem aber sinnvollerweise
;- 4). Auf diese Speicheradressen kann effektiver zugegriffen werden als auf "ungerade", das Programm sollte also
;- schneller werden. Dies zeigt sich messbar natürlich nur bei etwas größeren Anwendungen (EXE!); ein Zehnzeiler in
;- einer (fast) Endlos-Schleife als Test ist Nonsens. Ein Schachprogramm lief ca.7-8% schneller.
;- Da es Unfug ist, jede CPU-Instruktion zu "alignmentieren", wurden in Programmen häufig vorkommende Instruktionen 
;- ausgewählt, die 4-oder 8-Byte langen OP-Code haben.   
;- Der Original-Source-Code wird nicht verändert. Bei Nichtgefallen einfach FASM2.EXE wieder in FASM.EXE umbenennen.
;- Großartige Sicherheitsabfragen (Datei überhaupt vorhanden?) werden nicht gemacht.  
;- Setzt Alignment nach - JMP
;-                      - RET
;-                 vor  - CMP WORD[MEM],WERT  bei WERT <80h  ist 8-Byte-Opcode 
;-                      - CMP [16-Bit-REG],WERT  ist 4-Byte-Opcode für Wert<80h
;-                      - MOV      "         "           "
;-                      - ADD      "         "           "
;-                      - SUB      "         "           "         für Wert<80h wenn nicht AX-Register
;-                      - ADC      "         "           "
;-                      - SBB      "         "           " 
;-                      - AND      "         "           "
;-                      - SHL      "         "           "         für Wert >1 
;-                      - SHR      "         "           "               "
;-                      - LEA in Verbindung mit [ESP+...]"   Alle ausser ESP+0 
;-                      - PUSH         "     "      "
;-                      - INC          "     "      "
;-                      - DEC          "     "      "
;-                      - FADD         "     "      "
;-                      - FLD          "     "      "
;-
;- Das Ersetzen von 3 NOP´s hintereinander durch z.B. LEA eax,dword[eax+0h] (8d4000h), ein "nichts ändernder
;- Befehl", brachte keine weiteren Vorteile (war mal ein Thema im Flat-Assembler-Forum).    


Global FILELAENGE.l
Global S1.l
Global S2.l
Global M1.l
Global M2.l
Global M3.l
Global M4.l
Global M5.l
Global M6.l
Global M7.l
Global M8.l
Global M9.l
Global M10.l
Global M11.l
Global M12.l
Global M13.l
Global M14.l
Global M15.l
Global M16.l
Global M17.l
Global M18.l
Global M19.l

Global INSTR.l
Global WT.b
Global WT1.b

  S1=$47494c41    ;ALIG
  S2=$0a34204e    ;N 4
  M1=$564f4d      ;MOV    Leerzeichen werden unten auf Null gesetzt!
  M2=$44524f57    ;WORD
  M3=$504d43      ;CMP
  M4=$434e49      ;INC
  M5=$434544      ;DEC
  M6=$434441      ;ADC
  M7=$424253      ;SBB
  M8=$504d4a      ;JMP
  M9=$0a544552    ;RET
  M10=$444441     ;ADD
  M11=$4c4853     ;SHL
  M12=$524853     ;SHR
  M13=$425553     ;SUB
  M14=$0b505345   ;ESP+
  M15=$41454c     ;LEA 
  M16=$48535550   ;PUSH
  M17=$444e41     ;AND 
  M18=$44444146   ;FADD
  M19=$444c46     ;FLD 
  
     CopyFile("PureBasic.asm","OldPureBasic.asm")     ;für Testzwecke, kann entfallen

     OpenFile(1,"PureBasic.asm")
           FILELAENGE=Lof()
     CloseFile(1) 
     
              ;----------------------- RAM-Speicher für direkten Zugriff reservieren ----------------------
     *MemoryID = AllocateMemory(FILELAENGE+100000)    ;100000 Bytes für "ALIGN 4" (nach Bedarf anpassen)
    
     If *MemoryID=0 
         Debug "Konnte den angeforderten Speicher nicht reservieren!"     ;mehr für Testzwecke
         End  
     EndIf 

     ReadFile(1,"PureBasic.asm")
           ReadData(*MemoryID,FILELAENGE)
     CloseFile(1)

              PUSHAD 
              MOV esi,*MemoryID        ;ESI ist damit tabu!
              MOV ebx,1h               ;evtl. Test auf "Main" o.ä. für grösseren Wert, ist aber nicht relevant
              MOV edx,0dfdfdfdfh       
SEARCH:       MOV al,[esi+ebx-1h]
              CMP al,41h               ;wegen z.B. PAND, FIADD und ähnlichen möglichen Fehlinterpretationen 
              JAE l_nofound 
              MOV eax,[esi+ebx]
              AND eax,edx              ;Kleinbuchstaben-Bit löschen, Leerzeichen wird Null!  
              MOV INSTR,eax            ;für z.B. Test ob WORD      
              MOV edi,ebx              ;ist die eventuelle Einfüge-Stelle
           
              CMP eax,M18              ;FADD
              JE l_voradd3             ;Test auf esp+
              CMP eax,M19              ;FLD
              JE l_voradd3
              CMP eax,M8               ;JMP  
              JE l_nachjmp
              CMP eax,M9               ;RET
              JE l_nachjmp
              CMP eax,M3               ;CMP
              JE l_vorcmp
              CMP eax,M10              ;ADD
           JE l_vorcmp   
              ;JE l_voradd             ;mögliche Variationen, um Ergebnis evtl. zu verbessern (auch komplettes
                                       ; Weglassen von Abfragen möglich)
              CMP eax,M1               ;MOV
              JE l_voradd
              CMP eax,M11              ;SHL
              JE l_vorshift
              CMP eax,M12              ;SHR
              JE l_vorshift
              CMP eax,M13              ;SUB
           JE l_vorcmp  
              ;JE l_voradd
              CMP eax,M6               ;ADC
           ;JE l_vorcmp  
              JE l_voradd              
              CMP eax,M7               ;SBB
           ;JE l_vorcmp  
              JE l_voradd              
              CMP eax,M15              ;LEA
              JE l_voradd3
              CMP eax,M16              ;PUSH
              JE l_voradd3
              CMP eax,M4               ;INC
              JE l_voradd3
              CMP eax,M5               ;DEC
              JE l_voradd3
              CMP eax,M17              ;AND
           JE l_vorcmp 
              ;JE l_voradd
            
              JMP l_nofound

       ;----------------------- Align nach einem JMP oder RET einfügen -----------------------------------
NACHJMP:      INC ebx
              MOV al,[esi+ebx]
              CMP al,0ah               ;Ende der Zeile?
              JNE l_nachjmp            ;nein
              INC ebx
              MOV edi,ebx       
              JMP l_found

       ;---------------- Align vor div.Instruktionen bei bestimmten Konstellationen ----------------------
VORCMP:       CALL l_wordtest
              XOR ecx,ecx              ;für Werttest
              CMP WT,cl                ;Null?
              JE l_voradd2             ;kein Word, nächster Test
           ;------------------ ist WORD ----------------------------       
NOKLAMMER:    INC ebx
              MOV al,[esi+ebx]              
              CMP al,5bh               ;[
              JNE l_noklammer
NOKLAMMER1:   INC ebx
              MOV al,[esi+ebx]               
              CMP al,20h
              JE l_noklammer1          ;Leerzeichen
              CMP al,5fh               ;_  als Kennung für Variable
              JE l_werttest      
              CMP al,5dh               ;]
              JE l_nofound      
              JMP l_noklammer1

WERTTEST:     INC ebx
              MOV al,[esi+ebx]
              CMP al,2ch               ;Komma
              JNE l_werttest  
WERTTEST1:    INC ebx
              MOV al,[esi+ebx]
WERTTEST3:    CMP al,30h               ;Leerzeichen oder führende Nullen
              JBE l_werttest1
WERTTEST2:    CMP al,0ah
              JE l_auswertungd
              CMP al,68h               ;h
              JE l_auswertungh
              CMP al,48h               ;H
              JE l_auswertungh
              CMP al,20h
              JE l_werttest4           ;für dez bis Zeilenende     
              SHL ecx,8h
              MOV cl,al

WERTTEST4:    INC ebx
              MOV al,[esi+ebx]
              JMP l_werttest2       

AUSWERTUNGH:  TEST ecx,0ffff0000h
              JNZ l_nofound
              CMP ch,38h
              JAE l_nofound
              JB l_found
  
AUSWERTUNGD:  TEST ecx,0ff000000h
              JNZ l_nofound
              CMP ch,39h
              JA l_nofound             ;Register             
              MOV eax,ecx
              SHR eax,8h
              CMP ah,31h
              JA l_nofound
              JB l_found
              CMP ch,32h
              JA l_nofound
              JB l_found
              CMP cl,38h
              JAE l_nofound
              JMP l_found
;------------------------ Ende Werttest ----------------------------------------------

VORADD:       ADD ebx,3h
VORADD1:      INC ebx
VORADD2:      MOV al,[esi+ebx]              
              AND al,dl
              JZ l_voradd1
              MOV WT,al      
              INC ebx
              MOV al,[esi+ebx]         ;Test auf 2.Buchstaben
              CMP al,5fh               ;_  Variablen aussieben   
              JE l_nofound        
              AND al,dl
              MOV WT1,al     
              CMP al,58h               ;X? für AX.BX,CX,DX
              JE l_isregister
              CMP al,49h               ;I? für DI,SI
              JE l_isregister
              CMP al,50h               ;P? für BP
              JE l_isregister

;-------------------------------------- Suche nach ESP+Wert, Wert>0 ------------       
VORADD3:      INC ebx
              MOV eax,[esi+ebx]              
              CMP al,0ah
              JE l_nofound
              AND eax,edx
              CMP eax,M14              ;ESP+?
              JNE l_voradd3            
              ADD ebx,3h
VORADD4:      INC ebx
              MOV al,[esi+ebx]
              CMP al,5dh               ;]
              JE l_nofound             
              CMP al,31h               
              JAE l_found              ;grösser Null   
              JMP l_voradd4     

ISREGISTER:   INC ebx
              MOV al,[esi+ebx]
              CMP al,30h               ;Leerzeichen, Komma, Null
              JB l_isregister
              JE l_isregister1   
              CMP al,39h
              JA l_nofound
ISREGISTER1:  MOV ecx,INSTR
              CMP ecx,M1               ;MOV?
              JE l_found               ;kein Werttest
              CMP WT,41h
              JE l_found               ;ist AX-Register  DX???
              ;CMP WT,44h               ;nochmal in Ruhe anschauen, ob lohnend
              ;JNE l_isregister3     
              ;CMP WT1,58h
              ;JE l_found      
             
ISREGISTER3:  XOR ecx,ecx
              JMP l_werttest3        
            
VORSHIFT:     CALL l_wordtest
              CMP WT,1h
              JNE l_vorshift2 
              ADD ebx,3h
              JMP l_found

VORSHIFT1:    INC ebx
VORSHIFT2:    MOV al,[esi+ebx]              
              CMP al,5fh               ;_  Variablen aussieben    Klammer? Sollte hier egal sein
              JE l_nofound             
              AND al,dl
              JZ l_vorshift1
              INC ebx
              MOV al,[esi+ebx]         ;Test auf 2.Buchstaben
              AND al,dl
              CMP al,58h               ;X? für AX.BX,CX,DX
              JE l_isregister2
              CMP al,49h               ;I? für DI,SI
              JE l_isregister2
              CMP al,50h               ;P? für BP
              JNE l_nofound

ISREGISTER2:  INC ebx
              MOV al,[esi+ebx]
              CMP al,2ch               ;Leerzeichen, Komma
              JBE l_isregister2
              INC ebx
              CMP al,31h  
              JE l_nofound             ;1-er Shifts haben eigenen Opcode!
              CMP al,39h               ;Test nicht für Wert, sondern auf Register!
              JA l_nofound
                          
       ;-------------------------- was lohnenswertes (hoffentlich!) gefunden -----------------------------                      
FOUND:        ADD FILELAENGE,8h        ;für 1x ALIGN wird die Datei 8 Byte länger
              INC ebx
       ;---------------------------- Restdatei nach "hinten" verschieben ---------------------------------      
              MOV ecx,FILELAENGE
              SUB ecx,4h
SCHIEBEN:     MOV eax,dword[esi-8h+ecx]
              MOV dword[esi+ecx],eax
              SUB ecx,4h
              CMP ecx,edi
              JAE l_schieben 
      
       ;----------------------------- "ALIGN 4" einfügen mit LF ------------------------------------------
              MOV eax,S1
              MOV [esi+edi],eax
              MOV eax,S2
              MOV dword[esi+4h+edi],eax
                  
       ;----------------------------------- Rest der Datei -----------------------------------------------
NOFOUND:      INC ebx
              CMP ebx,FILELAENGE
              JB l_search
              POPAD
                                          
              JMP l_fertig
              
;-------------------------------------- Unterprogramme ---------------------------------------------------
WORDTEST:     MOV WT,0h
              ADD ebx,3h
LEERW:        INC ebx
              MOV eax,[esi+ebx]              
              AND eax,edx
              OR al,al
              JE l_leerw
                      
              CMP eax,M2               ;WORD
              JNE l_nofound1
              MOV WT,1
NOFOUND1:     RET 

FERTIG:
  
   OpenFile(0,"PureBasic.asm")
   WriteData(*MemoryID,FILELAENGE)
   CloseFile(0)
   
   CopyFile("PureBasic.asm","AlignPureBasic.asm")     ;für Testzwecke, kann entfallen 

   RunProgram("FAsm2.exe", "PureBasic.asm PureBasic.obj", "", 1)

End

Gruss
Helle

dige · Beitrag von **dige** » 27.04.2005 08:29

Habs mal getestet mit einem umfangreichen Programm (16.000 LoC)
Die Exe wurde etwas größer und die Programm ausführung ca. 5%
langsamer ... Schade eigentlich ...

Helle · Beitrag von **Helle** » 02.05.2005 19:28

Wirklich schade

, zeigt aber wohl auch das (mein) Problem: Ich habe diesen Zusatz für mein Testprogramm geschrieben; d.h. die "normale" EXE mit einem Disassembler durchforstet und das Alignment-Setzen darauf ausgerichtet. Erfolg: Gut 7% schneller. Die Grösse der EXE-Datei stieg von 132KB auf 133KB (um ca.1300Byte), dies sind die eingefügten NOP´s. Da mir klar ist, das dies Schmoren im eigenen Saft ist, hatte ich das Web nach rel. grossen PB-Dateien für Tests durchforstet. Ergebnis: Absolut Null. Deshalb habe ich hier mehr Testergebnisse erhofft, um evtl. das Programm zu erweitern (also mehr OP-Codes zu berücksichtigen). Vielleicht kann mir jemand Quellen für (grosse) brauchbare Test-Dateien nennen?

Gruss
Helle

Stefan · Beitrag von **Stefan** » 04.05.2005 16:58

Stefan hat geschrieben: Hi remi_meier
Man könnte auch noch ein paar einfache Funktionen optimieren:
Beispiele:
Code: Alles auswählen
Call PB_PokeL 
durch 
Pop dword[Eax] 
Code: Alles auswählen
Call PB_PeekL 
durch 
Mov Eax,[Eax] 
Code: Alles auswählen
Call PB_CallFunctionFast? 
durch 
Call Eax 
Hier noch ein Link für die Optimierung von Multiplikationen:
http://www.azillionmonkeys.com/qed/amultl1.html
Gruß
Stefan

Gruß
Stefan

remi_meier · Beitrag von **remi_meier** » 04.05.2005 19:30

@Stefan:
Ouu ja!
Hab ich wohl übersehen!
Aber im Moment hab ich sowieso wenig Zeit, musst dich also noch ein wenig gedulden..

@Helle:
Ja wirklich schade.. Aber irgendwas muss doch gehen, und zwar immer! Nur was...

greetz
Remi