How noticeable is the difference of performance among TList, TObjectList, and plain array, if it could be estimated?

N

8

9

*Summarization:

Please check the knowledgeable comments from the Delphi experts. Specifically for me, I would try to use old TList/TObjectList as David suggested, and use hard-cast and TObjectList.List property as A.Bouchez suggested. I will try TDynArray when refactoring in future.

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

Say that I have a TAtom class as defined in the following code. There are about hundreds up to thousands of TAtom instances at run time, stored in a dynamic array for now. At run time, I need to do simple float math on TAtom.X/Y/Z of all the existing TAtom instances more than 30 times per second.

Now, I need to add the ability of adding, inserting, deleting of TAtom instances at run time. It seems that my choices are (1) request a big array; (2) stick to dynamic array and manually SetLength; (3) switch to regular TList; (4) switch to regular TObjectList.

I want to avoid (1) unless it is necessary, because I then have to change quite a lot function signatures. (2) looks not good either, because TList/TObjectList seems born for this task. However, because type-casting is needed using the regular TList/TObjectList, could some one comment on the possible performance hit? I mean, it would be best if the performance burden could be estimated before I rewrites the code. If the performance will drop noticeably, is there other technics that I could use?

Furthermore, I am wondering if there is performance difference between using TList and TObjectList?

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

  TAAtom = array of TAtom;

Nectarine answered 18/3, 2011 at 12:32 Comment(14)

My advice would be to measure it and see for yourself. – Maldon 18/3, 2011 at 12:41

@TOndrej: I am just wondering if it could be estimated for my situation (simple float math upon hundreds upto thousands of instances 30 times per second)... :D There might be a rule of thumb? – Nectarine 18/3, 2011 at 12:48

@Xichen Li, the "Delete" and "Insert" operations are going to be the worst case for all of TList, TObjectList and dynamic array; If you need to think about performance, find a way to skip the penalty of Delete's, the "return on investment" is going to be significantly higher! – Crudden 18/3, 2011 at 12:54

@Xichen Li, do you need random access to any element in the array? If sequential access is enough you'd be better served by the humble "linked list": It provides O(1) insert, delete and append. – Crudden 18/3, 2011 at 13:2

@Cosmin: Thanks very much for your comments! Could you help to suggest some plausible ways to get higher return on investment in my situation? – Nectarine 18/3, 2011 at 13:3

@Xichen Li, my previous comment recommends the use of a linked list, because it has O(1) insert / delete / append. Other ideas include not deleting but replacing the values with nil (so you don't need to shift the buffer) or replacing the whole data structure with an tree: The tree might be able to better balance the cost of random access with the cost of insert and delete. Of course, it all depends on your workload, and only you know what that is. – Crudden 18/3, 2011 at 13:6

@cosmin: I don't make heavy use of random access. But I do sequential access a lot. For example, for each batch of simple float math calculation, I need to iterate through the instances. I assume the linked list data structure is not as good as array in sequential access? – Nectarine 18/3, 2011 at 13:7

@Cosmin: Thank you for helpful suggestions very much! I need to think about them for a while. :D – Nectarine 18/3, 2011 at 13:11

No, the linked list works perfectly well for sequential access but can't be used for random access. You need to drop random access all together or accept a really high penalty for using it (you'd need to walk the whole list to get a record by index). – Crudden 18/3, 2011 at 13:11

@Xichen Before you implement linked lists (more complex than lists or arrays), convince yourself that you actually have a performance problem. Otherwise you'll be complicating for no benefit. – Wotan 18/3, 2011 at 13:28

About linked lists: this is a very good pattern, especially for deletion or insertion, but for huge number of items, consider the memory consumption and fragmentation. For sequential reading, a preallocated array of record will be definitively faster than any collection of individual class instances. Each TAtom class instance will have its own memory (calls to GetMem/FreeMem always cost) and won't be contiguous allocated: it will be slower for sequential access. A pre-allocated array of records will be optimized for the CPU L1 and L2 cache. – Throw 18/3, 2011 at 13:31

@A.Bouchez, performance optimization is the art of balancing constraints: Sure, nothing beats an array of records for sequential access, but if you need to do an significant amount of deletes and inserts on a large array, you're going to really feel them. IMHO selecting the best data structures and algorithms are the best possible optimizations, not agonizing over the relative speed of dynamic array and TList. – Crudden 18/3, 2011 at 13:38

