3 ms·

> almost always As any generalization this one too is, of course, incorrect. Outside of the realm of academia, the need to keep data pieces in several contain

> almost always As any generalization this one too is, of course, incorrect. Outside of the realm of academia, the need to keep data pieces in several containers at the same time, with no heap operations on insertion or removal and O(1) removal is very common, especially in the kernel space and embedded contexts. The only option that fits the bill - you guessed it - are the linked lists.

nostrademons 4y ago
Note that this (and the article) describes an intrusive linked list. Extrusive linked lists (like you might see in a class library or CS 101 project), where the node structure is heap-allocated separately from the data that it points to, have very few practical advantages over vectors, which is why standard libraries are increasingly defaulting to vectors even when the class is named "list".
- majjgepolja 4y ago
  Is there a difference between intrusive and extrusive list when the member type is a struct (value type)?
  - nostrademons 4y ago
    Yes. An intrusive list puts the pointers to next & prev in the struct itself. IntrusiveList<Member>::iterator is a Member*, then member->next points to another Member*. An extrusive list puts the pointers in a separate node structure, which then has a pointer to the actual member type. ExtrusiveList<Member>::iterator is a ExtrusiveListNode<Member>*, node->next points to another ExtrusiveListNode*, and you access the actual Member* with node->data. Basically it's a double indirection. The advantage of extrusive linked lists is that you don't need to modify the data layout of Member at all. All the linked list manipulation happens on ListNodes, which have a pointer to the actual member, which can be accessed with just a cast. That's why they're so well-suited to class libraries: you can easily write a generic ExtrusiveLinkedList that works with any data that can be represented with a pointer, hide all the traversal (and the existence of individual ExtrusiveListNodes) in accessor functions, and present a simple API with no codegen or modifications to Member. The advantages of intrusive linked lists are 1) performance 2) no heap allocations 3) easy traversal when given a Member*. It's only a single indirection rather than a double, and usually that indirection is necessary anyway to avoid copies. Insertion and deletion are just pointer manipulation; you don't need to allocate new space for the nodes. Oftentimes your functions will take Member* anyway, and it's nice not to take or traverse the container if you just need to peek at the next element coming up. The point of this subthread is that intrusive linked lists have very clear use cases in the kernel & embedded spaces, where these advantages are often critical. Extrusive linked lists, however, have very few advantages over vectors (which also require heap allocation but are more cache & locality friendly). In a common business app responding to user input, the difference between O(1) amortized and O(1) is negligible; you can eat the occasional pause for a vector resizing, because the user isn't going to care about a few milliseconds. They both require heap allocation. The vector will give you much faster traversal, because subsequent reads all hit cache. The vector takes less memory (1 pointer per element, with a max of 50% overhead, while an extrusive doubly-linked list is 3 pointers per element). There's just little reason to use an extrusive linked list because the use-cases where intrusive linked lists are not better are precisely the same ones where vectors are better.
forrestthewoods 4y ago
As any generalization this one too is, of course, incorrect. In the real world of application development when choosing between Vector and LinkedList the answer is almost always Vector. There are, of course, certain problems where LinkedList is always the correct answer. However for all problem that have chosen either Vector or LinkedList as their container of choice a super majority should choose Vector.
- AstralStorm 4y ago
  There are essentially no vectors in most of the embedded world, including RTOS. Why would you need that many extra copies of data? Coopies are not free. Not in terms of stack, neither in terms of memory or its bandwidth. Both of which are in demand there. For an example, look into how most of Zephyr RTOS is implemented. It's mostly intrusive lists (called queues there for some reason, but they support iteration) or ring buffers (msgq or mpsc_pbuf or pipe). For bigger systems you can use red-black trees. There is no vector data structure, you can allocate a block from the heap and manage its size manually, but it's rarely done as most sizes are static and many data structures are preallocated by the bootloader or loaded directly from flash memory. Cache locality of these is of course possible to manipulate manually by use of memory sections. A list does not copy by default, which is an extremely important performance characteristic. And it does not require overallocation like a vector of pointers, plus has a fast remove, especially at head or tail.
  - forrestthewoods 4y ago
    Extra copies, huh? Feel free to replace the term “Vector” with “Contiguous Memory”. The relevant distinction in this conversation is “contiguous vs node pointers”. Embedded loves contiguous blocks. A dynamic array copies memory if it regrows, inserts, removes. The cost of that operation depends on numerous factors. But it doesn’t result in “extra copies” laying around. Oh wait maybe you mean array operations perform extra copies, not that they persist. In which case it comes down to which is more expensive: memcpy some bytes or cache inefficient pointer traversal. It depends! But most problems for most programs are MUCH faster if they avoid LinkedList. Many people, especially new programmers, radically underestimate the penalty of pointer chasing.

