News for hackers. Stuff that matters.
Re:Intrusive lists in Doom 3 by andrea_s on Thursday December 25, 2014 @03:44AM (#8795846)
Does anybody know what would the performance gain be in this case?
Re:Intrusive lists in Doom 3 by nly on Thursday December 25, 2014 @05:29AM (#8795978)
There isn't one. std::list<T> 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 your 'not in a list' items... well, in a list. You then get memory management for free and can use splice()[0] to efficiently move nodes around.

My philosophy on lists is: if you've never used or needed to splice then you probably don't really need a linked list. Splicing is what linked lists are all about.

[0] http://en.cppreference.com/w/cpp/container/list/splice

Re:Intrusive lists in Doom 3 by sharpneli on Thursday December 25, 2014 @07:11AM (#8796091)
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 by nly on Thursday December 25, 2014 @07:15AM (#8796099)
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 by sharpneli on Thursday December 25, 2014 @07:19AM (#8796106)
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 by nly on Thursday December 25, 2014 @08:00AM (#8796172)
For games and other micro-optimised uses yeah... super-fine control over where you put your pointer pairs with respect to other data members and cache lines could be warranted. If you're optimising at that level then fine, I'd do it (with Boost Intrusive). Otherwise I'd pick up Boost Multi_Index with a couple of 'sequenced' (linked node) or random_access (vector of pointers) indices. This is non-intrusive and has the construction and overhead you want.

I just wanted to spell out that in most use cases intrusion is a sucky trade-off with no benefit.

Re:Intrusive lists in Doom 3 by CrLf on Thursday December 25, 2014 @07:23AM (#8796113)
If you're storing pointers to elements in the list, you only have to change the pointed object.
Re:Intrusive lists in Doom 3 by latitude on Thursday December 25, 2014 @12:15PM (#8796653)
OK, then.

I'll give you a pointer to an element and you remove it from all containers that it is currently on, in O(1).

The only way to do that is to keep a bunch of iterators in the item itself, which is virtually identical to the intrusive container model except it involves more pointers, more heap allocations and introduces an extra invariant into the data model (the iterator stored in the item must point at a list that actually contains said item). And the only benefit you get for all this pain and suffering is that you don't have to do any "funny" casting via container_of() contraptions.

Point being is that once data items sit in more than one container, intrusive container model generally results in a simpler code that is also more efficient.

Re:Intrusive lists in Doom 3 by sharpneli on Thursday December 25, 2014 @07:27AM (#8796117)
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<T> 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.

Re:Intrusive lists in Doom 3 by sbi on Thursday December 25, 2014 @01:07PM (#8796757)
Doesn't std::list<T> generate different code for each type T, at least naively? The generated code could end up taking up more space even if the data structures on which it operates look the same in memory.
Re:Intrusive lists in Doom 3 by huhtenberg on Thursday December 25, 2014 @04:46AM (#8795919)
13.7% on average
Re:Intrusive lists in Doom 3 by dbrower on Thursday December 25, 2014 @11:48PM (#8798087)
73.6% of statistics are made up. I had to look that up: http://www.businessinsider.com/736-of-all-statistics-are-mad...