<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
</head>
<body bgcolor="#ffffff" text="#000000">
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>
</body>
</html>