@Cosmin Prund That was exactly my point. Amen ! – Throw 18/3, 2011 at 13:46

@Cosmin iiuc finding the insertion/deletion point in a linked list is O(n) - #841148 – Intolerable 18/3, 2011 at 17:1

W

7

If you use Generics.Collections.TObjectList<TAtom> and there's no need for casting.

Performance should be fine for the usage that you describe. Inserting is more demanding than adding to the end because you need to shift the items after the insertion point up the list.

So long as you avoid SetLength(A, Length(A)+1) and opt for a more sensible allocation strategy dynamic arrays are equivalent to all of the TList like classes.

On occasions I have had problems with performance and memory fragmentation when trying to maintain large lists as contiguous blocks of memory. Then I have resorted to a sub-allocation scheme. But since your lists contain object references which are essentially pointers, you already have implicit sub-allocation.

It's all somewhat speculative and you really need to measure – otherwise we can only guess.

Wotan answered 18/3, 2011 at 12:49 Comment(10)

@David: Thanks very much for your time! But if the old, regular TList/TObjectList is used, could the performance drop be estimated? – Nectarine 18/3, 2011 at 12:51

Old TList/TObjectList performance will be essentially the same as the generic versions. – Wotan 18/3, 2011 at 12:53

@David: Thank you very much for Old TList/TObjectList performance will be essentially the same as the generic versions. Secondly, I understand " Inserting is more demanding", but inserting seems to be necessary to undo the deleting. Furthermore, thank you very much for sharing your experience! I assume you had used array of record? Could you help to comment on the number of instances in your problems? – Nectarine 18/3, 2011 at 12:57

pre-allocation is the trick to use, with external Count variable: think about the dynamic array length as its capacity, not its number of items. – Throw 18/3, 2011 at 13:10

@A.Bouchez Pre-allocation doesn't help when your arrays need very large contiguous blocks of memory, and are constrained by 32 bit address space. Then you need sub-allocation. – Wotan 18/3, 2011 at 13:24

@Xichen Hard to give general advice without knowing your problem. The only area where you have room for manoeuvre is inserting and deleting to/from middle of the list. Do you really need to do this? Anyway, how many insertions do you perform per walk of the list? If that is a small number then you won't have performance problems. – Wotan 18/3, 2011 at 13:25

@David From what Xichen Li wrote above (100 or 1000s of items), data will definitively fit in 32 bit address space. ;) – Throw 18/3, 2011 at 13:32

@David: I only do simple float math on existing instances per walk. The inserting or deleting is done only upon users' requests. For example, one can select a group of atoms and delete them, or one can add a group of atoms into an existing molecule (set of atoms). As you say, it is a small number for most of the time. In this respect, if switching to TList/TObjectList gives almost the same speed for plain sequential access as using dynamic array, TList/TObjectList seems perfectly fine then. – Nectarine 18/3, 2011 at 13:33

@A.Bouchez Since it's only 100 or 1000s of small items containing a handful of floating point values, and one such list in the app, I'd probably be inclined to use Generics.Collections.TList<TMyRecord>. That is a record with methods rather than a class. Contiguous allocation is actually what you want here. – Wotan 18/3, 2011 at 13:36

@Xichen If insertion/deletion is only at user request, then definitely an array/list (same thing really) and not a linked list. And if performance is critical take @A.Bouchez's advice and lay it out in a value type record to get the best cache use. – Wotan 18/3, 2011 at 13:37

T

9

May I add another choice to your list?

If you don't use any inheritance feature for the data in TAtom, you could use a record instead of a class. Each class instance will require to be allocated in memory, filled with zero and initialized individually. Getmem/Freemem always cost, and memory fragmentation will increase.

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

For inserting and deleting, an array of such records will be slower than TList if you have a huge number of items, because there'll be more data to delete/insert (TList/TObjectList both maintain just a list of pointers). For even faster insertion/deletion, you should better use a linked list.

There is some overhead in the TList/TObjectList mechanism because of internal notification. mechanism And the GetItem() property could be a bit slower (because of range checking) than using directly a dynamic array.

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

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

Works with Delphi 6 up to XE.

With newer version of Delphi supporting generics, you should better go into this direction.

Throw answered 18/3, 2011 at 13:1 Comment(2)

Thank you very much for your suggestion! I will try first to understand your code before further commenting. :D – Nectarine 18/3, 2011 at 13:5

Feel free to ask question here or in our forum, if you need information. – Throw 18/3, 2011 at 13:7