Arrayoperationen beschleunigen

[himitsu]

Es ist ja wohl bekannt, daß bei vielen Änderungen der Arraygröße eine Menge Zeit draufgeht.

Dagegen gibt es eigentlich nur ein Mittel > die Anzahl der Änderungen muß verringert werden, so daß nicht gleich bei jeder kleinen Änderung der gesamte Arrayinhalt hin- und herkopiert wird.



Als Erstes könnte man es mal mit einem anderem Memory-Manager versuchen (z.B. FastMM),
allerdings ist es da nicht möglich das Verhalten an eigene Bedürfnisse anzupassen.


Also wäre es wohl nicht schlecht, wenn selber das Verhalten geändert wird.

1.) Verwendete und tatsächliche Größe unabhängig verwalten:
Wozu noch eine extra Variable für den verwendeten Bereich nötig wäre.

Code:

[b][color=blue]// Definition[/color][/b]
[b]Var[/b] MyArray: [b]Array of[/b] XXX;
  MyArray_Length: Integer;

[b][color=blue]// SetLength(MyArray, NewLength);[/color][/b]
MyArray_Length := NewLength;
SetLength(MyArray, [color=green](NewLength + $1FFF) [b]and not[/b] $1FFF[/color]);

[b][color=blue]// Length(MyArray)[/color][/b]
MyArray_Length

[b][color=blue]// High(MyArray)[/color][/b]
MyArray_Length - 1

[b][color=blue]// MyArray[Index][/color][/b]
MyArray[Index]

2.) Verwendete Größe mit Array speichern:
z.B. am Ende/nach den Array-Daten
Keine weitere Variable nötig, somit wären die Funktionen auf mehrere Arrays anwendbar.

Code:

[b][color=blue]// Definition[/color][/b]
[b]Type[/b] TMyArray = [b]Array of[/b] XXX;

[b]Var[/b] MyArray: TMyArray;

[b]Function[/b] Length_(Const A: TMyArray): Integer;
  [b]Begin[/b]
    [b]If[/b] A = nil [b]Then[/b] Result := 0
    [b]Else[/b] Result := PInteger(@A[High(A)])^;
  [b]End[/b];

[b]Function[/b] High_(Const A: TMyArray): Integer;
  [b]Begin[/b]
    Result := Length_(A) - 1;
  [b]End[/b];

[b]Procedure[/b] SetLength_([b]Var[/b] A: TMyArray; i: Integer);
  [b]Begin[/b]
    [b]If[/b] A <> nil [b]Then[/b] PInteger(@A[High(A)])^ := 0;
    [b]If[/b] i > 0 [b]Then[/b] [b]Begin[/b]
      SetLength(A, ([color=green](i + $1FFF) [b]and not[/b] $1FFF[/color]) + 1);
      PInteger(@A[High(A)])^ := i;
    [b]End Else[/b] A := nil;
  [b]End[/b];

[b][color=blue]// SetLength(MyArray, NewLength);[/color][/b]
SetLength_(MyArray, NewLength);

[b][color=blue]// Length(MyArray)[/color][/b]
Length_(MyArray)

[b][color=blue]// High(MyArray)[/color][/b]
High_(MyArray)

[b][color=blue]// MyArray[Index][/color][/b]
MyArray[Index]

Dieses Beispiel ist nur für SizeOf(XXX) >= 4,
wenn SizeOf(XXX) kleiner als SizeOf(Integer) ist, dann muß natürlich mehr als nur ein Feld für die zu speichernde Größenangabe verwendet werden.

Code:

[b]Function[/b] Length_(Const A: TMyArray): Integer;
  [b]Begin[/b]
    [b]If[/b] A = nil [b]Then[/b] Result := 0
    [b]Else[/b] Result := PInteger(@A[[color=red]Length(A) - 2{4}[/color]])^;
  [b]End[/b];

[b]Procedure[/b] SetLength_([b]Var[/b] A: TMyArray; i: Integer);
  [b]Begin[/b]
    [b]If[/b] A <> nil [b]Then[/b] PInteger(@A[[color=red]Length(A) - 2{4}[/color]])^ := 0;
    [b]If[/b] i > 0 [b]Then[/b] [b]Begin[/b]
      SetLength(A, ([color=green](i + $1FFF) [b]and not[/b] $1FFF)[/color] + [color=red]2{4}[/color]);
      PInteger(@A[[color=red]Length(A) - 2{4}[/color]])^ := i;
    [b]End Else[/b] A := nil;
  [b]End[/b];

[b][color=blue]// 2 für SizeOf(XXX)=2, oder SizeOf(XXX)=3
// 4 für SizeOf(XXX)=1[/color][/b]

3.) Größenangabe direkt im Array ändern:
Vorteil zum vorherigen (2) Vorgehen wäre, daß hier nur SetLength geändert werden muß.

Code:

[b][color=blue]// Definition[/color][/b]
[b]Type[/b] TMyArray = [b]Array of[/b] XXX;

[b]Var[/b] MyArray: TMyArray;

[b]Procedure[/b] SetLength_([b]Var[/b] A: TMyArray; i: Integer);
  [b]Begin[/b]
    [b]If[/b] A <> nil [b]Then[/b] PInteger(Integer(A) - SizeOf(Integer))^ :=
      [color=green](PInteger(Integer(A) - SizeOf(Integer))^ + $1FFF) [b]and not[/b] $1FFF[/color];
    SetLength(A, [color=green](i + $1FFF) [b]and not[/b] $1FFF[/color]);
    [b]If[/b] A <> nil [b]Then[/b] PInteger(Integer(A) - SizeOf(Integer))^ := i;
  [b]End[/b];

[b][color=blue]// SetLength(MyArray, NewLength);[/color][/b]
SetLength_(MyArray, NewLength);

[b][color=blue]// Length(MyArray)[/color][/b]
Length(MyArray)

[b][color=blue]// High(MyArray)[/color][/b]
High(MyArray)

[b][color=blue]// MyArray[Index][/color][/b]
MyArray[Index]

4.) Wer nicht direct im Array "rumpfuschen" möchte, könnte es auch mit einer Klasse versuchen.
Allerdings wird hierfür dann zusätzlich noch der Constructor und Destructor benötigt.

Code:

[b]Type[/b] TMyArrayClass = [b]Class[/b] 
    Private
      A: [b]Array of[/b] XXX;
      ALen: Integer;
      [b]Function[/b] GetField(i: Integer): XXX;
      [b]Procedure[/b] SetField(i: Integer; Value: XXX);
    Public
      [b]Procedure[/b] SetLen(i: Integer);
      [b]Function[/b] Len: Integer;
      [b]Property[/b] LenX: Integer [b]Read[/b] Len [b]Write[/b] SetLen; 
      [b]Property[/b] Field[i: Integer]: XXX [b]Read[/b] GetField [b]Write[/b] SetField; [b]Default[/b];
  [b]End[/b];

[b]Function[/b] TMyArrayClass.GetField(i: Integer): XXX;
  [b]Begin[/b]
    Result := A[i];
  [b]End[/b];

[b]Procedure[/b] TMyArrayClass.SetField(i: Integer; Value: XXX);
  [b]Begin[/b]
    A[i] := Value;
  [b]End[/b];

[b]Procedure[/b] TMyArrayClass.SetLen(i: Integer);
  [b]Begin[/b]
    SetLength(A, [color=green](i + $1FFF) [b]and not[/b] $1FFF[/color]);
    ALen := i;
  [b]End[/b];

[b]Function[/b] TMyArrayClass.Len: Integer;
  [b]Begin[/b]
    Result := ALen;
  [b]End[/b];

Var MyArray: TMyArrayClass;

[b][color=blue]// Initialisieren[/color][/b]
MyArray := TMyArrayClass.Create;

[b][color=blue]// SetLength(MyArray, NewLength);[/color][/b]
MyArray.SetLen(NewLength);
[b][color=blue]{oder}[/color][/b] MyArray.LenX := NewLength;

[b][color=blue]// Length(MyArray)[/color][/b]
MyArray.Len
[b][color=blue]{oder}[/color][/b] MyArray.LenX

[b][color=blue]// High(MyArray)[/color][/b]
MyArray.High

[b][color=blue]// MyArray[Index][/color][/b]
MyArray[Index]
[b][color=blue]{oder}[/color][/b] MyArray.Field[Index]

[b][color=blue]// Finalisieren[/color][/b]
MyArray.Free;

Fazit:
Aus OOP-Sicht wäre 4. zu bevorzugen,
auch wenn da vieles zu beachten und zu verändern ist.

Bei 1. ist zwar guz zu sehn was gemacht wird, allerdings mu da jedes SetLength, Length und High geändert werden.

2. ist im Grunde nicht zu empfehlen, da dort das Array besser mit SelLength_(MyArray, 0) freigegeben werden sollte, vorallem wenn im Typ dynamische Stukturen enthalten sind, welche von FinalizeArray behandelt werden (z.B. Strings), da es sonst Probleme mit dem Typ-Fremden Integer (der Längenangabe am Ende) geben könnte.
Schließlich wird aus gutem Grund die Größenangabe aus dem Array gelöscht, bevor die Größe geändert wird. If A <> nil Then PInteger(@A[High(A)])^ := 0;
Ich selber verwende gerne 3., da hierbei nur SetLength ersetzt werden muß und alles andere unverändert bleibt.
Außerdem kann dieses Array überall so verwendet werden, als wäre es ein ganz normalles Array.
Manchmal auch 1., da es ja im Grunde genau das Selbe wie 2. ist, nur halt etwas schneller.




