Funktionsaufruf: Dauert immer länger. Warum?

[Go2EITS]

Hallo, nachstehendes Programm bitte einmal ausprobieren.

In der vorliegenden Version wird Clearstring1 immer langsamer. Ich kann es nicht erklären.
Die drei Funktionen unterscheiden sich nur durch die Konstanten:
1. ValidChars = ['a'..'z','A'..'Z'];
2. ValidChars = ['a'..'z','A'..'Z',' '];
3. ValidChars = ['a'..'z','A'..'Z','ä','ö','ü','Ä','Ö','Ü','ß',' '];

Paradoxerweise ist die zweite Variante schneller als die erste! (Ich habe nur ein SPACE in ValidChars hinzugefügt). Probiert dies bitte aus.

Zur Funktion: Clearstring gibt einen "bereinigten" String zurück.
Welche Zeichen dann enthalten sind, wird mit z.B. ValidChars = ['a'..'z','A'..'Z']; definiert.

Delphi-Quellcode:

program ClearString;

{$APPTYPE CONSOLE}

uses
  //FastMM4,FastMove,
  SysUtils, // Für Profiler.inc notwendig
  Windows;  // Für Profiler.inc notwendig
{$include Profiler.inc}
var
  xx,ii:Integer;
// Langsame Variante
function ClearStr1(const Str: string): String;
var
  i:Integer;
const
ValidChars = ['a'..'z','A'..'Z'];
  begin
  if Str = '' then Exit;
  for i:=1 to Length(Str) do if str[i] in ValidChars then result:=result+Str[i];
end;

// Diese ist schneller...
function ClearStr2(const Str: string): String;
var
  i:Integer;
const
ValidChars = ['a'..'z','A'..'Z',' ']; // Schnelle Variante
  begin
  if Str = '' then Exit;
  for i:=1 to Length(Str) do if str[i] in ValidChars then result:=result+Str[i];
end;

function ClearStr3(const Str: string): String;
var
  i:Integer;
const
ValidChars = ['a'..'z','A'..'Z','ä','ö','ü','Ä','Ö','Ü','ß',' '];
  begin
  if Str = '' then Exit;
  for i:=1 to Length(Str) do if str[i] in ValidChars then result:=result+Str[i];
end;


begin
Writeln('Teste... ClearStr1');
for xx:=1 to 10 do
   begin
   Start;
   for ii:=1 to 10000 do ClearStr1('>a-uf d?er  Ma!uer<');
   Stopp;
   end;
Writeln('Ergebnis muss - aufderMauer - sein:');
Writeln(ClearStr1('>a-uf d?er  Ma!uer<'));Writeln;


Writeln('Teste... ClearStr2');
for xx:=1 to 10 do
    begin
    Start;
    for ii:=1 to 10000 do ClearStr2('>a-uf d?er  Ma!uer<');
    Stopp;
    end;
Writeln('Ergebnis muss - auf der  Mauer - sein:');
Writeln(ClearStr2('>a-uf d?er  Ma!uer<'));Writeln;

Writeln('Teste... ClearStr3');
for xx:=1 to 10 do
    begin
    Start;
    for ii:=1 to 10000 do ClearStr3('>a-uf d?er  Ma!uer<');
    Stopp;
    end;
Writeln('Ergebnis muss - auf der  Mauer - sein:');
Writeln(ClearStr3('>a-uf d?er  Ma!uer<'));Writeln;

Writeln('- ProgrammEnde mit [ENTER] -');Readln;

end.

Die Include:

Delphi-Quellcode:

// Date:  08.04.2009
// File:  Profiler.inc

//Timer Variablen
 var Profiler_StartWert, Profiler_StopWert, Profiler_Freq: int64;

/// Profiler Routinen Start...
procedure Start;
begin
QueryPerformanceFrequency(Profiler_Freq);
QueryPerformanceCounter(Profiler_StartWert);
end;

procedure Stopp;
begin
QueryPerformanceCounter(Profiler_StopWert);
Writeln('Profiler: '+floattostr(((Profiler_StopWert-Profiler_StartWert)/Profiler_Freq)*1000)+' ms');
end;
/// ...Profiler Routinen Ende

