I don't understand the higher performance either. What I know as the significant advantage is that you can have one object in multiple lists.
> What I know as the significant advantage is that you can have one object in multiple lists.
Another advantage is smaller code size, as the compiler doesn't need to generate code for SinglyLinkedList(i32), SinglyLinkedList(User), and SinglyLinkedList(PointCloud). This could have a performance impact by making it more likely that code remains in the cache.
Technically that should be possible the other way by using a Node<T> so the type of the second list ends up being a Node<Node<T>> but I can see why an intrusive list would be preferred to that, and also the linked list API might prevent that pattern.
Usually if I have multiple lists holding something I have one that's the 'owner' and then the secondary data structures would have a non-owning pointer to it. Is that the case where the performance would be better with an intrusive list? My intuition would be that having multiple Node members would pollute the cache and not actually be a performance win but maybe it is still better off because it's all colocated? Seems like the kind of thing I'd have to benchmark to know since it would depend on the number of lists and the size of the actual data.
Okay so in the multiple list case performance would actually be worse because you'd have a double pointer dereference. I was thinking you'd have the list nodes contiguous in memory so the first dereference would always hit cache but that's a bad assumption for a linked list.
Since you shouldn't reach for a linked list as a default data structure modern hardware anyway, I actually do see how this change makes sense for Zig. Neat!
Allocating list nodes in one block of memory is very common in the intrusive case.