3 ms·

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

by jokoon 12y ago

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 12y ago
> 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 12y ago
  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 12y ago
    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 12y ago
    Only without the owner pointer. But intrusive lists don't need an owner pointer either.
- jokoon 12y ago
  so it's a preallocation technique, a little like an object pool

by jokoon 12y ago

pushrax 12y ago

> 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 12y ago
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 12y ago
  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 12y ago
  Only without the owner pointer. But intrusive lists don't need an owner pointer either.
jokoon 12y ago
so it's a preallocation technique, a little like an object pool