On Wed, 14 Dec 2005 15:03:58 -0700 Sterling Bates <[EMAIL PROTECTED]> wrote:
> 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). Plus some bytes for the memory manager for each mem block. Typically 8. > In this case, 10,000 entries occupy 80,008 bytes > (80,000 + 4 for pointer to First + 4 for pointer to Last), ~160,000 > 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. ~40,000 > 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. i.e. plus a maximum of 25% with the current implementation ~50,000 > 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. Huh? > 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. The main problem is the mem fragmentation. Here a growing TList can need up to 4 times its used memory. So in worst case it will need the memory of a single linked list. Mattias _______________________________________________ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel