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]