[fpc-devel] TList or TFPList - a Linked list ?

[Mattias Gaertner]

On Wed, 14 Dec 2005 15:03:58 -0700
Sterling Bates <whoelse at sterlingbates.com> wrote:

> 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). 

Plus some bytes for the memory manager for each mem block. Typically 8.


> In this case, 10,000 entries occupy 80,008 bytes
> (80,000 + 4 for pointer to First + 4 for pointer to Last),

~160,000


> 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. 

~40,000


> 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.

i.e. plus a maximum of 25% with the current implementation
~50,000

 
> 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. 

Huh?


> 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.

The main problem is the mem fragmentation. Here a growing TList can need up
to 4 times its used memory. So in worst case it will need the memory of a
single linked list. 


Mattias