Stringkonkatenation ist schneller als direktes Kopieren?

[alzaimar]

Die ganzen Jahre predige ich, das man ständige Stringkonkatenationen vermeiden soll, und normalerweise stimmt das auch.
Aber hier nicht:

Delphi-Quellcode:

Function V1(s: TStringList): Integer;
Var
  i: Integer;
  x: String;

Begin
  x := '';
  For i := 0 To s.count - 1 Do
    x := x + s[i];
  Result := Length(x)
End;

Function V2(s: TStringList): Integer;
Var
  l, i, j, n: Integer;
  z, x: String;

Begin
  n := 0;
  For i := 0 To s.count - 1 Do
    inc(n, Length(s[i]));
  SetLength(x, n);
  j := 1;
  For i := 0 To s.count - 1 Do Begin
    z := s[i];
    l := Length(z);
    Move(z[1], x[j], l);
    inc(j, l);
  End;
 Result := Length (x);
End;

(Bitte keine Kommentare wegen der Variablennamen, ok?)

Preisfrage: Was ist schneller? V1 oder V2?

Ihr werdet's nicht glauben: Das ach so dilletantische V1.

Die Frage ist: Wieso?

[Apollonius]

Interessant. Hast du mal geschaut, wie es aussieht, wenn du statt der Stringliste ein Array verwendest? Dann könnte man zumindest den Bereichsüberprüfungs-Overhead vermeiden.

[SirThornberry]

ich würde es mal auf die Stringliste schieben. Folgendes Ergebnis bekomme ich wenn ich in V2 nur die schleife zum zählen der Länge noch drin hab.
Stringkonkatenation: 453
Direktes Einkopieren: 219

Delphi-Quellcode:

Function V2(s: TStringList): Integer;
Var
  l, i, j, n: Integer;
  z, x: String;

Begin
  n := 0;
  For i := 0 To s.count - 1 Do
    inc(n, Length(s[i]));
  result := n;

  {
  SetLength(x, n);
  j := 1;
  For i := 0 To s.count - 1 Do Begin
    z := s[i];
    l := Length(z);
    Move(z[1], x[j], l);
    inc(j, l);
  End;
  Result := Length (x);
 }
End;

[Gausi]

Wenn man z weglässt, und direkt immer auf s[i] zugreift, wird v2 deutlich schneller (aber immer noch langsamer als v1). Wahrscheinlich ist die Compiler-Magic bei Strings einfach wirklich gut. :stupid:

[SirThornberry]

das langsame ist einfach die get-methode hinter dem Stringlist.Strings property.

[jbg]

Da sind noch zwei UniqueString Aufrufe drinnen.

Aber das Hauptproblem sind die 3 LOCK Instruktionen die im LStrAsg enthalten sind (zwei Explizite und eine durch XCHG reg,mem). Und wenn z genutzt wird hat man den LStrAsg Aufruf in TStringList.Get und dann nochmal bei der Zuweisung an z. Das macht also 6 LOCKs, was der Geschwindigkeit natürlich gar nicht gut tut. Vor allem wenn man ein Mehrprozessorsystem besitzt.

[jfheins]

Ich werfe jetzt einfahc mal die Methode der VCL ins Rennen:

Delphi-Quellcode:

function TStrings.GetTextStr: string;
var
  I, L, Size, Count: Integer;
  P: PChar;
  S, LB: string;
begin
  Count := GetCount;
  Size := 0;
  LB := LineBreak;
  for I := 0 to Count - 1 do Inc(Size, Length(Get(I)) + Length(LB));
  SetString(Result, nil, Size);
  P := Pointer(Result);
  for I := 0 to Count - 1 do
  begin
    S := Get(I);
    L := Length(S);
    if L <> 0 then
    begin
      System.Move(Pointer(S)^, P^, L);
      Inc(P, L);
    end;
    L := Length(LB);
    if L <> 0 then
    begin
      System.Move(Pointer(LB)^, P^, L);
      Inc(P, L);
    end;
  end;
