|
note
that if the data you wan't to store in a tlist is the size of a pointer or less
you can store it directly in the tlist.
Mattias Gaertner wrote:
Your trick will only give a constant factor on growing/shrinking the list
memory, gives an extra O(n) factor for sorting a TList, the caching costs
time, and the memory usage will also grow.
Just saw this last statement. The memory usage is
very comparable to TList, even with bi-directional (doubly-linked) lists,
since TLists tend to grow by leaps.
For example, assuming a linked list
item comprises of only a "next" pointer, it requires 8 bytes of memory (4 for
the structure itself, 4 for the next pointer). In this case, 10,000
entries occupy 80,008 bytes (80,000 + 4 for pointer to First + 4 for pointer
to Last), distributed around the memory table. Also keep in mind that
the data payload for the linked list item is usually contained within the
structure itself.
A TList (stripped down for this case) requires 4
bytes for the list allocation, plus 4 bytes per list entry. 10,000
entries occupy 80,004 bytes. Now, two things:
1. With
automatically growing lists you have a very high likelihood of unused
pointers, so while a linked list of 10,000 items is utilizing all 80,004 bytes
of memory, the TList allocated (10,000-TList.Count)*4 unused bytes of
memory.
2. The TList entry only points to the actual data payload,
meaning another 4+n bytes must be allocated to store the data.
This means an additional 40,000 bytes is required for a TList vs. a linked
list. On the other hand, this is equalized in a doubly-linked
list.
Disclaimer: this is all based on the Delphi implementation of
TList, and may differ slightly (but probably not much) for the FP
lists.
Sterling
|
_______________________________________________
fpc-devel maillist - [email protected]
http://lists.freepascal.org/mailman/listinfo/fpc-devel
