<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content=text/html;charset=ISO-8859-1>
<META content="MSHTML 6.00.2745.2800" name=GENERATOR></HEAD>
<BODY text=#000000 bgColor=#ffffff>
<DIV><SPAN class=922211722-14122005><FONT face=Arial color=#0000ff size=2>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.</FONT></SPAN></DIV>
<BLOCKQUOTE
style="PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #0000ff 2px solid">
<DIV class=OutlookMessageHeader dir=ltr align=left><FONT face=Tahoma
size=2>-----Original Message-----<BR><B>From:</B>
fpc-devel-bounces@lists.freepascal.org
[mailto:fpc-devel-bounces@lists.freepascal.org]<B>On Behalf Of </B>Sterling
Bates<BR><B>Sent:</B> 14 December 2005 22:04<BR><B>To:</B> FPC developers'
list<BR><B>Subject:</B> Re: [fpc-devel] TList or TFPList - a Linked list
?<BR><BR></FONT></DIV>Mattias Gaertner wrote:
<BLOCKQUOTE cite=mid20051214215358.65fceb48@limapholos.matom.wg type="cite"><PRE wrap="">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.
</PRE></BLOCKQUOTE>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.<BR><BR>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.<BR><BR>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:<BR><BR>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.<BR><BR>2. The TList entry only points to the actual data payload,
meaning another 4+<I>n</I> 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.<BR><BR>Disclaimer: this is all based on the Delphi implementation of
TList, and may differ slightly (but probably not much) for the FP
lists.<BR><BR>Sterling<BR></BLOCKQUOTE></BODY></HTML>