nostrademons 4y ago

Note that this (and the article) describes an intrusive linked list. Extrusive linked lists (like you might see in a class library or CS 101 project), where the node structure is heap-allocated separately from the data that it points to, have very few practical advantages over vectors, which is why standard libraries are increasingly defaulting to vectors even when the class is named "list".

majjgepolja 4y ago
Is there a difference between intrusive and extrusive list when the member type is a struct (value type)?
- nostrademons 4y ago
  Yes. An intrusive list puts the pointers to next & prev in the struct itself. IntrusiveList<Member>::iterator is a Member*, then member->next points to another Member*. An extrusive list puts the pointers in a separate node structure, which then has a pointer to the actual member type. ExtrusiveList<Member>::iterator is a ExtrusiveListNode<Member>*, node->next points to another ExtrusiveListNode*, and you access the actual Member* with node->data. Basically it's a double indirection. The advantage of extrusive linked lists is that you don't need to modify the data layout of Member at all. All the linked list manipulation happens on ListNodes, which have a pointer to the actual member, which can be accessed with just a cast. That's why they're so well-suited to class libraries: you can easily write a generic ExtrusiveLinkedList that works with any data that can be represented with a pointer, hide all the traversal (and the existence of individual ExtrusiveListNodes) in accessor functions, and present a simple API with no codegen or modifications to Member. The advantages of intrusive linked lists are 1) performance 2) no heap allocations 3) easy traversal when given a Member*. It's only a single indirection rather than a double, and usually that indirection is necessary anyway to avoid copies. Insertion and deletion are just pointer manipulation; you don't need to allocate new space for the nodes. Oftentimes your functions will take Member* anyway, and it's nice not to take or traverse the container if you just need to peek at the next element coming up. The point of this subthread is that intrusive linked lists have very clear use cases in the kernel & embedded spaces, where these advantages are often critical. Extrusive linked lists, however, have very few advantages over vectors (which also require heap allocation but are more cache & locality friendly). In a common business app responding to user input, the difference between O(1) amortized and O(1) is negligible; you can eat the occasional pause for a vector resizing, because the user isn't going to care about a few milliseconds. They both require heap allocation. The vector will give you much faster traversal, because subsequent reads all hit cache. The vector takes less memory (1 pointer per element, with a max of 50% overhead, while an extrusive doubly-linked list is 3 pointers per element). There's just little reason to use an extrusive linked list because the use-cases where intrusive linked lists are not better are precisely the same ones where vectors are better.

forrestthewoods 4y ago

As any generalization this one too is, of course, incorrect. In the real world of application development when choosing between Vector and LinkedList the answer is almost always Vector. There are, of course, certain problems where LinkedList is always the correct answer. However for all problem that have chosen either Vector or LinkedList as their container of choice a super majority should choose Vector.

AstralStorm 4y ago
There are essentially no vectors in most of the embedded world, including RTOS. Why would you need that many extra copies of data? Coopies are not free. Not in terms of stack, neither in terms of memory or its bandwidth. Both of which are in demand there. For an example, look into how most of Zephyr RTOS is implemented. It's mostly intrusive lists (called queues there for some reason, but they support iteration) or ring buffers (msgq or mpsc_pbuf or pipe). For bigger systems you can use red-black trees. There is no vector data structure, you can allocate a block from the heap and manage its size manually, but it's rarely done as most sizes are static and many data structures are preallocated by the bootloader or loaded directly from flash memory. Cache locality of these is of course possible to manipulate manually by use of memory sections. A list does not copy by default, which is an extremely important performance characteristic. And it does not require overallocation like a vector of pointers, plus has a fast remove, especially at head or tail.
- forrestthewoods 4y ago
  Extra copies, huh? Feel free to replace the term “Vector” with “Contiguous Memory”. The relevant distinction in this conversation is “contiguous vs node pointers”. Embedded loves contiguous blocks. A dynamic array copies memory if it regrows, inserts, removes. The cost of that operation depends on numerous factors. But it doesn’t result in “extra copies” laying around. Oh wait maybe you mean array operations perform extra copies, not that they persist. In which case it comes down to which is more expensive: memcpy some bytes or cache inefficient pointer traversal. It depends! But most problems for most programs are MUCH faster if they avoid LinkedList. Many people, especially new programmers, radically underestimate the penalty of pointer chasing.