On: Intrusive lists in Doom 3

[jokoon]

I don't understand. Is it really well explained ?

Aren't ListNode just a way to index a list ? Isn't this Point2D just "marked" to be on a certain list ?

Why does he say "less dereferencing" ?

> Dereference the appropriate "next" pointer, get the next object from memory.

the prev/next pointer is in the ListNode, not in the object itself, so it's obviously a dereference...

I did not understand it very well... I can understand that a linked list will be faster thanks to branch prediction, but what does it have to do with an intrusive list ?

[pushrax → jokoon]

> the prev/next pointer is in the ListNode, not in the object itself, so it's obviously a dereference...

The ListNode is embedded in the Point, so their storage is actually combined. The memory layout would be something like

  0x0  x
  0x4  y
  0x8  next
  0xc  prev
  0x10 owner

with the total structure being 20 bytes if pointers are 32-bit.

> Aren't ListNode just a way to index a list ? Isn't this Point2D just "marked" to be on a certain list ?

The list itself is formed entirely by the ListNodes themselves. There is no backing array to index into; the storage for points (and nodes, which are contained in points) is created with an individual malloc per point. The way you reference a list is by holding a reference to the head, which is just a regular ListNode.

[ant6n → pushrax]

If you use a std::List<T>, doesn't it uses nodes like

    T data
    p next
    p previous
    p owner

anyway? It shouldn't create a pointer to the data, just like a std::vector<T> isn't an array of pointers to T.

[desdiv → ant6n]

Let's say I have a bunch of Bullet objects, and each Bullet belongs to multiple lists. In that case, std::list<Bullet> doesn't work and I have to use std::list<Bullet*> instead, thus the extra pointer dereference.

[SamReidHughes → ant6n]

Only without the owner pointer. But intrusive lists don't need an owner pointer either.

[jokoon → pushrax]

so it's a preallocation technique, a little like an object pool