String Translate

Little John · Beitrag von **Little John** » 21.06.2009 18:50

Ich habe jetzt mal die erste Möglichkeit weggelassen, da das ohnehin klar die langsamste war, und dann die Anzahl der Wiederholungen deutlich erhöht:

Code: Alles auswählen

; getestet mit PB 4.31 unter Windows XP

EnableExplicit

Procedure Translate1 (*text, textLen, Array trans.b(1))
   Protected *textPtr.Byte

   ; iterate through memory and replace bytes
   For *textPtr = *text To *text + textLen - 1
      *textPtr\b = trans(*textPtr\b)
   Next
EndProcedure


Procedure Translate2 (*text, textLen, *trans)
   ; iterate through memory and replace bytes
   ! mov   edx, [p.p_text]
   ! mov   ecx, [p.v_textLen]
   ! mov   eax, [p.p_trans]
   ! push  ebx
   ! mov   ebx, eax

 ! TransLoop:
   ! mov   al,  [edx+ecx]
   ! xlatb
   ! mov   [edx+ecx], al
   ! loop  TransLoop
   ! pop   ebx
EndProcedure


;-- Demo
Define n, i, t
Define old$, new$, s$

n = 500000     ; Anzahl der Schleifen (evtl. je nach PC verkleinern oder vergrößern)

old$ = "123456789"
new$ = "ABCDEFGHI"

; build translation table
Dim trans.b(255)
For i = 0 To 255
   trans(i) = i
Next
For i = 1 To Len(old$)
   trans(Asc(Mid(old$,i,1))) = Asc(Mid(new$,i,1))
Next

OpenConsole()

; translate string (1)
s$ = "Record 1; Record 2; Record 3; Record 4; Record 5; Record 6; Record 7; Record 8; Record 9"
t = ElapsedMilliseconds()
For i = 1 To n
   Translate1(@s$, Len(s$), trans())
