Maps/Listen von Composite Typen

Zur Vorstellung von Komponenten und Units für Lazarus
Antworten
Warf
Beiträge: 1908
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: Win10 | Linux
CPU-Target: x86_64

Maps/Listen von Composite Typen

Beitrag von Warf »

Hey ho, ich hab mal ne Frage. Was für Datentypen verwendet ihr wenn ihr Listen oder Maps mit Composite Typen benötigt?

Denn die FGL Klassen funktionieren nicht mit Records (außer man erstellt eine separate Datei, mit mode Delphi in der man diese typen mit Operator = überlädt). Das ist mMn. aber ein ziemlich beschissener Hack, den ich falls möglich umgehen will.

Es gibt noch die Unit GVector, die kann das zwar, deren Interface ist aber an C++'s vector klasse angelehnt, und damit hat man statt add die funktion push_back, statt count size, etc. Was natürlich auch wieder verwirrend ist. Außerdem ist da das typing anders, so ist size z.B. ein SizeUInt, und damit wirft

Code: Alles auswählen

for i:=0 to vec.size-1 do

für einen Leeren vektor nen fehler (im debug buiöd oder im optimierten release läuft von 0 bis 2^64-1), was bedeutet man muss entweder ne While schleife machen oder sowas:

Code: Alles auswählen

for i:=0 to SizeInt(vec.Size) -1 do

was auch wieder beschissen ist
Eine weiter Option ist einfach mehrere Listen zu benutzen, z.B. angenommen man möchte eine Liste von ID's und Namen füllen. Dann kann man ja eine Integer Liste und eine String Liste führen. Das schreit aber nach Synchronisationsfehlern und ist damit auch vom tisch.
Für Strings kann man ja die TStringList nehmen, die kann Objects (also Pointer) mit den Strings speichern. Wenn ich jetzt aber nur eine Zahl speichern will ists absolut unsinnig einen 64 bit pointer auf einen 32 bit integer im Heap zu benutzen. Das sind mit Heap overhead locker 112 bit statt 32. Den Integer direkt in den Pointer zu schreiben geht zwar unter x86 ist aber eigentlich Undefiniert und damit nicht Portabel, fällt also auch raus.

Objects statt records zu verwenden ist zwar eine Möglichkeit, dann muss man sich aber um Ownership kümmern, was ich wenn möglich vermeiden will (außerdem ist das extra pointer chasen und die 64 bit pointer overhead in vielen Cases nicht erwünscht). Ums genau zu nehmen habe ich bei meinem letzen projekt wofür ich das gebraucht hab mit z.T. gigabyte großen listen gearbeitet, da ist der Overhead von Objekten inakzeptabel. Außerdem ist die Fehlende Cache lokalität durch das Pointer chasen ein absoluter Performance Killer

Ich benutz aktuell den gvector, ist aber auch ne Suboptimale Lösung (siehe oben). Daher wollte ich mal fragen wie ihr das so macht. Ich mein ich kann ja nicht der erste sein der eine Liste mit mehreren Objekten benutzen möchte

Benutzeravatar
af0815
Lazarusforum e. V.
Beiträge: 6198
Registriert: So 7. Jan 2007, 10:20
OS, Lazarus, FPC: FPC fixes Lazarus fixes per fpcupdeluxe (win,linux,raspi)
CPU-Target: 32Bit (64Bit)
Wohnort: Burgenland
Kontaktdaten:

Re: Maps/Listen von Composite Typen

Beitrag von af0815 »

FGL verwendet, da gibt es Listen, wo man der Liste den Ownership übertragen kann. Der Typ der Liste hängt stark von den Daten und was ich brauche ab. Nur sind meine Listen nicht so umfangreich.
Blöd kann man ruhig sein, nur zu Helfen muss man sich wissen (oder nachsehen in LazInfos/LazSnippets).

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

Re: Maps/Listen von Composite Typen

Beitrag von Warf »

af0815 hat geschrieben:FGL verwendet, da gibt es Listen, wo man der Liste den Ownership übertragen kann. Der Typ der Liste hängt stark von den Daten und was ich brauche ab. Nur sind meine Listen nicht so umfangreich.


Ja das problem bei der Ownership ist, ich rede grade nur von daten, davon aber ne ganze menge. D.H. ich brauch keine Methoden und damit keine Klassen. Daher ists keine gute Idee eine ObjectList zu verwenden (für normale objekte verwende ich die auch sehr gerne). Aber damit verliere ich zum einen die Cachelokalität und muss immer einen Pointer chasen. Während ich bei einer Liste von Records praktisch gleichzeitig einen sehr effizienten Stack Allocator hätte, bei dem die zugriffszeiten minimal sind. Und ich bin grade bei einem Programm bei dem jede Millisekunde und jedes Byte zählt.

