Hacker News Reader

Comment by rsp1984 | Hacker News Reader

rsp1984

Lessons from high-performance / embedded development: If you know the size of your data beforehand, or can at least put a bound on it, it's best to pre-allocate your memory and then hand out bits as needed through a custom allocator working on the pre-allocated set. That way you have only a single allocation and all your data is contiguous in memory (huge deal for cache coherency and therefore speed of access). Very easy to put a vector/ArrayList -type interface on top of this.

If you don't know the size or bound, then do the next best thing and pre-allocate in chunks and use a slightly more sophisticated allocator that manages the chunks to hand out bits.

Not sure what mechanisms high-level languages use these days and whether there's any pre-allocation involved under the hood, but plain unoptimized linked lists can fragment your memory pretty badly and they also aren't cache coherent. Use them to store small #s of large objects, instead of large #s of small objects.

View on HN

Most GC languages use bump-pointer allocation and/or compacting garbage collection to (try to) ensure that objects are stored in memory in this way regardless of being dynamically allocated.

This means that even naive linked list implementations are typically much more cache efficient than you would expect coming from C, at least after a GC pass. It also means though that changes to the dependency graph of your program can have unexpected effects for your cache hit rates, since the compacting heuristics are pretty simple (they typically work by copying "child" objects immediately after the "parent" object, but there is no mechanism to define the "right" parent for an object)

I've seen a Linked List get allocated very contiguously at times in .NET when it is just a toy program, like just benchmarking linkedlist performance, it sometimes does really well. But in the context of a big running program with other things in the heap it is much less likely to work out so well.

In most GCs the mark phase also disrupts the cache by doing what looks a lot like a table scan. That’s one of the reasons for generational collectors. Better cache locality.

Even if you have a bump allocator, the fact is that a linked list requires storage for the pointers, which are not needed in an array. That makes the list bigger, and bigger means worse from a caching point of view. Fewer parts of a linked list fit into a cache line and so on.

Plus the pointer traversals are dependent loads. Until we load node->next, we don't know what address that is, so we cannot pre-fetch node->next->anything.

But when we access array[i], it's possible to pre-fetch array[i+1].

I'm still using linked lists because of the flexibility, functional substructure sharing and allocations you can avoid, but let's not kid ourselves.

Absolutely, I'm not claiming linked lists are "better" than arrays. The GP was mentioning memory fragmentation and cache behavior, and I was pointing out that GCs can, at least in some conditions, make linked lists more efficient then they are in C (comparing naive implementations).

But yes, linked lists are almost always worse than arrays, unless you're doing huge amounts of add/remove on large amounts of data.

And if your data is truly contiguous and its struct of arrays instead of the other way around, SIMD becomes much more usable.

Modern memory allocators like tcmalloc are pretty good with putting structs of the same size in contiguous areas of the heap. For smaller structs (which most real world cases fall under), it's just one lookup to find the next place to put the new object. So, C and Java will have similar performance for allocating a lot of small objects, I think. There's probably a difference on the deallocation side, especially with fragmentation, but I'm not as knowledgeable about that. If someone has a richer explanation, I'd love to hear.

As someone who worked on memory allocators in a past life: cosign. Size-class based allocation for small objects is how modern memory allocators have worked for a long time now. I'm genuinely baffled by how many people think that the bump-pointer allocation for same-sized objects is unique to garbage collection.

Thanks for confirming this. Do you have an idea of how modern allocators compare with generational GCs on the cleanup / realloc / fragmentation side?

No, and that would make a great empirical study. (Maybe there has been one! I should check ISMM over the past decade, someone may have done it already.)

From first principles, the biggest difference is that manual memory allocation can't move live objects around. But manual memory managers do still have the ability to be smart on deallocation, to the point that calling free will sometimes cause things to happen that would be similar in a garbage collector.

I think the term you're looking for is cache locality. Cache coherence is about ensuring that caches local to different cores see the same values for any one given chunk of memory.

It seems to be a very common mistake. Understandable as they are somewhat related as bad cache locality can cause unneeded coherency protocol traffic.

Of course locality is important even on single core cpus with no need for coherency.

Doesn't even malloc do this under the hood by only occasionally calling sbrk and otherwise handing out blocks from an internally managed contiguous region?

