GetNumberOfChars(str : string; chr : char) : Integer ?

Horst_H · Verfasst: 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:

markieren

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

markieren

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:

markieren

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

markieren

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.

markieren

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)

markieren

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

markieren

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

Einloggen, um Attachments anzusehen!

Horst_H · Verfasst: 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

markieren

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

markieren

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 www.entwickler-ecke....g+zaehlen_92019.html zur Sprache bringen.

Gruß Horst

Martok · Verfasst: 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.

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

OlafSt · Verfasst: 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.

_________________
Lies, was da steht. Denk dann drüber nach. Dann erst fragen.

mandras · Verfasst: 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.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme