Intrusive lists in Doom 3

They moved away from intrusive lists to vectors in the BFG edition for performance reasons. More about that here: <a href="http://fabiensanglard.net/doom3_documentation/DOOM-3-BFG-Technical-Note.pdf" rel="nofollow">http:&#x2F;&#x2F;fabiensanglard.net&#x2F;doom3_documentation&#x2F;DOOM-3-BFG-Tec...</a>

Instead of allocating each element of the list individually you can do this one better.<p>Allocate an array of elements. The prev and next don&#x27;t point to memory but to indexes in the array.<p>How do you handle empty elements? Have a special flag that means &quot;this element is blank&quot; 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.)<p>Also store the first empty (and first full) element separately of course.<p>You will need to initialize the memory before you use it, filling all the prev and next pointers for the empty elements.<p>When you &quot;allocate&quot; an element you just update the prev and next pointers of all 5 elements, as needed.<p>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.<p>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.<p>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).

This approach is more common in lower level software where each allocation is carefully managed. The Linux kernel uses them, for example:<p><a href="http://www.makelinux.net/ldd3/chp-11-sect-5" rel="nofollow">http:&#x2F;&#x2F;www.makelinux.net&#x2F;ldd3&#x2F;chp-11-sect-5</a><p>as does the Windows kernel:<p><a href="http://msdn.microsoft.com/en-us/library/windows/hardware/ff563802%28v=vs.85%29.aspx" rel="nofollow">http:&#x2F;&#x2F;msdn.microsoft.com&#x2F;en-us&#x2F;library&#x2F;windows&#x2F;hardware&#x2F;ff5...</a>

I really prefer intrusive data structures, for the exact reasons outlined in the article.<p>I&#x27;ve myself written many implementations of intrusive structures. But now I&#x27;d like to present the greatest of them, a super-generic implementation of an intrusive AVL tree in C. See [1], and example [2].<p>- It relies on a user-defined concept of a &quot;link&quot;. 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.<p>- 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 &gt;=X. Of course these all have O(log n) time complexity.<p>- 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.<p>[1] <a href="https://github.com/ambrop72/badvpn/tree/master/structure" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;ambrop72&#x2F;badvpn&#x2F;tree&#x2F;master&#x2F;structure</a> (see CAvl_* [2] <a href="https://github.com/ambrop72/badvpn/blob/master/examples/cavl_test.c" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;ambrop72&#x2F;badvpn&#x2F;blob&#x2F;master&#x2F;examples&#x2F;cavl...</a> (also see cavl_test_tree.h in the same dir defining some parameters for the structure)

I like intrusive lists. Another consideration is that a std::vector&lt;FooPtr&gt; 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)<p>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.<p>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&#x27;s a relatively rare need in my experience so it&#x27;s fine.<p>One thing I <i>don&#x27;t</i> 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.

&quot;There can be a lot of projectiles, they appear and disappear quickly, and every time that happens we incur the cost of allocating&#x2F;deallocating memory multiple times.&quot;<p>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&#x27;s unnecessary.

Just like that old joke -<p><pre><code> There are two ways to wash dishes - after a meal or before it. </code></pre> Same with data containers, there are two mindsets. Either data is primary and can be optionally organized into containers or containers are primary and they essentially own the data that&#x27;s put in them. STL model is of latter and &quot;intrusive&quot; lists are of former. I leave it up to you to decide which one is an ass-backward approach in the name of type safety :)

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

You can also make these using this structure:<p><pre><code> template &lt;class T&gt; struct node { node&lt;T&gt; *next, *prev; }; template &lt;class T&gt; struct intrusive_list : private node&lt;T&gt; { }; </code></pre> Your type foo then subclasses the node&lt;foo&gt; type, and in some places intrusive_list&lt;foo&gt; has to statically cast them back down.<p>This means you don&#x27;t need that messy &quot;T *owner;&quot; pointer anywhere.<p>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.

I don&#x27;t understand. Is it really well explained ?<p>Aren&#x27;t ListNode just a way to index a list ? Isn&#x27;t this Point2D just &quot;marked&quot; to be on a certain list ?<p>Why does he say &quot;less dereferencing&quot; ?<p>&gt; Dereference the appropriate &quot;next&quot; pointer, get the next object from memory.<p>the prev&#x2F;next pointer is in the ListNode, not in the object itself, so it&#x27;s obviously a dereference...<p>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 thing about linked lists is their Big O time looks nice, in theory, but in reality they do not work well with how most CPU&#x27;s are designed. (Because it makes the CPU cache mostly useless, and clock speeds aren&#x27;t really improving, so the CPU cache is pretty much the driver of better performance at this point). I&#x27;d rather just use a vector&#x2F;array and take the hit when I need to resize it, most of the time.

Oh, look, it&#x27;s my post :)

Here&#x27;s another example [1] of the same. Blizzard games from WC2 to SC2 use this code nearly verbatim (testing 1 instead of INT_MAX for 64-bit compat in newer titles).<p>1. <a href="http://www.codeofhonor.com/blog/avoiding-game-crashes-related-to-linked-lists" rel="nofollow">http:&#x2F;&#x2F;www.codeofhonor.com&#x2F;blog&#x2F;avoiding-game-crashes-relate...</a>

Wayland also uses intrusive circular linked lists - but it doesn&#x27;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.

It&#x27;s funny how this technique looks like something coming from a newbie programmer. This reminds me parallel areas. Looks like done by a profane, but hey, it&#x27;s actually cache-efficient these days.

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

I think I remember Turbo Pascal&#x27;s container library using a similar approach.

&gt; &quot; Every time a new projectile is created it has to be added to a bunch of lists. There can be a lot of projectiles, they appear and disappear quickly, and every time that happens we incur the cost of allocating&#x2F;deallocating memory multiple times.&quot; Lists can be pre-allocated though

I am somewhat confused by this article since to me it sounds like the writer has wanted the reader to think intrusive lists are &quot;trickier and weird&quot;, when they have been my bread and butter during all my C work... And I guess I am not alone.

The article contains many false claims and its main statement that intrusive lists are better than non-intrusive ones is simply wrong.<p>Outright wrong:<p>1) There is no additional dereferencing needed when using his &#x27;ListNode&#x27; implementation, since the object is stored directly in the ListNode.<p>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).<p>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.<p>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