4 ms·

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 (intrusi

by 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.
  - cmeacham98 6y ago
    And where do you think that "new" comes from? I guess my phrasing is poor so I should have been clearer: elements in kernel LLs generally came from a kmalloc, even though the LL functions don't use a malloc themselves.
- exDM69 6y ago
  Yes, preallocation was what I was referring to. The other strategy is what Linux does, embedding the links to the stored struct. Static arrays are poor at joining, splitting, removal and merging.
  - cmeacham98 6y ago
    > Static arrays are poor at joining, splitting, removal and merging. True, but these are relatively rare requirements for a data container. My point isn't that LLs are totally useless but it seems like they'll see relatively little use if the goal is "no allocations at all".
    - exDM69 6y ago
      Intrusive linked lists don't need any allocations.
  - MauranKilom 6y ago
    Merging (in the sense of retaining some order property) is probably just as fast in static arrays as in lists. For large element sizes, you'd use an array of pointers (requiring only one pointer per element in the data, doubling during the merge) and the pointer fiddling during the merge is about the same for either. For small elements, the list overhead alone is probably enough to make arrays faster. O(1) joining, splitting and removal are of course not beatable by contiguous data structures.

by exDM69 6y ago

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.
- cmeacham98 6y ago
  And where do you think that "new" comes from? I guess my phrasing is poor so I should have been clearer: elements in kernel LLs generally came from a kmalloc, even though the LL functions don't use a malloc themselves.
exDM69 6y ago
Yes, preallocation was what I was referring to. The other strategy is what Linux does, embedding the links to the stored struct. Static arrays are poor at joining, splitting, removal and merging.
- cmeacham98 6y ago
  > Static arrays are poor at joining, splitting, removal and merging. True, but these are relatively rare requirements for a data container. My point isn't that LLs are totally useless but it seems like they'll see relatively little use if the goal is "no allocations at all".
  - exDM69 6y ago
    Intrusive linked lists don't need any allocations.
- MauranKilom 6y ago
  Merging (in the sense of retaining some order property) is probably just as fast in static arrays as in lists. For large element sizes, you'd use an array of pointers (requiring only one pointer per element in the data, doubling during the merge) and the pointer fiddling during the merge is about the same for either. For small elements, the list overhead alone is probably enough to make arrays faster. O(1) joining, splitting and removal are of course not beatable by contiguous data structures.