Intrusive lists in Doom 3
gpfault.net
gpfault.net
But a linked list of any kind should basically never be used when performance matters.
Allocate an array of elements. The prev and next don't point to memory but to indexes in the array.
How do you handle empty elements? Have a special flag that means "this element is blank" and use prev and next to point to the empty elements in the list! (So you are essentially storing two interleaved lists as the same time.)
Also store the first empty (and first full) element separately of course.
You will need to initialize the memory before you use it, filling all the prev and next pointers for the empty elements.
When you "allocate" an element you just update the prev and next pointers of all 5 elements, as needed.
If you think about it - malloc also needs to store a list of unused memory areas, so despite being a bit more complex you can speed things up quite a bit by doing this.
An optimization: Since filling all the empties can allocate memory, even if you might never use it, have an optimization that if the next pointer is 0 (or -1) that implicitly means the next array index, but an uninitialized index.
By doing this you can allocate a 1GB array without worry, and allow the OS to only fault in pages as needed (i.e. there is no need to ever resize the array).
http://www.makelinux.net/ldd3/chp-11-sect-5
as does the Windows kernel:
http://msdn.microsoft.com/en-us/library/windows/hardware/ff5...
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)
And either throw away type safety completely or end up with a huge macro soup (which is even worse to debug than template soup). I also don't understand your static_if remark.
I'm not saying intrusive lists are never useful but saying that intrusive lists are generally better than the STL is just terrible advice.
I'm not a huge fan of C++ but if there's something I miss dearly when writing C it's generic containers.
Implementation: https://github.com/ambrop72/aprinter/blob/master/aprinter/st...
Usage: https://github.com/ambrop72/aprinter/blob/master/aprinter/sy... (the BusyEventLoop keep track of QueuedEvent objects).
If you wonder what's the purpose of the Accessor, it's for when you can't use the simple member-pointer based interface due to C++'s eager evaluation, and can hack around it with forward declaration of a custom Accessor class, followed by the complete definition later.
I think Boost intrusive structures are type safe too, but I'm not 100% sure. But Boost is another matter altogether.
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 easy and clean.
I do like intrusive lists to be inherited I think. That makes the interface for adding or removing objects from lists super clean. It also eliminates the extra obj pointer since the obj root address is known at compile time. Storing one object in multiple intrusive lists gets a little hairy and you need a tag parameter but that's a relatively rare need in my experience so it's fine.
One thing I don't like is lack of good debugging info in visual studio. For c++ at least their customization tools are seemingly nOT powerful enough to handle intrusive lists well. Not being able to clearly see all objects in the watch window is wildly frustrating. Things that make code harder to debug make me very, very cranky.
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.
:)
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.
I write a lot of shoot-em-ups (both 2d and 3d). I never do this. I preallocate all of the bullet entities on level initialization and never destruct them during runtime. If the number is large enough, I do sort them by status (alive or dead) and exit processing when I encounter a dead projectile, but usually that's unnecessary.
I take it that having a finite number of bullets in the game at any time is obviously an acceptable trade-off.
There are two ways to wash dishes -
after a meal or before it.
There's no one true way here. I personally find having a library of operations like map and filter more productive for most code that I write, rather than needing to specialize them per structure.
It makes the job much easier.
template <class T>
struct node { node<T> *next, *prev; };
template <class T>
struct intrusive_list : private node<T> { };
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 have to make spurious parent classes and inherit from those.
template <ptrdiff_t offset, class T>
struct node {
node<offset> *next, *prev;
T& operator*() { return *(this-offset); }
};
class Foo {
int data;
node<offsetof(Foo, list1_elem), Foo> list1_elem;
node<offsetof(Foo, list2_elem), Foo> list2_elem;
};
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.
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 ?
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
> 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.
T data
p next
p previous
p owner
1. http://www.codeofhonor.com/blog/avoiding-game-crashes-relate...
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.
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?
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.
I just wanted to spell out that in most use cases intrusion is a sucky trade-off with no benefit.
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.
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.
In C you don't have much of a choice to make a generic container but in C++ the templated std::list is much safer.
I'm a bit wary of that article to be honest, it's interesting but it oversells the intrusive list a bit IMO and I can definitely imagine inexperienced C++ coders deciding to use intrusive lists instead of the STL because of it. But at any rate that would be very premature optimization in my book. Even if intrusive lists happen to be faster in a certain use case (and I'd like to see benchmarks before I believe it) I'd feel much more comfortable using std::list while developing/debugging.
The std::vector container will outperform std::list surprisingly often. Just think of std::vector as your default container.
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
But in your last two paragraphs you switch to using the language of trolls ('disgusting example', 'stupid', 'you deserve each other'). no need - you went from being an obvious upvote to an obvious downvote and probably risk being hellbanned. (Where you see your contributions but nobody else does - then nobody can see you no matter how good your points are.)
see commenting guidelines: https://news.ycombinator.com/newsguidelines.html
I hope you will read that and be a positively contributing part of this community.