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

Op Wed, 14 Dec 2005, schreef Micha Nelissen:

Sorry to disappoint, but this doesn't look a very good idea to me; it would kill code that for example tries to sort a list. There will be also a lot of code that iterates using index[].

Programmers need both list like datastructures and array like data structures. It is part of converting mathematical abstraction principles like a sequence where every operation is O(1), to actual datastructures that are to be used inside a compiler. Programmers need both of them, not one or the other.

Daniël

This will break all random access uses. For example sorting a TList.

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.

TFPList/TList grows exponentially, which is pretty good for a generic dynamic array. It results in O(n).

Using aggregation possibly, TStringList must benefit from it too. What do you think about it ?

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.

Mattias

Did you read the paragraph, "to solve (2) ..." ? Sorting is also quite a "local" operation, no ? No truly random-access is needed.

Programmers need both list like datastructures and array like data structures. It is part of converting mathematical abstraction principles

Array like datastructures are provided by dynamic arrays, I'd say ?

like a sequence where every operation is O(1), to actual datastructures that are to be used inside a compiler. Programmers need both of them, not one or the other.

Yes, currently there is no linked list at all, is there ?

These issues are precisely the reason I'm writing to the list and gathering ideas first.

Micha

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).

Tiny addition: for 64bit OS you would also use 14 pointers, but 16 bytes are left, which again is one for next pointer and memory manager's "size: ptrint".

Micha

I strongly disagree here. I use T(FP)List quite a lot, and usually do a good estimate in setting the capacity. When storing/reading items of a list you always write/read the count first...

People that have large lists know this and take care of it.

What is more, I think that 1 large memory block (an array) is much more efficient memory wise than many small blocks.

Using aggregation possibly, TStringList must benefit from it too.

No way, e.g. the IndexOf for sorted stringlists would be crippled totally. Inside TList, The Move()/Exchange operations would be a horror, and hence the listsort as well.

What do you think about it ?

I think it's a bad idea. TFPList is implemented for speed and does very well.

But, on the bright side: A TLinkedList implementation is more than welcome, but it should be a separate class. LinkedLists and the regular List are 2 different beasts, that only have in common that they store a lot of pointers.

Michael.

QuickSort is not so local, definitely not in the beginning.

Excellent, maybe now we'll finally have a decent TLinkedList :)

An excellent location is the contnrs unit.
It already contains the TStack and TQueue.
TLinkedList perfectly fits in this list.

Michael.

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.

Op Wed, 14 Dec 2005, schreef Micha Nelissen:

Yes I did, but caching the previous and the next is no solution for sorting. There exists no magic data structure that can replace both the list and the array.

> Programmers need both list like datastructures and array like data > structures. It is part of converting mathematical abstraction principles Array like datastructures are provided by dynamic arrays, I'd say ?

Yes, but a linked list also can be implemented using a record with a pointer; object oriented libraries a little bit extra power to the code, which a dynamic array cannot provide.

Afaik, no, we could use one, so please add it, and we're all happy :)

These issues are precisely the reason I'm writing to the list and gathering ideas first.

I know, no problem.

Daniël

Examples:
- Binary search
- Quicksort in TList.Sort

Yes

It was one of Borland best ideas to name a dynamic array a 'TList'. You can implement a TLinkedList and TDoubelLinkedList like the glib's glist.

Mattias

Sorry. I meant TDoubleLinkedList.

Mattias

This is true in some cases; VMs and scripting engines (such as SpiderMonkey) use this technique. However, when the list size is underestimated and has to grow it can be a huge detriment to performance and memory efficiency.

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.

You may be underestimating the impact of the heap manager. I just checked the code in lists.inc. When there are less than 128 items, the list is increased by 8 items. So when adding 1000 (to take a number) items, the list is copied at least 10, possibly 13 times, 12 -> 28 -> 44 -> 60 -> 76 -> 92 -> 108 -> 124 -> 140 -> 206 -> 325 -> ~500 -> ~780 -> ~1000. For the linked list case, no memory is copied.

Sure, if you're going to sort a list, you should not use linked list of course, but an array (or tree maybe).

Due to memory fragmentation, it is debatable whether memory usage will really grow significantly more for linked list.

Micha

increased by 8 items. So when adding 1000 (to take a number) items, the list is copied at least 10, possibly 13 times, 12 -> 28 -> 44 -> 60 -> 76 -> 92 -> 108 -> 124 -> 140 -> 206 -> 325 -> ~500 -> ~780 -> ~1000. For the linked list case, no memory is copied.

Hmm, in case one doesn't know the number of items in advance, it would be nice to have a AssignTo/CopyTo(AList: TList) method that copies to items into a regular list, so it can be sorted or whatever random access you may need.

Micha

It was not my decision to increase TList by only one fourth. But still the list grows exponentially, which means for 1000 items there will be only c times 1000 copies.
For a growing of 25% as it is now c is less than 4.

Indeed.

Mattias

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.

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

~40,000

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?

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

If the linked list item contains the whole data, then you are either not talking of the generic list this thread is about, or you use templates. In the later case a TList will also use templates and the 'payload' is the same.

There are TList of integer. No mem blocks needed. Same for linked list. See above about the whole data contained in the list item.

Right.

Mattias

That's true of records, sure. Someone could also create a TLinkedListItem base class from which to descend and store their data there. The next & prev pointers can be stored in the base class.

Anyway, thanks for the discussion :)

Well, if you use objects, then you get even more mem overhead ... :)

Anyway, thanks for the discussion :)

With pleasure.
We could discuss it endless. Micha's original idea was even to use a block linked list. :)

Mattias

Mattias Gaertner wrote

Well, if you use objects, then you get even more mem overhead ... :)

I was thinking about that too. Then, IIRC, I read that object overhead is a one-time allocation of class tables and such. Of course, you might have some extra overhead inherited from TObject (ClassName etc). In my case, though, I use TList for objects anyway, so it all balances out. Guess it really depends on how one uses the tools.

Mattias Gaertner wrote

Plus some bytes for the memory manager for each mem block. Typically 8.

FYI, for small blocks (<512 bytes) it's only 4. And now I look at heap.inc again, I think that even alignment for small blocks could be upgraded to 4 byte granularity instead of 16 bytes. This would have a positive impact on memory usage (less slack), while retaining equal speed.

Anyone interested in smaller granularity there ? It would increase the number of freelists by a factor 4, but that's globally, once-allocated memory.

Micha