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

[peter green]

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.
  -----Original Message-----
  From: fpc-devel-bounces at lists.freepascal.org
[mailto:fpc-devel-bounces at lists.freepascal.org]On Behalf Of Sterling Bates
  Sent: 14 December 2005 22:04
  To: FPC developers' list
  Subject: Re: [fpc-devel] TList or TFPList - a Linked list ?


  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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freepascal.org/pipermail/fpc-devel/attachments/20051214/d7d34df3/attachment.html>