#0 perfomanceschonend aus String entfernen

[shmia]

Zitat:

Zitat von p80286

scheint mir "doppeltgemoppelt" und daher eigentlich ein Performance Killer.

Der Performance Killer ist die Indizierung durch den Array-Index.
Wenn da z.B. steht: s[i] , dann wird intern der Zeiger s genommen, dann wird i dazuaddiert, dies ergibt dann den Zeiger auf das zu lesende oder schreibende Zeichen.
Bei einem 4MB-String wären das 8 Millionen unnötige Additionen.

Hier die komplett getunte Funktion:

Delphi-Quellcode:

function StrReplaceChar(const S: Ansistring; const Source, Replace: AnsiChar): AnsiString; 
var 
  I: Integer;
  p : PAnsiChar;
begin 
  Result := S;
  UniqueString(Result);
  p := PAnsiChar(Result);
  for I := Length(S)-1 downto 0 do 
  begin
    if p^ = Source then 
      p^ := Replace;
    Inc(p);
  end;
end;

Hier wird der Zeiger p einmal gesetzt und dann immer nur mit Inc() weiterbewegt.
Inc(p) wird direkt in einen einzigen (schnellen) X86-Befehl übersetzt.
Da die Schleifenvariable nicht mehr benützt wird, kann man die Schleife auch rückwärts laufen lassen.
Schleifen, die rückwärts runter auf 0 zählen sind besonders gut in Maschinencode zu übersetzen und daher sehr schnell.

[alzaimar]

[quote="shmia"]

Zitat:

Zitat von p80286

Bei einem 4MB-String wären das 8 Millionen unnötige Additionen.

Ist das nicht eher indirekte Adressierung? Und was ist eigentlich das 'Inc(P)'? Ist das nicht auch eine Addition?

Meiner Erfahrung nach ist der Unterschied in diesem Fall marginal. Und wenn ich es ausprobiere, sehe ich auch keinen Unterschied. Ich würde dann die naive For-Schleife und einen stinknormalen String mit Index verwenden:

Delphi-Quellcode:

For i:=1 to Length(s) do
  if s[i]=ZuErsetzendesZeichen then 
    s[i] := NeuesZeichen;

Zitat:

Zitat von shmia

Hier die komplett getunte Funktion:...Schleifen, die rückwärts runter auf 0 zählen sind besonders gut in Maschinencode zu übersetzen und daher sehr schnell.

Hmm.. Zählt Dephi nicht automatisch rückwärts, wenn es keine Auswirkungen hat?
Hast Du wirklich verifiziert, das deine getunte Funktion schneller ist? Bei mir ist sie das nämlich nicht.

Ich stolpere immer wieder über diesen Vergleich zwischen Pointer und Indizierung. Bei solch naiven Schleifen sind beide gleich schnell, aber sobald man etwas mehr in der Schleife macht, ist die Pointer-Variante immer etwas schneller (20-30%, na ja, 'etwas'...)

Um es schneller zu bekommen, würde ich mir mal FastCode reinziehen, da gibt es eine 'CharPos' Funktion, die mit Sicherheit sehr viel schneller ist als die einfache Schleife. Sie verwendet Fluxkompensatoren, vierdimensionale Zeitfalten und *tunnelt* den Code, sodaß das das Programm fertig ist, bevor man überhaupt auf start gedrückt hat. Glaub ich jedenfalls.

[himitsu]

Blos noch etwas Zusätzliches:

PChar(S) gibt nur einen Zeiger auf das erste String-Zeichen oder bei einem Leerstring auf einen "anderen" Bereich, welcher auf 0000 steht.

@S[1] ruft UniqueString auf und gibt einen Zeiger auf das 1. Zeichen oder nil zurück.

StringReplace und #0 im zu Suchstring, sowie im zu durchsuchendem String geht nicht, da CodEmba blöder Weise intern eine auf PChar-basierende Pos-Funktion nutzen, welche ja bekanntlich bei #0 stoppen. :wall:

