4 ms·
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
by pclmulqdq 29d ago
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.
- abcd_f 29d agoThe main benefit is that adding/removing items to/from a list requires no heap operations. All control elements are basically preallocated.
- vlovich123 29d agoData is generally read more often than written and data is read in locally spatial way. That’s why having elements laid out next to one another is often more important than the algorithmic complexity of occasionally doing an O(n) or O(n log n) operation updating the layout. It’s not always the case of course but it is the case more often than you’d think.
- zahlman 29d agoI'm pretty sure the author there means to compare the intrusive linked list to a non-intrusive linked list (such as C++ std::list), not to vectors etc. that aren't "linked" at all. As described e.g. in https://news.ycombinator.com/item?id=49549542 https://news.ycombinator.com/item?id=49549542 .
- barchar 29d agoYou can do this with non intrusive lists too. See c++’s merge/splice/etc. You can store the iterators in some other place as you do this, making it quite handy on occasion.