What's the point of doing this again, manually? Or am I mistaken in my memory of the common modern malloc implementations?

It can be an order of magnitude faster to do it yourself, depending on how balled up the runtime library has gotten. If you can make some simple guarantees like "I'll realloc similar sized blocks mostly" and "I'm single-threaded thru these calls" then you can drop the bulk of the runtime drama.

What's the point of buying a jeep wrangler (or a ferrari), when you already have a subaru? Don't they all have 4 wheels?

General purpose tools are good for most cases. And being widely available they are cheaper too. Sometimes, however, you can do a better job with something special purpose tuned to the exact task at hand, but you have to buy the special purpose tool. The question is not IF it's better the question is whether it's worth the cost to you.

here are some things malloc can't do (afaik): - different pools for different parts (threads / datastructures / etc) of your app - better control over data locality - real time / non blocking allocations (i.e. low latency audio applications) - querying remaining available memory - releasing entire pools with a single call

Often, yes, you're better off just using the general purpose memory allocator.

I think the replies to your comment are unfairly giving you a hard time. Modern memory allocators are quite good. Before spending the time to roll your own allocation strategy, first do the experiments and analysis to convince yourself that memory allocation is even a performance problem. Once you've done that, do some work to implement a naive allocation strategy yourself and compare it against the standard allocator. If you're not outperforming it by a lot, work on it for a week. If after that week you're still not outperforming the standard allocator by a lot, just use the standard allocator.

Yes, sometimes optimizing for your exact use case can yield performance benefits. Buuuuuut... the chances that your use case actually falls out of what the general allocators have been designed for is small. And the people implementing the general purpose allocators are really good. They've optimized things you're not even aware of yet.

One random tidbit actually in favor of doing your own allocation: malloc and free are (in most compilers, I believe) always going to be function calls. Sometimes the benefit you get from rolling your own is just the benefit of eliminating a function call and inlining allocation code. ¯\_(ツ)_/¯

malloc aligns very conservatively (because it doesn't know the size of the data you're allocating for), so there are some space gains to be had there.

AFAIK also malloc will call sbrk quite a lot, at least from my cursory reading of this musl implementation[0].

[0] https://git.musl-libc.org/cgit/musl/tree/src/malloc/malloc.c...

That doesn't contain calls to sbrk at all, it maps memory in with mmap which is typical of every modern memory allocator.

It uses both brk/sbrk ("__brk()" in that code) and mmap, the latter for allocating larger bits of memory. GNU libc does the same thing from what I remember from straces.

You're right, I misinterpreted the calls to __brk

> Lessons from embedded development

Frequently you're working with hardware, devices, etc of which there's a limited number. I don't need a linked list to hold data for 3 peripherals. Even if the hardware is changed and the number changes and there's 10 peripherals I don't need a linked list. Sometimes an array is just fine.

I usually end up with a singly linked list when implementing a singleton API that needs to support an arbitrary number of application created objects. Rather than have the singleton pre-allocate the memory, the application has to do it, then pass it into the API to use for the lifetime of the program. The various parts of the application knows how many objects it needs, and can statically allocate just the right amount of memory.

Why can't we have this as a general interface in standard libraries? For example, we could have a contextual allocation function:

  // Contiguous array of 1024 objects of type
  context = contextual_allocation(1024, sizeof type);

  // obtain pointer to next free object 
  object = allocate(context);

This is called arena allocation, and there are many implementations of the concept.

For example, the C++ Protocol Buffers library has an Arena class, which is documented here: https://developers.google.com/protocol-buffers/docs/referenc...

The EA STL has fixed_allocator, which implements a similar concept while exposing more low-level details in the API: https://github.com/electronicarts/EASTL/blob/master/include/...

I'd describe it more as a pool or block allocator.

An arena allocator is specifically optimized for incremental allocation and then bulk deallocation (the entire arena is freed at once).

The example code instead appears to create a context of a number of fixed sized blocks. Because of the fixed size, the allocator can make a lot of simplifying assumptions and generally achieve constant time algorithmic complexity, while allowing for individual allocations to be freed and reused.

Zig requires the allocator to be specified for each allocation: https://ziglang.org/documentation/0.5.0/#Memory

This has a huge impact on the API design, so I don't think this can be retrofit in standard libraries of existing languages (because of backwards compatibility).

In the mid 00s, my advisor had me explore the concept of adding default parameters to C++ functions where the default snagged the nearest lexically scoped named object of the right type from the calling environment, i.e.,

    int someFunctionThatAllocates(int A, int B, allocator const& alloc = default);

Then in the calling environments:

    {
        auto& alloc = james;
        if (someFunctionThatAllocates(4, 5)) // ok, uses 'alloc'
        {
        }
    }
    {
        if (someFunctionThatAllocates(4, 5, james)) // ok, uses 'james'
        {
        }
    }
    {
        auto& alloc1 = james;
        if (someFunctionThatAllocates(4, 5)) // error: no `alloc` in scope
        {
        }
    }

It handily solves a number of problems. In particular, we were looking at how we manage heap allocation for large sparse matrix libraries a la MTL4.

Interesting. Isn't this this vaguely reminiscent of implicits in Scala?

Yep; Martin suggested it to us; he said the ergonomics were good.

It's called implicits in Scala

For an overview of how Zig does this and at the same time a nice overview on different types of allocators:

What's a Memory Allocator Anyway? by Benjamin Feng

https://www.youtube.com/watch?v=vHWiDx_l4V0

The obstack api in glibc is exactly this https://www.gnu.org/software/libc/manual/html_node/Obstacks....

I believe this is how Zig works. Specifically the FixedBufferAllocator. It can further be paired with the ArenaAllocator to make management dead simple.

I remember seeing a sizable astrophysics Fortran program from many decades prior that had one "MEMORY" array declared at the beginning of the program and legit used it for every single byte of memory for the entire program. It was nuts

The same goes for the AMBER computational chemistry FORTRAN program. The array is called X.

Actually, that might be what I'm thinking of. For some strange reason (this was in 2013, mind you) I was involved with translating legacy Fortran projects for multiple departments.

This is also how the TeX program works. Of course it has lots of variables (hundreds of "global" variables in fact), but for everything whose size may vary (boxes, lists of characters, lists of tokens for macros, …), it has two giant arrays of fixed size, one called “str” (aka the string pool, used for strings), and one called “mem” (used for everything else). It's this way partly because of the limitations of Pascal at the time.

TEKTON, a crater modeling code, had this, but I think it called the array 'a'.

the SOP with C++ is you overload the new and delete operators and implement your own heap.

It can be very handy especially when you add tags to your allocation so you can track the number of allocations from a specific piece of code, great for finding memory leaks.

You're talking about arenas, right? https://en.wikipedia.org/wiki/Region-based_memory_management

I think for C++ vector, when current underlying array gets filled, the common strategy is allocate a new array double the size of the current one, and copy contents over to that.

But if you expect an upper bound of the required size of that stay, it may be worthwhile to explicitly set the capacity of the vector to avoid these reallocations.

That's exactly the purpose of std::vector's “reserve“ method, btw.

I once worked with a C++ text processing library that saw more than a 50% throughput bump just from reserve()’ing std::string and std::vector space in hot code paths.

same in C# for list

I think this is the solution used in FreeRTOS if you use heap1 as allocator.

In Julia if you have an estimate of the size (not necessarily a hard bound) you can `sizehint!` to reduce the number of allocations.

> it's best to pre-allocate your memory and then hand out bits as needed through a custom allocator working on the pre-allocated set.

Yes. For linked lists this would typically mean creating a pool of objects to be allocated from the pool and returned to the pool as needed for operating the linked list.

On the contrary: small objects mean that fragmentation is NOT a problem: because your small nodes can be "fit anywhere". Furthermore, if you've got 1000x 8-sized allocations, any of those "holes" can be repurposed for other 8-sized allocations.

Meaning: linked lists innately make most simple allocators more efficient.

Linked lists are a tradeoff between the difficulty of malloc/free (of which arrays are very difficult), and latency (of which linked lists have much higher latency).

A ton of 8-sized allocations is better on fragmentation than a 8-sized / 16-sized / 32-sized ... allocation pattern that most arary-allocators use.

But then your objects are scattered all over the address space, which means that objects you’re accessing in sequence are unlikely to be in the same cache line, so you pay a cache miss on every single access.

Having (maybe?) more efficient malloc/free in exchange for dramatically increasing the cost of accessing your data is not a good trade-off for most access patterns.

See Chandler Carruth’s talk from CppCon 2014: https://youtu.be/fHNmRkzxHWs?t=2085

But the entire point of linked lists is to insert in the middle in constant time.

1 -> 2 -> 3 -> 4

Can become...

1 -> 2 -> 2.5 -> 3 -> 4

If you do that with arrays, you need a O(n) memcpy and maybe even a realloc.

-----------

Furthermore, linked lists don't even need a malloc routine !!!!!! See Knuth's dancing links (DXL) algorithm.

The ability to efficiently add and remove nodes from a linked list (even if that list was statically allocated) can sometimes beat the performance of arrays, because memcpy is just asymptotically slower than insert / remove.

Yes, but if you actually measure some scenarios, it is usually overall faster to pay the cost of O(1) copy. This of course depends on how often you insert things into the middle, vs how often you iterate over the collection. But on a modern computer it is surprising how big that ratio needs to be! In Knuths prime this tradeoff didn't really exist, because memory accesses were about at the same speed as executing an instruction, rather than ~200 times slower.

Knuth's Dancing Links is originally from 2001, and was first published to book form in Fasicle 6 (2019).

Dancing Links seems to have outstanding performance for a generic cover problem, even on modern cache heavy processors.

It seems like the static layout of the links benefits greatly from cache locality. Seriously, study the algorithm before hating on it.

EDIT: Knuth's original writing style may be "too mathematical" for some. Here's a dumbed down version: https://medium.com/javarevisited/building-a-sudoku-solver-in...

The original Knuth: https://arxiv.org/abs/cs/0011047

The 2001 code is suboptimal in a few ways compared to the more recent updates. Knuth discusses the updates in Fasicle 6, the cweb source code is: https://www-cs-faculty.stanford.edu/~knuth/programs/dlx1.w

-------------------

EDIT: But... I hate it when people tell me to read other papers without pointing out the issue. :-)

The specific issue is that in Dancing Links: 1 -> 2 -> 3 becomes 1->3, and then later becomes 1 -> 2 -> 3 again. This pattern of insert (and then un-insert at the same place) means that all linked-list operations will execute in L1 cache.

Furthermore, Knuth lays out the data such that 1, 2, and 3 are sequential in memory. So the entire process is incredibly cache-efficient and takes advantage of both temporal and spatial locality. (Because 1 usually inserts / removes 2, and because 1 and 2 are always next to each other in memory, you're never leaving L1 cache).

As such, all DXL-operations are outstandingly fast. Furthermore, the pattern of insert-uninsert is useful for Exact Cover (which Knuth then used to solve graph coloring, N-Queens, Sudoku, and other NP-complete problems at relatively high speed). No, its not a generic SAT solver, but it does pretty darn good, especially considering how simple the operations are.

>, you need a O(1) memcpy

I didn't downvote your comments but memcpy is O(n) instead of O(1) : https://stackoverflow.com/questions/362760/how-do-realloc-an...

I'll delete this reply if you meant something else.

Ah jeez. That's what I get for typing fast.

Yeah, I mean O(1) insert / remove for linked lists, and O(n) memcpys (most array insert / remove operations)

EDIT: I've edited my post above. I think its correct now. Thanks for pointing out the error.

In most real world problems, you don't really care about keeping a data structure sorted at all time. All you want, is to have it sorted when you're about to do X. So it's generally faster to just have a contiguous chunk, insert at the end, then sort when you need.

Sorted linked lists are also especially-not-useful, because you can’t binary search them, which is often the main benefit to having something sorted.

The only thing a sorted linked list is really good for is being able to cheaply peek/pop the lowest- or highest-valued item, and a heap is almost always better for that use-case in practice.

> The only thing a sorted linked list is really good for is being able to cheaply peek/pop the lowest- or highest-valued item, and a heap is almost always better for that use-case in practice.

Or cheaply peek/pop the middle items, and reinsert a middle item. As is the most common operation in Knuth's solution to the exact cover problem (aka: Dancing Links / Algorithm X)

There's also benefits to middle-operations, such as text editing (although text files are so small that inefficient operations aren't a big deal anymore).

----------

Linked Lists also can be "merged" together, in a sort of "inverse tree" sort of way.

Consider the following data: "ABCDEFG", "123ABCDEFG", and "111ABCDEFG".

