Avoiding game crashes related to linked lists (2012)(codeofhonor.com)
codeofhonor.com
Avoiding game crashes related to linked lists (2012)
http://www.codeofhonor.com/blog/avoiding-game-crashes-related-to-linked-lists
4 comments
The article is comparing intrusive (see linux's list_head as an example) vs non-intrusive (std::list) lists.
Given that comparison, intrusive lists (which the article appears to argue for over std::list) are almost certainly better (barring some type of list node allocator that can somehow obtain locality with other nearby list nodes).
Once you throw std::vector (or similar dynamic arrays) in, it is a bit different (different trade offs), but that is not what this article is comparing
Given that comparison, intrusive lists (which the article appears to argue for over std::list) are almost certainly better (barring some type of list node allocator that can somehow obtain locality with other nearby list nodes).
Once you throw std::vector (or similar dynamic arrays) in, it is a bit different (different trade offs), but that is not what this article is comparing
You're absolutely right. My apologies.
I was only trying to say that in the context of gamedev, when choosing between list vs vector, list is almost always the worse option due to caching.
But after re-reading, that's completely unrelated, as you say. Worse, ZeroMQ was going to be using list structures either way, so my point about ZeroMQ was both mistaken and irrelevant.
I guess I should take a break for awhile.
I was only trying to say that in the context of gamedev, when choosing between list vs vector, list is almost always the worse option due to caching.
But after re-reading, that's completely unrelated, as you say. Worse, ZeroMQ was going to be using list structures either way, so my point about ZeroMQ was both mistaken and irrelevant.
I guess I should take a break for awhile.
I don't understand how the double-checked locking recommendation is safe. Someone asked about it in the comments, but the response didn't make sense to me. It seems that the call to IsLinked would introduce a data-race with adjacent deletions, and cause undefined behaviour, unless there is already locking at an outer scope. If there is such locking, the lock inside the destructor is redundant. Have I misunderstood?
It has generally been my experience that if control enters a destructor while other threads are concurrently accessing the object, you are in a world of pain. For one thing, this makes it near impossible to safely subclass the object. (Because the subclass destructor will run first, rendering its invariants invalid before the base class has done whatever it needs to do to unlink the object from the outside world.) Anecdotally, I've also found code like this to be deadlock-prone, but I couldn't say for sure if the two are causally linked.
It has generally been my experience that if control enters a destructor while other threads are concurrently accessing the object, you are in a world of pain. For one thing, this makes it near impossible to safely subclass the object. (Because the subclass destructor will run first, rendering its invariants invalid before the base class has done whatever it needs to do to unlink the object from the outside world.) Anecdotally, I've also found code like this to be deadlock-prone, but I couldn't say for sure if the two are causally linked.
>Why not use boost intrusive lists?
Yeah, why not? "The implementation is complex" is not a sensible reason not to use them; it's the complexity of the API one should worry about, and it seems as simple as adding a link subobject. I wonder if the author of this article actually bothered to test the Boost implementation and its performance.
Yeah, why not? "The implementation is complex" is not a sensible reason not to use them; it's the complexity of the API one should worry about, and it seems as simple as adding a link subobject. I wonder if the author of this article actually bothered to test the Boost implementation and its performance.
Most C++ hard core game developers don't even use the STL that comes with the language ... Why do you think they will even consider linking the huge Boost library with their game ? Also, the use of templates is usually a big no - no for most game dev studios.
>Most C++ hard core game developers don't even use the STL that comes with the language ... Why do you think they will even consider linking the huge Boost library with their game ?
Boost has libraries that address specific efficiency concerns like the one the article discusses; the standard library containers don't. You also don't link with the entire Boost library. You link with the components you use, which in the case of a library like intrusive/list is whichever member functions you use from each container instantiation you use. That's a static link, too.
But no, I don't really expect anyone who considers themselves a "hard core" programmer to consider using a library like Boost.
>Also, the use of templates is usually a big no - no for most game dev studios.
Do you have a specific example?
Boost has libraries that address specific efficiency concerns like the one the article discusses; the standard library containers don't. You also don't link with the entire Boost library. You link with the components you use, which in the case of a library like intrusive/list is whichever member functions you use from each container instantiation you use. That's a static link, too.
But no, I don't really expect anyone who considers themselves a "hard core" programmer to consider using a library like Boost.
>Also, the use of templates is usually a big no - no for most game dev studios.
Do you have a specific example?
Well, I know for a fact that the Unreal Engine doesn't use STL. There used to be quite a large variance in the quality of any STL implementation and when you care about each single instruction that gets passed to the CPU, you turn a bit into a control-freak.
Some gamedev's also dislike interacting with STL code because of the metaprogramming in there and the associated error messages produced. Heavy template use makes compilation terribly slow, which is undesirable when you're trying to do a couple of quick iterations of code.
These are issues that can be avoided simply by just not using STL and templates in general, or very sparingly. The downside is that you need to roll your own of everything, with all of the bugs and devtime implied...
Some gamedev's also dislike interacting with STL code because of the metaprogramming in there and the associated error messages produced. Heavy template use makes compilation terribly slow, which is undesirable when you're trying to do a couple of quick iterations of code.
These are issues that can be avoided simply by just not using STL and templates in general, or very sparingly. The downside is that you need to roll your own of everything, with all of the bugs and devtime implied...
Was part 3 ever written?
But it doesn't. It makes your engine slower and more complicated. The reason is because of the CPU cache.
The author tries to brush this under the rug:
When traversing objects stored on an intrusive linked list, it only takes one pointer indirection to get to the object, compared to two pointer indirections for std::list. This causes less memory-cache thrashing so your program runs faster — particularly on modern processors which have huge delays for memory stalls.
They assert the importance of avoiding memory stalls, but then proceed to recommend a technique that will directly cause them: lists.
Particularly troublesome is his recommendation that ZeroMQ should adopt such a strategy. That would mean any app that uses ZeroMQ will inherently suffer from memory fragmentation and cache misses due to this technique.
Here's a conversation about the technical details of why lists are a bad idea: https://news.ycombinator.com/item?id=8939737
An explanation of how CPU caching works, and why lists will ruin your cache performance: https://news.ycombinator.com/item?id=8940270
Lists made sense before CPU pipelines became so deep. Nowadays, once you eliminate algorithmic bottlenecks, the only other bottleneck you can attack is cache performance. And the overall pipeline speedups are sometimes as much as a factor of 2x-5x when you layout your memory allocations to take advantage of caching.