Ich habe, eigentlich nur aus "Spaß", die FastMM4 mit eingebunden, da funktioniert es plötzlich.
Ist es ein BUG in Delphi 7? Und wenn ja, kann ich diesen ohne FastMM4 umgehen?
[Edit: Titel geändert]

[Hawkeye219]

Hallo,

du solltest den Rückgabewert deiner Funktionen initialisieren, sonst wird der String immer länger: klick

Gruß Hawkeye

[Go2EITS]

@Hawkeye219:
Opps, so einfach. Es funktioniert. Allein wäre ich nie darauf gekommen. Danke! :thumb:
Wenn man FastMM4 und FastNove einbindet, wird die Funktion noch schneller.

[DP-Maintenance]

Dieses Thema wurde von "mkinzler" von "Programmieren allgemein" nach "Sonstige Fragen zu Delphi" verschoben.
Ist eine Delphi-Frage

[jbg]

Und wenn man statt "result:=result+Str[i]" einmalig die Worstcase-Länge bestimmt und am Ende dann die echte Länge setzt, wird das ganze noch schneller.

[Go2EITS]

@Jbg: Wie soll das gehen?
Wenn ich einmal den Übergabestring durchlaufe und gleichzeitig den neuen String bilde mit "result:=result+Str[i]" habe ich wohl die schnellste Version.
Ein

Delphi-Quellcode:

for i:=1 to Length(Str) do if str[i] in ValidChars then s:=s+str[i];
result:=s;

bringt keinen Geschwindigkeitsvorteil.
Ich gehe mal davon aus, dass "str[i] in ValidChars " abbricht, wenn es einen gültigen Char gefunden hat und nicht immer bis zum Ende durchläuft. Sonst dürfte eine Tabelle schneller sein.

[Go2EITS]

Ich habe mal beide Versionen nachstehend eingefügt.
a) Version mit der Mengenabfrage und b) Abfrage mit einer Tabelle.

Delphi-Quellcode:

program ClearString1;

{$APPTYPE CONSOLE}

uses
  FastMM4, FastMove,
  SysUtils, // Für Profiler.inc notwendig
  Windows;  // Für Profiler.inc notwendig
{$include Profiler.inc}
var
  xx,ii:Integer;
var
  ValidChars1: array[1..53] of Char = ('a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',' ','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z');

// Alte Version:
function ClearStrAlt(const Str: string): String;
var
  i:Integer;
const
ValidChars = ['a'..'z','A'..'Z','ä','ö','ü','Ä','Ö','Ü','ß',' '];
  begin
  if Str = '' then Exit;
  result:='';
  for i:=1 to Length(Str) do if str[i] in ValidChars then result:=result+Str[i];
end;

//Neue Version:
function ClearStr(const Str: string): String;
var
  i,x:Integer;
  begin
  if Str = '' then Exit;
  result:='';
  for i:=1 to Length(Str) do
      begin
      for x:=1 to 53 do
      if (str[i] =  ValidChars1[x]) then //Hier durchlaufen wir die Tabelle
         begin
         result:=result+Str[i];
         Break; //... und for-Schleife verlassen.
         end;
  end;
end;

begin

Writeln('Teste... ClearStr - Alte Version:');
for xx:=1 to 10 do
   begin
   Start;
   for ii:=1 to 100000 do ClearStrAlt('>a-uf d?er  Ma!uer<');
   Stopp;
   end;
Writeln('Ergebnis muss - auf der  Mauer - sein:');
Writeln(ClearStrAlt('>a-uf d?er  Ma!uer<'));Writeln;

Writeln('Teste... ClearStr - Neue Version:');
for xx:=1 to 10 do
   begin
   Start;
   for ii:=1 to 100000 do ClearStr('>a-uf d?er  Ma!uer<');
   Stopp;
   end;
Writeln('Ergebnis muss - auf der  Mauer - sein:');
Writeln(ClearStr('>a-uf d?er  Ma!uer<'));Writeln;
Writeln('- ProgrammEnde mit [ENTER] -');Readln;
end.

