[Delphi] Datastructuren kiezen in een OO model

[Verwijderd]

Ik heb in Delphi een reeks datastructuren die heel veel gemeenschappelijk hebben met waar ik niet direct een gemeenschappelijke en efficiente objectstructuur kan op plakken.

Ik heb bijvoorbeeld (onvolledig, het is het idee dat telt)

code:

 DataRecA = record
    NR: Integer;
    XN,YN,DXN,DYN: Real;
    XT,YT,DXT,DYT: Real;
    DEV: Real;
    P, K: Integer;
  end;
  
  DataRecB = record
    NR: Integer;
    XN,YN: Real;
    THETA,X,Y,Z: Real;
    P: Integer;
  end;

 TDataContainerA = class
 protected
   FData: array[0..MAXDATACOUNT] of DataRecA;
   FCount: Integer;
 public
   procedure AddData(NR: Integer; const XN,YN,DXN,DYN,XT,YT,DXT,DYT,DEV: Real; P, K: Integer);
 end;
 
 TDataContainerB = class
 protected
   FData: array[0..MAXDATACOUNT] of DataRecB;
   FCount: Integer;
 public
   procedure AddData(NR: Integer; const XN,YN,THETA,X,Y,Z: Real; P: Integer);
 end;

De procedures AddData zetten dan een nieuw element in de array en verhogen FCount.

Ik heb nu zo heel veel van dergelijke structuren, telkens met een andere set van variabelen. Ik kan ze allemaal afzonderlijk implementeren geen probleem, maar ik heb toch zo'n gevoel dat er iets doordachter te werk kan gegaan worden. Overerving met override van AddData lijkt me omslachtig omdat ik voor elke structuur een ander aantal parameters wil ingeven. Snelheid is ook belangrijk daarom wil ik arrays gebruiken. Iemand een idee?

[joepP]

Wat jij wilt zijn generics, maar die zitten volgens mij pas in Delphi sinds 2005.

[mulder]

Overerving met override van AddData lijkt me omslachtig omdat ik voor elke structuur een ander aantal parameters wil ingeven. Snelheid is ook belangrijk daarom wil ik arrays gebruiken. Iemand een idee?

Overloading lijkt mij eigenlijk niet zo heel raar, of je moet generieke parameters gaan gebruiken en dan in de functie de boel uitelkaar trekken?

[Verwijderd]

Don Facundo schreef op dinsdag 30 mei 2006 @ 13:55:
[...]
Overloading lijkt mij eigenlijk niet zo heel raar, of je moet generieke parameters gaan gebruiken en dan in de functie de boel uitelkaar trekken?

Overloaden en overriden zijn twee verschillende dingen in Delphi en zoals ik al zei wil ik niet aan snelheid inboeten. Ik weet dat het zou kunnen met een dynamische array van Variants, maar Variants zijn te traag.

Ik gebruik Delphi 2005 op mijn werk en Delphi 7 thuis.

[ Voor 7% gewijzigd door Verwijderd op 30-05-2006 16:08 ]

[Verwijderd]

Verwijderd schreef op dinsdag 30 mei 2006 @ 15:49:
[...]Ik weet dat het zou kunnen met een dynamische array van Variants, maar Variants zijn te traag.

Blegh, variants

Maar waarom is de snelheid zo'n probleem? En weet je zeker dat die daarvan afhankelijk is? Meestal liggen bottlenecks bij subsystemen als data access of bij bepaalde algoritmiek.

[ Voor 6% gewijzigd door Verwijderd op 30-05-2006 20:11 ]

[Verwijderd]

Verwijderd schreef op dinsdag 30 mei 2006 @ 20:10:
[...]


Blegh, variants

Maar waarom is de snelheid zo'n probleem? En weet je zeker dat die daarvan afhankelijk is? Meestal liggen bottlenecks bij subsystemen als data access of bij bepaalde algoritmiek.

Het is voor het toepassen van een optimizatiealgoritme, waarbij elk testcase een bewerking is op een coordinatenlijst met een duizendtal elementen. Dit wil zeggen dat je duizend keer per case toegang tot je data wil om alle elementen in te lezen. De optimizatie daarrond zal misschien in totaal 10000 cases bekijken. 10000 * 1000 geeft dan 10 miljoen keer een element uit de datastructuur uitlezen. Een volledige berekening kan tot een minuut duren in soortgelijke optimizaties, maar eigenlijk vind ik dit al te lang voor mijn toepassing, dus elke factor tijdswinst is belangrijk.

[Verwijderd]

Verwijderd schreef op dinsdag 30 mei 2006 @ 20:36:
[...]Het is voor het toepassen van een optimizatiealgoritme, waarbij elk testcase een bewerking is op een coordinatenlijst met een duizendtal elementen. Dit wil zeggen dat je duizend keer per case toegang tot je data wil om alle elementen in te lezen. De optimizatie daarrond zal misschien in totaal 10000 cases bekijken. 10000 * 1000 geeft dan 10 miljoen keer een element uit de datastructuur uitlezen. Een volledige berekening kan tot een minuut duren in soortgelijke optimizaties, maar eigenlijk vind ik dit al te lang voor mijn toepassing, dus elke factor tijdswinst is belangrijk.

Heb je al assembly overwogen? Niet voor je hele applicatie natuurlijk, maar puur voor dit stukje rekenwerk.

[Verwijderd]

Verwijderd schreef op woensdag 31 mei 2006 @ 12:42:
[...]

Heb je al assembly overwogen? Niet voor je hele applicatie natuurlijk, maar puur voor dit stukje rekenwerk.

Nee, daar begin ik niet aan.
De evaluatie van een testcase is redelijk complex en moet overzichtelijk blijven. Waneer ik mijn code achterlaat voor mijn eventuele opvolger in de toekomst wil ik die persoon geen KLOCK's aan pure assembly voorschotelen

Ik heb al zoveel mogelijk geoptimaliseerd in die code (vermijden van sqrt en trigoniometrische functies enzo). Snelheid die ik nu heb is wel OK, hoor. Mijn vraag was eigenlijk of er, zonder teveel aan snelheid in te boeten, een meer gestructureerde manier van programmeren was voor mijn probleem. Al die klasses lijken namelijk zo hard op mekaar.

Ik zou eventueel eens verschillende datastructuren kunnen uitproberen en de performance benchmarken, misschien dat ik dat wel eens doe...

[Creepy]

En een afgeleide maken van TObjectList tot een TMyWhateverList? Zaken als items, add, delete e.d. aanpassen zodat ze alleen maar een TMyWhatever kunnen aanpaken dan vervolgens weer naar de inherited add/delete etc. (die van TObjectList) doorgeven.

Desnoods maak je van je Records echte classes zodat je alle zaken in de Contructor van je class kan zetten en dat object weer in een (afgeleide van) TObjectList kan zetten.

TList, TObjectList etc. zijn razendsnel (is in feite gewoon een dynamic list met pointers). Items invoegen, verwijderen is snel en sequentueel alle items doorlopen ook. Je eigen implementatie hiervan gaat echt niet (veel) sneller wezen.

Als je Delphi versie nog geen generics ondersteunt vind ik dit de mooiste oplossing.

Waarom gebruik je nu eigenlijk geen TList of TObjectList?

[ Voor 45% gewijzigd door Creepy op 31-05-2006 14:12 ]

[Verwijderd]

Misschien eens kijken naar de al-oude Variante records ? dan kun je je structuren combineren zonder twee datatypen te hoeven gebruiken.

Info : http://www.informit.com/a...asp?p=27383&seqNum=7&rl=1

[ Voor 23% gewijzigd door Verwijderd op 31-05-2006 14:21 ]

[Verwijderd]

@Creepy: Een lijst van pointers naar objecten lijkt mij trager. Ik heb ooit eens een algoritme dat ook met lijsten van coordinaten werkt, gevoelig kunnen versnellen door een bepaalde klasse TCurve, die een TList van records encapsuleert, te vervangen door een statische array van records. Sindsdien sta ik nogal wantrouwig tegenover dat soort OO.

@FFrenzy: misschien wel een elegante oplossing ja, ik zal het overwegen, alleen sta ik ook nogal wantrouwig tegenover alles met de naam Variant in. Om het met de woorden van vieux te zeggen: Blegh.

Misschien doe ik toch gewoon verder zoals ik bezig ben. Veel copy-pasten. Code reuse? Who cares, right?

[MicroWhale]

Het enige wat ik na het lezen van je reacties kan verzinnen is dit:

code:

  TDataRec = record
     rectype : byte;
     ints : array of Integer;
     reals : array of Real;  
  end;

 TDataContainer = class
 protected
   FData: array[0..MAXDATACOUNT] of TDataRec;
   FCount: Integer;
 public
   procedure AddData(aDataRec : TDataRec);
 end;

dit maakt het klein (of groot) en zeer flexibel.

In TDataContainer kan afhankelijk van rectype een bepaalde bewerking uitgevoerd worden.

[ Voor 11% gewijzigd door MicroWhale op 31-05-2006 15:47 ]

[Verwijderd]

Een TObjectList afgeleide met daarin (pointers naar) eenvoudige objectstructuren is in Delphi nauwelijks minder efficient dan een array of records, heb ik in de praktijk mogen ervaren.

Voor een directe koppeling tussen de hotels van een klant van ons en de 4 GDS's (global distribution systems, elke reisagent ter wereld is wel bij 1 van die 4 aangesloten om reserveringen te kunnen boeken, net als de grote websites: Expedia gebruikt bv. Amadeus als GDS) hadden we al ingeschat dat die koppeling niet iedere keer wanneer een aanvraag over de kamerprijzen voor verschillende kamertypes bij 1 of meer hotels in een bep. periode opnieuw naar de centrale database kan gaan, omdat dat a) niet snel genoeg gaat, en b) de database zoveel belast dat de hotels en de centrale reserveringsafdeling daar merkbaar onder te leiden zouden hebben.
Look-to-book verhoudingen (prijzen/beschikbaarheid raadplegen vs. een reservering maken) ligt nl. ruim boven de 1000:1...

