PureBoard

Das deutsche PureBasic-Forum
https://www.purebasic.fr/german/

String Translate

https://www.purebasic.fr/german/viewtopic.php?t=20282

Seite 2 von 3

Verfasst: 21.06.2009 18:50
von Little John
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

Verfasst: 21.06.2009 18:59
von cxAlex
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.

Verfasst: 21.06.2009 19:02
von Kaeru Gaman
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.

Verfasst: 22.06.2009 09:18
von PeterJ
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

Verfasst: 22.06.2009 10:05
von PeterJ
Seltsam, bei mir sind die Differenzen viel gavierender:

Translate1: 9390 ms
Translate2: 594 ms

Verfasst: 22.06.2009 14:24
von Kaeru Gaman
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?

Verfasst: 22.06.2009 15:45
von PeterJ
Kaeru Gaman hat geschrieben:hast du ein 64bit OS?
Nein gutes altes XP 32, werde es Zuhause nochmal probieren!

Verfasst: 22.06.2009 18:27
von PeterJ
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

Verfasst: 22.06.2009 20:38
von Little John
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()

Verfasst: 22.06.2009 21:09
von cxAlex
Meine Werte nun:

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

Also etwa 3x so schnell.
Alle Zeiten sind UTC+02:00
Seite 2 von 3

Powered by phpBB® Forum Software © phpBB Limited

Deutsche Übersetzung durch phpBB.de