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, see C++'s std::list. It is awkward in C, where the implementation has to be macro-generated. C naturally pushes towards an indirection through void *, which makes intrusive lists more attractive.
One other advantage of intrusive data structures is the ability to link a payload into several parallel collections without indirections (where traditional collections would require e.g. one collection owning the payloads, and the other collections merely holding non-owning pointers to them).
Las but not least, the defining property of intrusive data structures is that they leave the responsibility of allocating the elements to the user. 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. It is even reasonable to use non-uniform allocation strategies; for example, for a circular list, allocate an anchor node on the stack and the other nodes (those embedded in payloads) on the heap.
> It is awkward in C, where the implementation has to be macro-generated
I assume this is why they are putting the list pointer and payload in separate structs and doing pointer math to access the payload, so that it’s easy to build a set of macros that act like a generic list class for building lists out of any payload, right?
> One other advantage of intrusive data structures is the ability to link a payload into several parallel collections without indirections
Wait - how does this work? If I do address math on the pointer in order to find a payload, then isn’t the payload tied into exactly one next pointer, and thus exactly one list? For a minute I thought maybe this is why they put the pointer after the payload, but now I don’t see how to use a payload in more than one list, nor why they use subtract on the list pointer to find the payload instead of putting the list in front of the payload and adding (or using a type-cast pointer for direct access).
> the defining property of intrusive data structures is that they leave the responsibility of allocating elements to the user.
Indeed! This is why you see them in OS’s, in memory managers, and in embedded systems. We used to use them all the time in console video games before dynamic memory and heap allocations were common (or even allowed). Use of STL wasn’t allowed. Often the memory needed would be pre-allocated, and lists would be created and managed at run time without allocation, just by wiring up the pointers. Similar to what a memory manager has to do.
This was in C++, but back when (and before) EASTL was popular. EASTL was EA’s version of the STL without built-in heap allocation for container classes. We usually built payload classes with the list next pointer placed directly in the payload, and essentially did the list management as a one-off separately for each payload, because it was typically only a few lines of code and there weren’t enough list types for it to be a problem. This is the kind of intrusive list I’ve seen the most of, hence the questions about the particular C flavor shown here.
I was surprised to see the main benefit of intrusive linking mentioned as a bit of a side note: The ability to move data around between lists (and within a list) without copying. You also get O(1) removal from the middle of the list, assuming you have a pointer to the object somewhere else. As a result, when you have large state structs and you don't do a lot of list scans, intrusive linking makes things a lot faster than use of packed structures like vectors.
In an empty list, head points to &tail, and tail_pred points to &head. The tail pointer is always null (this is the 'end marker').
In a populated list, head points to the embedded Node struct of the first list node, and tail_pred points to the embedded Node struct of the last list node. The pred pointer of the last node points to the address of the list headers tail pointer (...which is always null).
That way you can start anywhere in the list given a Node pointer and walk forward or backward using the succ or pred pointers. When you hit a null pointer (the 'tail' pointer in the list header struct) you know you've reached the end.
Apparently the Linux-style lists in the article require to know the address of the list header to detect when the end is reached which isn't needed for the Amiga style list (at the cost of an additional 'sentinel null pointer' in the list header).
Pretty much of AmigaOS was held together by such doubly linked lists.
(I hope I got that all right, it's been a long time)
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 used in deep dark places like the OS kernel, maybe it’s easy to assume the ‘regular’ kind is non-intrusive.
What Stroustrup called ‘intrusive’ had been the default understanding of linked lists since around 1955, and what people used most often. A ‘regular’ linked list to most people is the intrusive kind, and the term ‘non-intrusive’ might have been an attempt to sell people on the benefits of abstracting and separating node types from payloads, but that maybe papers over the disadvantages a little.
The only kind of linked list I’ve ever used in my professional career is the intrusive kind. There are very few good reasons to ever use non-intrusive lists outside of the classroom. At least, not if you care about performance at all. They might be convenient & easy, but it’s usually the case that either an array or an intrusive list would be a better engineering choice.
You have it backwards, an intrusive linked list is a linked list that is embedded in another data structure. The classic example is a linked list whose elements live on the stack.
The article is wrong too, or at least using the term over-specifically.
GP points out that what the article calls "intrusive linked list" is a regular linked list. Wikipedia for instance gives the canonical linked list example of a struct with one embedded integer and a next link and of course does not call it "intrusive linked list".
"Intrusive" got popular with C++ intrusive pointers, and that is where the article gets is misinformation from.
And of coursed the web jockeys downvote the correct objection since they have no clue about data structures, history, logic or basic reading skills.
I came to this relatively late (2013-ish, windows kernel development, scouring OSDev, etc) so I thought that was always the right name for them. Prior experience was mostly... higher-level langs.
I concur. I recall being a student and when implementing LL for the first time, you did it this way (mix your data and ptr to next node). It is baby's first linked list.
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, see C++'s std::list. It is awkward in C, where the implementation has to be macro-generated. C naturally pushes towards an indirection through void *, which makes intrusive lists more attractive.
One other advantage of intrusive data structures is the ability to link a payload into several parallel collections without indirections (where traditional collections would require e.g. one collection owning the payloads, and the other collections merely holding non-owning pointers to them).
Las but not least, the defining property of intrusive data structures is that they leave the responsibility of allocating the elements to the user. 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. It is even reasonable to use non-uniform allocation strategies; for example, for a circular list, allocate an anchor node on the stack and the other nodes (those embedded in payloads) on the heap.
> It is awkward in C, where the implementation has to be macro-generated
I assume this is why they are putting the list pointer and payload in separate structs and doing pointer math to access the payload, so that it’s easy to build a set of macros that act like a generic list class for building lists out of any payload, right?
> One other advantage of intrusive data structures is the ability to link a payload into several parallel collections without indirections
Wait - how does this work? If I do address math on the pointer in order to find a payload, then isn’t the payload tied into exactly one next pointer, and thus exactly one list? For a minute I thought maybe this is why they put the pointer after the payload, but now I don’t see how to use a payload in more than one list, nor why they use subtract on the list pointer to find the payload instead of putting the list in front of the payload and adding (or using a type-cast pointer for direct access).
> the defining property of intrusive data structures is that they leave the responsibility of allocating elements to the user.
Indeed! This is why you see them in OS’s, in memory managers, and in embedded systems. We used to use them all the time in console video games before dynamic memory and heap allocations were common (or even allowed). Use of STL wasn’t allowed. Often the memory needed would be pre-allocated, and lists would be created and managed at run time without allocation, just by wiring up the pointers. Similar to what a memory manager has to do.
This was in C++, but back when (and before) EASTL was popular. EASTL was EA’s version of the STL without built-in heap allocation for container classes. We usually built payload classes with the list next pointer placed directly in the payload, and essentially did the list management as a one-off separately for each payload, because it was typically only a few lines of code and there weren’t enough list types for it to be a problem. This is the kind of intrusive list I’ve seen the most of, hence the questions about the particular C flavor shown here.
I was surprised to see the main benefit of intrusive linking mentioned as a bit of a side note: The ability to move data around between lists (and within a list) without copying. You also get O(1) removal from the middle of the list, assuming you have a pointer to the object somewhere else. As a result, when you have large state structs and you don't do a lot of list scans, intrusive linking makes things a lot faster than use of packed structures like vectors.
The main benefit is that adding/removing items to/from a list requires no heap operations. All control elements are basically preallocated.
Hmm interesting, the doubly linked list is missing the '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):
Most AmigaOS structs embed such a Node struct at the start....but the list header has three pointers which basically form two overlapped Node structs:
In an empty list, head points to &tail, and tail_pred points to &head. The tail pointer is always null (this is the 'end marker').In a populated list, head points to the embedded Node struct of the first list node, and tail_pred points to the embedded Node struct of the last list node. The pred pointer of the last node points to the address of the list headers tail pointer (...which is always null).
That way you can start anywhere in the list given a Node pointer and walk forward or backward using the succ or pred pointers. When you hit a null pointer (the 'tail' pointer in the list header struct) you know you've reached the end.
Apparently the Linux-style lists in the article require to know the address of the list header to detect when the end is reached which isn't needed for the Amiga style list (at the cost of an additional 'sentinel null pointer' in the list header).
Pretty much of AmigaOS was held together by such doubly linked lists.
(I hope I got that all right, it's been a long time)
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 used in deep dark places like the OS kernel, maybe it’s easy to assume the ‘regular’ kind is non-intrusive.
What Stroustrup called ‘intrusive’ had been the default understanding of linked lists since around 1955, and what people used most often. A ‘regular’ linked list to most people is the intrusive kind, and the term ‘non-intrusive’ might have been an attempt to sell people on the benefits of abstracting and separating node types from payloads, but that maybe papers over the disadvantages a little.
The only kind of linked list I’ve ever used in my professional career is the intrusive kind. There are very few good reasons to ever use non-intrusive lists outside of the classroom. At least, not if you care about performance at all. They might be convenient & easy, but it’s usually the case that either an array or an intrusive list would be a better engineering choice.
You have it backwards, an intrusive linked list is a linked list that is embedded in another data structure. The classic example is a linked list whose elements live on the stack.
The article is wrong too, or at least using the term over-specifically.
It's not really tied to C++isms at all.
GP points out that what the article calls "intrusive linked list" is a regular linked list. Wikipedia for instance gives the canonical linked list example of a struct with one embedded integer and a next link and of course does not call it "intrusive linked list".
"Intrusive" got popular with C++ intrusive pointers, and that is where the article gets is misinformation from.
And of coursed the web jockeys downvote the correct objection since they have no clue about data structures, history, logic or basic reading skills.
I came to this relatively late (2013-ish, windows kernel development, scouring OSDev, etc) so I thought that was always the right name for them. Prior experience was mostly... higher-level langs.
I concur. I recall being a student and when implementing LL for the first time, you did it this way (mix your data and ptr to next node). It is baby's first linked list.