Entwickler-Ecke
Algorithmen, Optimierung und Assembler - repne schlägt fehlt
Heiko - So 12.10.08 18:45
Titel: repne schlägt fehlt
Hallo,
ich hab mal wieder eine Unit vom mir angefasst um diese zu optimieren. Dabei soll im String überprüft werden, wo Zeilenumbrüche sind. Doch leider findet
repne nichts :(. Zum testen habe ich in eine Datei drei Zeilen á drei Buchstaben getippt. repne liefert aber die Position 9 zurück - also schon hinter dem String. Sieht ewiner von euch den Fehler?
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:
| function CharPos(const PStr: PChar; Chr: Char; StrLen: Integer): Integer; begin asm push edi mov edi, PStr mov ecx, StrLen mov al, Chr cld repne scasb mov Result, ecx pop edi end; end;
function TFileStreamW.ReadLn(var Buffer: String): Boolean; const bufMaxSize = 4096; var start : integer; bufSize : integer; chrPos : integer; newPos : integer;
begin SetLength(Buffer, bufMaxSize); start := position;
chrPos := 1; bufSize := Read(Buffer[chrPos], bufMaxSize); while(bufSize<>0) do begin newPos := CharPos(@Buffer[chrPos], #13, bufSize); if newPos = bufSize then begin newPos := CharPos(@Buffer[chrPos], #10, bufSize); end; if newPos < bufSize then begin SetLength(Buffer, chrPos+newPos); Position:=start+chrPos+newPos+1; end else begin SetLength(Buffer, length(Buffer)+bufMaxSize); bufSize := Read(Buffer[chrPos], bufMaxSize); inc(chrPos, bufMaxSize); end; end; |
cytrinox - So 12.10.08 19:05
Hi,
ich könnte mich irren, aber rein von der Logik her hätte ich gesagt scasb such im esi (source index) und nicht edi (destination index) Register.
Edit: gut, habs grad nachgelesen - ich hab mich geirrt ;)
Marc. - So 12.10.08 20:12
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15:
| function CharPos(const PStr: PChar; Chr: Char; StrLen: Integer): Integer; asm cld push edi mov edi, PStr mov ecx, StrLen mov eax, ecx push eax mov al, Chr repnz scasb pop eax sub eax, ecx mov Result, eax pop edi end; |
Hi! Ersetze das repne durch ein repnz.
Beachte, dass von hinten gezählt wird, beginnend bei Null! Bei meiner Variante bereits korrigiert.
€1: So scheint es bei mir zu funktionieren, allerdings auch mit einem repne.
€2: Bei mir funktioniert nun plötzlich auch Deine ursprüngliche Funktion. Bin etwas confused. :gruebel:
€3: Hat es einen Grund, weshalb Du das EDI - Register sicherst?
€4: Hast Du vielleicht vergessen, dass Zeilenumbrüche als zwei Zeichen gezählt werden? (#10#13)
€5: Codeupdate, ist nun performanter.
Silas - So 12.10.08 20:55
N'Abend,
zuerst:
repne ==
repnz weil
*z immer ==
*e ist
Bei
rep* kommt eigentlich immer
Position+1 heraus, weil er
nach dem Fund abbricht (ohne Gewähr).
Ein cld kann nie schaden, sonst wird u.U. rückwärts gesucht (Direction Flag).
EBX muss immer gesichert werden (natürlich nur wenns geändert wird),
EDI und
ESI nur bei Klassenfunktionen (hat mir
BenBE mal irgendwann erklärt), also in diesem Fall nicht unbedingt.
Komisch, ich wäre jetzt auch zu 95�icher gewesen, dass es bei
scas* ESI ist.
BenBE - Mo 13.10.08 00:13
Nana ...nicht mir meine Erklärungen verdrehen ;-)
Silas hat folgendes geschrieben : |
EBX muss immer gesichert werden (natürlich nur wenns geändert wird), EDI und ESI nur bei Klassenfunktionen (hat mir BenBE mal irgendwann erklärt), also in diesem Fall nicht unbedingt. |
Wo ich Dir das erklärt habe, habe ich gesagt: in EDI werden bei Klassen-Funktionen die RTTI\Instanztyp-Daten übergeben, bzw. der DMI bei Dynamic-Methoden. Nicht sichern muss man nur EAX, EDX und ECX; alle anderen Register sind IMMER zu sichern, wenn diese verändert werden, da dies der Compiler von selbst nicht tut (und er sogar davon ausgeht, dass fremde Methoden da nicht dran rumspielen)!
Bzgl. CLD vielleicht mal noch ne Anmerkung: Sollte man immer mit setzen, selbst wenn der Default-Wert Cleared ist. Es gibt einige Bugs (Buffer Overruns), die darauf beruhen, dass das Direction-Flag in einem unerwarteten Zustand vorgefunden wird. Um aber für das Setzen des Direction-Flags nicht unnötig Zeit zu verschwenden, kann man diess in seiner Methodee soweit keine Verzweigungen vorhanden sind, nach vorne verlagern, und es an eine Stelle auslagern, wo die entsprechende Pipeline des Prozessors gerade frei ist. Anbieten tun sich dafür Befehle, die das Flag-Register nicht verändern (z.B. mov r32,r32).
Thorsten83 - Mo 13.10.08 01:15
Hi,
mal eine ganz doofe Frage am Rande: Bringt es überhaupt was das in Assembler zu programmieren?
Wie sieht der von Delphi generierte Code aus?
BenBE - Mo 13.10.08 01:22
Thorsten83 hat folgendes geschrieben : |
Hi,
mal eine ganz doofe Frage am Rande: Bringt es überhaupt was das in Assembler zu programmieren? |
Wenn man weiß, was man tut: JA!
Thorsten83 hat folgendes geschrieben : |
Wie sieht der von Delphi generierte Code aus? |
Meistens grausam und redundant.
Thorsten83 - Mo 13.10.08 01:55
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:
| pushl %ebp movl %esp, %ebp movl 16(%ebp), %ecx pushl %ebx movzbl 12(%ebp), %edx movl 8(%ebp), %ebx testl %ecx, %ecx jle .L2 xorl %eax, %eax cmpb %dl, (%ebx) jne .L7 jmp .L6 .p2align 4,,7 .L8: cmpb %dl, (%eax,%ebx) .p2align 4,,5 je .L6 .L7: addl $1, %eax cmpl %ecx, %eax .p2align 4,,5 jne .L8 .L2: movl $-1, %eax .L6: popl %ebx popl %ebp .p2align 4,,1 ret |
Ist zugegebenermaßen vom gcc, aber ich finde der Code sieht noch einigermaßen aus...
Und ist letztendlich auch nicht viel anders als das selbst geschriebene, oder ist die Variante mit repne schneller?
Heiko - Mo 13.10.08 11:23
Da hier scheinbar kein Fehler zu finden ist, hänge ich mal das Projekt an. Vlt. sieht einer da etwas?
Marc. hat folgendes geschrieben : |
€4: Hast Du vielleicht vergessen, dass Zeilenumbrüche als zwei Zeichen gezählt werden? (#10#13) |
Nein. Das kommt noch. Aber ich teste lieber zwischenstände als später einen größeren Block, der nicht mehr so übersichtlig ist ;).
@Silas: Der Code dürfte dir bekannt Vorkommen - wobei ich den abgespeckt habe (unnötige Berechnungen entfernt).
@BenBE: Kennst du eine alternative zu repne, die nach #10 & #13 (& #21) gleichzeitig sucht?
Thorsten83 hat folgendes geschrieben : |
Und ist letztendlich auch nicht viel anders als das selbst geschriebene, oder ist die Variante mit repne schneller? |
Das Teste ich auch mit diesem Code. Das Borland-readln benutzt eine eigenen Code dafür (such "parallel" nach #10, #13, #21). Mein Ziel ist es: Borland performancetechnisch zu überbeiten ;).
jaenicke - Mo 13.10.08 12:24
Ganz einfach: ecx wird ja
heruntergezählt bei der Schleife, und sobald das 0 ist (Stringende) oder das Zeroflag gesetzt ist wird abgebrochen bei repne.
Du musst nur das Ergebnis von der Länge abziehen ;-). 13 - 9 = 4 ;-).
Was den Abbruch verursacht hat musst du dann glaube ich auch noch unterscheiden. (Am Zeroflag)
// EDIT:
Wobei das bei dir aber auch egal ist, warum es abgebrochen hat, wenn ich es mir genauer überlege.
Ach ja:
Heiko hat folgendes geschrieben : |
repne liefert aber die Position 9 zurück - also schon hinter dem String. |
Naja, nicht ganz, die (unsichtbaren) jeweils 2 Zeilenumbruchszeichen darfst du auch nicht vergessen, dahinter wäre das nicht ;-).
jaenicke - Mo 13.10.08 14:47
Heiko hat folgendes geschrieben : |
jaenicke hat folgendes geschrieben : | Ganz einfach: ecx wird ja heruntergezählt bei der Schleife, und sobald das 0 ist (Stringende) oder das Zeroflag gesetzt ist wird abgebrochen bei repne. |
Mhm, kann man den heraufzählen lassen? Ich möchte ja den nächsten Zeilenumbruch finden und nicht irgendeinen (sry in ASM bin ich nicht ganz standfest ;) ). |
Halt! Nicht falsch verstehen ;-). Es wird
nicht von hinten gesucht, nur die Zählung im Register zählt rückwärts, da eine Prüfung auf 0 einfacher ist als ein Vergleich mit der Stringlänge.
In dem Register steht zuerst die Länge des Strings, die hast du ja hineinkopiert, und dann werden die Zeichen der Reihe nach verglichen und dabei heruntergezählt. Beim ersten Zeilenumbruch von vorne an wird abgebrochen.
Quelltext
1: 2:
| 13 12 11 10 9 a b c #13 |
Heiko - Mo 13.10.08 14:52
Ahhh alles klar. Danke. Da kann ich das ja endlich weitermachen :).
Thorsten83 - Mo 13.10.08 18:54
Poste mal bitte wenn du Ergebnisse hast...
Hab damit gerade mal ein bißchen rumgespielt, erste Feststellung war dass die Laufzeit um ca. 60% ansteigt wenn ich vorher den Cache mit Müll überschreibe, eine while- statt for-Schleife brachte 15%, ein Entrollen der Schleife und Doppelwortzugriff fast eine Verdoppelung :D
Heiko - Di 14.10.08 16:08
Testergebnisse poste ich, sobald ich welche habe ;).
Allerdings habe ich gerade ein kleines Prob. Ich hab mir mal die Testversion von 2009 installiert und die meckrt den ASM-Code an.
Und zwar das
mov al, Chr, wobei Chr ein Char ist. Fehlermeldung
Quelltext
1:
| [DCC Fehler] UniCodeFileStream.pas(232): E2107 Operandengröße stimmt nicht überein |
€: Ok das Char ist jetzt 16bit groß. Weiß einer zufälligerweise ob es für das repne auch eine 16bit-Version gibt bzw. wie man char als 8Bit definiert?
€2: Ah ok. Es heißt nicht CharA, sondern AnsiChar :).
Heiko - Sa 18.10.08 10:32
Der Code ist inkompatibel zur aktuellen Delphiversion (Char = WideChar und nicht mehr AnsiChar)... Und ich mag die MPL nicht (wenn ichs richtig verstehe muss ein Teil des Codes ja OpenSource sein, was ich aber nicht voraussetzten möchte) ;).
Nichts desto trotz ein interessantes Projekt.
Hast du ein kommentiertes Beispiel dafür?
Btw: Wenn ich das
hier [
http://www.fh-wedel.de/~wol/ass/sose2003/repscas.asm.html] richtig interpretiere braucht man bei diesen Befehlen ja weiterhin repne.
jaenicke - Sa 18.10.08 13:25
Heiko hat folgendes geschrieben : |
Und ich mag die MPL nicht (wenn ichs richtig verstehe muss ein Teil des Codes ja OpenSource sein, was ich aber nicht voraussetzten möchte) ;). |
Die MPL erlaubt die darunter lizenzierten Code auch in proprietären Code einzubinden, solange du alle verwendete Units mit MPL-lizenziertem Code auch unter der MPL zur Verfügung stellst. Und das einige Zeit oder so.
Heißt: Solange du nur MPL-Units einbindest musst du auch nur diese weiter unter der MPL zur Verfügung stellen, wenn du dein Projekt veröffentlichst, dein eigener Code muss nicht Open Source sein, wenn er in anderen Units liegt.
Wie da genau alle Bedingungen sind weiß ich nicht so genau, aber so habe ich das in Erinnerung.
Horst_H hat folgendes geschrieben : |
repne ist doch nur für die Anzahl: |
Wie meinst du das? repne führt doch die Schleife bis zur Abbruchbedingung aus, nämlich bis zum ersten Fund in diesem Fall. :nixweiss:
Heiko - So 19.10.08 00:02
Zur Urspungsversion: kann man hier noch etwas optimieren?
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20:
| function CharPos(const PStr: PAnsiChar; Chr: AnsiChar; StrLen: Integer): Integer; asm push edi push ebx mov edi, eax mov ebx, ecx mov al, dl cld repne scasb JNC @@FOUND xor eax,eax JMP @@END
@@FOUND: mov eax, ebx sub eax, ecx @@END: pop ebx pop edi end; |
Horst_H - Mo 20.10.08 17:15
Hallo,
Laut Fastcode ist CharPos_Sha_Pas_2_c der schnellste Code, der nicht MMX/SSE 1,2... nutzt (Die sind 50 % schneller) . Minimal schneller noch als Assembler-Variante dieses Code's .
Grauselig mit goto..
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:
| function CharPos_Sha_Pas_2_c(ch: char; const s: AnsiString): integer; const cMinusOnes = -$01010101; cSignums = $80808080; var Ndx, Len, c, d, Mask, Sign, Save, SaveEnd: integer; label Small, Middle, Large, Found0, Found1, Found2, Found3, NotFound, Matched, MatchedPlus1, MatchedMinus1, NotMatched, Return; begin c:=integer(@pchar(integer(s))[-4]); if c=-4 then goto NotFound; Len:=pinteger(c)^; if Len>24 then goto Large; Ndx:=4; if Ndx>Len then goto Small;
Middle: if pchar(c)[Ndx+0]=ch then goto Found0; if pchar(c)[Ndx+1]=ch then goto Found1; if pchar(c)[Ndx+2]=ch then goto Found2; if pchar(c)[Ndx+3]=ch then goto Found3; inc(Ndx,4); if Ndx<=Len then goto Middle;
Ndx:=Len+1; if pchar(c)[Len+1]=ch then goto Found0; if pchar(c)[Len+2]=ch then goto Found1; if pchar(c)[Len+3]<>ch then goto NotFound; Result:=integer(@pchar(Ndx)[-1]); exit; goto Return; Small: if Len=0 then goto NotFound; if pchar(c)[Ndx+0]=ch then goto Found0; if Len=1 then goto NotFound; if pchar(c)[Ndx+1]=ch then goto Found1; if Len=2 then goto NotFound; if pchar(c)[Ndx+2]<>ch then goto NotFound;
Found2: Result:=integer(@pchar(Ndx)[-1]); exit; Found1: Result:=integer(@pchar(Ndx)[-2]); exit; Found0: Result:=integer(@pchar(Ndx)[-3]); exit; NotFound: Result:=0; exit; goto NotFound; Found3: Result:=integer(@pchar(Ndx)[0]); exit; goto Return; Large: Save:=c; Mask:=ord(ch); Ndx:=integer(@pchar(c)[+4]);
d:=Mask; inc(Len,c); SaveEnd:=Len; Mask:=(Mask shl 8); inc(Len,+4-16+3);
Mask:=Mask or d; Len:=Len and (-4); d:=Mask; cardinal(Sign):=cSignums;
Mask:=Mask shl 16; c:=pintegerArray(Ndx)[0]; Mask:=Mask or d; inc(Ndx,4);
c:=c xor Mask; d:=integer(@pchar(c)[cMinusOnes]); c:=c xor (-1); c:=c and d; d:=Mask;
if c and Sign<>0 then goto MatchedMinus1; Ndx:=Ndx and (-4); d:=d xor pintegerArray(Ndx)[0];
if cardinal(Ndx)<cardinal(Len) then repeat; c:=integer(@pchar(d)[cMinusOnes]); d:=d xor (-1); c:=c and d; d:=Mask;
d:=d xor pintegerArray(Ndx)[1]; if c and Sign<>0 then goto Matched; c:=integer(@pchar(d)[cMinusOnes]); d:=d xor (-1); c:=c and d; d:=pintegerArray(Ndx)[2]; if c and Sign<>0 then goto MatchedPlus1; d:=d xor Mask;
c:=integer(@pchar(d)[cMinusOnes]); d:=d xor (-1); inc(Ndx,12); c:=c and d;
d:=Mask; if c and Sign<>0 then goto MatchedMinus1; d:=d xor pintegerArray(Ndx)[0]; until cardinal(Ndx)>=cardinal(Len);
Len:=SaveEnd; while true do begin; c:=integer(@pchar(d)[cMinusOnes]); d:=d xor (-1); c:=c and d; inc(Ndx,4); if c and Sign<>0 then goto MatchedMinus1; d:=Mask; if cardinal(Ndx)<=cardinal(Len) then d:=d xor pintegerArray(Ndx)[0] else begin; if Len=0 then goto NotMatched; d:=d xor pintegerArray(Len)[0]; Ndx:=Len; Len:=0; end end;
NotMatched: Result:=0; exit;
MatchedPlus1: inc(Ndx,8); MatchedMinus1: dec(Ndx,4); Matched: c:=c and Sign; dec(Ndx,integer(Save)+2); if word(c)=0 then begin; c:=c shr 16; inc(Ndx,2); end; if byte(c)<>0 then dec(Ndx); Result:=Ndx; Return: end; |
Wie Du erkennst, werden bei langen Strings(len>24) 4 Byte aufeinmal verarbeitet.
Das macht es schnell.Rate mal wie viele MMX und SSE vergleichen.
Die Geschwindigkeit hängt jetzt sehr davon, ob Du sehr lange oder kurze Strings untersuchst.
http://www.math.uni-wuppertal.de/~fpf/Uebungen/GdR-SS02/opcode_i.html
Dort steht ja 4 Takte für einen Pentium pro Vergleich mittels scas(..b/w/d)
Also 16 Takte pro integer.
Teste es doch mal selbst in einem Vergleich.
erzeuge einen String mit #1 bis #255 und lasse darin nach #1.. #255 suchen len ist eben immer 255
Oder du testest mit verschiedenen Längen 1,4,5,23,24,32,33,63,64,255.
Viel Spass dabei.
Gruß Horst
BenBE - Mo 20.10.08 17:29
Was ist an Goto eigentlich so gruselig??? Ist doch auch nur Source ;-)
jaenicke - Mo 20.10.08 18:34
Sprich es mal aus :D:
[Tiefe Stimme]Gooooo....toooooo... *echo* *schall*[/Tiefe Stimme]
Heiko - Mi 19.11.08 22:26
moin moin,
da hier ja nach Testerfahrungen gefragt wurde: also bisher habe ich nur die repne-Variante getestet. Allerdings ist die Variante um Faktor 4 langsamer als das readln von Delphi. Hat einer von euch da ne Ahnung, wo ich so ineffizient bin bzw. wie Borland es macht? Ich sehe im ASM-Code von readln leider nicht durch, wie er genau vorgeht.
Horst_H - Do 20.11.08 15:19
Hallo,
Dein readln bremst Dich doch garnicht:
aus deiner *.dpr habe ich statt readln einfach nur die Position geändert:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7:
| FSW:=TFileStreamW.Create('Test.txt', fmOpenRead); t:=GetTickCount; while FSW.Position<FSW.Size do FSW.Position:= FSW.Position+i; inc(t2, GetTickCount-t); FSW.Free; |
Das ist 2 Sekunden schneller als readln.
readln 12,5 Sekunden /Position ändern 10,4 Sekunden.
Du suchst an der falschen Stelle nach der Bremse im System.
Gruß Horst
jaenicke - Do 20.11.08 15:46
Was ist i? Du änderst so doch nur die Position um einen festen Wert? Was hat das mit dem Thema zu tun?
Horst_H - Do 20.11.08 18:17
Hallo,
Es wird eine Textdatei erzeugt in der alle i Zeichen ein CR/LF/CR+LF eingefügt wird.
Damit rücke ich im Stream genauso oft vor wie das vorherige auskommentierte readln.
Also wird die while-Schleife genauso oft durchlaufen.Somit hat man ähnliche Bedingungen.
Also readln wird nicht ausgeführt, bei dem beim Einlesen auch die Position geändert wird.
Der overhead für das Einlesen und suchen nach dem Zeilenende selbst wollte ich wissen.
Das verzweifelte suchen Heiko's ,nach einer Beschleungung der CharPos - Funktion, geht also am wahren Problem vorbei.
Gruß Horst
Horst_H - Do 20.11.08 19:44
Hallo,
Zitat: |
Der overhead für das Einlesen und suchen nach dem Zeilenende selbst wollte ich wissen. |
Wenn man die Position in so kleinen Schritten ändert, wird der Stream vom Betreibssystem bis dorthin auch eingelesen (falls es das nicht sowieso schon ist, des vorauslesens read ahead) .
Der Zeitliche Unterschied Postion/readln rührt also nur von dem Kopieren der Streamdaten in deinen Puffer und dem suchen des Zeilenendes her.
Und da war ich erstaunt über das geringe Tempo.
Die Datei ist doch just vorher geschrieben worden und müßte noch im Cache sein und mit maximaler Geschwindigkeit gelesen werden können (ich glaube 350 oder 700 Mb/s waren da mal..) also für 1 Mb 30 ms oder so .
Und wenn man bedenkt das Delphi-readln etwas länger als Dein Overhead für Dein-readln braucht, bedeutet dies:
Delphi liest aus dem Cache und Dein readln könnte minimal schneller sein.
Lange Rede keinen Sinn:
Kannst Du meine Messwerte bestätigen Position statt readln nutzend??
Gruß Horst
Heiko - Do 20.11.08 19:52
Horst_H hat folgendes geschrieben : |
Lange Rede keinen Sinn:
Kannst Du meine Messwerte bestätigen Position statt readln nutzend?? |
Ungefähr: Borland-Radln: 3,5Sek. Mein ReadLn: 15Sek. Letzteres nur mir Pos. setzten: 10 Sek.
Allerdings verstehe ich auch nicht, wieso Borland da schneller ist. Denn eigentich müssten wir beide aufn Cache zugreifen, sofern Win den nutzt...
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 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!