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)

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.

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

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.

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

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

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

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. ¯\_(ツ)_/¯

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

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.

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

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

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

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.

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

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

    {
        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
        {
        }
    }

What's a Memory Allocator Anyway? by Benjamin Feng

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

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.

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.

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.

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

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.

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.

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.

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.

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)

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

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

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.

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.

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

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.

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

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.

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.

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

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.

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];
    }

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.

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

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