Dus cachen in het geheugen van de machine waar die interface op draait was de beste (en meest betaalbare) optie. We hebben gekozen voor 1 TObjectList per hotel met simpele objecten waar alle info die die GDS's willen zien staat. 't Gaat dan om 1 object per hotel / dag / kamertype / tarieftype, en dat loopt aardig op: op dit moment zitten we op zo'n 12 miljoen gecachede objecten, en komen akelig dicht in de buurt van de standaard 2GB geheugenruimte voor een Windows service...
Maar 't performt als een zonnetje!

Vanwege die 2GB grens die steeds dichterbij komt zijn we nu aan het testen met hetzelfde systeem, maar dan met arrays of records: die zijn in Delphi nl. makkelijk op te slaan in een file of record, en de afzonderlijke records in die file zijn snel weer direct in te lezen.
De GDS's eisen dat gegevens voor minimaal een jaar beschikbaar zijn, maar de meeste aanvragen (95%+) hebben betrekking op de eerste 3 maanden, dus dan zouden we alleen die 3 maanden in mem hoeven houden, en de rest uit een file op een dedicated SCSI RAID array halen.

De tests zijn veelbelovend, maar wat hier belangrijker is: performance tests tussen de ObjectList oplossing en arrays geeft (wanneer de objecten/records in mem zitten) een voordeel van <5% voor de array oplossing.

[Verwijderd]

Verwijderd schreef op woensdag 31 mei 2006 @ 20:59:
[...]
op dit moment zitten we op zo'n 12 miljoen gecachede objecten, en komen akelig dicht in de buurt van de standaard 2GB geheugenruimte voor een Windows service
[...]
De tests zijn veelbelovend, maar wat hier belangrijker is: performance tests tussen de ObjectList oplossing en arrays geeft (wanneer de objecten/records in mem zitten) een voordeel van <5% voor de array oplossing.

Volgens mij is de reden van de geringe performancewinst in jouw geval het feit dat je een heel groot geheugengebruik hebt waarbinnen je voortdurend random locaties aanspreekt. In jouw geval heb je dus random access in gans dat 2GB geheugengebied, dit wil zeggen dat je niks voordeel hebt van de veel snellere L2-cache van de CPU omdat quasi elke geheugentoegang via het relatief trage RAM geheugen moet. Voortdurend cache misses zijn dan de oorzaak. Het grootste performanceverschil tussen TList met pointers en array zit hem denk ik in de L2-hitrate.

Mijn toepassing gebruikt voor het algoritme zeker nooit meer dan 200 KB geheugen (enkel voor het algoritme, niet de rest) dus dat past perfect volledig in de L2-cache, wat een snelheidsboost geeft. Het is nu de bedoeling dat we kost wat kost moeten vermijden dat er veel cache misses voorkomen. Werken met TList, dus met pointers, heeft meer kans op geheugen buiten de L2-cache, aangezien pointers zowat naar verspreide geheugenlocaties wijzen. Zo is het voorspelmechanisme van de CPU die bepaalde geheugenblokken op voorhand in de L2 steekt, minder effectief dan bij een mooie aaneensluitende blok geheugen die je hebt bij een array. In jouw geval waren de arrays zo gigantisch groot dat ze niet voortdurend helemaal in de cache konden zitten, dus was er geen sprake van een voordeel.

[Verwijderd]

OK, daar heb je een punt. Ik heb nog nooit de behoefte gehad om 't te testen met minder dan een paar miljoen objecten/records...

offtopic:
Ik zie dat je in je AddData methods je Reals als const doorgeeft. Heb je daar een speciale reden voor? Bij mijn weten heeft 't in Delphi alleen maar zin om strings als const mee te geven, omdat de compiler dan geen rekening hoeft te houden met evt. wijzigingen in die string (die zorgen voor een copie van die string in het geheugen), maar bij integers en floating point variabelen is dat voor zover ik weet niet aan de orde...

[ Voor 64% gewijzigd door Verwijderd op 31-05-2006 23:30 ]

[Verwijderd]

Verwijderd schreef op woensdag 31 mei 2006 @ 23:12:

offtopic:
Ik zie dat je in je AddData methods je Reals als const doorgeeft. Heb je daar een speciale reden voor? Bij mijn weten heeft 't in Delphi alleen maar zin om strings als const mee te geven, omdat de compiler dan geen rekening hoeft te houden met evt. wijzigingen in die string (die zorgen voor een copie van die string in het geheugen), maar bij integers en floating point variabelen is dat voor zover ik weet niet aan de orde...

offtopic:
Inderdaad, die const kan ik even goed weglaten, soms type ik die const namelijk zonder dat ik het zelf besef, aangezien je weet dat het nooit kwaad kan en je vingers sneller typen dan je kan nadenken.