Hacker News Reader

Hacker News

Comment by dragontamer | Hacker News Reader

Parent Full thread

dragontamer

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.

View on HN

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.

Reply on news.ycombinator.com