Micha Nelissen wrote:
Hi,
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 ?
Micha
_______________________________________________
fpc-devel maillist - fpc-devel@lists.freepascal.org
http://lists.freepascal.org/mailman/listinfo/fpc-
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
around that.
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.
_______________________________________________
fpc-devel maillist - fpc-devel@lists.freepascal.org
http://lists.freepascal.org/mailman/listinfo/fpc-devel