Schrittweite:
In den Beispielen wird die Arraygröße jeweils in Schritten von 1024 geändert.

Es sind natürlich auch andere Werte möglich,
aber im allgemeinen sind 2er-Potenzen idealer, da dort binär (mit AND) gerechnet werden kann,
wärend sonst mathematische Rechnungen (mit MOD und *) nötig sind.

Also einmal ein "schnelles" AND (das NOT wird mit einkopiliert),
oder zweimal "langsame" DIV/MUL.

Code:

[b][color=blue]// binär (nur bei 2er-Potenzen)[/color][/b]
[color=green](i + (AllocSize - 1)) [b]and not[/b] (AllocSize - 1)[/color]
[b][color=blue]{=}[/color][/b] [color=green](i + $*****) [b]and not[/b] $*****[/color]

[b][color=blue]// matematisch[/color][/b]
[color=darkgreen]((i + (AllocSize - 1)) [b]div[/b] AllocSize) * AllocSize[/color]

[negaH]

Fairerweise muß noch noch Methode 5 erwähnen

Delphi-Quellcode:

var
  Count: Integer;
  MyArray: array of anytype;
begin
  Count := 0;
  while xyz do
  begin
    if Count mod 256 = 0 then 
      SetLength(MyArray, Count +256); // 256 Elemente preallozieren
    MyArray[Count] := XYZ;
    Inc(Count);
  end;
  SetLength(MyArray, Count);
end;

Dh. wenn der Programierer weiß das die Reallokation der dyn. arrays ein Problem darstellt so reichen im Allgemeinen 3 zusätzliche Zeilen Sourcecode um das zu optimierern. Der Effekt ist der selbe wie bei den komplizierten Methode oben

Gruß hagen

[Der_Unwissende]

Zitat von negaH:

Fairerweise muß noch noch Methode 5 erwähnen

Dann aber auch Methode 6, die etwas mehr für die enttäuschten OOPler aus Methode 4 ist

Delphi-Quellcode:

var
  MyArray: TList;
begin
  MyArray := TList.Create;

  // schreiben:
  while xyz do
  begin
    MyArray.Add(abcd);
  end;
  
  // und wahlfrei lesen:
  doFoo(AnyType(MyArray[abc])^);
  ....
end;

Auch nur ein Array, dass dyn. wächst und schrumpft, aber man selbst muss sich halt darum nicht kümmern.

Gruß Der Unwissende

[himitsu]

Upps ... tschuldsche, hast ja recht DAX

Aber zu Hagens ... deines funktioniert nur, wenn es schrittweise anwächst/schrumpft ... laß mal dein Array in 3er-Schritten wachsen

Besser wäre da wohl etwas mit < und >, statt MOD.



@Der_Unwissende: klar ginge das ... is halt was schönes für Typen-Konvertierungs-Liebhaber.
Bei der eigenen Implementierung kann man dann allerdings noch zusätzliche Sachen mit einbauen, wenn man schon mal dabei ist ^^

[negaH]

Delphi-Quellcode:

const
  PreAllocCount = (256 + 2) div 3;

var
  Count: Integer;
  MyArray: array of anytype;
begin
  Count := 0;
  while xyz do
  begin
    if Count mod (PreAllocCount * 3) = 0 then
      SetLength(MyArray, Count + (PreAllocCount * 3)); 
    MyArray[Count +0] := XYZ;
    MyArray[Count +1] := XYZ;
    MyArray[Count +2] := XYZ;
    Inc(Count, 3);
  end;
  SetLength(MyArray, Count);
end;

// Vermeidung der langsammen Division

var
  Count,Size: Integer;
  MyArray: array of anytype;
begin
  Count := 0;
  Size := 0;
  while xyz do
  begin
    if Size mod 256 = 0 then
      SetLength(MyArray, (Size + 256) * 3);
    Inc(Size); 

    MyArray[Count +0] := XYZ;
    MyArray[Count +1] := XYZ;
    MyArray[Count +2] := XYZ;
    Inc(Count, 3);
  end;
  SetLength(MyArray, Count);
end;

Also sage nicht "es funktioniert nicht", es funktioniert doch wenn man ein bischen nachdenkt.

Der entscheidende Punkt auf den ich hinweisen möchte ist:

