12 ms·
Avoiding game crashes related to linked lists
- xtdx 14y agoOne thing about intrusive lists, you have to know and specify every list the item may be on. Maybe you like that, maybe you don't. Also, it doesn't appear the provided code gracefully handles removing an item from a list twice.
- kevingadd 14y agoHe mentions that it's fine to call Unlink twice. Presumably the first Unlink zeroes out the prev/next fields.
- xtdx 14y agoIndeed, I may have read the code wrong. But look at line 188. m_prevLink->m_nextNode = m_nextNode; I don't see where m_prevLink is changed. If the previous link has gone away, and you call RemoveFromList on this node a second time, it's going to chase that pointer.
- Ogre 14y agoRemoveFromList is a private method. All the public methods, other than the destructor, that call it also modify m_prevLink.
- gsg 14y agoThere's a better trick: point the link structure at itself. This avoids any need to test for null.
- chadnickbok 14y agoI believe this was one of the main things he was actually trying to achieve - By embedding the linked list declarations inside the object, you can make sure to 'balance' all of them in destructors, and from a single place you can ensure that the object is never deleted without all references being removed. I feel like this kind of problem is actually a specific instance of a much larger problem - that being explicit about these things leads to more maintainable code, at the expense of some 'leet things' that can cause troubles if not implemented perfectly.
- eps 14y agoAh, the potent mix of the offsetof and C++. It takes one junior dev to sprinkle a bit of inheritance on top and wonderous things will start happening in your crash-proof code. In other words, it takes much more displine to use embedded data containers instead of embedding ones, the C-style discipline, which is clearly not for everyone.
- eps 14y agoAh, the potent mix of the offsetof and C++. It takes one junior dev to sprinkle a bit of inheritance on top and wonderous things will start happening in your crash-proof code. In other words, it takes much more displine to use embedded data containers instead of embedding ones, the C-style discipline, which is clearly not for everyone.
- Negitivefrags 14y agoBefore you consider intrusive lists, in fact, before you consider almost any other data structure, try a vector. People grossly overestimate the cost of vector relocation while underestimating the benefits of cache coherency. Vector relocation is so cheap because all the bits are in the cache. You can relocate all the elements in a reasonably sized vector faster than you can dereference a pointer to somewhere in memory that isn't in cache. If you want log(n) lookup like a set/map you can keep the vector sorted. If you want fast erase (and don't care about order) you can move the last element to the middle and resize down by one (no memory allocation). The <algorithm> header makes these operations trivial. C++11 move semantics mean that there are a lot of types you can keep by value in a vector that you wouldn't have before and they stay fast.
- jon6 14y agoI agree, although I have never had a performance bottleneck related to std::list that required a move to std::vector. Do you know at what point std::set becomes more optimal (in some dimension) than std::vector?
- Negitivefrags 14y agoBjarne Stroustrop showed in a presentation a while back that std::list never becomes more optimal than std::vector regardless of size. Edit: Sorry, I read your comment incorrectly. Instead of std::set I would use a sorted vector without thought for anything up a thousand elements or so. After that it's probably worth profiling. Vector is probably still good even quite a good way after that depending on your use case.
- quotemstr 14y ago> Bjarne Stroustrop showed in a presentation a while back that std::list never becomes more optimal than std::vector regardless of size. Until memory fragments and you can't allocate a contiguous block for a big vector.
- 14y ago
- beder 14y agoThere's plenty of discussion relating to the article he references at http://news.ycombinator.com/item?id=4455225 http://news.ycombinator.com/item?id=4455225, and much of the same applies here. 1. He's not comparing apples-to-apples between `std::list` and his intrusive linked list; the proper analogue would be to unlink a node from its iterator, for which the running time is still O(1). 2. The main (only?) reason to use intrusive lists is for the single indirection (which helps both memory and speed). In his example for how using std::list would crash his server because of the O(N) node removal, he's just not storing the right data for each connection (again, use an iterator). 3. He looked at boost's intrusive list, but I'm guessing he didn't actually try it out. The examples are pretty good, and it's much easier than it "looks". (That is, boost libraries can look intimidating when you first look at them because they're so template-heavy.) 4. It may even be that a vector, plus an auxiliary data structure for lookup, may be faster.
- huhtenberg 14y agoTHE reason to use "intrusive" containers is to let a piece of data to sit in multiple containers, none of which is primary. I'll give you an skbuff and you show me how to put it on several linked lists and a couple of hashmaps with STL-style containers.
- shrughes 14y ago
- kev009 14y agoWhat's funny is he mentions the ZMQ in C entries as an impetuous but then essentially writes the list the way any novice C programmer _would_ (vs. expert/"leet" C++ prgorammers from the article). To me, this unwittingly plays into the "why ZMQ would be better in C" meme far more than the other way around :o) See also <sys/queue.h>.
- ChuckMcM 14y agoI think that is somewhat intentional. C++ obfuscation gives folks a false sense of security about what they are doing. C programmers come out of school realizing they have to be careful. Nothing quantifiable mind you, just my experience in hiring them.
- fusiongyro 14y agoI'm not a game programmer and I seldom use C or C++, but I don't find the article particularly convincing. If the motivation is to reduce bugs caused by additional allocations, he wouldn't be avoiding boost or suggesting a copy-and-paste job with his off-the-cuff locking regime. If the motivation is really performance, it seems like one should consider other data structures such as std::vector. Part of the reason to use std::list et. al. is to benefit from the STL functions—hand-writing remove, find, sort, etc. is additional code which will need to be made correct and performant and maintained internally. I understand game programming is a very different enterprise with very different tradeoffs and motivations, but I don't feel well-sold for "pedestrian" application development.
- ericbb 14y agoSee also: http://lwn.net/Articles/336255/ http://lwn.net/Articles/336255/ (A discussion of Linux data structures, including lists).
- btmorex 14y agoI think there is a subtle bug in his second two person::~person examples. Specifically, from the perspective of other threads an object is no longer valid once its destructor has been called. So, imagine two person objects side-by-side in a linked list. If they are both deleted simultaneously and both destructors get called at the same time, they can no longer safely unlink from each other even with locking because they are technically no longer valid. The first two examples don't have this problem though.
- ioquatix 14y agoWhile valid and useful in specific cases, I think that this approach is short-sighted in general. In-place algorithms can lead to significant problems as it is typically hard to enforce strong invariants during the game update loop. In many cases, you wouldn't be erasing elements except as a final step in your game update loop anyway, and you can normally do this as part of a loop where you'd have access to the non-intrusive iterator which can then be removed O(1). I see little benefit to using intrusive linked-lists in this context.
- pubby 14y agoThe reason this guy thinks std::list is buggy is because he's using it incorrectly. There's not reason to write removal functions like delete_person when they already exist with list::remove, list::erase, find, search, etc. There's no reason to use std::list<foo*> either when std::list<foo> and std::list<std::unique_ptr<foo>> work just as well. His example code is very dubious as it looks like C-with-classes rather than C++, mostly due to the lack of RAII. Intrusive lists are still worth knowing and using, it's just that the author's reasoning was terrible. I found the Boost.Intrusive page to be much more knowledgeable: http://www.boost.org/doc/libs/1_35_0/doc/html/intrusive/intrusive_vs_nontrusive.html http://www.boost.org/doc/libs/1_35_0/doc/html/intrusive/intr...
- jd 14y agoI don't think it's fair to say the author's reasoning is terrible. A blogpost is always written for some specific audience, and in this case it looks like the blog post was targeted at programmers generally, not C++ experts. I agree that constructs like std::some_container<T*> are almost never the optimal solution. And yes, with RAII locks can be freed in the destructor, which rules out a class of mistakes. The main things to take away from the blogpost were, I think, the concept of intrusive lists, to think about what objects look like in memory, and how you can construct code so that an object can be part of multiple containers and can remove itself from all of them when it's destroyed. Those are certainly concepts worth talking about, and so I think the blogpost was pretty great.
- bradleyjg 14y agoThis article is one in a series dealing with problems that arose out of programming Starcraft in the mid-90s. There was no unique_ptr back then, and it was rare to find even junior programmers that were native c++'ers.
- pubby 14y agoActually this seems to be from Guild Wars which was from 2005. IIRC when he talked about Starcraft developement the team just used pointer structs with no abstractions.
- 14y ago
- jheriko 14y ago'best defence, no be there' linked lists are seldom the right answer, contiguous blocks of memory are cache - and therefore algorithm - friendly. the stl performance is usually quite easy to beat in special cases as well (i.e. all game code). some stls are terrible as well - the ms one is riddled with locks and all sorts of sledgehammer thread safety measures, which you just don't need if you know which bits of code are threaded and which arent.
- gsg 14y agoLinked lists are appropriate when you need (usually multiple) sequences of pointers to objects: thus, the real alternative is not vector of t but vector of pointer to t. A vector of pointers gives no contiguity advantage over an intrusive list during traversal (or any other operation).
- ggchappell 14y agoThis points out a real problem, but It think it seems a bit confused about what the problem actually is. In particular, this isn't something "wrong" with std::list. He has a situation where he wants an object to manage its own membership in a mutable container. He says you can't do this efficiently with a simple non-intrusive linked list. He is right. You also can't do it efficiently with an array (std::vector, in this context). You can do it efficiently with an intrusive linked list, as he points out. You can also use a non-intrusive linked list in which each object holds an iterator to itself. Or you can use an associative structure (std::map, std::unordered_map), in which each object holds its own key. The instrusive linked list solution is going to have the fastest container insert & delete operations of all of these. But that doesn't mean it is the best solution for every circumstance. Another point to be made, which he kinda-sorta gets at, is that it is a good idea to know how to code a linked list. The bulk of data structure decisions are just figuring out what already written package to use. But there is definitely still a place for a custom, application-specific linked list, and these are not difficult to write.
- Evbn 14y agoAnd yet the classic old "code a linked list" problem is now a reviled and banned interview question at enlightened tech firms....
- cpeterso 14y agoEA open-sourced their EASTL game-optimized container library back in 2007, including intrusive lists. Here is a detailed introduction: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n227... And a github repository that is still maintained: https://github.com/paulhodge/EASTL https://github.com/paulhodge/EASTL
- Luyt 14y agoReliability is more important than speed, and if you’re reduced to using those hacks for speed-gains your program needs help. Remember Y2K bugs! I think the reason for dropping centuries from dates was not to gain speed, but to save two bytes. In the 70's of previous millennium, two bytes of storage would cost a lot more than today, and also space on punch cards was limited.