The two array representations are obvious. But Linked-Lists can optimize that into:

* A -> B -> C -> D -> E -> F -> G

* 1 -> 1 -> 1 -> A ...

* 1 -> 2 -> 3 -> A ...

This has come up a lot for me in a recent toy problem I've been working on. A lot of sub-lists happen to be have the same "ending" as other lists, so I'm merging the linked lists and saving precious RAM (I'm building up GBs of data: so saving redundant chunks like this really wins)

> There's also benefits to middle-operations, such as text editing (although text files are so small that inefficient operations aren't a big deal anymore).

Applications operating on text would normally use a rope (aka cord) or gap buffer. A linked list would have horrible performance because random access within the text is important for most applications.

> (I'm building up GBs of data: so saving redundant chunks like this really wins)

You’re likely spending a huge amount of memory to store pointers between elements within the unshared chunks (8 or 16 extra bytes per element adds up in a hurry) so it may be worth investigating some “chunking” so that you only have to use pointers to link between chunks, which can be stored continuously.

Alternatively, consider whether the index representation used by suffix arrays will work for your use-case: https://en.wikipedia.org/wiki/Suffix_array

Gap buffer is very good.

> You’re likely spending a huge amount of memory to store pointers between elements within the unshared chunks (8 or 16 extra bytes per element adds up in a hurry) so it may be worth investigating some “chunking” so that you only have to use pointers to link between chunks, which can be stored continuously.

Yeah, they're chunked or unrolled in practice. (Unrolled Linked List was one term I've seen. Chunking is also another term).

> Alternatively, consider whether the index representation used by suffix arrays will work for your use-case: https://en.wikipedia.org/wiki/Suffix_array

Haven't heard of these before. But I'll look into it.

EDIT: Its... kind of a complicated situation I'm in. I'm basically searching a game tree, and building a "linked list" for how the children relate to their parent. I need "breadcrumbs" to relate any position back to the root.

Not necessarily because I need the root, but because the root contains information that's relevant to all of its children. So a linked list of (Grandchild -> child -> root) is very natural for this application. I originally had an array and just copied the data to an array (for "more locality") to all the children. But this uses way more space.

And the depth of this tree is ~12+, exponentially increasing width as usual. You really don't want to copy the root's data to all of the children unnecessarily: even on a GPU, its far better to just pass a pointer and connect the children-to-parent relationships, and traverse the linked list.

Hooking "child.parent = parent" is very easy. And traversing the while(node != root) node = node.parent; loop is also easy as cake. There's only ~12 of these linked-list operations in practice (because the depth of the search tree only goes to ~12 deep or so), across literally billions of possibilities. The billions of possibilities lead to the ability to process the tree in parallel (billions of possibilities to search with "only" 16384 hardware threads suddenly makes the GPU seem small!)

Despite the linked-list in the algorithm, its clear to me that the GPU is the ideal architecture for processing all of these nodes in parallel.

And ironically, that's when we get into fragmentation issues for arrays!

Growing the array from size 8 -> 16 -> 32 -> 64 ... 1024->2048 makes it harder, and harder to find contiguous, exponentially growing chunks.

If you have a fragmented memory allocator, you may run out of memory due to fragmentation. In contrast, if each of those elements were a small and constant-sized 8-byte chunk (or 16-byte chunk), then you'd be able to fit that small chunk anywhere.

-----------------

Anyway, I agree with you that vector.push_back() is an outstanding methodology on modern systems. But Linked-Lists aren't as bad as people make them out to be.

What environment are you working in where this is a problem in practice?

In tiny embedded devices with very limited memory, you do all your allocation at startup and avoid malloc during runtime, so you’d never run into this.

On server, desktop, or even smartphone applications, I’ve never run into cases where “the allocator was unable to get a chunk of memory to complete a vector resize()” is a significant problem. If my vector is going to be a significant fraction of the memory available on the system, I generally know that up-front, and would just call reserve() with a conservative estimate of the upper-found size. That’s pretty rare though - not many problems call for vectors that are 1+ GB in size. For anything that’s not a significant fraction of the system’s available memory, the allocator can generally find you a chunk.

