2 ms·
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
by sillysaurus3 12y 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 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 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 12y agoThe 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
- sillysaurus3 12y agoYou'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.