strlen nachbau (Versuch)

Hallo,

ich habe versucht, "strlen" nachzubauen.
Habe in groben den Code von http://www.int80h.org/strlen/ genommen, das ist im Prinzip dieser:

sub	ecx, ecx
sub	al, al
not	ecx
cld
repne	scasb
not	ecx
dec	ecx

Dann habe ich meine Funktion, sowie die "Standard"-strlen-Funktion 100000000 mal aufgerufen um die Geschwindigkeit zu vergleichen.
Dabei ist meine Funktion sehr viel langsamer, warum ist das so?
Wie ist strlen implementiert, dass es so viel schneller ist?

Benutze Windows 7 64bit (ist aber eine 32bit Anwendung), Visual Studio.

Danke!

http://www.strchr.com/optimized_strlen_function (siehe auch die Links!)

nachtfeuer

scas ist nicht die schnellste Variante, guck die mal den optimierten Code auf der Seite von agner.org an ( http://www.agner.org/optimize/#manuals )

Außerdem sieht man auch nicht wirklich, wie deine Wiederholungsschleifen aufgebaut sind, welche Registerabhängigkeiten da sind, welche Parallelisierungsfallen usw., das dürfte auch eine Rolle spielen, und natürlich, dass man auf Alignment achten muß usw. Ein typisches Beispiel dafür, das gewisse Kenntnisse nicht ausreichen, um performant in Assembler zu programmieren. Außerdem kann man sich noch die Frage stellen, ob man wirklich Bytweise durchsteppen muß. Speicherzugriffe sind eben langsam...
Probier auch mal aus, was passiert, wenn du die scas Funktion nachbaust, um gleich mehrere Bytes auf einmal aus dem Speicher zu lesen (nach RAX) um dann mit logischen Operationen in RAX weiterzumachen und Flags testen usw.

Ein typisches Beispiel dafür, das gewisse Kenntnisse nicht ausreichen, um performant in Assembler zu programmieren

Wenn es nicht so wäre, würde ich die Frage nicht stellen
Ich weiß, dass meine Assembler-Kenntnisse noch am Anfang sind, deshalb interessiert es mich ja, wie man solche Probleme bestmöglichst löst.

Danke euch auf jedenfall schon einmal für die Links, werde mir das mal anschauen!

So, wunderbar, ist jetzt ca. gleich schnell wie die originale Funktion.
Aber jetzt das nächste Problem, wollte dafür keinen neuen Thread aufmachen:
So sieht mein Code für x86 / Ansi aus:

push	EBP
mov	EBP, ESP

push	ECX
push	ESI

xor	EAX, EAX
xor	ECX, ECX

mov	ESI, string

Loop1:
lodsd

inc	ECX
test	EAX, 0FFh
je	End

inc	ECX
test	EAX, 0FF00h
je	End

inc	ECX
test	EAX, 0FF0000h
je	End

inc	ECX
test	EAX, 0FF000000h
je	End

jmp	Loop1

End:
dec	ECX

mov	EAX, ECX

pop	ESI
pop	ECX

mov	ESP, EBP
pop	EBP
ret

Für x64 habe ich folgende Zeilen eingefügt (natürlich nur im groben, der Rest ist momentan nicht relevant):

inc	RCX
test	RAX, 0FF00000000h
je	Ende

inc	RCX
test	RAX, 0FF0000000000h
je	Ende

inc	RCX
test	RAX, 0FF000000000000h
je	Ende

inc	RCX
test	RAX, 0FF00000000000000h
je	Ende

Das findet ml64.exe nicht so toll und sagt bei allen Vieren "constant value too large"...

Bin gerade verwirrt...

DrakoXP

du könntest ja das probieren:

push    EBP
mov    EBP, ESP

push    EBX ; neu
push    ECX
push    ESI

xor    EAX, EAX
xor    ECX, ECX

mov    ESI, string

Loop1:
lodsd

inc    ECX
mov    EBX, 0FFh ; neu
test    EAX, EBX
je    End

inc    ECX
shl     EBX, 16
test    EAX, EBX
je    End

inc    ECX
shl     EBX, 16
test    EAX, EBX
je    End

inc    ECX
shl     EBX, 16
test    EAX, EBX
je    End

jmp    Loop1

End:
dec    ECX

mov    EAX, ECX

pop    ESI
pop    ECX
pop    EBX ; neu

mov    ESP, EBP
pop    EBP
ret

bin mir leider gerade nicht sicher, ob test auch ein register als rechten Operanden annimmt...
aber wenn, dann würde das in dem Stil sicher auch mit RAX und RBX klappen...
dann meckert zumindest ml64 nicht wegen zu großer Literale

strlen schrieb:

Das findet ml64.exe nicht so toll und sagt bei allen Vieren "constant value too large"...

Bin gerade verwirrt...

Bei dem x86-x64 Befehlssatz können Immediates maximal 32 Bit groß sein. Einzige Ausnahme ist MOV, bei dem 64Bit Werte verwendet werden können.

mov rax,1234567891234

Wenn du schon auf x64 umsteigst, kannst du auch gleich SSE2 verwenden.

BTW: für x64 empfiehlt sich jWasm

@DrakoXP:
Ja, test REGISTER, REGISTER ist möglich.
Das wäre natürlich eine Lösung, wenn auch keine "saubere"

@masm:
Hm...das ist natürlich lästig...woran liegt die 32bit Grenze?
jWasm werde ich mir bei gelegenheit mal anschauen, bin bis jetzt aber mit masm ganz zufrieden, wahrscheinlich da es so schön in Visual Studio integriert ist

SSE2... hab ich dran gedacht, allerdings bin ich da noch ungefähr bei 0...außerdem dachte ich, dass SSE in diesem Fall nicht unbedingt viel bringen würde, da die berechnung doch meistens aufgrund der Stringlänge relativ kurz ist...
Aber ich werde es auf jedenfall mal ausprobieren, da ich SSE sowieso mal näher kommen wollte.

Danke euch!

strlen schrieb:

@DrakoXP:
Ja, test REGISTER, REGISTER ist möglich.
Das wäre natürlich eine Lösung, wenn auch keine "saubere"

Es wäre die Beste Lösung, wenn da nicht noch das SHL wäre.

strlen schrieb:

Hm...das ist natürlich lästig...woran liegt die 32bit Grenze?

Um die Befehlsgröße klein zu halten. Außerdem braucht man 64Bit Werte nur sehr selten – da tut es dann auch ein Speicher-Operand.
Ansonsten mal bei AMD anrufen und nachfragen

strlen schrieb:

außerdem dachte ich, dass SSE in diesem Fall nicht unbedingt viel bringen würde, da die berechnung doch meistens aufgrund der Stringlänge relativ kurz ist

Da ist was dran – eine einfache, abgerollte Schleife die BYTE für BYTE arbeitet, ist für kurze Strings absolut ausreichend. Mal davon abgesehen, muss man sich bei BYTE-Scannern keine Gedanken um das algiment und mögliche Seitenfehler machen (!).

Das wäre natürlich eine Lösung, wenn auch keine "saubere"

Mein Fehler, das bezog sich auf das SHL...

Okay, werde mir SSE aber trotzdem mal ansehen, nur zum testen.
Was hat es eigentlich mit dem "algiment" auf sich. Ich lese immer nur, dass darauf zu achten sei, aber nicht wieso und nach welchen Kriterien...?

http://de.wikipedia.org/wiki/Speicherausrichtung
Als grobe Faustregel gilt:
Bei Datentypen <= 8 Byte entsprechend ihrer Größe ausrichten. Bei allen Anderen nach 16 ausrichten.

Vielen dank erneut!

DrakoXP

masm schrieb:

strlen schrieb:

@DrakoXP:
Ja, test REGISTER, REGISTER ist möglich.
Das wäre natürlich eine Lösung, wenn auch keine "saubere"

Es wäre die Beste Lösung, wenn da nicht noch das SHL wäre.

Hier muss ich nochmal nachfragen.
Was ist an shl so schlimm? Zu langsam?

DrakoXP schrieb:

Hier muss ich nochmal nachfragen.
Was ist an shl so schlimm? Zu langsam?

In diesem Zusammenhang ist es zu langsam.