I've been experimenting with data-structures on GPUs. 8GBs of RAM to share across 4096 SIMD-cores (well... 64 "compute units" with 64-way SIMD... you know...). But Vega64 runs 4-threads per SIMD-core, so you actually need 16384-SIMD threads before you utilize the processor. (And at occupancy 10, you have 10-threads per hardware thread, or 163840 SIMD-threads total)

Anyway, you run out of RAM really, really quickly if you try to give data-structures to each of those SIMD individually. 8GBs RAM / 16384-GPU-threads is 500kB per GPU-thread... 50kB at the theoretical max occupancy 10.

Yeah, you want your data-structures to be read-mostly so that your 16384-threads can all be reading the same stuff. But every now and then, you need a per-GPU-thread data-structure. And... well... there's not a lot of per-GPU-thread data available (because you have so many darn threads...)

--------

You end up using Linked lists, even though GPU latency is wtf terrible. Like really, really, really bad. If you think a CPU's 50-nanosecond DDR4 access time is slow, try 500ns or even 1000ns for a linked-list "node = node->next" operation on GPUs. And GPUs are in-order too, so no out-of-order latency hiding for you...

Not sure what GPU algorithms you’re trying to implement, but linked lists (and generally anything with pointer-chasing) are almost maximally terrible on GPUs - they are really not designed for that.

> (and generally anything with pointer-chasing)

You mean like... going through a BVH tree to find what AABB bounding box collides with a ray? :-) I'm pretty sure its been demonstrated that GPUs are fastest at that.

Yeah, I know that linked lists take a latency hit. But even with that big hit, O(1) operations vs O(n) adds up. Don't avoid linked-lists, trees, or graphs just because you're trapped thinking about cache-locality or whatever.

A win in asymptotic complexity (especially O(1) vs O(n)) is utterly huge. On the one hand, its common for beginners to overestimate how much this matters. But on the other hand... its an asymptotic win. You gotta give it a shot.

Arrays win in many cases (and more cases in GPUs, because GPUs are worse at pointer chasing than arrays). Still, there are plenty of situations where the linked-list / tree / graph is simply unavoidable. Be it an oct-tree, linked list, or... BVH-tree traversals in Raytracing.

Naive tree traversal on a GPU actually has pretty bad performance, due to execution divergence. It takes a lot of application-specific reframing of the problem to making working with BVH trees efficient: https://developer.nvidia.com/blog/thinking-parallel-part-ii-...

Its not as complicated as it sounds. Stream compaction solves execution divergence. The end. Instead of recursively searching the tree, you select the members of the tree with a child.

No, you can't do naïve recursion for this. GPUs just don't do that very well. But break it up with stream compaction, and everything is cake.

http://www.cse.chalmers.se/~uffe/streamcompaction.pdf

----------

Its not the memory-link latency that gets you here. Its branch divergence. Solve branch divergence, and then you're far faster than a CPU at traversing that BVH tree. Even without Raytracing Hardware. Even with lol 1000ns latency per node = node->next (GPUs turn out to be decent at latency hiding if you up that occupancy a bit... and just double-check on the compiler / assembly language stuff to ensure that the access was rearranged to a sane location).

MSVC STL uses the golden ratio instead of doubling for std::vector allocation which means that you can reuse contiguous runs of previously deallocated chunks to fulfill future allocations, while still meeting the standard asymptotic O(1) bound on push_back.

I believe that GCC's libstdc++ tested the strategy on a set of real programs and didn't measure any actual difference so they still use doubling.

This is extremely poor advice in practice.

Memory mapping, pages and organization of the heap means that allocating as much memory in as few chunks as possible and reusing it if possible stands out when you profile the two different approaches.

Even if tiny chunks are allocated in their own arenas, the overhead of the allocation and dealing with the pointer it returns is still unnecessary compared to just dealing with the numbers on a loop through an array and moving on.

My understanding is that push/pop from the front/back of linked lists are constant time, but that inserts in the middle necessitate looping through the linked list until you get to the correct index, which is a O(n) operation.

> but that inserts in the middle necessitate looping through the linked list until you get to the correct index, which is a O(n) operation.

Not if you save the node you are working on. Inserting (when you have a node) is simply:

    NewNode = malloc(...) or new or something.
    NewNode.next = node.next
    node.next = NewNode

Oh, gotcha; I just meant in the general case.

Everything you mentioned can be done with statically allocated arrays - if you have known bounds - or lists of large arrays, as mentioned before.

