See also: http://lwn.net/Articles/336255/
(A discussion of Linux data structures, including lists).
Avoiding game crashes related to linked lists
11–20 of 60 posts
Re: Avoiding game crashes related to linked lists
#12One 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.
He mentions that it's fine to call Unlink twice. Presumably the first Unlink zeroes out the prev/next fields.
Indeed, I may have read the code wrong. But look at line 188.
m_prevLink->m_nextNode = m_nextNode;
Re: Avoiding game crashes related to linked lists
#13Before 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 memo…
I 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?
Re: Avoiding game crashes related to linked lists
#14Before 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 memo…
I 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?
Bjarne 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.
Re: Avoiding game crashes related to linked lists
#15What'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 .
I 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.
Re: Avoiding game crashes related to linked lists
#16Earlier quoted context omitted.
He mentions that it's fine to call Unlink twice. Presumably the first Unlink zeroes out the prev/next fields.
Indeed, 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.
RemoveFromList is a private method. All the public methods, other than the destructor, that call it also modify m_prevLink.
Re: Avoiding game crashes related to linked lists
#17There's plenty of discussion relating to the article he references at 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 indi…
THE 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.
Re: Avoiding game crashes related to linked lists
#18Before 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 memo…
Sure, but an ordered list with O(1) removal by an element reference is pretty damn useful (as indirectly confirmed by an abundance of lists in the Linux kernel).
Re: Avoiding game crashes related to linked lists
#19Before 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 memo…
The only problem with std::vector is that you can only belong to one (unless you have a vector of pointers, but that almost negates the whole point).
The way I've typically done this is by having one global "all entities" std::vector and then lists, maps or whatever for specific subsets.
Usually, my "entity" object is little more than a container for behaviours so in reality its a little more complicated than that...
Re: Avoiding game crashes related to linked lists
#20There's plenty of discussion relating to the article he references at 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 indi…
1. Yes.
2. Also the safety. You can include assertions that the object is not a member of a linked list, when you add it to the linked list.
3. A general rule of thumb when using C++ is that you shouldn't use Boost. Boost is a source of major headaches -- even in innocuous looking parts like smart pointers. There are many reasons to avoid it in general, the most important one being compile times, because boost developers are terrible at avoiding creating long compile times. You can reimplement a boost header (for example, for uuid, shared_ptr, intrusive_ptr, and so on) and get a significant compile time speed-up. The other problem with boost libraries is that they lack assertions that are appropriate for software development. For example, with a scoped_ptr, it is better to have an init(T *) method that asserts the object has not been initialized, not just a general reset method, because with most uses of scoped_ptr::reset() (in code that I've worked with) you're expecting it to currently be empty.
(Edit: Also, boost libraries are intimidating because the documentation is bad.)
4. Maybe.