Fazit: Die Version mit der Menge ist deutlich schneller, als die mit der Tabelle.
Das Einbinden von FastMM4 und Move bringt nochmals einen deutlichen Gewindigkeitsschub.

[Cyf]

Delphi-Quellcode:

SetLength(Result, Length(Str));
for ...
begin
  Result[i]:= Str[i]; //falsch, siehe nächster Post
  Inc(Count);
end;
SetLength(Result, Length(Count));

[Edit] http://www.delphi-treff.de/delphi-st...e/anweisungen/

[Edit2]Ja, natürlich. :wall:

[Christian Seehase]

Moin Cyf,

vielleicht besser so ;-)

Zitat:

Zitat von Cyf

Code:

SetLength(Result, Length(Str));
for ...
begin
  Result[[color=red]Count[/color]]:= Str[i];
  Inc(Count);
end;
SetLength(Result, Length(Count));

[EDIT]
@Go2EITS:
Ein String ist eigentlich ein dynamisches Array.
Wenn Du dieses verlängerst, muss, normaler Weise, jedesmal der Speicher neu angefordert, und der bisherige Inhalt dort hineinkopiert werden. Deswegen sollte man, nach Möglichkeit, ein dynamisches Array von Anfang an so gross machen, wie erforderlich, und erst zum Schluss die Länge setzen.
(Wenn man die Länge nicht vorab genau kennt, empfiehlt es sich, die Länge vorab so gut wie möglich abzuschätzen, und dann, ggf. um mehere Elemente vergrössern, z.B. um 10% des ursprünglichen Schätzwertes. Um welchen Wert man vergrössert sollte davon abhängen, wie gut man den Initialwert abschätzen kann.)
[/EDIT]

[Go2EITS]

Danke Christian und Cyf, nochmals 50% rausgeholt.
Kleine Änderungen am Vorschlag vorgenommen, damit der Text auch angezeigt wird:

Delphi-Quellcode:

// Zur Erinnerung:
// var
//  ValidChars1: array[1..53] of Char = //('a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',' //','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z');


//Neue Version mit Vorschlag von Cyf:
function ClearStrTest(const Str: string): String;
var
  i,x,count:Integer;
begin
  if Str = '' then Exit;
  result:='';
  count:=1;     // Start bei 1..
  SetLength(Result, Length(Str));
  for i:=1 to Length(Str) do
      begin
      for x:=1 to 53 do
      if (str[i] =  ValidChars1[x]) then //Hier durchlaufen wir die Tabelle
         begin
         Result[Count]:= Str[i];
         Inc(Count);
         Break; //... und for-Schleife verlassen.
         end;
      end;
  SetLength(result, Count-1); //... und hier 1 wieder abgezogen
end;

Möglicherweise geht es mit Pointern noch schneller?
[Edit] Damit "schlägt Tabelle die Menge", vorausgesetzt die Tabelle ist so groß wie oben.

[3_of_8]

Zitat:

Zitat von Christian Seehase

Wenn Du dieses verlängerst, muss, normaler Weise, jedesmal der Speicher neu angefordert, und der bisherige Inhalt dort hineinkopiert werden.

Naja, ned unbedingt. Ich bin mir jetzt nicht ganz sicher, aber ich denke schon, dass der Delphi-Speichermanager schlau genug ist, um das Array einfach zu vergrößern, wenn noch genug Platz dahinter frei ist - also es wird nicht bei jeder Größenänderung das gesamte Array kopiert.
Trotzdem ist es natürlich besser, eher einmal zu viel anzufordern als mehrmals stückchenweise.

EDIT: @Go2EITS: Strings sind, wie alle dynamischen Arrays, sowieso intern Pointer auf dem Stack, die auf irgendeinen Bereich auf dem Heap zeigen. Wenn du da was mit Pointern machst, ist das intern genau das gleiche, nur schwerer zu lesen.

[Go2EITS]

@3_of_8
Bin mir da nicht so sicher, ob es mit Pointern manchmal doch schneller geht... :gruebel:
Vielleicht, weil man dann maschinennäher programmiert?

[3_of_8]

Das kann man so allgemein nicht sagen. Du kannst auch in Assembler langsamen Code programmieren. Delphi verwaltet Strings intern auch einfach als Pointer auf den Heap. Anders kannst du es auch nicht machen.

