array of string und die Performance-Schraube

[Meflin]

Moin moin!

Folgende Situation: ich habe mehrere Instanzen einer Klasse (sg. "Nodes"). Jede dieser Nodes hat ein array of string sowie einen Tickcounter, der einen Array-Index repräsentiert.

Nun müssen die jeweiligen Werte aus jedem Node ausgelesen und zu einem string zusammen gesetzt werden. Bis jetzt mache ich das schlicht und einfach so:

Delphi-Quellcode:

Result := '';
for i := Low(FNodes) to High(FNodes) do begin
  Result := FNodes[i].ElementList[FNodes[i].IncCount] + Result;
end;

Doch nun habe ich das Projekt mal durch einen Profiler gejagt und da hat sich diese Operation ganz klar als Flaschenhals herausgestellt. Nun ist es auch so, dass das Millionenfach ausgeführt wird, also es sich durchaus um eine Stelle handelt, an der sich Optimieriungen lohnen würden.

Nur fehlt mir da gerade jegliche Idee, wie man das anders gestalten könnte. Vorschläge sind also sehr erbeten

[Christian Seehase]

Moin Leo,

also ein Ansatzpunkt wäre es, erst einmal die erforderliche Gesamtlänge zu errechnen (vielleicht kannst Du Dir die Änderungen ja irgendwo bei jedem hinzufügen eines Strings merken), dann Result auf die erforderliche Gesamtlänge initialisieren, und anschliessend per CopyMemory die Inhalte in Result übertragen.
Dann fällt schon mal das, Performance fressende, "Addieren" der Strings weg.

[thkerkmann]

Hi,

ich würde mal über die Datenstruktur nachdenken.

Für mich sieht das so aus, als ob aus jedem Node nur noch der letzte String interessiert.
Frage also:
werden die anderen nicht mehr gebraucht - warum werden sie dann gespeichert.

Falls doch, habe ich leider auch keinen anderen Ansatz, jedoch würde ich dem Node eine Methode spendieren, die mir diesen letzen string zurückliefert. Dann schaut die Schleife schon mal netter aus

Gruss

[Meflin]

Zitat von thkerkmann:

Für mich sieht das so aus, als ob aus jedem Node nur noch der letzte String interessiert.
Frage also:
werden die anderen nicht mehr gebraucht - warum werden sie dann gespeichert.

Doch, die werden gebraucht, da der Inccounter auch reseted werden kann (und auch wird), sodass es in dem Node wieder von vorne losgeht.

@Christian: Danke für den Tipp, das werde ich ausprobieren.

Im Moment verlangsamt o.g. Ansatz den Vorgang ca. um den Faktor 50

[alzaimar]

Zitat von Meflin:

Im Moment verlangsamt o.g. Ansatz den Vorgang ca. um den Faktor 50

Fallst Du mit 'o.g.Ansatz' das meinst, was Christian vorgeschlagen hat, dann hast Du was falsch gemacht.

Die werden vorne immer rangebepselt? Hmm.

Delphi-Quellcode:

// 1. Maximal mögliche Länge ausrechnen
MaxLength := (High(FNodes) - Low(FNodes) + 1)*MaxLengthOfElementList;
SetLength (Result, MaxLength);
// 2. Das Zeugs am Ende von Result beginnend nach vorne auffüllen
j := MaxLength+1;
for i := Low(FNodes) to High(FNodes) do begin
  // Einzufügenden String holen
  sTmp := FNodes[i].ElementList[FNodes[i].IncCount]; 
  If Length (sTmp)>0 Then Begin // wenn der nicht leer ist
    // Einfügeposition nach vorne schieben
    dec (j,Length (sTmp));  
    // String vorne ranbepseln
    Move (s[1], Result[j], Length (sTmp));
  End
End;
// Wenn wir noch nicht vorne angekommen sind, verschieben wir unser Resultat an Position 1.
If j>1 Then Begin
  Dec (MaxLength, j-1); // Länge anpassen
  Move (Result[j], Result[1], MaxLength); // Verschieben
End;

SetLength (Result, MaxLength); // Fertig.

Ungetestet, vielleicht die üblichen +/-1 Fehler. Sollte aber weeesentlich schneller sein.

[SirThornberry]

ist ElementList ein Property hinter dem eine Funktion steckt oder ist es wirklich ein richtiges Array?
@alzaimar: Anstelle von verschieben würde ich die Schleife einfach andersrum laufen lassen und somit den String von vorne auffüllen.
Ich persönlich würde auch nicht mehr speicher anfordern als benötigt sondern einmal die Schleife durchlaufen lassen und mit length die jeweiligen Längen abfragen und addieren und dann nochmal die Schleife her nehmen und dann in den genau reservierten Speicher kopieren. (Ich glaube meine Variante wäre langsamer, wollte nur anmerken wie ich es machen würde um zu vermeiden das man an die Speichergrenzen kommt)

[alzaimar]

@Thornberry: logisch, natürlich.

[Meflin]

@alzaimar: Nein, ich meinte meinen eigenen Code

Habe jetzt mal ein bisschen gemessen. Was verbrauchts ohne die string-Zusammensetzung, wie lange dauerts mit "string-Addition" und wie lange mit alzaimars Methode. Es fehlen noch sirThornberrys und Christians Vorschlag.

Die Ergebnisse gibts im Anhang, aber alzaimar, dein Vorschlag ist nochmal gut 1/4 langsamer als die string-Addition

[alzaimar]

So hätte es Sir Thornberry wohl gemacht.

Delphi-Quellcode:

MaxLength := 0;
For i:= Low(FNodes) To High (FNodes) Do 
  Inc (MaxLength, Length (FNodes[i].ElementList[FNodes[i].IncCount]));

SetLength (Result, MaxLength);
j := 0;
For i := Hight(FNodes) Downto High(FNodes) do begin
  sTmp := FNodes[i].ElementList[FNodes[i].IncCount]);
  If Length (sTmp)>0 Then Begin 
    Move (s[1], Result[j], Length (sTmp));
    inc (j,Length (sTmp)); 
  End
End;

Das müsste aber eigentlich viel schneller sein, als Deine Methode...

Wie ist den der Getter von 'IncCount'?

[Meflin]

Zitat von alzaimar:

Wie ist den der Getter von 'IncCount'?

IncCount ist keine property, der Zugriff auf den Wert erfolgt also direkt.
ElementList ist zwar eine property, aber der Zugriff erfolgt direkt auf das array (inzwischen, anfangs war ElementList das "echte" array, jetzt wird mit FElementList gearbeitet)

Der letzte Algo ist katastrophal: nochmal fast dreimal langsamer als dein erster Vorschlag
Bis jetzt ist also immernoch string-Addition (deutlich) am schnellsten