six1 hat geschrieben:Ok, an dieser Stelle wäre eine Übergabe des Parameter als var möglich, um dies zu verhindern.
siehe die antwort von m.fuchs.
Als kleine erklärung wie TList (oder auch TFPGList für generische typen) das macht, die haben neben der Länger noch eine Kapazität. Wenn du eine Liste erzeugst wird eine gewisse kapazität alloziiert, z.B. 1 eintrag. Dann, solang die Länge kleiner als die Kapazität ist kann hinzugefügt werden ohne kosten. Wenn länge gleich Kapazität ist, wird die Kapazität geometrisch erhöt. Bei TList ist das glaube ich ein Faktor 2 wenn die Liste klein ist und ein Faktor 1,5 wenn die Liste größer wird.
Als array implementierung wäre das etwa so:
Code: Alles auswählen
void addItem(Item: TSomeType);
begin
if Length = Capacity then
begin
Capacity = Capacity * 2;
SetLength(Array, Capacity);
end;
Array[Length] := Item;
Inc(Length);
end;
und die entsprechende RemoveItem würde dann irgendwie so aussehen (aus einfachheit nehmen wir an das nur das letzte element gelöscht wird:
Code: Alles auswählen
void removeItem();
begin
Dec(Length)
if Length < Capacity div 2 then
begin
Capacity = Capacity div 2;
SetLength(Array, Capacity);
end;
end;
Denn SetLength muss ja den speicherbereich vergrößern, d.h. wenn aber an der stelle wo der Speicher liegt kein freier platz hintendran mehr frei ist (Arrays garantieren ja kontinuierlichen Speicher) muss wo ganz anders neuer Speicher gesucht werden, und alle alten elemente rüberkopiert werden. Das ist verdammt teuer. Die annahme ist jetzt, kleine listen bleiben klein. daher wachsen die listen am anfang recht langsam (1-2-4-8-16-32), außerdem ist da das kopieren noch billig (32 werte zu kopieren ist nix bei ner GHZ CPU). Wenn die Liste groß wird, im extrem fall im GB bereich, willst du nicht für jedes Add ein paar gigabyte kopieren, daher muss man da sehr selten realloziieren. Außerdem kann man davon ausgehen das sobald eine Liste "warmgelaufen" ist sich ihre größe nur sehr selten ändert, d.h. es kommen wahrscheinlich ähnlich viele elemente hinzu wie gelöscht werden, die gesammt größe ändert sich also irgendwann kaum noch.
Für die Performancekitzler die sich jetzt denken: Oh mein gott im worst case verbrauche ich also doppelt so viel speicher, das ist auch kein Problem, denn auf modernen CPU's verwendet man virtuellen speicher. D.H. du kannst auf einem 64bit system problemlos 2^64 bytes alloziieren, ohne das es kracht, unabhängig wie viel speicher deine Maschine Physisch hat. Solang da nix reingeschrieben wird ist das absolut kein problem. Also selbst wenn bei einer 2 GB liste 4GB alloziiert sind, sitzen im Physischen RAM trozdem nur 2GB.
Das gilt natürlich nicht für Microcontroller! Aber sowohl bei i386, x86_64 oder auch ARM ist das praktisch kostenlos, und gibt immense performance boosts im vergleich zu jedes mal ein SetLength machen.
Aber sowas muss man als Programmierer eigentlich nicht mal wissen, wichtig ist nur, wenn man fertige Klassen hat, sollte man die auch benutzen. Die FPC und lazarusentwickler wissen (zumindest in den aller meißten fällen) was sie tun!
PS: Wenn man eine Liste von Komplexeren Objekten z.B. records hat, ist es dementsprechend auch schlauer einen Kontinuierlichen Memory block (z.B. TFPGList<RecordType>) zu verwenden, statt eine TList und pointer zu übergeben, da die TFPGList sich bereits um das alloziieren des speichers kümmert. Das new und dispose (oder auch bei Klassen Create und Free) sind relativ teure operationen, und wenn man große listen hat lohnt sich ne FPGList von nem (advanced)record oder nem object(Nicht Klasse) manchmal deutlich mehr (Memory Operationen sind mit das teuerste was man machen kann).