Intrusive linked lists (2019) • Hacker News Board

Re: Intrusive linked lists (2019)

#71

Post by el_pollo_diablo » Fri, Sep 04, 2026, 7:22 AM UTC

Joker_vD wrote: post #67

el_pollo_diablo wrote: post #42

Earlier quoted context omitted.

> It does matter, for malloc-returned storage. You can put whatever objects you want into that storage as long as it fits and the pointer is properly aligned. You can certainly store an object of arbitrary type, but here it is done through a pointer to an object with pointer arithmetic going beyond the allowed bounds. > memcpy takes a void pointer as its destination, sets the effective type of the storage behind it A…

> but here it is done through a pointer to an object with pointer arithmetic going beyond the allowed bounds. When you do "void *x = malloc(sizeof(struct node))", the returned storage doesn't have struct node object in it, it has an object of no effective type in it, with size "sizeof(struct node)". Taking the pointer to payload[] field is in no way different from doing "(char*) x + offsetof(struct node, payload)" —…

> Taking the pointer to payload[] field is in no way different from doing "(char*) x + offsetof(struct node, payload)"

It may differ, depending on the precise notion of provenance being applicable. If provenance only has allocation granularity, I suppose that there is no difference. I know that there were some discussions about provenance and subobjects. I do not know whether the question is resolved.

Where this gets complicated is that zero-sized arrays are non-standard. So even if we could build a convincing argument from standard notions of provenance, how would it transfer to a subobject that is excluded from the standard?

Last but not least, this is not only about creating the effective type through memcpy. The question is also whether this destroys the effective type of the structure. See my previous point about possible padding after 'payload'.

Please also consider that flexible array members are here for a reason. If I follow your argument, then they bring nothing that arrays of length 0 or 1 do not already cover.

Re: Intrusive linked lists (2019)

#72

Post by el_pollo_diablo » Fri, Sep 04, 2026, 7:31 AM UTC

Joker_vD wrote: post #66

el_pollo_diablo wrote: post #53

Earlier quoted context omitted.

We mean compatible as defined by the C language standard. It is much more restrictive than having the same layout. In particular, you may not pass a pointer to a type where a pointer to an incompatible type is expected, even if the types have the same layout, which prevents the sort of sharing between two libraries that is being discussed. Moreover, there is no guarantee that two distinct structure types with the sam…

Furthermore, two structure, union, or enumerated types declared in separate translation units are compatible in the following cases: — both are declared without tags and they fulfill the preceding requirements; the preceding requirements being — there shall be a one-to-one correspondence between their members such that each pair of corresponding members are declared with compatible types; — if one member of the pair…

> declared in separate translation units

Now if I include both library headers in code that attempts to plug them together, the types will be incompatible.

Although not a proof in itself, GCC and Clang seem to agree: https://godbolt.org/z/1ocr5Go5b.

Re: Intrusive linked lists (2019)

#73

Post by max_k » Fri, Sep 04, 2026, 3:43 PM UTC

flohofwoe wrote: post #70

zahlman wrote: post #47

Is this sort of thing no longer part of a standard computer science or software engineering undergrad curriculum?

When did you last encounter or use a linked list ? :) Linked lists fell out of fashion once the cpu/memory latency gap opened up towards the end of the 1990s. For most use cases it's simply better to use a tightly packed array, even use cases where linked lists would intuitively make more sense.

Every day, all day. It is a myth that linked lists fell out of fashion.

Of course, "it depends". There are things that better live in tightly-packed arrays (large lists of free-standing objects), but there are things that are almost impossible without linked lists. In these cases, being "intrusive" has massive advantages.

I guess you can spend an entire coder career without having to use linked lists, and then you cannot imagine why anybody would ever use them (and make it a meme). The linked lists that do exist in your programs may be abstracted away from your visibility.

Therefore: sure, an article about linked lists will spawn numerous HN comments from such coders who don't know the shoulders they're standing on. It's linked lists all the way down... below the flat surface of high-level frameworks.

Re: Intrusive linked lists (2019)

#74

Post by uecker » Fri, Sep 04, 2026, 3:49 PM UTC

Joker_vD wrote: post #69

uecker wrote: post #68

Earlier quoted context omitted.

No, you are right, but it is not "in separate files" but "translation units". Two distinct list(int) from two different libraries need to be compatible when used together, which means you would include the header of those two libraries and then both end up in the same translation unit. C23 relaxed requirements for types with tag, this works for structures with tag, but for type generic structures you then need to syn…

I don't think that's the scenario the other commenter was talking about: > there is no centralized monomorphization. If an application uses two libraries, each of which handles lists of int, each library will have to independently macro-generate its separate list implementation, and because C's type system is nominal, the generated types will be isomorphic but incompatible. So, lib_a.c includes header_only_list.h, an…

But "the generated types will be isomorphic but incompatible" is right. It is ok if you have lib_a.c and lib_b.c because these are two separate translation units. But this only works if both of these libraries use the list type internally and pass the pointer to each other as a void pointer. The moment you have two headers lib_a.h lib_b.h both including header_only_list.h and defining an API using a generic type list(int) and where you then try to also include lib_b.h from lib_a.c it does not work.

Re: Intrusive linked lists (2019)