Und die Listen in der FGL sind schon sehr umfangreich (grad im vergleich zum GVector), so kann man z.B. sortieren, binary search drauf machen und dublikate rausfiltern, was echt nett ist, aber die Tatsache das es mit records nicht geht ist halt sehr schade

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

Re: Maps/Listen von Composite Typen

Beitrag von fliegermichl »

Was spricht gegen FPList?

Da wird ja standardmäßig eine Liste von Pointern verwaltet. Worauf die Pointer zeigen kannst du doch selber festlegen.

Code: Alles auswählen

 
type
 PMyRecord = ^TMyRecord;
 TMyRecord = record
  Id : integer;
  Name : string;
 end;
 
 TMyList = class ( TList )
  function Get(Index : integer) : PMyRecord;
  procedure Put(Index : integer; Item : PMyRecord;
  property Items[Index : integer] : PMyRecord read Get write Put; default;
 end;
 
implementation
function TMyList.Get(Index : integer) : PMyRecord;
begin
 Result := PMyRecord(inherited Get(Index));
end;
 
procedure Put(Index : integer; Item : PMyRecord);
begin
 inherited Put(Index, Item);
end;
 


Nun kannst du ganz normal mit Add / Delete / Sort usw mit der Liste arbeiten.
Oder ich habe die Fragestellung nicht richtig verstanden.

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

Re: Maps/Listen von Composite Typen

Beitrag von Warf »

fliegermichl hat geschrieben:Was spricht gegen FPList?

Da wird ja standardmäßig eine Liste von Pointern verwaltet. Worauf die Pointer zeigen kannst du doch selber festlegen.
{...}
Nun kannst du ganz normal mit Add / Delete / Sort usw mit der Liste arbeiten.
Oder ich habe die Fragestellung nicht richtig verstanden.


Naja, bei deinem Beispiel ist der Record 16 Byte groß, der Pointer auf den Record 8 Byte. Wenn ich also 1 GB von diesen Records habe, sind es insgesamt 1,5GB mit den Pointern in der Liste. Das ist inakzeptabel. Außerdem was ist wenn ich auf das ite und das i+1te element zugreifen will? die pointer können in ganz unterschiedliche Regionen zeigen, wodurch kein cache Lokalität besteht und die Daten immer über den Langsamen SystemBUS laufen müssen statt das sie gecached werden können

TFPGList macht es richtig und legt die Objekte direkt in einem Kontinuierlichen Memoryblock ab, sodass 1. Kein overhead entsteht, du hast praktisch den selben Memoryverbrauch wie in nem array (+ die 32 byte ode so für das Listenobjekt), und du hast cache Lokalität, was beim drüberiterieren bei großen listen den unterschied zwischen ich merke kaum das er am arbeiten ist und ich kann mir noch entspannt nen Kaffee kochen bis das fertig ist sein kann.

Bei kleinen listen ist das überhaupt kein Problem, da benutz ich ne FPGObjectList mit Klassen, die über Create erstellt werden und von der Liste selbst gefreed werden, da hab ich aber natürlich das selbe problem bei sehr großen listen.

Außerdem, wer arbeitet freiwillig mit Pointern wenn mans nicht muss?

Benutzeravatar
af0815
Lazarusforum e. V.
Beiträge: 6198
Registriert: So 7. Jan 2007, 10:20
OS, Lazarus, FPC: FPC fixes Lazarus fixes per fpcupdeluxe (win,linux,raspi)
CPU-Target: 32Bit (64Bit)
Wohnort: Burgenland
Kontaktdaten:

Re: Maps/Listen von Composite Typen

Beitrag von af0815 »

Warf hat geschrieben:Außerdem, wer arbeitet freiwillig mit Pointern wenn mans nicht muss?

Derjenige der große, selbst optimierte Datenmengen hat :-)

Ich glaube du kommst mit der Frage hier nicht weiter, dazu ist deine Fragestellung schon zu fortgeschritten.
Blöd kann man ruhig sein, nur zu Helfen muss man sich wissen (oder nachsehen in LazInfos/LazSnippets).

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

Re: Maps/Listen von Composite Typen

Beitrag von Warf »

af0815 hat geschrieben:Ich glaube du kommst mit der Frage hier nicht weiter, dazu ist deine Fragestellung schon zu fortgeschritten.

Ja was sowas angeht bin ich halt mittlerweile von C++ verwöhnt, da ist alles auf performance optimiert.

Hab mal in die FPGList Sourcen geschaut und den missetäter gefunden. Damit strings in den Listen benutzt werden können muss der Gleichheitsoperator verwendet werden (da ja bitwise vergleich nur den Pointer auf den string überprüfen würde) und da strings ja sehr häufig verwendet werden macht es auch sinn das als Standardverhalten drin zu haben

Ist eventuell sogar sinnig für meinen Fall eine eigene Listen-Klasse zu implementieren, denn die GVector variante die ich aktuell verwende kann leider nicht so sachen wie sorted und Dublikate rausfiltern

Antworten