Lists will eventually become a problem since your next/prev pointers may not be pointing to adjacent memory positions, now your linear iteration over elements will not be cache friendly. Not only that but you need to retrieve pointers and dereference them, more pressure and worse for the cache again. You also add a "load" dependency between all elements so you can't easily break processing between multiple cores.

Lists may be conceptually elegant but they are not the most suited for performance or efficiency.

> Lists will eventually become a problem since your next/prev pointers may not be pointing to adjacent memory positions

But what if they were pointing to adjacent memory positions in the common case? What if the problem you're suggesting doesn't exist in some circumstances?

Like in Knuth's Dancing Links. The neighbors of links are laid out in memory next to each other. If the list upon program startup is "1 -> 2 -> 3", we know that 1, 2, and 3 are neighbors in memory.

And what if it is demonstrated that this weird "linked list with nodes laid out next to each other" is shown to be sufficient to solve NP-complete problems like the exact-cover problem with great efficiency in practice?

-----------------

What if, when creating 100 nodes at a time, we lay out all 100-nodes in a row.

    chunk = malloc(sizeof(Node) * 100). 

    for(int i=99; i>=0; i--){
        chunk[i].next = head;
        chunk[i].data = foobar();
        head = chunk[i];
    }

Now we have the spatial locality you so desire, while still retaining the ability to rearrange the list. In fact, add/remove is still possible (though the malloc/free is harder to keep track of: if you're in a Dancing-links scenario, you may not ever need to call free)

Perhaps naively, would a struct-of-arrays perform better than an array-of-structs? I imagine that the separate `next` and `data` arrays might be packed better, and instead of processing one cache line at a time, you could load two cache lines simultaneously to process double the sequential data with every round-trip to RAM.

More to the point of the discussion, it seems to me that you're describing situations where the cells of your container do have a natural inherent order, but may have additional relationships imposed on top of them. In the case of Algorithm X, the matrix has an inherent, consistent sense of order across rows and columns, but any particular line may skip elements depending on the state of the algorithm.

I think that doubly-layered structure is important to recognize; it's not something all data will have, and it's an inherent property of the problem or domain, not of the linked list data structure itself.

Hmm. Good thoughts.

I'd like to respond more deeply but I'm not sure what to say, lol. You've just got a good post here so I feel like I should acknowledge it.

I mentioned 3 points, you addressed one for a very specific scenario. In any case, even if you say your list has adjacent elements, the other two points still apply.

I don't know why you keep bringing this algorithm to the discussion, everything that was mentioned applies to any linked list. It's a fundamental property of linked lists, period.

Seems like you're completely missing the point: the discussion started on performance properties of data structures. That's what's being pointed out, and it's going to be a fact regardless of how you want to apply it.

I can address the other point too.

> You also add a "load" dependency between all elements so you can't easily break processing between multiple cores.

You might be surprised.

Lets say we have that Node arrayOfNodes[100]. However, we do not know which node is the beginning, the end, which nodes are in the array, or which ones have been erased.

You might think that its an innately sequential algorithm to discover all the nodes in the array as well as its length. You'd be wrong: its a parallel algorithm, called Pointer Jumping.

https://en.wikipedia.org/wiki/Pointer_jumping

This "Pointer Jumping" methodology can be implemented on a GPU with high degrees of parallelism (one GPU-core per node), as long as you have enough nodes. In this arrayOfNodes[100] example, the parallelism is at best 100 (for example).

We can even perform order-dependent operations such as "prefix sum" over the arrayOfNodes, in parallel, while we are discovering the order of the nodes thanks to Pointer jumping. So in fact: it is very possible to operate linked lists in parallel (even SIMD / GPU parallel).

No, its not how the typical programmer traverses a linked list. But its a good trick for speeding things up in some circumstances.

A great example of pointer jumping is in the paper "Data Parallel Algorithms" by Hillis and Steele.

-----------

I'm not sure what your "3rd point" is. I only count two points.

> the discussion started on performance properties of data structure

The root of the discussion is a linked-list discussion. The literal text of the submission and title is: "Drop millions of allocations by using a linked list"

The point I make is that there's a great many tricks of Linked Lists that typical programmers don't seem to know about that mitigate the common complaints of linked-lists.

Reply on news.ycombinator.com