Quanto è evidente la differenza di prestazioni tra TList, TObjectList e plain array, se potesse essere stimata?

Question

*<”Summarization:

Si prega di controllare i commenti ben informati degli esperti Delphi. In particolare per me, proverei a utilizzare il vecchio TList / TObjectList come suggerito da David e utilizzare le proprietà hard-cast e TObjectList.List come suggerito da A.Bouchez. Proverò TDynArray durante il refactoring in futuro.

=====================================================================

Supponiamo che io disponga di una classe TAtom come definita nel codice seguente. Ci sono da hundreds fino a thousands di istanze TAtom in fase di esecuzione, per ora stored in a dynamic array. In fase di esecuzione, devo eseguire semplici calcoli in virgola mobile su TAtom.X/Y/Z di tutte le istanze TAtom esistenti più di 30 volte al secondo.

Ora, devo aggiungere la capacità di adding, inserting, deleting delle istanze TAtom in fase di esecuzione. Sembra che le mie scelte siano (1) richiedere un grande array; (2) attenersi alla matrice dinamica e impostare manualmente la lunghezza; (3) passare al normale TList; (4) passare alla normale TObjectList.

Voglio evitare (1) a meno che non sia necessario, perché poi devo cambiare parecchio le firme delle funzioni. Anche (2) non va bene, perché TList / TObjectList sembra nato per questo compito. Tuttavia, poiché il casting del tipo è necessario utilizzando il normale TList / TObjectList, qualcuno potrebbe commentare il possibile impatto sulle prestazioni? Voglio dire, sarebbe meglio se il carico delle prestazioni potesse essere stimato prima di riscrivere il codice. Se le prestazioni diminuiranno notevolmente, ci sono altre tecniche che potrei usare?

Inoltre, mi chiedo se ci sia differenza di prestazioni tra l'utilizzo di TList e TObjectList?

  TAtom = class
  public
    ElementZ: Integer;
    X, Y, Z: Extended;  
    other variables: other types;
  end;

  TAAtom = array of TAtom;

Answer 1

Se utilizzi Generics.Collections.TObjectList<TAtom> e non è necessario trasmettere.

Le prestazioni dovrebbero andare bene per l'utilizzo che descrivi.L'inserimento è più impegnativo dell'aggiunta alla fine perché è necessario spostare gli elementi dopo il punto di inserimento in alto nell'elenco.

Fintanto che eviti SetLength(A, Length(A)+1) e scegli una strategia di allocazione più sensata, gli array dinamici sono equivalenti a tutte le classi TList.

In alcune occasioni ho avuto problemi con le prestazioni e la frammentazione della memoria durante il tentativo di mantenere elenchi di grandi dimensioni come blocchi di memoria contigui.Quindi ho fatto ricorso a uno schema di sottoallocazione.Ma poiché le tue liste contengono riferimenti a oggetti che sono essenzialmente puntatori, hai già sottoallocazione implicita.

È tutto in qualche modo speculativo e devi davvero misurare, altrimenti possiamo solo supporre.

Answer 2

Posso aggiungere un'altra scelta alla tua lista?

Se non utilizzi alcuna funzione di ereditarietà per i dati in TAtom, puoi utilizzare un record invece di un class. Ogni istanza di classe richiederà di essere allocata in memoria, riempita con zero e inizializzata individualmente. Getmem/Freemem costa sempre e la frammentazione della memoria aumenterà.

Un array of record dinamico preallocato sarà più veloce delle istanze di singole classi per l'aggiunta. E i dati si adatteranno meglio alla cache L1 / L2 della CPU.

Per l'inserimento e l'eliminazione, un array di tali record sarà più lento di TList se si dispone di un numero enorme di elementi, perché ci saranno più dati da eliminare / inserire (TList/TObjectList mantengono entrambi solo un elenco di puntatori). Per un inserimento / eliminazione ancora più veloce, dovresti utilizzare meglio un elenco collegato.

È presente un sovraccarico nel meccanismo TList/TObjectList a causa della notifica interna. meccanismo E la proprietà GetItem() potrebbe essere un po 'più lenta (a causa del controllo dell'intervallo) rispetto all'utilizzo diretto di un array dinamico.

Ma con il nostro wrapper TDynArray , puoi attenersi a un array dinamico, e hanno ancora buone prestazioni, funzionalità di pre-allocazione e metodi TList simili. E ancora più metodi disponibili, come SaveToStream, Slice, Reverse, ordinamento con indici esterni e simili ...

type
  TAtom = record // could be 'packed record' to save memory (but loose perf)
    ElementZ: Integer;
    X, Y, Z: Extended;  
    other variables: other types;
    // TDynArray also handle complex (e.g. string) types here
  end;
  TAtoms = array of TAtom;

var Atom: TAtom;
    AtomArray: TAtoms;
    AtomCount: integer;
    Atoms: TDynArray;
