Listen sind dynamische Arrays

Für Fragen zur Programmiersprache auf welcher Lazarus aufbaut
Mathias
Beiträge: 6165
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunk)
CPU-Target: 64Bit
Wohnort: Schweiz

Listen sind dynamische Arrays

Beitrag von Mathias »

Ich dachte immer in Listen, zB. TStringList, seien alle Items über Pointer verknüpft.
In etwa so:

Code: Alles auswählen

type
  PRec = ^TRec;
  TRec = record
    data : integer;
    next : PRec;
  end;
So war es in Turbo-Pascal üblich.

Aber bei genauerem gucken in der Souren ist mir aufgefallen, das dies einfach nur ein dynamischen Array im Hintergrund ist.

Code: Alles auswählen

  TPointerList = array[0..MaxListSize - 1] of Pointer; // classesh.inc   Zeile:195


So kann man sich täuschen. :shock: :oops:

Es gibt noch die Klasse TList, hat die überhaupt einen Vorteil gegenüber wen man direkt ein dynamische Array verwendet ?
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot

Benutzeravatar
theo
Beiträge: 10468
Registriert: Mo 11. Sep 2006, 19:01

Re: Listen sind dynamische Arrays

Beitrag von theo »

Mathias hat geschrieben:
Sa 5. Sep 2020, 13:29
Es gibt noch die Klasse TList, hat die überhaupt einen Vorteil gegenüber wen man direkt ein dynamische Array verwendet ?
Was heisst Vorteil?
TList stellt halt zusätzliche Methoden zur Verfügung. Add, Exchange, Clear, Sort etc. und erspart dir das Speichermanagement.
Das weißt du ja selber:
https://www.freepascal.org/docs-html/rt ... tlist.html

Mathias
Beiträge: 6165
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunk)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: Listen sind dynamische Arrays

Beitrag von Mathias »

Was momentan für dynamische Array spricht, unterdessen gibt es Delete und Insert, wie man es von Strings kennt, auch für dynamische Arrays.
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot

martin_frb
Beiträge: 572
Registriert: Mi 25. Mär 2009, 21:12
OS, Lazarus, FPC: Laz trunk / fpc latest release / Win and other
CPU-Target: mostly 32 bit

Re: Listen sind dynamische Arrays

Beitrag von martin_frb »

TList hat Capacity.

Das bedeutet weniger Memory re-allocation.

Mathias
Beiträge: 6165
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunk)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: Listen sind dynamische Arrays

Beitrag von Mathias »

martin_frb hat geschrieben:
Sa 5. Sep 2020, 21:40
TList hat Capacity.

Das bedeutet weniger Memory re-allocation.
Wieso ?
TList greift intern auch auf eine dynamische Array zu.
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot

Benutzeravatar
fliegermichl
Lazarusforum e. V.
Beiträge: 1432
Registriert: Do 9. Jun 2011, 09:42
OS, Lazarus, FPC: Lazarus Fixes FPC Stable
CPU-Target: 32/64Bit
Wohnort: Echzell

Re: Listen sind dynamische Arrays

Beitrag von fliegermichl »

Mathias hat geschrieben:
So 6. Sep 2020, 14:08
martin_frb hat geschrieben:
Sa 5. Sep 2020, 21:40
TList hat Capacity.

Das bedeutet weniger Memory re-allocation.
Wieso ?
TList greift intern auch auf eine dynamische Array zu.
Das schon, wenn das Array aber erweitert werden muß, so wird nicht nur ein neuer Eintrag angehängt sondern gleich mehrere. Das spart enorm Zeit.

siro
Beiträge: 730
Registriert: Di 23. Aug 2016, 14:25
OS, Lazarus, FPC: Windows 11
CPU-Target: 64Bit
Wohnort: Berlin

Re: Listen sind dynamische Arrays

Beitrag von siro »

Ich habe mich grade gefragt wie TList.Insert wohl funktioiniert.
Es sind ja keine dynamsich verketten Zeiger, sondern ein Array.

Es wird also erst das Array vergrößert und dann der Speicherinhalt einfach alles nach hinten geschoben bzw. dort hin copiert.

Code: Alles auswählen

procedure TFPList.Insert(Index: Integer; Item: Pointer);
begin
  if (Index < 0) or (Index > FCount )then
    Error(SlistIndexError, Index);
  iF FCount = FCapacity then Self.Expand;
  if Index<FCount then
    System.Move(Flist^[Index], Flist^[Index+1], (FCount - Index) * SizeOf(Pointer));
  FList^[Index] := Item;
  FCount := FCount + 1;
end;          
das wuste ich voher auch noch nicht...
Grüße von Siro
Bevor ich "C" ertragen muß, nehm ich lieber Lazarus...

