C/C++ Forum :: strlen nachbau (Versuch)

Unregistrierter

Hallo,

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

Assembler Code:
sub ecx, ecx sub al, al not ecx cld repne scasb not ecx dec ecx

Assembler Code:
sub ecx, ecx sub al, al not ecx cld repne scasb not ecx dec ecx

Assembler Code:
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!

Unregistrierter

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

nachtfeuer Mitglied 08:47:11 04.01.2012 Titel:

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.

Unregistrierter

Zitat:

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!

Unregistrierter

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:

Assembler Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43	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

Assembler Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43	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

Assembler Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43	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):

Assembler Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15	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

Assembler Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15	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

Assembler Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15	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... :confused:

DrakoXP Mitglied 22:45:49 04.01.2012 Titel:

du könntest ja das probieren:

Assembler Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49	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

Assembler Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49	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

Assembler Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49	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 ;-)

Unregistrierter

strlen schrieb:

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

Bin gerade verwirrt... :confused:

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.

Code:
mov rax,1234567891234

Code:
mov rax,1234567891234

Code:
mov rax,1234567891234

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

BTW: für x64 empfiehlt sich jWasm

Unregistrierter

@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!

Unregistrierter

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 (!).

Unregistrierter

Zitat:

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...?

Unregistrierter

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.

Unregistrierter

Vielen dank erneut!

DrakoXP Mitglied 05:13:05 05.01.2012 Titel:

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?

Unregistrierter

DrakoXP schrieb:

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

In diesem Zusammenhang ist es zu langsam.