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'//  l= "el" und nicht "eins"

res := GetNumberOfChars(Inputstring, SearchChar); // res = 3


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 user profile iconAXMD: Delphi-Tags hinzugefügt
Moderiert von user profile iconNarses: 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);// gibt sicher was besseres als copy grad nur keine zeit zu gucken
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);
// gibt sicher was besseres als copy grad nur keine zeit zu gucken
  Result := Anzahl // so :D das wichtigste vergessen :P
// soweit ich weis könnte man Anzahl auch weglassen und es so lösen 
  Result:= 0;
  .... then inc(Result);
// dann kann man die letzte Zeile sparen :D (nicht ausprobiert)
end;


JayEff - Do 30.04.09 12:55

user profile iconthepaine91 hat folgendes geschrieben Zum zitierten Posting springen:
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

user profile iconthepaine91 hat folgendes geschrieben Zum zitierten Posting springen:
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

user profile iconthepaine91 hat folgendes geschrieben Zum zitierten Posting springen:
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

user profile iconthepaine91 hat folgendes geschrieben Zum zitierten Posting springen:
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

user profile iconjaenicke hat folgendes geschrieben Zum zitierten Posting springen:
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:
// returns the number of found characters (Note: comparison is case sensitive!)
function GetNumberOfChars(const sInput : stringconst 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

user profile iconthepaine91 hat folgendes geschrieben Zum zitierten Posting springen:
Mal eine Frage @jeanicke welche Delphi version benutzt du? Ich finde leider kein PosEx.

Hast Du StrUtils eingebunden?


jaenicke - Mo 04.05.09 13:46

Und für Delphi 5 oder früher gibts hier einen Ersatz:
http://www.delphipraxis.net/post409954.html


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 : Stringconst aChar : Char) : Integer;
var
  FCount : integer;
  FFind  : Integer;
begin
  FCount := 0;
  FFind  := ord(aChar);
  asm
    // ****
    // **** Initialisierung
    // ****
    mov eax, aString // ** Der zu durchsuchende String
    mov ecx, FCount  // ** Ergebnis

    @CNT:                  // ** Schleife
    inc eax                // ** Schleifenzähler inkrementieren
    movzx edx, byte [eax]  // ** n. Zeichen holen
    cmp edx, FFind         // ** Vergleiche n. Zeichen mit Suche
    jne @NXT               // ** Nicht gefunden, springe zu Schleifenende
    inc ecx                // ** Gefunden, Ergebnis inkrementieren
    @NXT:                  // ** Schleifenende
    cmp edx, 0             // ** Ende von String ?
    jne @CNT               // ** Nein, also nächstes Zeichen
    mov FCount, ecx        // ** Fertig, Ergebnis zuweisen
  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
  // Wenn edx 0 ist, abbrechen und 0 zurückgeben
  or edx, edx
  jnz @ValidString
  xor eax, eax
  ret
  @ValidString:

  // Register sichern
  push edi

  // in al ist bereits aChar drin, fehlt für scasb noch der zu scannende
  // String in edi
  mov edi, edx
  mov dword ptr ecx, [edx - $04]

  xor edx, edx // Zähler auf 0

  @repeat:
  inc edx
  {$ifdef UNICODE}
  repne scasw
  {$else}
  repne scasb
  {$endif}
  jz @repeat

  // Ergebnis zurückgeben
  dec edx
  mov eax, edx

  // Register wiederherstellen
  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
  // Wenn edx 0 ist, abbrechen und 0 zurückgeben
  cmp edx, 0
  jnz @ValidString
  xor eax, eax
  ret
  @ValidString:

  // Register sichern
  push edi
  push ebx
  push ecx

  xor ebx, ebx // Zähler auf 0

  // in al ist bereits aChar drin, fehlt für scasb noch der zu scannende
  // String in edi
  mov edi, edx
  mov ecx, [edx - $04]

  @repeat:
  inc ebx
  {$ifdef UNICODE}
  repne scasw
  {$else}
  repne scasb
  {$endif}
  jz @repeat

  // Ergebnis zurückgeben
  dec ebx
  mov eax, ebx

  // Register wiederherstellen
  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
    // Wenn edx 0 ist, abbrechen und 0 zurückgeben
    TEST    EDX, EDX
    JNZ     @@ValidString

    XOR     EAX, EAX
    RET

@@ValidString:

    // Register sichern
    PUSH    EDI

    // in al ist bereits aChar drin, fehlt für scasb noch der zu scannende
    // String in edi
    MOV     EDI, EDX
    MOV     ECX, DWORD PTR [EDX - $04]

    // Zähler auf 0
    XOR     EDX, EDX

