Seite 2 von 3
Verfasst: 08.10.2006 23:51
von Helle
@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
Verfasst: 08.10.2006 23:54
von Hellhound66
Also ich denke trotzdem, dass:
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:
Verfasst: 09.10.2006 00:06
von Helle
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
Verfasst: 09.10.2006 00:34
von Hellhound66
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
Verfasst: 09.10.2006 08:41
von Helle
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
Verfasst: 09.10.2006 18:00
von Hellhound66
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 ^^.
Verfasst: 09.10.2006 19:21
von Kaeru Gaman
theoretisch kommen alle stringlängen gleich oft vor,
also würde ich austesten, welche routine mit Len%16=8 am schnellsten ist.
Verfasst: 10.10.2006 08:49
von Karl
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
Verfasst: 10.10.2006 12:37
von Hellhound66
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 -.-
Verfasst: 10.10.2006 12:43
von Kaeru Gaman
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.