3 ms·

Yes, linked lists have terrible cache behavior and usually the performance of any packed structure with less pointer chasing should beat it. ArrayList, Vector,

by exDM69 6y ago

Yes, linked lists have terrible cache behavior and usually the performance of any packed structure with less pointer chasing should beat it. ArrayList, Vector, whatever you call it usually is faster. But computers aren't fast in allocating memory. In particular, they're not predictably fast in allocating memory, as most allocators will have complex internal data structures and may end up having to call the operating system to give fresh pages of unused memory. The best case may be smoking fast, the amortized cost may be decent but the worst case is pretty bad. So when reliable and predictable performance is needed, memory allocations are to be avoided. This is relevant if you're working on (soft) real time applications, say audio, games or so. And linked lists are still mighty fast in addition and removal, joining and splitting. Intrusive linked lists drop one extra pointer chase. In kernel space, there are tons of use cases for linked lists that are never traversed, or at least not traversed in the fast path. Traversal is the slow part, but that's not necessary for a lot of cases where you add something to a list or a set, and remove items one by one. There's no other data structure that beats linked lists when there's only addition, removal, joins and splits, but no traversals. Linked lists are almost always the wrong data structure for the job, but in special niche cases (which are not that rare, at least in kernel space) it's the simplest and most effective.

pdpi 6y ago
> Intrusive linked lists drop one extra pointer chase. Template-based lists (in the style of C++ STL) let you have your cake and eat it too in that you still keep the list structure out of your data, but you still get the cache locality of an intrusive list.
- DSMan195276 6y ago
  I think your typical template-based list is actually a bad example :P Maybe there's something about C++ I don't know, but typically those implementations only allow for adding one list node (via the template wrapping), and also they can't usually take an element from one list and then attach it to another one. Where-as intrusive implementations like the Linux Kernel's allow for any number of list nodes or other data structures to be placed alongside the data, and the elements can be moved onto any list you want without any allocations necessary.
  - gpderetta 6y ago
    std::list has splice to move nodes between lists. boost.intrusive does, among other things, provide true intrusive lists and, for example, can insert the same node on multiple containers (not just lists) at the same time. But really, no need for boost.intrusive, writing a templated intrusive list is not hard.
    - DSMan195276 6y ago
      Once you do that though (use a "true" intrusive implementation), you typically lose the "keep the list structure out of your data" aspect. std::list allows you to avoid that, but carries its own limitations that embedding the list structures into the data does not. Don't get me wrong, I'm not saying one is better or worse, just that containers like std::list aren't better for every use-case you might have compared to an intrusive implementation. Perhaps I just misunderstood your "have your cake in eat it too" remark though.
cmeacham98 6y ago
> So when reliable and predictable performance is needed, memory allocations are to be avoided. This is relevant if you're working on (soft) real time applications, say audio, games or so. Surely LLs are a poor example of this because _every_ newly created element becomes an allocation? The PR in the GP only managed to significantly reduce allocations because it was a particularly niche case and the PR was accidentally cheating. My understanding from friends in the worlds where allocation matters is they use a lot of statically sized arrays.
- exDM69 6y ago
  You don't need to couple the linked list nodes with your allocations. Either you make an array of link structs or embed your links in the stored struct (intrusive linked list). The linux kernel uses intrusive linked lists (and intrusive rbtrees) a lot. They are the perfect data structure for a lot of uses where performance matters and allocations are a no go.
  - cmeacham98 6y ago
    You still need to allocate a node for each addition to the LL for the stored struct, unless you pre-allocate a set of them, and at that point you very likely are better off using a static array. The linux kernel LL implementation uses kmalloc (i.e. it performs allocations) - although they get to dodge some of the problems of userspace allocators by using their own.
    - gsg 6y ago
      You can easily see by searching for 'kmalloc' (or 'malloc') at https://github.com/torvalds/linux/blob/master/include/linux/list.h https://github.com/torvalds/linux/blob/master/include/linux/... that it does no such thing. Here's the logic for adding a list node: /* * Insert a new entry between two known consecutive entries. * * This is only for internal list manipulation where we know * the prev/next entries already! */ static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next) { if (!__list_add_valid(new, prev, next)) return; next->prev = new; new->next = next; new->prev = prev; WRITE_ONCE(prev->next, new); } No allocation, just mutating some fields in preexisting list_head structures. Those are by convention stored as a field in whatever struct needs to be kept in the list, which is what 'intrusive' means.

by exDM69 6y ago

pdpi 6y ago

> Intrusive linked lists drop one extra pointer chase. Template-based lists (in the style of C++ STL) let you have your cake and eat it too in that you still keep the list structure out of your data, but you still get the cache locality of an intrusive list.

DSMan195276 6y ago
I think your typical template-based list is actually a bad example :P Maybe there's something about C++ I don't know, but typically those implementations only allow for adding one list node (via the template wrapping), and also they can't usually take an element from one list and then attach it to another one. Where-as intrusive implementations like the Linux Kernel's allow for any number of list nodes or other data structures to be placed alongside the data, and the elements can be moved onto any list you want without any allocations necessary.
- gpderetta 6y ago
  std::list has splice to move nodes between lists. boost.intrusive does, among other things, provide true intrusive lists and, for example, can insert the same node on multiple containers (not just lists) at the same time. But really, no need for boost.intrusive, writing a templated intrusive list is not hard.
  - DSMan195276 6y ago
    Once you do that though (use a "true" intrusive implementation), you typically lose the "keep the list structure out of your data" aspect. std::list allows you to avoid that, but carries its own limitations that embedding the list structures into the data does not. Don't get me wrong, I'm not saying one is better or worse, just that containers like std::list aren't better for every use-case you might have compared to an intrusive implementation. Perhaps I just misunderstood your "have your cake in eat it too" remark though.

cmeacham98 6y ago

> So when reliable and predictable performance is needed, memory allocations are to be avoided. This is relevant if you're working on (soft) real time applications, say audio, games or so. Surely LLs are a poor example of this because _every_ newly created element becomes an allocation? The PR in the GP only managed to significantly reduce allocations because it was a particularly niche case and the PR was accidentally cheating. My understanding from friends in the worlds where allocation matters is they use a lot of statically sized arrays.

exDM69 6y ago
You don't need to couple the linked list nodes with your allocations. Either you make an array of link structs or embed your links in the stored struct (intrusive linked list). The linux kernel uses intrusive linked lists (and intrusive rbtrees) a lot. They are the perfect data structure for a lot of uses where performance matters and allocations are a no go.
- cmeacham98 6y ago
  You still need to allocate a node for each addition to the LL for the stored struct, unless you pre-allocate a set of them, and at that point you very likely are better off using a static array. The linux kernel LL implementation uses kmalloc (i.e. it performs allocations) - although they get to dodge some of the problems of userspace allocators by using their own.
  - gsg 6y ago
    You can easily see by searching for 'kmalloc' (or 'malloc') at https://github.com/torvalds/linux/blob/master/include/linux/list.h https://github.com/torvalds/linux/blob/master/include/linux/... that it does no such thing. Here's the logic for adding a list node: /* * Insert a new entry between two known consecutive entries. * * This is only for internal list manipulation where we know * the prev/next entries already! */ static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next) { if (!__list_add_valid(new, prev, next)) return; next->prev = new; new->next = next; new->prev = prev; WRITE_ONCE(prev->next, new); } No allocation, just mutating some fields in preexisting list_head structures. Those are by convention stored as a field in whatever struct needs to be kept in the list, which is what 'intrusive' means.