How noticeable is the performance difference among TList, TObjectList and a simple array, if this can be appreciated?

Question

* Summation:

Please check out Delphi's great expert commentary. In particular, for me I would try to use the old TList / TObjectList, as David suggested, and use the hard-cast property and TObjectList.List, as suggested by A. Bushez. I will try TDynArray when refactoring in the future.

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

Say that I have a TAtom class as defined in the following code. Roughly hundreds to thousands TAtom instances at runtime, stored in a dynamic array now. At runtime, I need to do simple floating-point TAtom.X/Y/Z on TAtom.X/Y/Z all existing TAtom instances more than 30 times per second.

Now I need to add the ability to add, inserting , deleting instances at runtime. My choice seems to be: (1) a large array request; (2) stick to the dynamic matrix and manually SetLength; (3) switch to a regular TList; (4) switch to a regular TObjectList.

I want to avoid (1) if it is not necessary, because I have to change quite a few function signatures. (2) does not look very good, because TList / TObjectList seems to be born for this task. However, since type casting is needed using a regular TList / TObjectList, can someone comment on possible performance? I mean, it would be better if the performance score could be evaluated before I rewrote the code. If performance drops noticeably, is there another technique I could use?

Also, I am wondering if there is a performance difference between TList and TObjectList?

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

Answer 1

If you are using Generics.Collections.TObjectList<TAtom> and there is no need for casting.

Performance should be perfect for the use you are describing. Inserting is more complicated than adding to the end, because you need to move items after pasting to the list up.

As long as you avoid SetLength(A, Length(A)+1) and choose a more reasonable distribution strategy, dynamic arrays are equivalent to all TList classes.

In some cases, I had performance and memory fragmentation issues when trying to save large lists as contiguous blocks of memory. Then I resorted to the allocation scheme. But since your lists contain references to objects, which are essentially pointers, you already have an implicit sub-distribution.

All this is somewhat speculative, and you really need to measure, otherwise we can only guess.

Answer 2

Can I add another list to your list?

If you do not use the inherit function for data in TAtom , you can use record instead of class . Each instance of the class must be allocated to memory, filled with zero and initialized separately. Getmem/Freemem always stands, and memory fragmentation increases.

A pre-allocated dynamic array of record will be faster than individual instances of the class to add. And the data is better for the L1 / L2 CPU cache.

For insertion and deletion, an array of such records will be slower than TList if you have a huge number of elements, because there will be more data to delete / insert ( TList/TObjectList as supporting only a list of pointers). For even faster insertion / deletion, you better use a linked list.

The TList/TObjectList mechanism has some overhead due to internal notification. mechanism And the GetItem() property may be slightly slower (due to range checking) than using a dynamic array directly.

But with our TDynArray wrapper, you can stick with a dynamic array and still have good performance, pre-allocation functions, and TList methods. And even more methods available, such as SaveToStream, Slice, Reverse , sorting with external indexes, etc.

 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 (eg 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); AX := Random; AY := Ramdom; AZ := 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 

Works with Delphi 6 to XE.

With a newer version of Delphi that supports generics, you'd better go in that direction.

Answer 3

However, since type casting needs to use regular TList / TObjectList, can someone comment on the possible performance hit?

If you type cast using the form

 List[I] as TAtom 

as little overhead will be added, which can really fit your situation. However, if you are a heavy type

 TAtom(List[I]) 

as far as I know, there is actually no overhead, since type casting is done without checks, and I also think that this is done at compile time.

As for the other aspect of your question, I think they were already completely covered ...

Answer 4

Make a test project and measure the time to add, insert, and delete thousands of TAtom instances using four methods. Then determine which one to use.

TList and TObjectList are probably faster than a dynamic array when adding, inserting, and deleting, because the dynamic array needs to be constantly redistributed. The implementation of TList and TObjectList does not.

Answer 5

Since TObjectList is a direct descendant of TList, the actions will be very close.

Answer 6

First question: are we talking about Classes.TList and Contnrs.TObjectList or are we talking about Generics.Collections.TList respectively Generics.Collections.TObjectList ?

If we are talking about generics, TList and TObjectList are implemented using dynamic arrays. If there is a performance difference between using the dynamic array directly or using the more convenient interface of the universal container, this will be negligible.

---

If we are talking about the “older” TList and TObjectList , we only need to compare the TList with the equivalent of the dynamic array, since the TObjectList is a descendant of the TList , so it inherits all these performance characteristics. TList uses a block of memory allocated using ReallocMem . A dynamic array does the same inside, so there should be no significant difference!

Conclusion

If there is a difference in performance between the two, it is likely because the naive use of a dynamic array uses the scary SetLength(A, Length(A)+1) , while the best implementation in all containers supplied by Delphi predetermines memory in large chunks. With the right code, there should not be a significant difference between these alternatives!

Answer 7

TList etc. they do exactly what code working on pieces of memory or dynamic devices should do, but their implementation is already optimized for the general case and includes considerations about how the memory manager behaves.

One criterion may be the ratio of read / update to sequence. If the sequence is updated infrequently after creation, then there should be a noticeable higher speed with the help of speakers, because access to elements with TList and the like requires a method check plus plus a method check plus type check if you use the as operator.

In the end, the cost of arithmetic done on TAtom should dominate the execution time, making the choice of dynarray or TListXXX inconsequential.

Answer 8

Dynamic record arrays will have the lowest impact when accessing elements, if your atoms are objects, then all lists will be somewhat equivalent in terms of access speed.

However, if you do many of these, insertion and deletion will be a key issue, for which all lists and arrays will work poorly, but that is what profiling will tell you. If this happens, you might think:

• linked list if you don't need to access atoms by index
• tree, if you use the spatial separation of your atoms, you can also use this section to store your atoms, not an array
• allows undefined / nil elements in your array / list and support a stack of undefined / nil elements and an index if you need a sorted list (perhaps the solution with the highest performance, but also probably the most difficult to get right in terms of efficiency)