[fpc-devel] TList or TFPList - a Linked list ?
whoelse at sterlingbates.com
Wed Dec 14 22:13:27 CET 2005
Micha Nelissen wrote:
>I've been thinking about adding a linked list implementation to either TList
>or TFPList. The basic problem to that is of course
>1) space overhead of linked list is quite large
>2) Index[..] will be O(N)
>For (1) I was thinking about making a linked list of an array of items, for
>example 14 pointers (so that 8 bytes are left for next pointer and memory
>manager needs on 32 bit platform).
>To solve (2), we can make the observation
>that generally people access lists in a linear fashion, and we might cache
>the previous and next list entry.
>The big advantage is getting rid of the many reallocs needed to grow
>the lists, because one usually doesn't set Capacity in advance, but keeps
>adding items until done.
>Using aggregation possibly, TStringList must benefit from it too.
>What do you think about it ?
>fpc-devel maillist - fpc-devel at lists.freepascal.org
My most recent project at work involves a good deal of non-linear access
to TList items (sorry, not Free Pascal <g>), and this implementation
would essentially kill the efficiency gains that we achieved by doing
so. In addition, the caching overhead (the last requested index, as
well as next & prev pointers, and corresponding logic) would blow away
the efficiency of iterating through TList items. There's no way to work
Linked lists are very specialized, and definitely have their place, and
classes should be built for them. However, they're definitely their own
beast, and should be treated as such. For instance, you made the valid
point that they grow very easily and without the overhead of having to
find large contiguous chunks of memory when the list grows, but
iterating them is relatively slow. Programmers just need to recognize
when this is an advantage and when it isn't.
Just my $0.02.
More information about the fpc-devel