Ein Programmierer OHNE Backgroundwissen der Informatik, eben über Algorithmen, wird immer nur nach einer fertigen Lösung suchen können, mehr nicht. Es geht hier also nicht darum eine fertige Lösung zu präsentieren sondern das fehlende Grundwissen der Programmierung nachzuliefern.

Eine TList ist sehr oft überdimensioniert, unhandlich in der Benutzung aus Sicht der Typsicherheit (sprich TList mit Integern und Typcasts etc.pp.) und meistens langsammer als eine Lösung die nur 2 Zeilen mehr an Source benötigt weil der Programierer das fachspezifische Grundwissen intus hat bzw. beherrscht.

Was mich an Gausi's Vorschlägen so stört ist das es Programmiertechnische Tricks sind (also Mißbrauch der Array Strukturen und TypCast, Pointerarithmetiken). Natrülich nicht alle deine Vorschläge, dafür sind diese dann aus meiner Sicht schon wieder zu aufwendig und überdimensiert für die eigentliche Problemstellung

"Vermeidung von Reallokationen beim Anlegen und Füllen dynamischer Arrays"

und das ist diejenige Operation die meiner Meinung nach im praktischen Alltag am häufigsten zu einer besseren Performance führt.
Gruß Hagen

[negaH]

Und da gäbe es ja noch Methode 7, bei der der Programmierer offensichtlich die meisten Informationen über seine Daten zur Hand hat

Delphi-Quellcode:

var
  MyArray: array of mytype;
  Count: Integer;
begin
  SetLength(MyArray, Anzhal der Daten XYZ);
  for (count := 0 to Anzhal der Daten XYZ -1 do
    MyArray[Count] := XYZ;
end;

Wir wissen also schon wieviele Daten auf uns zukommen, höchst wahrscheinlich deshalb weil der Programmierer systematisch seine "Umwelt" geplant hat und so das Gesamtproblem korrekt zerlegt hat in kleine Unterprobleme und auch die Effizienz dabei nicht aus den Augen gelassen hat.

Also statt "blind vorwärts irrend" und mit irgendwas ein Problem zu lösen, wird der Programmierer systematisch das Problem lösen indem er von Anfang an seine notwenige Umwelt (Sourcecode, Datentypen, Objekte, Algorithmen etc.pp) auswählt und kombiniert. Das kann er dann aber nur wenn er eine entsprechende "Wissensdatenbank" besitzt, also sein Handwerk beherrscht.

Gruß Hagen

[DGL-luke]

Wobei ich aber doch den Hinweis fallen muss, dass der Programmierer manchmal vor Anfang der Schleife nicht weiß, wie viel auf ihn zukommt... Meine Methode ist da der ersten von negaH sehr ähnlich, aber ich lagere das meist in eine funktion aus:

Delphi-Quellcode:

var Arr: array of string;
    ArrOccupied: Integer;

function ArrayAdd(s: string)
begin
  Inc(ArrOccupied);

  //memory management
  if length(Arr) <= ArrOccupied then
    setlength(Arr, round(length(arr) * 1.72)+1);

  Arr[Arrocupied] := s;
  Result := ArrOccupied;
end;

ArrOccupied ist hierbei der Index des letzten belegten Elements. Diese 172% sind ein Erfahrnungswert, der öfters mal in Threads kursiert, weswegen ich ihn einfach ohne nachdenken benutze und nur zur sicherheit ein +1 anhänge (obwohls eigentlich gar nicht nötig ist , es sei denn length(array)=1)

[negaH]

Hm, netter Wert -> 172%. Davon habe ich bisher noch nichts gehört.

Was mich aber leicht stören würde sind

1.) der explizite Aufruf einer Funktion
2.) die Fließkommaarithmetik
3.) der Aufruf von Length() bei jedem Einfügen
4.) globale Variable

denn das sind alles "Performance-bremsen" verglichen zu meiner direkten Methode. Im Grunde handelt es sich doch nur um ein Beispiel das man in den eigenen Sourcen direkt umsetzt. Dein Vorschlag ist schon wieder eine Generalisierung die auf Grund dessen einen zusätzlichen Overhead mitsichbringt.

Je nach Erfordernisse haben wir hier im Thread nun alle möglichen Wege aufgezeichnet, schön

Gruß Hagen

[DGL-luke]

1.) Neuere Delphi-Compiler sollten den inlinen
2.) ja. geht bestimmt auch per boolescher Verknüpfungen... aber das kann ich nicht^^
3.) Naja... man kann dafür auch eine zusätzliche variable deklarieren^^
4.) Wärs die lieber als typisierte private Konstante? Kann man natürlich jederzeit innerhalb der am nchsten gelegenen Klasse deklarieren

Das nur zder Vollständigkeit halber.