Entwickler-Ecke
Algorithmen, Optimierung und Assembler - GetNumberOfChars(str : string; chr : char) : Integer ?
sky21 - Do 30.04.09 11:23
Titel: GetNumberOfChars(str : string; chr : char) : Integer ?
Ich bin Programmierer und deshalb faul ;-) Weshalb gibt es nicht bereits eine Systemfunktion, welche mir bei einem String die Anzahl gesuchter Elemente zurück gibt? Ich habe zumindest nichts brauchbares in dieser Richtung gefunden.
Delphi-Quelltext
1: 2: 3: 4:
| Inputstring = 'halloWelt'; SearchChar := 'l'; res := GetNumberOfChars(Inputstring, SearchChar); |
Muss man wirklich immer alles selber machen? Ok, Anstatt Zeit für diesen Beitrag aufzuwenden, hätte man diese auch gleich benutzen können, die Funktion selber zu schreiben, harr harr.
Moderiert von AXMD: Delphi-Tags hinzugefügtModeriert von Narses: Topic aus Sonstiges (Delphi) verschoben am Do 30.04.2009 um 17:00
thepaine91 - Do 30.04.09 12:20
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7:
| function TForm1.SubstringFinden(const Text, Suchstring: String): integer; var i, Anzahl: integer; begin Anzahl := 0; for i := 1 to length(Text) - length(Suchstring) +1 do if copy(Text, i, length(Suchstring)) = Suchstring then inc(Anzahl);end; |
damit du faul bleiben kannst ^^ aber wenns da doch eine Fertige funktion geben sollte lasst es mich wissen :D
JayEff - Do 30.04.09 12:27
Gefällt mir aus verschiedensten Gründen absolut nicht.
Warum ist Suchstring ein Var-Parameter, warum wird mein ursprünglicher String verändert, kann das auch nur im entferntesten Sinnvoll sein? :autsch:
Mal ausprobiert: Es ist unendlich langsam, was auch kein Wunder ist, da es ja Elemente aus dem String löscht, wodurch der komplette String hin- und herkopiert werden muss.
... Ok, ich breche meinen ursprünglichen Test ab, 50000 Durchgänge dauern bei mir mehr als 1 Minute.
... 5000 Durchgänge. 22,6 Sekunden (!), im Vergleich dazu
Delphi-Quelltext
1: 2: 3:
| for i := 1 to Length(s) do if s[i] = ' ' then inc(m1); |
ebenfalls 5000 Durchgänge dauerte 47 ms (!)
:roll:
thepaine91 - Do 30.04.09 12:34
Das kommt noch aus anfangszeiten meiner Programmierung war nur copy paste ^^
Das deine so viel schneller ist wundert mich dann auch nicht ^^
Aber ich editier sie mal so das es sinnvoll ist
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13:
| function TForm1.SubstringFinden(const Text, Suchstring: String): integer; var i, Anzahl: integer; begin Anzahl := 0; for i := 1 to length(Text) - length(Suchstring) +1 do if copy(Text, i, length(Suchstring)) = Suchstring then inc(Anzahl); Result := Anzahl Result:= 0; .... then inc(Result); end; |
JayEff - Do 30.04.09 12:55
thepaine91 hat folgendes geschrieben : |
Das kommt noch aus anfangszeiten meiner Programmierung war nur copy paste ^^
Das deine so viel schneller ist wundert mich dann auch nicht ^^
Aber ich editier sie mal so das es sinnvoll ist |
Deine Funktion arbeitet halt mit einem Suchstring während meine nur einen Char sucht. Wenn's um Strings geht, funktioniert das nicht so einfach. In ADA könnte man einfach die Grenze des Strings als Slice angeben... Aus s(1 .. 5) = 'hallo' wird s(4 .. 5) = 'o', das ist recht schnell. In Delphi gibt es soweit ich weiß auch slices aber ich weiß nicht, wie das geht.
Deine neue Methode brauchte im Test nur 4,4 Sekunden, schon viel besser :zustimm: Optimieren lässt es sich sicherlich mit PosEx... Ich probier mal was :)
Edit:
Result := Anzahl; vergessen :rofl:
BenBE - Do 30.04.09 13:00
Nicht ganz ernst gemeint (bevor jetzt jemand an mir zweifelt :P)
Delphi-Quelltext
1: 2: 3: 4:
| function CountChars(Haystack: String; Needle: Char): Integer; begin Result := Length(Haystack) - Length(StringReplace(Haystack, Needle, '', [rfReplaceAll])); end; |
Für nicht-überlappende Strings funktioniert auch:
Delphi-Quelltext
1: 2: 3: 4:
| function CountNonOverlappingStr(Haystack: String; Needle: String): Integer; begin Result := Length(Haystack) - Length(StringReplace(Haystack, Needle, '', [rfReplaceAll])); end; |
thepaine91 - Do 30.04.09 13:03
Hm ich guck auch mal wenn ich Zeit hab ob ich was finde :P und er wollte das ja garnicht mit strings wo du es sagst :D
JayEff - Do 30.04.09 13:08
Auf 93 ms komme ich mit
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:
| function SubstringFinden(Text, Suchstring: String): integer; var i, Anzahl: integer; begin Anzahl := 0; i := Pos(SuchString, Text); while i > 0 do begin inc(Anzahl); i := PosEx(Suchstring, Text, i + Length(SuchString)); end; Result := Anzahl; end; |
und mit BenBEs nicht ganz ernst gemeinter Funktion kommt man auf 26 Sekunden :lol:
thepaine91 - Do 30.04.09 13:12
Puhh 93 ms..... geht das nicht schneller ? -.- Ich mein für so ein bisschen String suche will ich ja nicht gleich meinen ganzen Tag vergeuden. Und wenn du hier schon Messwerte raushaust dann bitte auch deine Systemleistung. ^^ Ansonsten kann man damit nix anfangn.
JayEff - Do 30.04.09 13:30
thepaine91 hat folgendes geschrieben : |
Puhh 93 ms..... geht das nicht schneller ? |
für 5000 Durchgänge eines 3720 Zeichen langen Strings. 2,2GHz (dualcore, wird ja nur 1 genutzt)
Gern geschehen, übrigens, ich brauch atm keine Stringsuche aber für so freundliche Antworten arbeite ich auch mal gern kostenlos :roll:
thepaine91 - Do 30.04.09 13:42
jayeff liegt an meinem seltsamen Humor. War nicht ernst gemeint. Super Lösung :zustimm:
Außer das mit der Systemleistung ist immer ganz nett zu wissen damit man es wenigstens ein bissel einschätzen kann.
Und ben be deine nicht ganz ernst gemeinte lösung bietet mir nicht ganz richtige Ergebnise :P
JayEff - Do 30.04.09 14:14
thepaine91 hat folgendes geschrieben : |
jayeff liegt an meinem seltsamen Humor. War nicht ernst gemeint. Super Lösung :zustimm: |
Jaaa das hab ich zuerst eig auch gedacht... :roll: komisch, dass ich das dann trotzdem nochmal uminterpretiert hab :shock:
Nix für ungut ;)
Ich hab meine Werte eigentlich nur zum Vergleichen angegeben.
Edit: Bei meinem Test funktionierte Ben's Funktion mit Chars, aber die mit Strings ist falsch. Man muss das Endergebniss noch durch die Suchstring-Länge teilen =P
thepaine91 - Do 30.04.09 14:51
:D das erklärt einiges...
BenBe auch wenn es nicht die effektivste Lösung ist immerhin ein einzeiler :D
und ehrlich gesagt hab ich keine Ahnung was du da machst :P war auch zu faul die Delphi Hilfe durchzulesen. ^^
Und die für Strings dann eben so
Delphi-Quelltext
1: 2: 3: 4:
| function CountNonOverlappingStr(Haystack: String; Needle: String): Integer; begin Result := (Length(Haystack) - Length(StringReplace(Haystack, Needle, '',[rfReplaceAll])))div length(Needle); end; |
jaenicke - Do 30.04.09 15:08
thepaine91 hat folgendes geschrieben : |
und ehrlich gesagt hab ich keine Ahnung was du da machst :P war auch zu faul die Delphi Hilfe durchzulesen. ^^ |
Naja, was wird StringReplace schon machen? Richtig: Einen String durch einen anderen ersetzen.
Er ersetzt einfach alle Vorkommen des gesuchten Strings durch '', löscht diese also. Die Differenz aus der Länge vorher und des Strings ohne diese Teile des Strings ist dann die Anzahl der Buchstaben damit. Und geteilt durch die Länge des gesuchten Strings ist das dann dessen Anzahl.
Nersgatt - Do 30.04.09 15:18
jaenicke hat folgendes geschrieben : |
Er ersetzt einfach alle Vorkommen des gesuchten Strings durch '', löscht diese also. Die Differenz aus der Länge vorher und des Strings ohne diese Teile des Strings ist dann die Anzahl der Buchstaben damit. Und geteilt durch die Länge des gesuchten Strings ist das dann dessen Anzahl. |
Erinnert mich irgendwie an die Frage, wie Mathematiker Elefanten fangen:
Zitat: |
Mathematiker fangen Elefanten, indem sie nach Afrika gehen, alles entfernen, was nicht Elefant ist und ein Element der Restmenge fangen. |
sky21 - Do 30.04.09 15:36
Hey danke für die vielen Beiträge hier! Mittlerweile habe ich es auch selber implementiert und präsentiere meine Version hier:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:
| function GetNumberOfChars(const sInput : string; const chrSearch : char) : Integer; var i : Integer;
begin Result := 0; for i:=1 to Length(sInput) do if (sInput[i] = chrSearch) then Inc(Result); end; |
thepaine91 - Mo 04.05.09 12:38
Mal eine Frage @jeanicke welche Delphi version benutzt du? Ich finde leider kein PosEx.
Nersgatt - Mo 04.05.09 13:17
thepaine91 hat folgendes geschrieben : |
Mal eine Frage @jeanicke welche Delphi version benutzt du? Ich finde leider kein PosEx. |
Hast Du StrUtils eingebunden?
espen - Mo 04.05.09 14:11
Hallo,
ich glaube meine Version ist etwas schneller ;-)
Delphi-Quelltext
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:
| function GetNumberOfChars(const aString : String; const aChar : Char) : Integer; var FCount : integer; FFind : Integer; begin FCount := 0; FFind := ord(aChar); asm mov eax, aString mov ecx, FCount @CNT: inc eax movzx edx, byte [eax] cmp edx, FFind jne @NXT inc ecx @NXT: cmp edx, 0 jne @CNT mov FCount, ecx end; Result := FCount; end; |
Gruss.
jaenicke - Mo 04.05.09 14:16
Ok, es soll schnell sein? Das geht dann aber noch besser. ;-)
Nämlich direkt per Assembler statt nur eingebettet und mit repne scasb als Assemblerbefehl. Ich kann es ja kurz mal komplett schreiben.
Nebenbei zu deiner Initialisierung: Der erste Parameter liegt eh in eax. ;-)
BenBE - Mo 04.05.09 14:19
Du verschenkst Zyklen, weil Du noch Begin\End schreibst. Mach rein ASM, ohne Variablen-Deklaration, dann sparst Du noch paar. Wobei es auch noch was bringen könnte, mit REPNE SCASB zu suchen und nur zu zählen,. wie häufig die Schleife abbricht ...
@jaenicke: Nicht, wenn er das eingebettet schreibt. Dann liegt der zwar in EAX, Delphi kopiert den aber zwischenzeitlich noch mal sonstwo hin.
jaenicke - Mo 04.05.09 14:20
Erster :P, bin grad dabei es richtig zu schreiben.
BenBE - Mo 04.05.09 14:21
Zwei ..., ein Gedanke ?? Oder wie.
Aber ja, mach Dir kurz die Arbeit, dann darf ich meckern ;-)
thepaine91 - Mo 04.05.09 14:54
Was ich jetzt noch toll finden würde wenn die Version auch Stringkompatible wäre.
Wenn du das noch ändern könntest wäre super. =)
Da du keine Testergebnise dazugestellt hast würd ich das gerne mal testen ;)
jaenicke - Mo 04.05.09 21:24
Soo, hier eine Version mit repne scasb/scasw, die auch mit Unicode und Delphi 2009 klarkommen sollte:
// EDIT: modifizierte Fassung:
Delphi-Quelltext
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:
| function CountCharOccurrences(const aChar: Char; const aString: String): Integer; asm or edx, edx jnz @ValidString xor eax, eax ret @ValidString:
push edi
mov edi, edx mov dword ptr ecx, [edx - $04]
xor edx, edx @repeat: inc edx {$ifdef UNICODE} repne scasw {$else} repne scasb {$endif} jz @repeat
dec edx mov eax, edx
pop edi end; |
Alte Fassung:
Delphi-Quelltext
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:
| function GetNumberOfChars(const aChar: Char; const aString: String): Integer; asm cmp edx, 0 jnz @ValidString xor eax, eax ret @ValidString:
push edi push ebx push ecx
xor ebx, ebx mov edi, edx mov ecx, [edx - $04]
@repeat: inc ebx {$ifdef UNICODE} repne scasw {$else} repne scasb {$endif} jz @repeat
dec ebx mov eax, ebx
pop ecx pop ebx pop edi end; |
BenBE - Mo 04.05.09 23:16
@jaenicke: ECX brauchst Du nicht mit sichern. EAX, EDX und ECX sind Vogelfrei ;-)
Bitte ergänze aber bei den expliziten Speicherzugriffen mal noch die Memory Size Modifier (BYTE PTR vs. WORD PTR @LOC 20).
Ferner: Vergleich auf 0 mit OR EDX, EDX oder TEST EDX, EDX in LOC 4
Sonst seh ich jetzt erstmal nichts, außer, dass Du das Zählen der Vorkommen nach EDX legen solltest, dann fällt das Sichern von EBX weg (2 Befehle + 2 Memory Zugriffe auf den Stack)
Edit: Okay, ich bin heut mal nicht so: Hier eine etwas optimierte Fassung:
Delphi-Quelltext
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:
| function GetNumberOfChars(const aChar: Char; const aString: String): Integer; asm TEST EDX, EDX JNZ @@ValidString
XOR EAX, EAX RET
@@ValidString:
PUSH EDI
MOV EDI, EDX MOV ECX, DWORD PTR [EDX - $04]
XOR EDX, EDX
@@repeat: INC EDX
{$IFDEF UNICODE} REPNE SCASW {$ELSE} REPNE SCASB {$ENDIF} JZ @@repeat
LEA EAX, DWORD PTR [EDX - $01] POP EDI end; |
Die Änderung bzgl. der ALU müsste man testen, sollte aber IMHO eine Einsparung liefern, vorausgesetzt die CPU benötigt für POP keine Memory Address Unit, ansonsten die Variante über die ALU nehmen ;-)
jaenicke - Mo 04.05.09 23:29
Ich hatte auch gerade eine editierte Version oben reineditiert. :mrgreen:
Deine schau ich gleich noch an. ;-)
BenBE hat folgendes geschrieben : |
Bitte ergänze aber bei den expliziten Speicherzugriffen mal noch die Memory Size Modifier (BYTE PTR vs. WORD PTR @LOC 20). |
Ich dachte das würde reichen, dass ich eax, also ein 32-Bit-Register, angebe, damit das klar ist.
Was passiert da denn mit dieser Änderung anders? So genau kenne ich mich dann doch nicht damit aus. ;-)
BenBE - Mo 04.05.09 23:35
jaenicke hat folgendes geschrieben : |
Ich hatte auch gerade eine editierte Version oben reineditiert. :mrgreen:
Deine schau ich gleich noch an. ;-) BenBE hat folgendes geschrieben : | Bitte ergänze aber bei den expliziten Speicherzugriffen mal noch die Memory Size Modifier (BYTE PTR vs. WORD PTR @LOC 20). | Ich dachte das würde reichen, dass ich eax, also ein 32-Bit-Register, angebe, damit das klar ist.
Was passiert da denn mit dieser Änderung anders? So genau kenne ich mich dann doch nicht damit aus. ;-) |
Der DCC32 nimmt automatisch schon bei vielen Befehlen 32 Bit als Operandengröße an, teilweise auch da, wo das Weglassen der Größenangabe mehrdeutig ist (Bei MOVZX nimmt er z.B. 8 Bit an). Wenn man das also mit angibt sorgt man dafür, dass der Leser den Überblick behält, in welcher Größe wo gelesen wird. Zusätzlich macht es den Code auch für ältere Delphi-Versionen kompatibel, wo eine Reihe solcher automatischen Annahmen noch nicht getroffen wurden. Zu dem Thema gab es mal Bugreports in der uallCollection, wo ich uall einmal etwas genauer darauf hingewiesen hab. Such einfach mal hier in der Sparte, falls Du das genauer brauchst.
thepaine91 - Di 05.05.09 08:59
Naja den großen Geschwindigkeits Unterschied erkenne ich da nicht. Habe gerade meine Version mit eurer verglichen und die waren immer knap aneinander. Mal war die eine und mal die andere schneller. Das bei 100000 durchläufgen in einem String mit 250 Zeichen.
thepaine91 - Mi 06.05.09 15:48
Posex existiert bei mir nicht: Delphi6
Hab meine Funktion nochmal verändert und diese ist deutlich schneller als die Funktion mit Copy.
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14:
| function TForm1.Substringmenge(Substring, Text: Pchar): integer; var PC :Pchar; i : integer; begin Result := 0; PC := Text - 1; while (PC <> nil) do begin inc(PC); PC := AnsiStrPos(PC, substring); inc(Result); end; Result := Result - 1; end; |
Konnte das ganze leider nicht mit der Version von jeanicke vergleichen da ich kein Posex zu verfügung stehen habe.
BenBE - Mi 06.05.09 15:50
Dann vergleich bitte einmal mit der (ASM-)Version von mir ...
thepaine91 - Mi 06.05.09 16:05
BenBe bei deiner Funktion bekomme ich einzig und alleine eine Fehlermeldung: Zugriffsverletzung bei Addresse ...
cursor hält hier : REPNE SCASB
Dann funktioniert deine Version auch nur mit Char und nicht mit String. (Somit haben die Funktionen nicht die gleiche Vorraussetzung)
BenBE - Mi 06.05.09 19:22
k, dann tausch mal EDI durch ESI (an allen Stellen).
@jaenicke: Der Bug stammt noch von dir!
jaenicke - Mi 06.05.09 19:53
Aber der zu durchsuchende String gehört doch in EDI, jedenfalls hatte ich das so gelesen. :gruebel:
// EDIT:
Mit ESI gibt es eine Schutzverletzung. :gruebel:
Chemiker - Mi 06.05.09 22:22
Hallo thepaine91,
es sollte beide ASM – Function funktionieren.
Kann es sein, dass Du die Routinen als Methode einer Klasse aufrufst(z.B. Form1)? Dort werden beide ASM-Routinen nicht funktionieren.
Der Threadstarter wollte auf ein Char prüfen nicht einen Stringvergleich.
Bis bald Chemiker
thepaine91 - Do 07.05.09 09:49
HI jo mir ist bewusste das es um Charsuche ging aber finde es Praktisch wenn die FUnktion beides kann.
Für chars ist aber eindeutig die asm version vom benbe zu empfehlen.
Ergebnis bei 250 Zeichen vorkommen des Chars 250* :
Zeit mit Pcharfunktion: 177,307459467785
Zeit mit ASMfunktion: 6,85811744229895
Ergebnis bei 250 Zeichen vorkommen des Chars 1 :
Zeit mit Pcharfunktion: 2,56759448476828
Zeit mit ASMfunktion: 1,60512579112585
Angaben in mikrosekunden für einen Durchlauf ca. (pentium4 2,8 ghz)
Horst_H - Do 07.05.09 14:26
Hallo,
merkwürdige Zahlen.( AMDX2 2,3 Ghz )
Zeit mit ASMfunktion: 1,60512579112585
wären bei mir Asm : 0.250 mikrosekunden
Ich habe ASm/Pas doppelt laufen lassen falls Cool&quite dazwischen funken sollte, tut es aber nicht.
Für 1 Mio Durchläufe mit Stringlänge 250.
Wiederholerate = 1 => Alle Zeichen des Strings sind das Suchzeichen.
Freepascal 2.2.4:
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:
| Running "c:\fpc\2.2.4\bin\i386-win32\noofchar.exe " 250 Asm : 00:00:02.125 250 Pas : 00:00:00.359 250 Asm : 00:00:02.141 250 Pas : 00:00:00.375 125 SubStringPas : 00:00:06.906 |
Turbo-Delphi 2006
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10:
| 250 Asm : 00:00:02.125 250 Pas : 00:00:00.235 250 Asm : 00:00:02.156 250 Pas : 00:00:00.234 250 SubStringPas : 00:01:54.032 // Holla??? |
Asm dauert 10 mal so lang.
Für 1 Mio Durchläufe
Wiederholerate = 250 => ein einziges Vorkommen des Suchzeichens.
Freepascal 2.2.4:
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:
| Running "c:\noofchar.exe " 1 Asm : 00:00:00.250 1 Pas : 00:00:00.562 1 Asm : 00:00:00.235 1 Pas : 00:00:00.562 1 SubStringPas : 00:00:00.266 |
Turbo-Delphi2006
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10:
| 1 Asm : 00:00:00.235 1 Pas : 00:00:00.453 1 Asm : 00:00:00.250 1 Pas : 00:00:00.453 1 SubStringPas : 00:00:00.953 |
Assembler ist etwa doppelt so schnell.
Und die Pascal Umsetzung von Delphi ist immer noch ein wenig besser als von Freepascal.
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14:
| function GetNumberOfChars_Pas(const aChar: Char; const aString: String): Integer; var i : integer; begin result := 0; IF aString = '' then exit; For i := length(aSTring) downto 1 do begin if aString[i] = aChar then inc(result); end; end; |
Gruß Horst
EDIT:
Hier eine Assembler Version, die konstante Zeit braucht, egal, wie oft das gesuchte Zeichen vorkommt, statt Sprung nach vergleich wird gerechnet.
Wenn ich richtig gerechnet habe, braucht diese Version ~3 Takte pro Zeichen.
BenBe's bei seltenem vorkommen 2 Takte und die Pascalversion zwischen 3 und 8 Takten ( Abstand von 7 zwischen den Vorkommen brachte die Sprungverhersage wohl aus dem Tritt)
Delphi-Quelltext
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:
| asm .....
XOR EDX,EDX;
PUSH EBX MOVZX EBX, AL
@@repeat: SUB AL,Byte Ptr [EDI+ECX]
SUB AL,1 ; MOV EAX, EBX ADC EDX,0 ; DEC ECX JGE @@repeat ADC EDX,0 ; POP EBX POP EDI MOV EAX,EDX end; |
Ergibt mit 10000 Zeichen langen Strings (sehr kleiner Aufrufoverhead ) aus einem Buchstaben und 100000 Durchläufen:
EDIT: 14.7.2010 AMD Athlon II X2 2,9 Ghz
Quelltext
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:
| ./NoOfChar
Alle 1 Zeichen kommt chr(1) im String der Länge 10000 vor Asm_BenBe : 00:00:06.562 Asm_BenBe_Takte : 19.03 Asm : 00:00:00.806 Asm_Takte : 2.34 Pas : 00:00:01.385 PasTakte : 4.02
Alle 7 Zeichen kommt chr(1) im String der Länge 10000 vor Asm_BenBe : 00:00:01.529 Asm_BenBe_Takte : 4.43 Asm : 00:00:00.806 Asm_Takte : 2.34 Pas : 00:00:01.976 PasTakte : 5.73
Alle 32 Zeichen kommt chr(1) im String der Länge 10000 vor Asm_BenBe : 00:00:00.875 Asm_BenBe_Takte : 2.54 Asm : 00:00:00.806 Asm_Takte : 2.34 Pas : 00:00:02.266 PasTakte : 6.57
Alle 96 Zeichen kommt chr(1) im String der Länge 10000 vor Asm_BenBe : 00:00:00.752 Asm_BenBe_Takte : 2.18 Asm : 00:00:00.806 Asm_Takte : 2.34 Pas : 00:00:02.139 PasTakte : 6.20
Alle 254 Zeichen kommt chr(1) im String der Länge 10000 vor Asm_BenBe : 00:00:00.714 Asm_BenBe_Takte : 2.07 Asm : 00:00:00.807 Asm_Takte : 2.34 Pas : 00:00:02.097 PasTakte : 6.08
Habe fertig |
Es ist erstaunlich, wie sehr scawb ausgebremst wird.
Auch, dass meine 6 Befehle der inneren Schleife in 2.34 Takten abgearbeitet werden.
Ab einem Abstand größer 64 Buchstaben ist ASM_BenBe immer schneller als meine angepasste Version, aber nicht die Welt.
P.S. ein paar Tags
Buchstaben Buchstabe char chars Anzahl zählen count
Horst_H - Di 07.04.15 09:07
Hallo,
es hat sich bei den CPUs wohl was getan.
Mit Intel Haswell i4330 sieht es schon wieder ganz anders aus.Mit freepascal 3.0.1 getestet.
Selbst die Pascal-Version ist schneller als die ASM Version mit
repne scasX
Delphi-Quelltext
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: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123: 124: 125: 126: 127: 128: 129: 130: 131: 132: 133: 134: 135: 136: 137: 138: 139: 140: 141: 142: 143: 144: 145: 146: 147: 148: 149: 150: 151: 152: 153: 154: 155: 156: 157: 158: 159: 160: 161: 162: 163: 164: 165: 166:
| {$IFDEF FPC} {$MODE objFPC} {$H+} {$ASMMODE INTEL} {$Optimization ON,RegVar,CSE,ASMCSE,PeepHole} {$CODEALIGN proc= 32,loop=4} {$ELSE} {$APPTYPE CONSOLE} {$ENDIF} uses sysutils;
function GetNumberOfChars_Pas(const aChar: Char; aString: AnsiString): Integer; var i : integer; pc : pchar; begin result := 0; IF aString = '' then exit; i := length(aSTring)-1; pc := pChar(aString); For i := i downto 0 do IF pc[i] = aChar then inc(result); end;
function GetNumberOfChars_ASM(const aChar: Char; const aString: AnsiString): Integer;assembler;nostackframe; asm TEST EDX, EDX JNZ @@ValidString XOR EAX, EAX JMP @@Ende
@@ValidString:
PUSH EDI PUSH EBX
MOV EDI,EDX MOV ECX, DWORD PTR [EDX - $04]
MOVZX EBX, AL
clc XOR EDX,EDX;
@@repeat: SUB AL,Byte Ptr [EDI+ECX] SUB AL,1 ; MOV EAX, EBX ADC EDX,0 ; DEC ECX JGE @@repeat ADC EDX,0 ; POP EBX POP EDI MOV EAX,EDX @@Ende: end;
function GetNumberOfChars_ASMBe(const aChar: Char; const aString: AnsiString): Integer;assembler; asm TEST EDX, EDX JNZ @@ValidString
XOR EAX, EAX RET
@@ValidString:
PUSH EDI
MOV EDI, EDX MOV ECX, DWORD PTR [EDX - $04]
XOR EDX, EDX
@@repeat: INC EDX
{$IFDEF UNICODE} REPNE SCASW {$ELSE} REPNE SCASB {$ENDIF} JZ @@repeat
LEA EAX, DWORD PTR [EDX - $01] POP EDI end;
const CPUF = 3500000000; MAXCOUNT= 100000; MAXLENGTH = 10000;
procedure Test(Wiederholrate:integer); var t1,t0: TDateTime; TestStr : AnsiString; TestChr : char; i : integer; begin setlength(TestStr,MAXLENGTH); For i := length(TestStr) Downto 1 do TestStr[i] := chr(i mod WIEDERHOLRATE +1); testChr := chr(1);
Writeln('Alle ',Wiederholrate,' Zeichen kommt chr(1) im String der Länge ',length(TestStr),' vor');
t0 := time; For I := 1 to MAXCOUNT do GetNumberOfChars_ASMBe(TestChr,TestStr); t1 := time; write('Asm_BenBe : ',FormatDateTime('hh:mm:ss.zzz',t1-t0)); writeln(' Asm_BenBe_Takte : ',(t1-t0)*86400 /MAXCOUNT/MAXLENGTH*CPUF:6:2);
t0 := time; For I := 1 to MAXCOUNT do GetNumberOfChars_ASM(TestChr,TestStr); t1 := time; write('Asm : ',FormatDateTime('hh:mm:ss.zzz',t1-t0)); writeln(' Asm_Takte : ',(t1-t0)*86400 /MAXCOUNT/MAXLENGTH*CPUF:6:2);
t0 := time; For I := 1 to MAXCOUNT do GetNumberOfChars_PAS(TestChr,TestStr); t1 := time; write('Pas : ',FormatDateTime('hh:mm:ss.zzz',t1-t0)); writeln(' PasTakte : ',(t1-t0)*86400 /MAXCOUNT/MAXLENGTH*CPUF:6:2); writeln; end; Begin Test(1); Test(7); Test(32); Test(96); Test(254); writeln; writeln('Habe fertig'); readln; end. |
Mit der Ausgabe
Quelltext
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:
| Alle 1 Zeichen kommt chr(1) im String der Länge 10000 vor Asm_BenBe : 00:00:14.314 Asm_BenBe_Takte : 50.10 Asm : 00:00:00.409 Asm_Takte : 1.43 Pas : 00:00:00.487 PasTakte : 1.70
Alle 7 Zeichen kommt chr(1) im String der Länge 10000 vor Asm_BenBe : 00:00:02.582 Asm_BenBe_Takte : 9.04 Asm : 00:00:00.410 Asm_Takte : 1.44 Pas : 00:00:00.906 PasTakte : 3.17
Alle 32 Zeichen kommt chr(1) im String der Länge 10000 vor Asm_BenBe : 00:00:01.014 Asm_BenBe_Takte : 3.55 Asm : 00:00:00.416 Asm_Takte : 1.46 Pas : 00:00:00.910 PasTakte : 3.18
Alle 96 Zeichen kommt chr(1) im String der Länge 10000 vor Asm_BenBe : 00:00:00.723 Asm_BenBe_Takte : 2.53 Asm : 00:00:00.408 Asm_Takte : 1.43 Pas : 00:00:00.687 PasTakte : 2.40
Alle 254 Zeichen kommt chr(1) im String der Länge 10000 vor Asm_BenBe : 00:00:00.632 Asm_BenBe_Takte : 2.21 Asm : 00:00:00.408 Asm_Takte : 1.43 Pas : 00:00:00.624 PasTakte : 2.18
Habe fertig |
Das sollte man vielleicht in
http://www.entwickler-ecke.de/topic_Vorkommen+eines+Buchstabens+in+einem+String+zaehlen_92019.html zur Sprache bringen.
Gruß Horst
Martok - Di 07.04.15 16:58
Und die Goldene Threadarchäologenschaufel geht an.... :lol:
Mittlerweile bin ich auch dazu übergegangen, PurePascal-Versionen statt speziell optimierter zu nehmen. FPC 3.0 (bzw 2.7) generiert da zumindest für x86 und x64 ausreichend optimalen Code, dass sich die geopferte Lesbarkeit und Portabilität nicht lohnt.
In dem Fall würde ich ja auf konstante Branch Mispredictions tippen, oder? "Registerzugriff, Memory Access, CJump basierend auf Memory" klingt nicht grade Cachefreundlich. Die naive Implementation ist dafür sehr einfach, da ist die Loopbedingung klar und der Speicherzugriff definitiv linear.
OlafSt - Di 07.04.15 23:45
Sämtliche REP-Befehle (CMPSB, SCASB und deren Word und DWord-Varianten) wurden von Intel mit der Einführung von SSE böse vermurkst. Sie wurden so langsam, das es tatsächlich schneller war, eine Schleife zu bauen (dec ecx; jne @@loop). Daran hat sich bis heute nichts geändert.
mandras - Mi 08.04.15 01:07
OlafSt hat folgendes geschrieben : |
Sämtliche REP-Befehle (CMPSB, SCASB und deren Word und DWord-Varianten) wurden von Intel mit der Einführung von SSE böse vermurkst. Sie wurden so langsam, das es tatsächlich schneller war, eine Schleife zu bauen (dec ecx; jne @@loop). Daran hat sich bis heute nichts geändert. |
Ja, und ich war wirklich überrascht daß bei meinen Tests ein loop-Befehl langsamer war als ein dec/jmp.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!