end;

Wenn die direkte Kondingsda wirklich schneller ist, warum haben die Jungs bei codegear das dann so gemacht?

[alzaimar]

Noch lustiger: Ich ersetze also TStringList mit einem dynamischen Stringarray... Lasst Euch überraschen :shock:

Nebenbei: Die Ursache in TStringList zu suchen, halte ich für falsch, denn das wird ja in beiden Routinen aufgerufen. Ich kann die Berechnung der Gesamtlänge auch weglassen, schneller als die Konkatenation wirds damit auch nicht. Und dann wird in beiden Routinen GetTextStr gleich oft aufgerufen.

[jbg]

Lass das ganze doch mal unter Delphi 1, 2, 3, 4, 5, 6, 7 und 2005 laufen. Dann wirst schon sehen, warum die das so gemacht haben. Tipp: Ab Delphi 2006 wird der FastMM4 als Standard Speichermanager eingesetzt.


Der FastMM ist fast nicht zu schlagen. Aber ein paar mickrige Millisekunden habe ich dann doch noch herausschlagen können. Die lassen sich aber nicht mittels GetTickCount ermitteln.

Delphi-Quellcode:

Function V2(s: TStringList): Integer;
Var
  l, i, j, n: Integer;
  z: PChar;
  x: String;
  Arr: array of record
    Data: PChar;
    Len: Integer;
  end;
Begin
  n := 0;
  SetLength(Arr, s.Count);
  For i := 0 To s.count - 1 Do
  begin
    Arr[i].Data := PChar(s[i]); // nur einmal in s.Get(i) wird LStrAsg ausgeführt => 3x LOCK
    Arr[i].Len := Length(PString(@Arr[i].Data)^);
    inc(n, Arr[i].Len);
  end;

  SetLength(x, n);
  j := 0; // PChar startet bei 0
  For i := 0 To High(Arr) Do Begin
    z := Arr[i].Data;
    l := Arr[i].Len;
    Move(z^, PChar(PChar(Pointer(x)) + j)^, l * SizeOf(Char)); // kein UniqueString aufrufen
    inc(j, l);
  End;
 Result := Length (x);
End;

procedure TForm1.btClick(Sender: TObject);
Var
  s: TStringList;
  i : IntegeR;
  t0 : Cardinal;
  z0: Int64;
  z1: Int64;
  Freq: Int64;
begin
  QueryPerformanceFrequency(Freq);
  s := TStringlist.Create;
  try
    for i:=1 to 1000000 do s.add(IntToStr(i));

    QueryPerformanceCounter(z0);
    v1(s);
    QueryPerformanceCounter(z1);
    Memo.Lines.Add('Stringkonkatenation: '+FloatToStr((z1 - z0) / Freq));

    QueryPerformanceCounter(z0);
    v2(s);
    QueryPerformanceCounter(z1);
    Memo.Lines.Add('Direktes Einkopieren: '+FloatToStr((z1 - z0) / Freq));
  finally
    s.free;
  end;
end;

Stringkonkatenation: 0,07990568633723
Direktes Einkopieren: 0,072708333042328

[SirThornberry]

auch unter Delphi7 ist V2 langsamer.

[Meflin]

Zitat:

Zitat von alzaimar

Noch lustiger: Ich ersetze also TStringList mit einem dynamischen Stringarray... Lasst Euch überraschen

Womit meine Ergebnisse aus dem anderen Thread ja bestätigt wären :stupid:

Freut mich, dass meine Frage zu einer so regen Diskussion geführt hat :mrgreen: Ich hoffe es kommt auch noch was schnelles dabei raus :zwinker:

[jbg]

Zitat:

Zitat von Meflin

Ich hoffe es kommt auch noch was schnelles dabei raus

Klar geht es noch schneller. Nur wird es dann ziemlich lowlevelig und spezialisierter.

Delphi-Quellcode:

type
  THackedStringList = class(TStrings) // funktioniert nur noch mit echten TStringList Klassen
  public
    FList: PStringItemList;
  end;

function V2(s: TStringList): Integer;
var
  l, i, j, n: Integer;
  z: PChar;
  x: String;
  Arr: array of record
    Data: PChar;
    Len: Integer;
  end;
begin
  n := 0;
  SetLength(Arr, s.Count);
  for i := 0 To s.Count - 1 Do
  begin
    Arr[i].Data := Pointer(THackedStringList(s).FList[i].FString); // kein CPU LOCK mehr
    Arr[i].Len := Length(PString(@Arr[i].Data)^);
    Inc(n, Arr[i].Len);
  end;

  SetLength(x, n);
  j := 0; // PChar startet bei 0
  for i := 0 To High(Arr) do
  begin
    z := Arr[i].Data;
    l := Arr[i].Len;
    Move(z^, PChar(PChar(Pointer(x)) + j)^, l * SizeOf(Char)); // kein UniqueString aufrufen
    Inc(j, l);
  end;

  Result := Length(x);
end;

[alzaimar]

@jbg: Wir argumentieren doch immer so, das bei einer Stringkonkatenation (hier) 1 Mio mal neuer Speicher angefordert und der String umkopiert werden muss, und das dauert und daher sollte man V2 nehmen. Wir alle predigen das, und das basiert ja i.A. auf eigenen Erfahrungen.

Wenn man das dann mal manifestieren will (sozusagen als Demo fur Dummies), fällt man so richtig (aber so richtig!) auf die Plautze.

Ehrlich gesagt bin ich etwas verwirrt.

[jbg]

Zitat:

Zitat von alzaimar

@jbg: Wir argumentieren doch immer so, das bei einer Stringkonkatenation (hier) 1 Mio mal neuer Speicher angefordert und der String umkopiert werden muss, und das dauert und daher sollte man V2 nehmen.

Das ist auch so richtig. Nur gehen wir dabei nicht mehr mit der Zeit. Wenn FastMM4 im Spiel ist, werden String-Konkatenationen schon mal von Haus aus schneller, weil nicht mehr für jedes zusätzliche Zeichen neuer Speicher angefordert wird, sondern immer in größeren Blöcken. Das wird dann zwar mit mehr Speicherverbrauch bezahlt, aber bei den heutigen RAM Größen ist das vernachlässigbar.
Zum anderen kommen bei heutigen Systemen mehrere CPUs ins Spiel. Dort sind die CPU LOCKs (derer gleich drei Stück in LStrAsg enthalten sind) teurer, weil ja tatsächlich eine andere CPU auf den Speicher zugreifen könnte. Davon sind Hyperthreading Prozessoren ebenfalls betroffen.

Zitat:

Wenn man das dann mal manifestieren will (sozusagen als Demo fur Dummies), fällt man so richtig (aber so richtig!) auf die Plautze.

Compilermagic kann eben grausam sein. :mrgreen:

Zitat:

Ehrlich gesagt bin ich etwas verwirrt.

Das bin ich zwar nicht, aber um das ganze Schneller zu machen, muss nun der ohnehin schon kompliziertere Code nochmals verkompliziert werden. Am Schluss blickt man dann gar nicht mehr durch, weil es nur noch so von "Compiler lass die verdammte Compilermagic hier weg" Anweisungen so wimmelt.

[alzaimar]

Bei mir ist selbst bei FastMM4 die Konkatenation schneller.

Ich schließe daraus, das wir uns nicht mehr so sehr um Performance scheren müssen, sondern eher die Verfahren optimieren können. Delphi und moderne MMS kompilieren das schon recht ordendlich. Ich persönlich finde das beruhigend, weil ich -ehrlich gesagt- nicht ständig mit irgendwelchen Tricks rumhantieren muss, sondern mich auf Algorithmen und Verfahren konzentrieren kann.

Danke für die Analysen.