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

[Mattias Gaertner]

On Wed, 14 Dec 2005 22:40:40 +0100
Micha Nelissen <micha at neli.hopto.org> wrote:

> On Wed, 14 Dec 2005 21:53:58 +0100
> Mattias Gaertner <nc-gaertnma at netcologne.de> 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.
> 
> You may be underestimating the impact of the heap manager. I just checked
> the code in lists.inc. When there are less than 128 items, the list is
> increased by 8 items. So when adding 1000 (to take a number) items, the
> list is copied at least 10, possibly 13 times, 12 -> 28 -> 44 -> 60 -> 76
> -> 92 -> 108 -> 124 -> 140 -> 206 -> 325 -> ~500 -> ~780 -> ~1000. For the
> linked list case, no memory is copied.

It was not my decision to increase TList by only one fourth.
But still the list grows exponentially, which means for 1000 items there
will be only c times 1000 copies.
For a growing of 25% as it is now c is less than 4.

 
> Sure, if you're going to sort a list, you should not use linked list of
> course, but an array (or tree maybe).
> 
> Due to memory fragmentation, it is debatable whether memory usage will
> really grow significantly more for linked list.

Indeed.


Mattias