Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Intrusive linked lists (2019)

data-structures-in-practice.com

Post reply on HN
Print view View original

21–30 of 80 posts

Re: Intrusive linked lists (2019)

#21

Post by drdexebtjl »

el_pollo_diablo wrote: post #2

The go a bit further than the article on the advantages of intrusive data structures, taking linked lists as an example: As the article mentions, intrusive data structures naturally lead to one fewer indirection. To do the same with a traditional list (where the list node owns the payload), a different node type is needed for each payload type. This is easy to do with the proper support for monomorphized generics, se…

> It is awkward in C, where the implementation has to be macro-generated.

You can avoid having the implementation be macro-generated by "hiding" the list pointers before a char payload[0]. See https://pastebin.com/DE69mbJD for an example.

The same technique is used by glibc's malloc to store metadata about the allocation right next to your data, and then recover it when you call realloc/free, without needing a separate metadata allocation.

The caveat is that the type of the pointer does not indicate provenance. For example, nothing stops you from calling list_next on an arbitrary pointer to data that is not on a list, and that would be UB. The same happens with realloc and free, where it's UB if you pass them a pointer that was not returned by the heap allocator.

Re: Intrusive linked lists (2019)

#22

Post by samatman »

el_pollo_diablo wrote: post #2

The go a bit further than the article on the advantages of intrusive data structures, taking linked lists as an example: As the article mentions, intrusive data structures naturally lead to one fewer indirection. To do the same with a traditional list (where the list node owns the payload), a different node type is needed for each payload type. This is easy to do with the proper support for monomorphized generics, se…

> This is easy to do with the proper support for monomorphized generics, see C++'s std::list. It is awkward in C, where the implementation has to be macro-generated.

Fairly pleasant in Zig, through abuse of @fieldParentPointer and a pinch of comptime.

https://github.com/mnemnion/zelda

It was a little nicer in the `usingnamespace` days. So it goes.

> The elements can be allocated on the heap, on the stack, in a global array (like "initholes" in the article), in a special arena, etc.

An "etc" worth mentioning specifically is a memory pool: they're useful for any same-sized struct which gets recycled a lot, but for linked lists there are further advantages. You don't have to cast the object to bytes and declare a link pointer, since it already has one: not really an advantage, casting is free, but: if you can arrange to give both sides of the list back, then recycling can be done on a per-list level by prepending the whole thing to the freelist.

Re: Intrusive linked lists (2019)

#24

Post by thewillowcat »

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.

This was my reaction exactly. I was surprised by the diagram of a "normal" linked list.

Re: Intrusive linked lists (2019)

#25

Post by layer8 »

flohofwoe wrote: post #11

Hmm interesting, the doubly linked list presented here is missing the elegant 'overlapped list header' trick from AmigaOS (at least that's where I saw it first): E.g. an AmigaOS list node looks conventional, it has two pointers, one to the next node (succ), and one to the previous node (pred): struct Node { struct Node* ln_Succ; struct Node* ln_Pred; }; Most AmigaOS structs embed such a Node struct at the start. ...b…

This looks correct, here is a reference: https://wiki.amigaos.net/wiki/Exec_Lists_and_Queues#List_Hea....

Re: Intrusive linked lists (2019)

#26

Post by layer8 »

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…

It really depends on the ecosystem you’re working in. For a good while, most developers have been working with managed runtimes, where “non-intrusive” linked lists are generally the default and “intrusive” linked lists correspondingly rare.

(Actually, in many cases arrays are the default (like ArrayList in Java), because lists tend to only get assembled once and then passed around without further modification.)

Re: Intrusive linked lists (2019)

#27

Post by el_pollo_diablo »

drdexebtjl wrote: post #21
el_pollo_diablo wrote: post #2

The go a bit further than the article on the advantages of intrusive data structures, taking linked lists as an example: As the article mentions, intrusive data structures naturally lead to one fewer indirection. To do the same with a traditional list (where the list node owns the payload), a different node type is needed for each payload type. This is easy to do with the proper support for monomorphized generics, se…

> It is awkward in C, where the implementation has to be macro-generated. You can avoid having the implementation be macro-generated by "hiding" the list pointers before a char payload[0]. See https://pastebin.com/DE69mbJD for an example. The same technique is used by glibc's malloc to store metadata about the allocation right next to your data, and then recover it when you call realloc/free, without needing a separa…

Zero-sized arrays are not standard. Accessing an array out of bounds is UB. At the very least, you should use a flexible array member instead (char payload[];).

But even if you did that, strict aliasing implies that 'payload' can only be accessed as an array of character type. It is correct to memcpy between 'payload' and another object of arbitrary type T of the appropriate size (as list_push_ does in your example), but it is UB to access 'payload' in place as a T (as main does, by casting to struct point * and dereferencing). Oh, and 'payload' may not satisfy the alignment requirement of T.

There is no realistic strict-aliasing-abiding way around a distinct node type per payload type.

Re: Intrusive linked lists (2019)

#28

Post by Joker_vD »

el_pollo_diablo wrote: post #27
drdexebtjl wrote: post #21

Earlier quoted context omitted.

> It is awkward in C, where the implementation has to be macro-generated. You can avoid having the implementation be macro-generated by "hiding" the list pointers before a char payload[0]. See https://pastebin.com/DE69mbJD for an example. The same technique is used by glibc's malloc to store metadata about the allocation right next to your data, and then recover it when you call realloc/free, without needing a separa…

Zero-sized arrays are not standard. Accessing an array out of bounds is UB. At the very least, you should use a flexible array member instead (char payload[];). But even if you did that, strict aliasing implies that 'payload' can only be accessed as an array of character type. It is correct to memcpy between 'payload' and another object of arbitrary type T of the appropriate size (as list_push_ does in your example),…

> Accessing an array out of bounds is UB.

There is no OoB access of an array; the calculated pointer is pointing to the payload object that's residing in the malloc-returned storage right after the node struct.

I think the actual problem is the alignment; that malloc-returned storage simply can't have enough space to hold a "struct { struct node header; PAYLOAD_TYPE payload; }" (which is what the parent comment is trying to emulate) if the payload type has an alignment that's greater than the size of a pointer, and that pointer will be pointing at what would've been the padding in that struct.

Re: Intrusive linked lists (2019)

#29

Post by dietr1ch »

el_pollo_diablo wrote: post #2

The go a bit further than the article on the advantages of intrusive data structures, taking linked lists as an example: As the article mentions, intrusive data structures naturally lead to one fewer indirection. To do the same with a traditional list (where the list node owns the payload), a different node type is needed for each payload type. This is easy to do with the proper support for monomorphized generics, se…

> One other advantage of intrusive data structures is the ability to link a payload into several parallel collections without indirections

My example here from the top of my head are intrusive heaps, which are provide a neat way of implementing A*. Here you combine a HashMap and a Heap (over a Vec) where the Heap has the data, and the HashMap maps SearchNodeId to Heap indices. This allows O(1) lookups by search node Id into the Heap (as opposed to a linear scan) despite elements in the heap being constantly shuffled around as search nodes enter and leave the heap.

I'm sure that using HashMaps as a parallel index to other collections can be useful in other scenarios, but I don't know if combination of other data structures works this well, the synchronisation cost might not be worth it.

Post reply on HN