Schneller Len(String$) Befehl

Helle · Beitrag von **Helle** » 08.10.2006 23:51

@Hellhound66: Gute Idee (mit jnc), aber je mehr Rücksprünge, desto langsamer wird das Ganze. Stringlängen von Vielfachen von 16 sind superschnell, danach wirds bis zum nächsten 16-er immer langsamer, und zwar wesentlich langsamer als die vorhandene Methode.

Gruss
Helle

Hellhound66 · Beitrag von **Hellhound66** » 08.10.2006 23:54

Also ich denke trotzdem, dass:

Code: Alles auswählen

@LOOP:
INC EBX
SHR EAX,1
JNC @LOOP
DEC EBX

schneller ist als

Code: Alles auswählen

!sub ebx,16                 ;Zeiger in String 16 Byte zurück und Ende suchen
W1:
 !mov eax,[ebx]              ;ab hier muss Byte-weise gesucht werden
 !test eax,0ffh
 !jz l_w2
 !inc ebx
 !test eax,0ff00h
 !jz l_w2
 !inc ebx
 !test eax,0ff0000h
 !jz l_w2
 !inc ebx
 !test eax,0ff000000h
 !jz l_w2
 !inc ebx
 !jmp l_w1
W2:

Helle · Beitrag von **Helle** » 09.10.2006 00:06

Ich hab´s ausprobiert, Alignments gesetzt, andere Abfragen - hat nicht überzeugt. Es sieht allerdings viel eleganter aus. Zum Selbertesten:

Code: Alles auswählen

;- Helle 08.10.2006 PB4.00
;- Zeigt Einsatz von SSE zur Ermittlung von Len(String)
;- Auf Feinheiten wie Überprüfung auf Verfügbarkeit und Sicherungen der Umgebung wurde verzichtet

Global X.l
Global Y.l
Global Len.l

Global String.s = "Ich bin ein fieser Teststaksjdfasdfkajslödfjaslkdjflöalöaksjdflkasjdlkfjasölkdfjlaksdjfing" 
;Global string.s = "Ich bin ein fieser Teststring"
 TestZeit.l  = ElapsedMilliseconds() 

 X = @String                 ;Zeiger auf den String

For i = 1 To 20000000 
 !mov ebx,[v_X]
W0: 
 !movdqu xmm0,[ebx]          ;16 Byte des Strings einlesen
 !add ebx,16
 !pxor xmm1,xmm1             ;xmm1 auf Null setzen
 !pcmpeqb xmm0,xmm1          ;jedes der 16 Byte von xmm0 mit Null (xmm1) vergleichen und auf 0 oder 255 (bei Gleichheit) setzen
 !pmovmskb eax,xmm0          ;die Vorzeichen-Bits der einzelnen Bytes nach eax kopieren 
 !or ax,ax                   ;auf Null testen. Waren in xmm1 Null-Bytes, ist ax nicht mehr Null  
 !jz l_w0                    ;weiter einlesen, wenn Null-Byte (String-Ende) noch nicht gefunden

 !sub ebx,16                 ;Zeiger in String 16 Byte zurück und Ende suchen
W1:                          
 !inc ebx                    ;das erste gesetzte Bit (= Null-Byte des Strings suchen)
 !shr ax,1
 !jnc l_w1                   ;weitersuchen, wenn Bit nicht gesetzt
 !dec ebx

 ;!mov eax,[ebx] 
 ;!test eax,0ffh 
 ;!jz l_w2
 ;!inc ebx
 ;!test eax,0ff00h
 ;!jz l_w2
 ;!inc ebx
 ;!test eax,0ff0000h
 ;!jz l_w2
 ;!inc ebx
 ;!test eax,0ff000000h
 ;!jz l_w2 
 ;!inc ebx 
 ;!jmp l_w1 
W2:
Next 

!mov [v_Y],ebx              ;"nur" für Anzeige der Stringlänge

Zeit = ElapsedMilliseconds() - TestZeit 

 !mov edx,[v_Y]
 !sub edx,[v_X]
 !mov [v_Len],edx    

MessageRequester("Len(String) mit SSE","Stringlänge = " + Str(Len) + Chr(13) + "Testzeit = " + Str(Zeit) + " ms")

End

Gruss
Helle

Hellhound66 · Beitrag von **Hellhound66** » 09.10.2006 00:34

Das hier wird dich aber freuen:

Code: Alles auswählen

;- Helle 08.10.2006 PB4.00
;- Zeigt Einsatz von SSE zur Ermittlung von Len(String)
;- Auf Feinheiten wie Überprüfung auf Verfügbarkeit und Sicherungen der Umgebung wurde verzichtet

Global X.l
Global Y.l
Global Len.l

Global String.s = "Ich bin ein fieser Teststaksjdfasdfkajslödfjasl"
;Global string.s = "Ich bin ein fieser Teststring"
TestZeit.l  = ElapsedMilliseconds()

X = @String                 ;Zeiger auf den String