Next
t = ElapsedMilliseconds() - t
PrintN("'" + s$ + "'" + #LF$ + Str(t) + " ms")

; translate string (2)
s$ = "Record 1; Record 2; Record 3; Record 4; Record 5; Record 6; Record 7; Record 8; Record 9"
t = ElapsedMilliseconds()
For i = 1 To n
   Translate2(@s$, Len(s$), @trans(0))
Next
t = ElapsedMilliseconds() - t
PrintN("'" + s$ + "'" + #LF$ + Str(t) + " ms")

Input()

Dabei erhalte ich wiederholt Ergebnisse wie etwa die folgenden:
Translate1() 406 ms
Translate2() 266 ms

Also ist Translate2() wohl doch schneller. Ich weiß aber nicht, wie weit die Ergebnisse eines Tests mit 1/2 Million Wiederholungen relevant für die Praxis sind.

Gruß, Little John

cxAlex · Beitrag von **cxAlex** » 21.06.2009 18:59

Ich bekomme folgende Ergebnisse:

Translate1(): 171 ms
Translate2(): 125 ms

weniger als 50 ms auf 500.000 Wiederholungen Differenz entspicht etwa 0.1 µS/Call Differenz, glaube kaum das sich da so großartig Speed holen lässt.

Kaeru Gaman · Beitrag von **Kaeru Gaman** » 21.06.2009 19:02

so langsam werden die Werte ja schon aussagekräftiger...

generell würde ich empfehlen, Messbereiche von 3-10 Sekunden zu wählen.
je länger die Messung, desto weniger fällt die 16ms TimeSlice ins Gewicht.

PeterJ · Beitrag von **PeterJ** » 22.06.2009 09:18

Eine kleine Korrektur zum Look up Ansatz:

Code: Alles auswählen

MyBuffer.s="Record 1; Record 2; Record 3" 
; 
; Set full ASCII character set  
Global Dim trfull.b(255) 
For i = 0 To 255 
    TRFULL(i)=i 
Next 
; Now change the characters to replace 
trfull(Asc("1"))=Asc("A") 
trfull(Asc("2"))=Asc("B") 
trfull(Asc("3"))=Asc("C") 
; run through buffer and replace it's character as defined in translation table 
*ptr.BYTE 
*ptr=@MyBuffer 
slen=Len(MyBuffer)  
For i = 0 To slen    ; Ende Bedingung !
   *ptr\b=trfull(*ptr\b) 
   *ptr+1 
Next 
Debug MyBuffer

Ich habe die Endebedingung (LEN(MyBuffer)) rausgenommen, da ja statisch! Dabei habe ich eine enorme Beschleunigung bei großen Stringbuffern (10 MB u.m.) erlebt. Ich habe die Vermutung die LEN funktion zählt den String durch bis es das X'00' Byte findet. Bei kleinen Strings fällt das natürlich nicht ins Gewicht.
Es schaut so aus als wenn die Ende Bedingung jedesmal neu "berechnet" wird, also nicht statisch ist, was ja auch Sinn macht. D.h. die LEN() Funktion wird für jedes Byte neu ermittelt.
Den ASM werde ich mal testen!

Peter

PeterJ · Beitrag von **PeterJ** » 22.06.2009 10:05

Seltsam, bei mir sind die Differenzen viel gavierender:

Translate1: 9390 ms
Translate2: 594 ms

Kaeru Gaman · Beitrag von **Kaeru Gaman** » 22.06.2009 14:24

ich meine mal gelesen zu haben, dass die ende bedingung nicht neu berechnet wird...
bin mir aber jetzt nicht sicher.

> Seltsam, bei mir sind die Differenzen viel gavierender:

hast du ein 64bit OS?

PeterJ · Beitrag von **PeterJ** » 22.06.2009 15:45

Kaeru Gaman hat geschrieben:hast du ein 64bit OS?

Nein gutes altes XP 32, werde es Zuhause nochmal probieren!

PeterJ · Beitrag von **PeterJ** » 22.06.2009 18:27

cxAlex hat geschrieben:Das ganze mit Debugger zu testen bringt gar nix:

Tja, das hatte ich überlesen, ausgeschaltet schaut es nun so aus:

Translate1: 468 ms
Translate2: 250 ms

Little John · Beitrag von **Little John** » 22.06.2009 20:38

Ich habe jetzt beide

Prozeduren noch etwas beschleunigt.

Translate1():
Ich hatte gedacht, PB würde den Endwert der Schleife

Code: Alles auswählen

*text + textLen - 1

nur 1x berechnen, und das Ergebnis zum wiederholten Vergleich intern temporär zwischenspeichern. Das ist anscheinend nicht der Fall, daher bringt es eine Beschleunigung wenn man den Wert selbst 1x vor Beginn der Schleife ausrechnet und in einer Variablen speichert.

Translate2():
Auf http://www.agner.org/optimize/ habe ich gelesen, dass folgende Anweisung

Code: Alles auswählen

! loop

nicht so schnell ist. Daher habe ich sie ersetzt durch

Code: Alles auswählen

! dec   ecx
! jnz   again

Typische Messergebnisse auf meinem System sind nun
Translate1(): 375 ms
Translate2(): 140 ms

D.h. während die ASM-Prozedur vorher ca. 1,5x so schnell war wie die PB-Prozedur, beträgt der Faktor nun immerhin ca. 2,6.

Gruß, Little John

//edit 2009-06-23: Fehler in der ASM-Prozedur korrigiert!

Code: Alles auswählen

; getestet mit PB 4.31 unter Windows XP

EnableExplicit

Procedure Translate1 (*text, textLen, Array trans.b(1))
   Protected *last, *textPtr.Byte

   ; iterate through memory and replace bytes
   *last = *text + textLen - 1
   For *textPtr = *text To *last
      *textPtr\b = trans(*textPtr\b)
   Next
EndProcedure


Procedure Translate2 (*mem, memSize, *trans)
   ; -- Iterate through memory and replace bytes.
   ; in: *mem   : Zeiger auf Beginn des zu verändernden Speicherbereichs
   ;     memSize: Anzahl zu verändernder Bytes (muss mindestens 1 sein)
   ;     *trans : Zeiger auf eine Nachschlagetabelle, die für jeden
   ;              der 256 Byte-Werte den "Ersatzwert" enthält

   ! mov   edx, [p.p_mem]
   ! dec   edx
   ! mov   ecx, [p.v_memSize]
   ! mov   eax, [p.p_trans]
   ! push  ebx
   ! mov   ebx, eax

 ! TranslateAgain:
   ! mov   al, [edx+ecx]
   ! xlatb
   ! mov   [edx+ecx], al
   ! dec   ecx
   ! jnz   TranslateAgain

   ! pop   ebx
EndProcedure


;-- Demo
Define n, i, t
Define old$, new$, s$

n = 500000     ; Anzahl der Schleifen (evtl. je nach PC verkleinern oder vergrößern)

old$ = "123456789"
new$ = "ABCDEFGHI"

; build translation table
Dim trans.b(255)
For i = 0 To 255
   trans(i) = i
Next
For i = 1 To Len(old$)
   trans(Asc(Mid(old$,i,1))) = Asc(Mid(new$,i,1))
Next

OpenConsole()

; translate string (1)
s$ = "Record 1; Record 2; Record 3; Record 4; Record 5; Record 6; Record 7; Record 8; Record 9"
t = ElapsedMilliseconds()
For i = 1 To n
   Translate1(@s$, Len(s$), trans())
Next
t = ElapsedMilliseconds() - t
PrintN("'" + s$ + "'" + #LF$ + Str(t) + " ms")

; translate string (2)
s$ = "Record 1; Record 2; Record 3; Record 4; Record 5; Record 6; Record 7; Record 8; Record 9"
t = ElapsedMilliseconds()
For i = 1 To n
   Translate2(@s$, Len(s$), @trans(0))
Next
t = ElapsedMilliseconds() - t
PrintN("'" + s$ + "'" + #LF$ + Str(t) + " ms")

Input()

cxAlex · Beitrag von **cxAlex** » 22.06.2009 21:09

Meine Werte nun:

Translate1(): 172 ms
Translate2(): 47 ms

Also etwa 3x so schnell.