#75

Post by max_k » Fri, Sep 04, 2026, 3:51 PM UTC

cryptonector wrote: post #61

Doubly-linked lists -all data structures that have back pointers- are really difficult to mutate thread-safely.

Difficult compared to what?

Mutating a std::vector is much more difficult because you need a coarse lock and serialize every access with it - there's no other option. Linked lists, on the other hand, can be made thread-safe with a single coarse lock, or many finer-grained locks, or atomics, or fancier tricks like RCU.

All of that is difficult, sure, but what is less difficult than thread-safe linked lists?

Re: Intrusive linked lists (2019)

#76

Post by zahlman » Fri, Sep 04, 2026, 10:23 PM UTC

flohofwoe wrote: post #70

zahlman wrote: post #47

Is this sort of thing no longer part of a standard computer science or software engineering undergrad curriculum?

When did you last encounter or use a linked list ? :) Linked lists fell out of fashion once the cpu/memory latency gap opened up towards the end of the 1990s. For most use cases it's simply better to use a tightly packed array, even use cases where linked lists would intuitively make more sense.

Anything where you use a state machine that has to remember the parent state is effectively an intrusive linked list (even if they rarely have more than two elements); similarly the most obvious implementation of undo/redo. In these uses it's less complex and more understandable than having an explicit container, and constant-factor performance is irrelevant since we're talking about spending a few clock cycles to retrieve information in response to a human-speed GUI interaction.

You might also note that TFA is much more recent than "the end of the 1990s" and describes one of the most important software systems out there, which to the best of my knowledge still uses these techniques in the same way.

Re: Intrusive linked lists (2019)

#77

Post by afdbcreid » Sat, Sep 05, 2026, 5:18 PM UTC

amelius wrote: post #58

afdbcreid wrote: post #52

Earlier quoted context omitted.

Easy. https://docs.rs/intrusive-collections .

Importing a library does not count. (Besides, perhaps you can tell but I don't even know if the library uses safe Rust internally.)

Internally? No. Externally? Yes. That is the point.

Re: Intrusive linked lists (2019)

#78

Post by afdbcreid » Sat, Sep 05, 2026, 5:19 PM UTC

cryptonector wrote: post #62

afdbcreid wrote: post #52

Earlier quoted context omitted.

Easy. https://docs.rs/intrusive-collections .

The issue is that back-links in data structures are inherently difficult to handle a thread-safe way in mutators.

Not more than regular collections (unless you mean working on different parts with different threads, then it's still possible but harder, just like with regular collections).

Re: Intrusive linked lists (2019)

#79

Post by cben » Mon, Sep 07, 2026, 7:40 PM UTC

dahart wrote: post #13

klps10 wrote: post #3

I think this article rewrites history and it is unfortunately already cited by the clankers. "Intrusive" is C++ speak. The regular linked lists always had embedded data or a mix of embedded data and pointers to outside data in a C struct.

I googled it and got the response that Bjarne Stroustrup first used “intrusive” in his 1985 C++ book. He was adding a new distinction between the older intrusive kind and the new ‘non-intrusive’ kind, because some people had started using C++ to allocate the list nodes and the payload structs separately. Now with std::list and college classes often teaching non-intrusive linked lists, and intrusive lists only being u…

> benefits of abstracting and separating node types from payloads

If you mean being able to a generic `list` type (whether by C++ templates, macros, or good old void* casts), it's more than that. The benefit of non-intrusive is being able to create/manipulate/pass around multiple collections pointing to same payloads, without disturbing the payloads or the other collections in any way¹. That makes it easier to return and manipulate collections functionally (both in the narrow immutable sense, but also in the wider "treat collections like _values_ sense)... The deepest benefit arising from that I suppose is code modularity: different code areas need not be aware of each other's existence.

That all obviously comes at some tradeoff to performance. By definition, not having a full picture of the pathways your data travels means you can't choose the fastest representation!

¹The cheat is GC. For multiple unconnected collections to point to same payload, you need ref counting, or mark&sweep or similar to control its lifetime. Technically, GC does disturb the objects it's tracking (though that's well abstracted from other code).

However, you're largely right that specifically linked lists are rarely a good choice for non-intrusive collections => Arrays usually beat them, and if not then hash sets. (LISP & ML & Haskell do stick to lists for tail sharing — a choice which is arguably outdated by growing CPU / mem random access gap. I suppose Clojure's persistent vectors are an improvement.)

Re: Intrusive linked lists (2019)

#80

Post by cryptonector » Wed, Sep 09, 2026, 3:11 AM UTC

max_k wrote: post #75

cryptonector wrote: post #61

Doubly-linked lists -all data structures that have back pointers- are really difficult to mutate thread-safely.

Difficult compared to what? Mutating a std::vector is much more difficult because you need a coarse lock and serialize every access with it - there's no other option. Linked lists, on the other hand, can be made thread-safe with a single coarse lock, or many finer-grained locks, or atomics, or fancier tricks like RCU. All of that is difficult, sure, but what is less difficult than thread-safe linked lists?

Difficult to do thread-safely and lock-less-ly. An atomic compare-and-swap operation can be used to build lock-less, thread-safe singly-linked list. Doing that for doubly-linked lists is harder.