Sieben
Beiträge: 202
Registriert: Mo 24. Aug 2020, 14:16
OS, Lazarus, FPC: Ubuntu Xenial 32, Lazarus 2.2.0, FPC 3.2.2
CPU-Target: i386

Re: Listen sind dynamische Arrays

Beitrag von Sieben »

Das Array wird aber eben nur vergrößert, wenn seine Kapazität erschöpft ist, also immer nur in Schritten. Keineswegs bei jedem Insert.

Mathias
Beiträge: 6165
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunk)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: Listen sind dynamische Arrays

Beitrag von Mathias »

Bei den Listen kann man nur ein Element auf einmal einfügen.
Bei einem Arrax sind mehrere Elemente auf einmal mäglich, so wie es bei Stirngs auch ist.
Beim Löschen von Elementen das gleiche.
Dank der neuen Befehlen Insert(...) und Delete(...).
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot

Mathias
Beiträge: 6165
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunk)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: Listen sind dynamische Arrays

Beitrag von Mathias »

Sieben hat geschrieben:
So 6. Sep 2020, 20:05
Das Array wird aber eben nur vergrößert, wenn seine Kapazität erschöpft ist, also immer nur in Schritten. Keineswegs bei jedem Insert.
Ein Nachteil hat eine Array doch. Wen der Speicherbereich zu klein wird, muss das ganze Array umkopiert werden. Wobei das bei Insert und Delete auch passiert, vor allem wen man das Element 0 bearbeitet.
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot

Sieben
Beiträge: 202
Registriert: Mo 24. Aug 2020, 14:16
OS, Lazarus, FPC: Ubuntu Xenial 32, Lazarus 2.2.0, FPC 3.2.2
CPU-Target: i386

Re: Listen sind dynamische Arrays

Beitrag von Sieben »

Ich meinte auch das Array, das TList intern verwendet.

Warf
Beiträge: 1908
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: Win10 | Linux
CPU-Target: x86_64

Re: Listen sind dynamische Arrays

Beitrag von Warf »

Array basierte Listen sind grundsätzlich besser als verkettete Listen, grund dafür is Cache lokalität. In Java sind selbst linked lists nicht listen bei denen jedes element gelinked wird, sondern sind so implementiert das man mehrere elemente zu einem array zusammenfasst und den dann linked.

TList im vergleich zu dynamischen Arrays hat einen entscheidenden vorteil, undzwar implementiert TList geometrisches wachstum, undzwar richtig.

Erstmal, geometrisches wachstum heist, eine Liste startet mit einer gewissen Kapazität, und immer wenn Count = Kapazität ist und was geadded wird, wird die Kapazität verdoppelt. Das heißt, für N insertions muss nur log(N) oft geresized werden. Für 1000 insertions sind also nur 10 resizes nötig. Bei einem Dynamischen Array würde das naiv implementiert 1000 resizes benötigen (für jeden insert einen).
Der Grund warum man das haben will ist, das das resizen eine der mit abstand teuersten operationen ist die man mit einem Array machen kann. Je nach Memory Manager und Fragmentation kann man massive performance einbußen haben.
Beispiel:

Code: Alles auswählen

program Project1;

{$mode objfpc}{$H+}

uses
  classes, SysUtils;

var
  arr: array of Pointer;
  l: TList;
  start: QWord;
  i: Integer;
const
  numElements = 10000000;
begin
  Randomize;
  l := TList.Create;
  arr := nil;
  start := GetTickCount64;
  for i:=0 to numElements do
    l.Add(Pointer(Random(Integer.MaxValue)));
  WriteLn('List: ', GetTickCount64 - start);
  start := GetTickCount64;
  for i:=0 to numElements do
    Insert(Pointer(Random(Integer.MaxValue)), arr, Length(arr));
  WriteLn('Array: ', GetTickCount64 - start);
  ReadLn
end.
Bei numElements = 10 Mio braucht TList c.a. 140 ms und Array c.a. 2,1 sekunden. Bei 1 mio ist es 15 zu 63 ms.
Vor allem wenn man regelmäßig elemente Löscht und wieder einfügt wird wenn die Liste einmal warm gelaufen ist keine einzige resize operation mehr benötigt.

Am anfang habe ich gesagt das TList dieses geometrische Wachstum vor allem richtig implementiert, was ich damit meine ist, im grunde kann man sowas auch auf Array basis implementieren, man benötigt nur eine separate Count variable. Das problem ist aber das Arrays management code ausführen, was im grunde heißt das bei einem Resize einmal auf allen neuen feldern des arrays Initialize aufgerufen wird, und auf allen feldern am ende auch einmal Finalize aufgerufen wird. Ist toll für Dynamische Arrays, für geometrisches Wachstum spuckt dir das aber ganz gewalltig in die Suppe, da es dafür sorgt das Memory bereiche die eventuell sonst nie angefasst werden einmal überschrieben werden. TList im gegensatz dazu benutzt rohe GetMem, ReallocMem und FreeMem calls um den speicher zu verwalten.
Das widerum macht dir den tollen vorteil von Virtuellem addressraum kaputt, mit dem du beliebig großen speicher alloziieren kannst, ohne das der je geladen werden muss. Beispiel:

Code: Alles auswählen

program Project1;

{$mode objfpc}{$H+}

uses
  classes, SysUtils;

var
  arr: Array of Byte;
  p: PByte;
const
  Size = 1024*1024*1024; // 1 GB
begin
  SetLength(arr, Size);
  WriteLn('Array allocated');
  ReadLn;
  arr := nil;
  p := GetMem(Size);
  WriteLn('Array freed, Pointer allocated');
  ReadLn;
end.
Wenn ich jetzt in meinen Taskmanager schaue, wenn Array allocated geprinted wird, habe ich 1 GB ram verbrauch bei diesem program. Drücke ich enter und warte bis Array freed, Pointer allocated da steht, ist der ram verbrauch nur noch 7MB, obwohl auch 1 GB alloziiert wurde.

Der Grund dafür ist der virtuelle addressraum den das Betriebsystem zur verfügung stellt. So kann man beliebig große speicherblöcke alloziieren (bis 2^48 byte oder so), während allerdings immer nur die menge an speicher physisch belegt wird die auch tatsächlich angefasst wird. Eine TList belegt damit zwar theoretisch im worst case doppelt so viel virtuellen speicher wie ein Array, aber physisch ist maximal eine pagesize (4kb oder so) zu viel im Speicher, da das betriebsystem die anderen pages nie geladen hat.

Es gibt also praktisch nur ein szenario in dem ein Array besser ist als eine TList, und das ist wenn die benötigte größe von anfang an exakt bekannt ist, und im vorhinein alloziiert werden kann. In allen anderen fällen ist TList, TStringList, TFPGList (fgl unit) oder TVector (gvector unit) besser.

marcov
Beiträge: 1100
Registriert: Di 5. Aug 2008, 09:37
OS, Lazarus, FPC: Windows ,Linux,FreeBSD,Dos (L trunk FPC trunk)
CPU-Target: 32/64,PPC(+64), ARM
Wohnort: Eindhoven (Niederlande)

Re: Listen sind dynamische Arrays

Beitrag von marcov »

Mathias hat geschrieben:
Sa 5. Sep 2020, 13:29
So war es in Turbo-Pascal üblich.
Das Turbo Pascal's TCollection Objekt war sich TList Ähnlich, und hätte darum auch eine Beschränkung nur bis zu 16384 Elementen (sizeof(pointer)*16384=64k)

Timm Thaler
Beiträge: 1224
Registriert: So 20. Mär 2016, 22:14
OS, Lazarus, FPC: Win7-64bit Laz1.9.0 FPC3.1.1 für Win, RPi, AVR embedded
CPU-Target: Raspberry Pi 3

Re: Listen sind dynamische Arrays

Beitrag von Timm Thaler »

siro hat geschrieben:
So 6. Sep 2020, 19:52
Ich habe mich grade gefragt wie TList.Insert wohl funktioiniert.
Es sind ja keine dynamsich verketten Zeiger, sondern ein Array.

Es wird also erst das Array vergrößert und dann der Speicherinhalt einfach alles nach hinten geschoben bzw. dort hin copiert.
Autsch! Warum sind die Listen nicht verkettet?

In PureBasic funktionieren verkettete Listen wunderbar. Bei einem Insert wird der neue Eintrag irgendwo angelegt - und Vorgänger und Nachfolger erhalten den Zeiger auf den neuen Eintrag. Da muss nix rumkopiert werden. Bei einem Delete erhalten einfach Vorgänger und Nachfolger ihre wechselweisen Zeiger.

Es gibt noch eine Variable, die die aktuelle Listengröße enthält, damit man nicht für ein CountList die ganze Liste durchackern muss.

Warum hat Pascal das nicht so implementiert?

PascalDragon
Beiträge: 825
Registriert: Mi 3. Jun 2020, 07:18
OS, Lazarus, FPC: L 2.0.8, FPC Trunk, OS Win/Linux
CPU-Target: Aarch64 bis Z80 ;)
Wohnort: München

Re: Listen sind dynamische Arrays

Beitrag von PascalDragon »

Timm Thaler hat geschrieben:
Fr 11. Sep 2020, 16:03
Warum hat Pascal das nicht so implementiert?
Weil du mit Arrays 'nen schnelleren indexbasierten Zugriff hast. Dafür ist halt Einfügen/Entfernen potentiell langsamer (wobei Einfügen am Ende auch trivial ist, so lange die aktuelle Kapazität noch nicht erreicht ist).
FPC Compiler Entwickler

Antworten