begin
  Atoms.Init(TypeInfo(TAtoms),AtomArray,@AtomCount);
  Atoms.Capacity := 10000; // pre-allocate array = same as SetLength(AtomArray,10000)
  for i := 1 to 10000 do begin
    A.ElementZ := Random(1000);
    A.X := Random;
    A.Y := Ramdom;
    A.Z := Random;
    // set other fields
    Atoms.Add(A); // fast adding of A properties
  end;
  // you have TList-like methods for your dynamic array
  Atoms.Delete(500); // delete 500th item
  A.ElementZ := 5000;
  Atoms.Insert(500,A); // insert A values at 500th index
  assert(Atoms.Count=10000);
  assert(AtomCount=10000); // same as Atoms.Count
  Atoms.Compare := SortDynArrayInteger;
  Atoms.Sort; // will sort by 1st Integer value = ElementZ
  for i := 1 to Atoms.Count-1 do // or AtomCount-1
    // you have still direct access to AtomArray[]
    // -> this is even the fastest access to the data
    assert(AtomArray[i].ElementZ >=AtomArray[i-1].ElementZ )
  Atoms.SaveToStream(aStream); // will also save any string content
  Atoms.Reverse; // reverse all items order
  Atoms.Clear;
  // faster adding will be done with direct access to the dynamic array
  Atom.Count := 10000; // allocate memory for 10000 items
  for i := 0 to 10000-1 do
  with AtomArray[i] do
  begin
    ElementZ := Random(2000);
    X := Random;
    Y := Random;
    Z := Random;
  end;
  Atoms.Sort; // TDynArray knows about the data just created
end; // no need to have any try...finally ..Free block

Funziona con Delphi 6 fino a XE.

Con la versione più recente di Delphi che supporta i generici, dovresti andare in questa direzione.

Answer 3

Tuttavia, poiché il casting del tipo è necessario usare il normale TList / TObjectList, potrebbe qualcuno commentare la possibile performance hit?

Se digiti cast utilizzando il modulo

List[I] as TAtom

poiché verrà aggiunto un piccolo overhead, che può davvero aumentare nella tua situazione.Tuttavia, se scrivi hard typecast

TAtom(List[I])

per quanto ne so, in realtà non si verifica alcun sovraccarico poiché il typecast viene eseguito senza controlli e credo anche che venga eseguito in fase di compilazione.

Per quanto riguarda l'altro aspetto della tua domanda, penso che siano già stati tutti adeguatamente trattati ...

Answer 4

Poiché TObjectList è un discendente diretto di TList, le prestazioni saranno molto simili.

Answer 5

Prima domanda: stiamo parlando di Classes.TList e Contnrs.TObjectList o stiamo parlando di Generics.Collections.TList rispettivamente di Generics.Collections.TObjectList?

Se parliamo di generici, sia TList che TObjectList sono implementati utilizzando array dinamici. Se c'è qualche differenza di prestazioni tra l'utilizzo diretto di un array dinamico o l'utilizzo dell'interfaccia più bella del contenitore generico, sarà trascurabile.

---

Se stiamo parlando dei "vecchi" TList e TObjectList, dobbiamo confrontare solo TList con l'equivalente dell'array dinamico, poiché TObjectList è un discendente di TList, quindi eredita tutte le sue caratteristiche prestazionali. TList utilizza un blocco di memoria allocato utilizzando ReallocMem. L'array dinamico fa la stessa cosa internamente, quindi non dovrebbe esserci una differenza significativa!

Conclusione

Se c'è qualche differenza di prestazioni tra i due, è probabilmente perché l'uso ingenuo dell'array dinamico utilizza il temuto SetLength(A, Length(A)+1), mentre la migliore implementazione in tutti i contenitori forniti da Delphi pre-alloca la memoria in blocchi più grandi. Con il codice corretto non dovrebbe esserci alcuna differenza significativa tra quelle alternative!

Answer 6

Crea un progetto di prova e misura il tempo necessario per aggiungere, inserire ed eliminare migliaia di istanze di TAtom utilizzando i quattro metodi.Quindi decidi quale usare.

TList e TObjectList sono probabilmente più veloci di un array dinamico durante l'aggiunta, l'inserimento e l'eliminazione, perché l'array dinamico deve essere costantemente riallocato.L'implementazione di TList e TObjectList non lo fa.

Answer 7

TList ecc. fanno esattamente quello che dovrebbe fare il codice che lavora su blocchi di memoria o dynarrays, ma la loro implementazione è già ottimizzata per i casi comuni e include considerazioni su come si comporta il gestore della memoria.

Un criterio potrebbe essere il rapporto tra letture / aggiornamenti e la sequenza.Se la sequenza viene aggiornata di rado dopo la creazione, dovrebbe essere percepibile una maggiore velocità con i dynarrays, poiché l'accesso agli elementi con TList e simili richiede una chiamata al metodo più il controllo dei limiti, più un controllo del tipo se si utilizza l'operatore as.

Alla fine, il costo dell'aritmetica eseguita su TAtom dovrebbe dominare il tempo di esecuzione, rendendo irrilevante la scelta di dynarray o TListXXX.

Answer 8

Un array dinamico di record avrà il minor impatto quando si accede agli elementi, se i tuoi atomi sono oggetti, tutti gli elenchi saranno in qualche modo equivalenti in termini di velocità di accesso.

Tuttavia, se ne esegui molti, il tuo problema chiave saranno gli inserimenti e le eliminazioni, per i quali tutte le liste e gli array funzioneranno male, ma questo è ciò che ti dirà la profilazione. In tal caso, potresti prendere in considerazione:

• un elenco collegato se non è necessario accedere agli atomi per indice
• un albero, se dovessi usare una partizione spaziale dei tuoi atomi, potresti anche usare quella partizione per contenere i tuoi atomi piuttosto che l'array
• consentire elementi undefined / nil nel tuo array / elenco e mantenere una pila di elementi non definiti / nil e un indice se hai bisogno di un elenco ordinato (potenzialmente la soluzione con le prestazioni più elevate, ma probabilmente anche la più complessa da inseriretermini di efficienza)