Avoiding game crashes related to linked lists (2012)

http://www.codeofhonor.com/blog/avoiding-game-crashes-related-to-linked-lists

by davedx • 12 years ago

33 9 12 years ago

Then I’m going to share techniques (with source code) to make your game engine code simpler, faster, more memory efficient and more reliable. Wow!

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.

codys• 12 years ago

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

sillysaurus32• 12 years ago

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.

ntumlin• 12 years ago

Was part 3 ever written?

sjolsen2• 11 years ago

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.

AlexeyBrin• 11 years ago

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.

sjolsen2• 11 years ago

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?

clockworkweeble• 11 years ago

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.

Avoiding game crashes related to linked lists (2012)

Related Stories