For i = 1 To 60000000
    !MOV Ebx,[v_X]
    !pxor xmm1,xmm1             ;xmm1 auf Null setzen
    W0:
    !MOVDQU xmm0,[Ebx]          ;16 Byte des Strings einlesen
    !ADD Ebx,16
    !pcmpeqb xmm0,xmm1          ;jedes der 16 Byte von xmm0 mit Null (xmm1) vergleichen und auf 0 oder 255 (bei Gleichheit) setzen
    !pmovmskb Eax,xmm0          ;die Vorzeichen-Bits der einzelnen Bytes nach eax kopieren
    !OR Eax,Eax                   ;auf Null testen. Waren in xmm1 Null-Bytes, ist ax nicht mehr Null
    !JZ l_w0                    ;weiter einlesen, wenn Null-Byte (String-Ende) noch nicht gefunden
    
    !SUB Ebx,16                 ;Zeiger in String 16 Byte zurück und Ende suchen
    !BSF Edx,Eax
    !ADD Ebx,Edx
    
    W2:
Next

!MOV [v_Y],Ebx              ;"nur" für Anzeige der Stringlänge

Zeit = ElapsedMilliseconds() - TestZeit

!MOV Edx,[v_Y]
!SUB Edx,[v_X]
!MOV [v_Len],Edx   

MessageRequester("Len(String) mit SSE","Stringlänge = " + Str(Len) + Chr(13) + "Testzeit = " + Str(Zeit) + " ms")

End

Helle · Beitrag von **Helle** » 09.10.2006 08:41

Auch nicht schlecht

! Da mir die Bitsuch-Befehle aber ein Graus sind (Taktzyklen-Fresser, aber offensichtlich noch besser als viele kurze Rücksprünge - Pipeline?) habe ich folgendes probiert und siehe da, ist noch schneller:

Code: Alles auswählen

;- Helle 09.10.2006 PB4.00
;- Zeigt Einsatz von SSE zur Ermittlung von Len(String)
;- Auf Feinheiten wie Überprüfung auf Verfügbarkeit und Sicherungen der Umgebung wurde verzichtet

Global X.l
Global Y.l
Global Len.l

Global String.s = "Ich bin ein fieser Teststaksjdfasdfkajslödfjaslkdjflöalöaksjdflkasjdlkfjasölkdfjlaksdjfing" 

 TestZeit.l  = ElapsedMilliseconds() 

 X = @String                 ;Zeiger auf den String

For i = 1 To 20000000 
 !mov ebx,[v_X]
 !pxor xmm1,xmm1             ;xmm1 auf Null setzen, natürlich ausserhalb der Schleife
W0: 
 !movdqu xmm0,[ebx]          ;16 Byte des Strings einlesen
 !add ebx,16
 !pcmpeqb xmm0,xmm1          ;jedes der 16 Byte von xmm0 mit Null (xmm1) vergleichen und auf 0 oder 255 (bei Gleichheit) setzen
 !pmovmskb eax,xmm0          ;die Vorzeichen-Bits der einzelnen Bytes nach eax kopieren 
 !or eax,eax                 ;auf Null testen. Waren in xmm1 Null-Bytes, ist ax nicht mehr Null  
 !jz l_w0                    ;weiter einlesen, wenn Null-Byte (String-Ende) noch nicht gefunden

 !sub ebx,17                 ;Zeiger in String 17 Byte zurück und Ende suchen
 !test al,255
 !jnz l_w1
 !xchg ah,al
 !add ebx,8
W1: 
 !inc ebx                    ;das erste gesetzte Bit (= Null-Byte des Strings suchen)
 !shr ax,1
 !jnc l_w1                   ;weitersuchen, wenn Bit nicht gesetzt
Next 

!mov [v_Y],ebx              ;"nur" für Anzeige der Stringlänge

Zeit = ElapsedMilliseconds() - TestZeit 

 !mov edx,[v_Y]
 !sub edx,[v_X]
 !mov [v_Len],edx    

MessageRequester("Len(String) mit SSE","Stringlänge = " + Str(Len) + Chr(13) + "Testzeit = " + Str(Zeit) + " ms")

End

Gruss
Helle

Hellhound66 · Beitrag von **Hellhound66** » 09.10.2006 18:00

Jaein. Du hast den String deinem Testmuster angepasst ^^

Code: Alles auswählen

Global String.s = "Ich bin ein fieser Teststaksjdfasdfkajslödfjasl"

Dieser geht vom schlimmsten Fall aus Len%16=15. Probier da mal meine Variante, du wirst sehen, da ist sie schneller. Jetzt bleibt uns nur noch zu ermitteln, welche Strings relativ häufiger vorkommen, um sagen zu können, welche Methode sinnvoller ist ^^.

Kaeru Gaman · Beitrag von **Kaeru Gaman** » 09.10.2006 19:21

theoretisch kommen alle stringlängen gleich oft vor,
also würde ich austesten, welche routine mit Len%16=8 am schnellsten ist.

Karl · Beitrag von **Karl** » 10.10.2006 08:49

Für mich sehen beide Routinen nach n log n aus. Der Restunterschied ist marginal. Als "Beweis" verwende man einen sehr großen String (65000 Zeichen)

Gruß Karl

Hellhound66 · Beitrag von **Hellhound66** » 10.10.2006 12:37

Schon klar.
Wir reden ja nur über den Teil, der abläuft, wenn die 16-Bytesegmente des Strings abgelaufen sind. Also um den Teil, der das ganze ausbremst. Und da suchen wir optimale Verfahren. Der Kern beider Routinen ist ja gleich -.-

Kaeru Gaman · Beitrag von **Kaeru Gaman** » 10.10.2006 12:43

Kaeru Gaman hat geschrieben:theoretisch kommen alle stringlängen gleich oft vor,
also würde ich austesten, welche routine mit Len%16=8 am schnellsten ist.