PS: diese Move-Funktionen sind insoweit nicht gefährlich, wie man auf die Datengößen achtet und weiß was man tut.
Bei dem StringStream muß man in diesem Fall ab D2009 auch aufpassen, daß man nicht durch ein falsches/unpassendes Encoding die Daten zerschrottet.
PSS: Aus soeinem Grund hatte ich auch extra den AnsiString, statt String verwendet.

[p80286]

Hallo zusammen

ich hab mich dann mal aufgemacht und quickndirty versucht heraus zu bekommen was es in der Praxis bring:

Zitat:

---------------------
2063 1.lauf
---------------------
2000 2.lauf

Delphi-Quellcode:

function StrReplaceChar(const S: Ansistring; const Source, Replace: AnsiChar): AnsiString;
var
  I: Integer;
  p : PAnsiChar;
begin
  Result := S;
  UniqueString(Result);
  p := PAnsiChar(Result);
  for I := Length(S)-1 downto 0 do
  begin
    if p^ = Source then
      p^ := Replace;
    Inc(p);
  end;
end;

function StrReplaceChar_(const S: Ansistring; const Source, Replace: AnsiChar): AnsiString;
var
  I: Integer;
begin
  Result := S;
  UniqueString(Result);
  for I := Length(S)-1 downto 0 do
    if result[i] = Source then
      result[i] := Replace;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  i,j : integer;
  start1,
  start2,
  end1,
  end2 : integer;
  ts   : string;
begin
  setlength(ts,4096*1024);

  fillchar(ts[1],length(ts),#32);
  for i:=1 to 4096 do
    if i mod 13 =0 then ts[i]:=#0;
  start1:=gettickcount;
  for j:=0 to 255 do
    StrReplaceChar(ts,#0,'A');
  end1:=gettickcount;
  {---------------------------------------------}
  fillchar(ts[1],length(ts),#32);
  for i:=1 to 4096 do
    if i mod 13 =0 then ts[i]:=#0;
  start2:=gettickcount;
  for j:=0 to 255 do
    StrReplaceChar_(ts,#0,'A');
  end2:=gettickcount;
  memo1.lines.add('---------------------');
  memo1.lines.add(inttostr(end1-start1)+' 1.lauf');
  memo1.lines.add('---------------------');
  memo1.lines.add(inttostr(end2-start2)+' 2.lauf');
end;

Ja ich weiß, Zeitmessung mit tickcount sind alles andere als genau, (ich hab die bessere Funktion nicht mehr gefunden) aber da der Fehler bei beiden Versionen auftritt ignorier ich ihn einfach.
Irgendwie drängt sich mir der Schluß auf, daß beide Varianten gleich schnell sind.

Gruß
K-H

[himitsu]

Erstmal das:
sonst würde ja schon beim ersten Durchlauf alles erstetzt und die letzten 255 Mal passiert nicht mehr viel.

Und dann:
Tja, da siehst du mal, wie gut der Compiler optimiert. :stupid:

[p80286]

Zitat:

Zitat von himitsu

Erstmal das:
sonst würde ja schon beim ersten Durchlauf alles erstetzt und die letzten 255 Mal passiert nicht mehr viel.

Äh, willst Du mich auf den Arm nehmen? die Schleife über den String durchläuft er trotzdem, nur die eigentliche Ersetzen-Funktion fällt weg, und darum ging es Doch?

Gruß
K-H

[himitsu]

:oops: Ups, ich glaub ich war vorhin so sehr in Klassenprozeduren vertieft, daß ich das Function glatt übersah. :shock:

Zitat:

Zitat von himitsu

Tja, da siehst du mal, wie gut der Compiler optimiert. :stupid:

Nja, dann bleibt immernoch das übrig. :angel:


Ach ja, das Andere wäre z.B. QueryPerformanceCounter gewesen,
aber auf die ~16 Millisekunden kommt es bei den "langen" Messzeiten wirklich nicht an.

[p80286]

Mann könnte annehmen, daß heute Freitag ist.

???????????????????????????????????????????????

Gruß
K-H