How realistic is it to have a linked list in contiguous memory that stays nicely ordered? In my experience, lists are normally cobbled together with nodes that are allocated widely separated in time and hence I have no knowledge that I can use to predict the address of the next pointer.
If you're in a scenario where this optimization works, it seems like it would be better to just use an array.
Are you familiar with Donald Knuth's "Dancing Links" ??
Its a covering-problem solver (NP-complete) that uses linked lists highly-efficiently. All nodes are "statically allocated" (at least, with respect to the algorithm), because the covering-problem takes up a constant amount of space.
The linked-list "Dances", pointing at other nodes to represent which combination of covers are attempted. So any link could potentially point to any other link later in its list. However, the number of nodes themselves is constant and set before the algorithm runs.
As such, the linked-list is fully X1->X2->X3->X4... at the start of the algorithm. (where X1, X2, X3 are contiguously allocated in memory). If X3 is proven to "not be a good guess" for our covering problem, then it is cut out of the linked list (X1->X2->X4).
All links remain in order, and are ordered on a 2-dimensions (So not only X1->X2->X3... but also X1->Y1->Z1...). Where X, Y and Z are the compound-elements trying to cover locations 1, 2, 3, ...
------------
Most simple malloc implementations also have the free-list as a simple linked-list that is in fact, ordered in memory. (The first node in the free-list is the lowest numbered RAM spot, while the final node in the free-list is in the highest-numbered RAM spot).
The FAT32 linked-list across a hard drive is also nicely ordered (and when it isn't, the user will perform "defragmentation" to reorder the list and optimize the hard drive).
-----------
IMO, the "nicely ordered Linked List" is uncommon, but... common enough that its worth discussion. And sure, maybe we don't use FAT32 filesystems today very often, but that's the technology I used growing up lol. I know the methodology works!!
I think you need to be aware of why such an implementation (fat32) had to exist. As I believe (I also grew up with fat32) that it basically vanished when HDDs with caches in the MB started to show up. Journaling became a thing; actual caches became a thing so the HDD could actually lay things out well by utilizing said cache.
NTFS still needed to occasionally be defragmented but it allocated more of a buffer to prevent having to do so at all.
I think; in general; You're very spot on about utilizing continuous arrays of memory for linked lists as they will almost always result in better performance characteristic (unless you really need insertion/removal in order and it's very write heavy).
It's fairly standard for a compacting GC to rearrange lists this way, because memory latency was a concern even back in the 80s.
If you're using linked lists in a language without a compacting GC, then you almost certainly want something else instead.
If you're using them in a language with one, then you still usually want something else, but at least the cost isn't as high. Also you might be using Haskell or something, where other constraints make data-structures like arrays painful to use.
You can get help from the allocator. For example jemalloc has an experimental API called "batch allocation" where it returns a list of allocations of the same size, and it makes its best effort to make them contiguous (not guaranteed though): https://github.com/jemalloc/jemalloc/blob/12cd13cd418512d9e7...
The idea is that you may have a data structure that you want to be able to modify (in which case you need to free individual nodes) but in most cases you do not.
Then you could use batch allocation, and pair it with this optimization.
It's extremely common in Lisp. Linked lists are the natural data structure of Lisp and in most modern programs they rarely get modified. Common Lisp provides vectors for greater efficiency but they might be less necessary in many programs if this trick works.
Comments
How realistic is it to have a linked list in contiguous memory that stays nicely ordered? In my experience, lists are normally cobbled together with nodes that are allocated widely separated in time and hence I have no knowledge that I can use to predict the address of the next pointer.
If you're in a scenario where this optimization works, it seems like it would be better to just use an array.
Are you familiar with Donald Knuth's "Dancing Links" ??
Its a covering-problem solver (NP-complete) that uses linked lists highly-efficiently. All nodes are "statically allocated" (at least, with respect to the algorithm), because the covering-problem takes up a constant amount of space.
The linked-list "Dances", pointing at other nodes to represent which combination of covers are attempted. So any link could potentially point to any other link later in its list. However, the number of nodes themselves is constant and set before the algorithm runs.
As such, the linked-list is fully X1->X2->X3->X4... at the start of the algorithm. (where X1, X2, X3 are contiguously allocated in memory). If X3 is proven to "not be a good guess" for our covering problem, then it is cut out of the linked list (X1->X2->X4).
All links remain in order, and are ordered on a 2-dimensions (So not only X1->X2->X3... but also X1->Y1->Z1...). Where X, Y and Z are the compound-elements trying to cover locations 1, 2, 3, ...
------------
Most simple malloc implementations also have the free-list as a simple linked-list that is in fact, ordered in memory. (The first node in the free-list is the lowest numbered RAM spot, while the final node in the free-list is in the highest-numbered RAM spot).
The FAT32 linked-list across a hard drive is also nicely ordered (and when it isn't, the user will perform "defragmentation" to reorder the list and optimize the hard drive).
-----------
IMO, the "nicely ordered Linked List" is uncommon, but... common enough that its worth discussion. And sure, maybe we don't use FAT32 filesystems today very often, but that's the technology I used growing up lol. I know the methodology works!!
I think you need to be aware of why such an implementation (fat32) had to exist. As I believe (I also grew up with fat32) that it basically vanished when HDDs with caches in the MB started to show up. Journaling became a thing; actual caches became a thing so the HDD could actually lay things out well by utilizing said cache.
NTFS still needed to occasionally be defragmented but it allocated more of a buffer to prevent having to do so at all.
I think; in general; You're very spot on about utilizing continuous arrays of memory for linked lists as they will almost always result in better performance characteristic (unless you really need insertion/removal in order and it's very write heavy).
It's fairly standard for a compacting GC to rearrange lists this way, because memory latency was a concern even back in the 80s.
If you're using linked lists in a language without a compacting GC, then you almost certainly want something else instead.
If you're using them in a language with one, then you still usually want something else, but at least the cost isn't as high. Also you might be using Haskell or something, where other constraints make data-structures like arrays painful to use.
You can get help from the allocator. For example jemalloc has an experimental API called "batch allocation" where it returns a list of allocations of the same size, and it makes its best effort to make them contiguous (not guaranteed though): https://github.com/jemalloc/jemalloc/blob/12cd13cd418512d9e7...
The idea is that you may have a data structure that you want to be able to modify (in which case you need to free individual nodes) but in most cases you do not.
Then you could use batch allocation, and pair it with this optimization.
That depends on the allocator you use. If you allocate your nodes from an arena that belong to the list, the resulting layout is usually pretty good.
It's extremely common in Lisp. Linked lists are the natural data structure of Lisp and in most modern programs they rarely get modified. Common Lisp provides vectors for greater efficiency but they might be less necessary in many programs if this trick works.
That's a very good use case. I wonder if a good CL compiler would be able to convert many of these lists to arrays anyway.