Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Intrusive lists in Doom 3

gpfault.net

Post reply on HN
Print view View original

21–30 of 68 posts

Re: Intrusive lists in Doom 3

#21

Post by 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 ?

Re: Intrusive lists in Doom 3

#22

Post by noodly »

Wayland also uses intrusive circular linked lists - but it doesn't need owner pointer, since that pointer can be computed from pointer to link, and offset of that link in owner structure. I wonder if doom 3 really needed it.

Re: Intrusive lists in Doom 3

#23

Post by nly »

sorbits wrote: post #18
repsilat wrote: post #14

Earlier quoted context omitted.

> Another consideration is that a std::vector is as fast to iterate over as intrusive list of Foos. A "normal" linked-list of strings or vectors always makes me sad -- the reasoning goes, - The list elements need to live on the heap because they might live forever, - The string object has to be fixed-size because objects are always (at least officially) fixed-size. - The string storage has to live on the heap, becaus…

> C++ programmers don't like non-zero-cost abstractions I think you’re confusing zero cost with zero overhead. What C++ programmers like is that the compiler does not add overhead, for example calling `a[10]` will read the word at address `a + 10` and return that. No bounds checks are inserted, no function call is done to lookup the element in some implementation defined sparse data structure, etc. But C++ programmer…

std::map is implemented using a tree and not a hash table because it's specified as an ordered data structure.

Re: Intrusive lists in Doom 3

#24

Post by fit2rule »

pubby wrote: post #20
yason wrote: post #17

I didn't think these "non-intrusive lists" were actually used much in real world programs. Even if allocations weren't a big issue performance-wise, the sheer amount of work required manage the allocations themselves would put me off using them.

Just use Boost.Intrusive: http://www.boost.org/doc/libs/1_57_0/doc/html/intrusive.html It makes the job much easier.

Except: boost.

Re: Intrusive lists in Doom 3

#25

Post by showHNshow »

The article contains many false claims and its main statement that intrusive lists are better than non-intrusive ones is simply wrong.

Outright wrong:

1) There is no additional dereferencing needed when using his 'ListNode' implementation, since the object is stored directly in the ListNode.

2) If you want objects to be non-pointer members of ListNodes of several lists, you can achieve that with both intrusive and non-intrusive lists in exactly the same way (contrary to the authors claim).

The article is a disgusting example of someone trying to proof a point he heard somewhere else. So it is not his original idea and he is failing hard.

Why are there no comments on HN (except for jokoon) addressing that? Instead everybody uses the comment system as a platform to show off his own bad ass C++ skills... stupid. You deserve each other

Re: Intrusive lists in Doom 3

#26

Post by sharpneli »

nly wrote: post #19
andrea_s wrote: post #7

Does anybody know what would the performance gain be in this case?

There isn't one. std::list has the same space requirements, memory locality and capabilities of an intrusive list. Period. The naivety of an 'intrusive' list, where all your objects are always 'list ready', is that it allows the insertion and removal of elements without copying them, which is beneficial if your lists experience a lot of churn. The thing is, you can achieve this without intrusion anyway by keeping all…

What about modifying the elements while keeping them on multiple lists?

With intrusive list you need only modify any element on a single place (A bullet location as an example).

How could you achieve this with std::list?

Re: Intrusive lists in Doom 3

#27

Post by nly »

sharpneli wrote: post #26
nly wrote: post #19

Earlier quoted context omitted.

There isn't one. std::list has the same space requirements, memory locality and capabilities of an intrusive list. Period. The naivety of an 'intrusive' list, where all your objects are always 'list ready', is that it allows the insertion and removal of elements without copying them, which is beneficial if your lists experience a lot of churn. The thing is, you can achieve this without intrusion anyway by keeping all…

What about modifying the elements while keeping them on multiple lists? With intrusive list you need only modify any element on a single place (A bullet location as an example). How could you achieve this with std::list?

I don't know what you mean. How do you keep an object on multiple lists with only one pair of pointers?

Re: Intrusive lists in Doom 3

#28

Post by sharpneli »

nly wrote: post #27
sharpneli wrote: post #26

Earlier quoted context omitted.

What about modifying the elements while keeping them on multiple lists? With intrusive list you need only modify any element on a single place (A bullet location as an example). How could you achieve this with std::list?

I don't know what you mean. How do you keep an object on multiple lists with only one pair of pointers?

That's the point of intrusive lists. You add a pair of pointers for every list the object is in. So when you do your physics pass using the "moving objects" list the value of the bullet is automatically updated in the "renderable objects" list without having to go trough renderable objects separately.

It was explained in the original article "If you want your structure to be in two lists at the same time, you have to add another field: " with an example.

Re: Intrusive lists in Doom 3

#29

Post by CrLf »

sharpneli wrote: post #26
nly wrote: post #19

Earlier quoted context omitted.

There isn't one. std::list has the same space requirements, memory locality and capabilities of an intrusive list. Period. The naivety of an 'intrusive' list, where all your objects are always 'list ready', is that it allows the insertion and removal of elements without copying them, which is beneficial if your lists experience a lot of churn. The thing is, you can achieve this without intrusion anyway by keeping all…

What about modifying the elements while keeping them on multiple lists? With intrusive list you need only modify any element on a single place (A bullet location as an example). How could you achieve this with std::list?

If you're storing pointers to elements in the list, you only have to change the pointed object.

Re: Intrusive lists in Doom 3

#30

Post by sharpneli »

CrLf wrote: post #29
sharpneli wrote: post #26

Earlier quoted context omitted.

What about modifying the elements while keeping them on multiple lists? With intrusive list you need only modify any element on a single place (A bullet location as an example). How could you achieve this with std::list?

If you're storing pointers to elements in the list, you only have to change the pointed object.

Then "Less Dereferencing" is not achieved as there are 2 pointer dereferences per access to an element instead of just one, and that goes against the claim "std::list has the same space requirements, memory locality and capabilities of an intrusive list. Period."

I have no idea how to implement something that has same memory locality and capabilities as intrusive list with std::list and that's why I'm asking how it's done. Storing a pointer does not have same memory locality.

Post reply on HN