@@repeat:
    INC     EDX

    {$IFDEF UNICODE}
    REPNE   SCASW
    {$ELSE}
    REPNE   SCASB
    {$ENDIF}
    JZ @@repeat

    // Ergebnis zurückgeben
//    DEC     EDX
//    MOV     EAX, EDX
    LEA     EAX, DWORD PTR [EDX - $01
    //Do the copying with one instruction instead of two
    //This leaves the ALU free for other tasks

    // Register wiederherstellen
    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. ;-)
user profile iconBenBE hat folgendes geschrieben Zum zitierten Posting springen:
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

user profile iconjaenicke hat folgendes geschrieben Zum zitierten Posting springen:
Ich hatte auch gerade eine editierte Version oben reineditiert. :mrgreen:
Deine schau ich gleich noch an. ;-)
user profile iconBenBE hat folgendes geschrieben Zum zitierten Posting springen:
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 <> nildo
  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;
  //Abwärts,weil sonst jedesmal length abgefragt wird
  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
    .....

    // Zähler auf 0
    XOR     EDX,EDX;

    //aChar retten
    PUSH    EBX
    MOVZX   EBX, AL

@@repeat:
    SUB     AL,Byte Ptr [EDI+ECX]
{***** EDIT: wie umständlich....  
    NOT     AL    ; //Nur wenn AL= 0 =>AL = $FF
    ADD     AL,1  ; //und nur dann ist Carry gesetzt
******}

    SUB     AL,1  ; //Nur wenn AL= 0 =>AL-1 = $FF=> Carry gesetzt
    MOV     EAX, EBX  // EAX wiedre zu aChar machen
    ADC     EDX,0 ; //Carry addieren

    DEC     ECX
    JGE     @@repeat //

    ADC     EDX,0 ;
    // Register wiederherstellen

    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);
//  For i :=  i downto 0 do   result := result + ORD(pc[i] = aChar);      
end;

function GetNumberOfChars_ASM(const aChar: Char; const aString: AnsiString): Integer;assembler;nostackframe;
asm
    // Wenn edx 0 ist, abbrechen und 0 zurückgeben
    TEST    EDX, EDX
    JNZ     @@ValidString
    XOR     EAX, EAX
    JMP     @@Ende

@@ValidString:

    // Register sichern
    PUSH    EDI
    PUSH    EBX

    // in al ist bereits aChar drin
    MOV     EDI,EDX
    MOV     ECX, DWORD PTR [EDX - $04]

    //aChar retten
    MOVZX     EBX, AL

    // Zähler auf 0
    clc
    XOR     EDX,EDX;

@@repeat:
    SUB     AL,Byte Ptr [EDI+ECX]
    SUB     AL,1  ;   //Nur wenn AL= 0 =>AL = $FF und Carry/Borrow gesetzt
    MOV     EAX, EBX  //EAX wieder zu aChar machen    
    ADC     EDX,0 ;   //Carry addieren
    DEC     ECX
    JGE     @@repeat //

    ADC     EDX,0 ;
    // Register wiederherstellen

    POP     EBX
    POP     EDI
    MOV     EAX,EDX
@@Ende:
end;

function GetNumberOfChars_ASMBe(const aChar: Char; const aString: AnsiString): Integer;assembler;
asm
    // Wenn edx 0 ist, abbrechen und 0 zurückgeben
    TEST    EDX, EDX
    JNZ     @@ValidString

    XOR     EAX, EAX
    RET

@@ValidString:

    // Register sichern
    PUSH    EDI

    // in al ist bereits aChar drin, fehlt für scasb noch der zu scannende
    // String in edi
    MOV     EDI, EDX
    MOV     ECX, DWORD PTR [EDX - $04]

    // Zähler auf 0
    XOR     EDX, EDX

@@repeat:
    INC     EDX

    {$IFDEF UNICODE}
    REPNE   SCASW
    {$ELSE}
    REPNE   SCASB
    {$ENDIF}
    JZ @@repeat

    // Ergebnis zurückgeben
//    DEC     EDX
//    MOV     EAX, EDX
    LEA     EAX, DWORD PTR [EDX - $01]
    //Do the copying with one instruction instead of two
    //This leaves the ALU free for other tasks

    // Register wiederherstellen
    POP     EDI
end;

const
  CPUF = 3500000000;   // CPU-Frequenz

  MAXCOUNT= 100000;
  MAXLENGTH = 10000;

procedure Test(Wiederholrate:integer);
var
  t1,t0: TDateTime;
  TestStr : AnsiString;
  TestChr : char;
  i : integer;
begin
  setlength(TestStr,MAXLENGTH);
  //Strings ,die die Abfolge 1234..WIEDERHOLRATE-1 enthalten
  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

user profile iconOlafSt hat folgendes geschrieben Zum zitierten Posting springen:
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.