[Go2EITS]

Ich habe die Version von Christian einfach mal probeweise mit der Mengenabfrage probiert.
Und das Ergebnis ist, 145 ms zu 45ms mit der Mengenabfrage! So sieht der momentan schnellste Code aus:

Delphi-Quellcode:

function ClearStr4(const Str: string): String;
const
ValidChars = ['a'..'z','A'..'Z','ä','ö','ü','Ä','Ö','Ü','ß',' '];
var
  i,x,count: Integer;
  begin
  if Str = '' then Exit;
  result:= '';
  count:= 1;
  SetLength(Result, Length(Str));
  for i:= 1 to Length(Str) do
      begin
      if str[i] in ValidChars then //Hier fragen wir die Menge ab.
         begin
         Result[Count]:= Str[i];
         Inc(Count);
         end;
      end;
  SetLength(result, Count-1);
  end;

Tabelle schlägt Menge ist hiermit wiederlegt. Mit FastMM4 und FastMove.pas gibt es nochmals einen Geschwindigkeitsschub.
Im Anhang die einzelnen Exen und den Source incl. der Exen beigefügt.
[Edit: Move.pas heißt FastMove.pas und //Break... aus Source entfernt]

[jaenicke]

Ich würde noch die impliziten Aufrufe von UniqueString unterdrücken indem ich diese Automatik durch Pointer aushebele. Damit komme ich auf ca. 20ms:

Delphi-Quellcode:

function ClearStr5(const Str: string): String;
const
  ValidChars = ['a'..'z','A'..'Z','ä','ö','ü','Ä','Ö','Ü','ß',' '];
var
  i, Len: Integer;
  CurIn, CurOut: ^Char;
begin
  Len := Length(Str);
  SetLength(Result, Len);
  CurIn := Pointer(Str);
  CurOut := Pointer(Result);
  for i := 1 to Len do
  begin
    if CurIn^ in ValidChars then
    begin
      CurOut^ := CurIn^;
      Inc(CurOut);
    end;
    Inc(CurIn);
  end;
  SetLength(Result, Integer(CurOut) - Integer(Pointer(Result)));
end;

[jbg]

Zitat:

Zitat von jaenicke

CurIn, CurOut: ^Char;

Und hierfür gibt es bereits den Datentyp PChar.

Zitat:

SetLength(Result, Integer(CurOut) - Integer(Pointer(Result)));

Einen Zeiger in einen Integer zu konvertieren funktioniert unter Win32, aber unter Win64 wird der Code dann so nicht mehr funktionieren. Und da der Compiler eine Spezialbehandlung für PChar bereitstellt, kann man sich die Konvertierung nach Integer auch ganz sparen.

Zitat:

SetLength(Result, CurOut - PChar(Pointer(Result)));

[Go2EITS]

@Janicke
Was Pointer, richtig eingesetzt, bewirken können. Das Ergebnis und die vorhergehenden Vorschläge sind sehr lehrreich und wohl auch für andere DP'ler interessant. Vielen Dank!

[jaenicke]

Es hilft zur Optimierung oft in den generierten Assemblercode zu schauen. Ich wusste das ja nun schon, aber wenn man da nachschaut, dann sieht man, dass bei jedem Zugriff auf ein Zeichen UniqueString aufgerufen wird, wenn man normale Strings benutzt.

Mit PChar wie jbg sagte kann man das genauso verhindern, da diese Automatik nur bei Delphi-Strings passiert, deshalb ist das natürlich besser, wenn du das noch entsprechend änderst.

Der Grund für den Aufruf von UniqueString ist, dass Delphi (in 4 Byte beginnend 8 Byte vor dem Beginn des Strings, auf den der Pointer in der String-Variable zeigt) bei Strings einen Referenzzähler mitführt, der die Anzahl der Referenzen auf den String zählt um den String bei 0 verbleibenden Referenzen freizugeben. Deshalb wird bei jeder Veränderung des Strings mit UniqueString sichergestellt, dass man nicht einen anderweitig referenzierten String verändert. Und das eben bei jedem Zeichen.