I am somewhat confused by this article since to me it sounds like the writer has wanted the reader to think intrusive lists are "trickier and weird", when they have been my bread and butter during all my C work... And I guess I am not alone.
Intrusive lists in Doom 3
11–20 of 68 posts
Re: Intrusive lists in Doom 3
#12Does anybody know what would the performance gain be in this case?
13.7% on average
Re: Intrusive lists in Doom 3
#13You can also make these using this structure: template struct node { node *next, *prev; }; template struct intrusive_list : private node { }; Your type foo then subclasses the node type, and in some places intrusive_list has to statically cast them back down. This means you don't need that messy "T *owner;" pointer anywhere. The downside is that if you want your type to be a member of multiple intrusive lists, you ha…
One possible alternative is having your objects be members of "lists of slightly different type". For example,
template
struct node {
node *next, *prev;
T& operator*() { return *(this-offset); }
};
class Foo {
int data;
node list1_elem;
node list2_elem;
};
Re: Intrusive lists in Doom 3
#14I like intrusive lists. Another consideration is that a std::vector is as fast to iterate over as intrusive list of Foos. The memory access pattern is the same. (Note: typed FooPtr instead of Foo Asterisk because the single asterisk italicized everything) Another perk is that an element can remove itself from the list without actually having to know anything about the list. This makes a lot of shutdown code super eas…
> 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, because it can be arbitrarily large.
So printing out a linked-list of strings gets two pointer dereferences per string instead of one. I guess that's the cost of abstraction, though.
(This actually fits into the C++ zero-cost-abstraction narrative pretty well, though:
- Linked-lists are not zero cost, - C++ programmers don't like non-zero-cost abstractions, - C++ programmers don't like linked lists.
:)
Re: Intrusive lists in Doom 3
#15You can also make these using this structure: template struct node { node *next, *prev; }; template struct intrusive_list : private node { }; Your type foo then subclasses the node type, and in some places intrusive_list has to statically cast them back down. This means you don't need that messy "T *owner;" pointer anywhere. The downside is that if you want your type to be a member of multiple intrusive lists, you ha…
One possible alternative is having your objects be members of "lists of slightly different type". For example, template struct node { node *next, *prev; T& operator*() { return *(this-offset); } }; Maybe? It has been a while since I've written C++. I guess you have a big problem setting up your base class in a portable way, though, because the types of its member nodes depend on their offsets, and I don't think you c…
I'm not sure if that would work, because computing the offset of list1_elem could depend on the template instantiation of list1_elem because that could (ostensibly) affect the alignment. But you can drop the template altogether on the list element type and put the offsetof expression in the list type declaration. An example of that is linked by some other comment in this thread: http://www.codeofhonor.com/blog/avoiding-game-crashes-relate...
The base class option is, I think, best only for the case where you have only one kind of list you want the object to be part of.
Also your pointer should be cast to char before you do offsetof arithmetic on it.
Re: Intrusive lists in Doom 3
#16I really prefer intrusive data structures, for the exact reasons outlined in the article.
I've myself written many implementations of intrusive structures. But now I'd like to present the greatest of them, a super-generic implementation of an intrusive AVL tree in C. See [1], and example [2].
- It relies on a user-defined concept of a "link". In particular, this means the structure can be in an array and linked with array indices, and can be copied correctly with a single memcpy. Of course the user may still use pointers as links.
- It supports implementation of user-defined associative operations (e.g. sum). This consists of operations: CAvl_AssocSum: Calculate the sum of all the nodes. CAvl_ExclusiveAssocPrefixSum: Calculate the sum of elements from the first one up to but not including node X. CAvl_FindLastExclusiveAssocPrefixSumLesserEqual: Find the first node where the sum of all preceding nodes is >=X. Of course these all have O(log n) time complexity.
- The implementation is made generic by include files which rely on macros a lot. Other than the macro madness, I think this is better then C++ templates, due to easy #if, where in templates one would need to jump through hoops due to non-existence of static_if.
[1] https://github.com/ambrop72/badvpn/tree/master/structure (see CAvl_* [2] https://github.com/ambrop72/badvpn/blob/master/examples/cavl... (also see cavl_test_tree.h in the same dir defining some parameters for the structure)
Re: Intrusive lists in Doom 3
#17I 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.
Re: Intrusive lists in Doom 3
#18I like intrusive lists. Another consideration is that a std::vector is as fast to iterate over as intrusive list of Foos. The memory access pattern is the same. (Note: typed FooPtr instead of Foo Asterisk because the single asterisk italicized everything) Another perk is that an element can remove itself from the list without actually having to know anything about the list. This makes a lot of shutdown code super eas…
> 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++ programmers are generally not opposed to using things that has a cost associated with it (basically everything has a cost) — for example `std::map` is quite popular and certainly not “zero cost”, though it has its running time defined, and the implementation is actually using a self-balancing search tree rather than a hash table because we can give guarantees about the running time of the former, not the latter.
Re: Intrusive lists in Doom 3
#19Does 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 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.
Re: Intrusive lists in Doom 3
#20I 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.