Autor |
Beitrag |
Horst_H
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 07.05.09 13: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
Einloggen, um Attachments anzusehen!
|
|
Horst_H
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Di 07.04.15 08: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
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 www.entwickler-ecke....g+zaehlen_92019.html zur Sprache bringen.
Gruß Horst
|
|
Martok
Beiträge: 3661
Erhaltene Danke: 604
Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
|
Verfasst: Di 07.04.15 15:58
Und die Goldene Threadarchäologenschaufel geht an....
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
Beiträge: 486
Erhaltene Danke: 99
Win7, Win81, Win10
Tokyo, VS2017
|
Verfasst: Di 07.04.15 22: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
Beiträge: 429
Erhaltene Danke: 107
Win 10
Delphi 6 Prof, Delphi 10.4 Prof
|
Verfasst: Mi 08.04.15 00: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.
|
|
|