Before 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.
Vector is a fine data structure, but doesn't do the same job.
The purpose of intrusive linked lists is to provide constant time, allocation-free insert/remove from multiple sequences that all refer to the same object (identity, not value), given only a pointer to the object.
Multiple vectors obviously don't provide this, since vectors contain objects by value. Multiple vectors of pointers can work, but then removal requires either an iterator or a linear scan for each vector. If your object is in many lists at once, that gets pretty messy.
In particular the way that game engines use this, with objects packed in preallocated arrays, gives constant time insertion and deletion from multiple sequences with absolutely zero allocation or copying at any time. Vectors simply do not provide this functionality.
Traversing a vector of pointers isn't much less efficient than traversing an intrusive linked list, and is significantly more efficient than traversing a normal linked list. With a vector of pointers, you need to do an arithmetic operation (usually on a register), a dereference to L1 cache (to fetch the pointer), and a dereference to main memory (to fetch the object). With an intrusive linked list, it's just a dereference to main memory. With a normal linked list, it's 2 dereferences to main memory, one for the link and one for the object. On most processors, accessing cache and performing address arithmetic takes a tiny fraction of the time that accessing RAM does, so for practical purposes your vector-of-pointers and intrusive linked list implementations should be pretty similar in performance.
If you can own the objects in one by-value vector, that's even better, then traversing over them involves only address arithmetic on objects that are already probably in the cache.
You forgot insertion and removal, which intrusive lists provide in constant time and vectors do not.
If you can own the objects, linked list (of any kind) is usually not appropriate. The essence of the efficiency of an intrusive linked list is that the same indirection that must point at an object that is not owned is reused to give the list structure. Without this trick, linked lists are not much good.
Again, you're not getting the point. Constant time != "fast", it just has to do with how the operation scales with N. The point, though counter intuitive, is that the constant time of the list operation is larger than the linear time of the vector operation for many values of N.
> The point, though counter intuitive, is that the constant time of the list operation is larger than the linear time of the vector operation for many values of N.
Citation needed. The kernel guys in particular would probably be interested in a faster alternative to intrusive linked lists.
Keep in mind that we're talking about vectors of pointers due to the problem domain (multiple lists of potentially large or polymorphic objects), so using vectors won't really help locality.
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).
Excellent response, and it's also why the standard class called "List" in many toolkits (Delphi and .Net for e.g.) are equivalent to a C++ vector - essentially a smart array with capacity management ( http://msdn.microsoft.com/en-us/library/y52x03h2.aspx ).
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.
If memory serves me right, even on 64bit, the standard malloc won't allow you to grab a chunk larger than about 2G. You can still have as many chunks as you like, but you can't have a single chunk larger than that. Of course, you can always use a different memory manager.
Depends on your platform, libc version, compiler, etc. Anything recent should default to just passing through to mmap for allocations that are a small multiple of page size or larger, and on 64bit systems you can happily mmap huge regions.
He said big vectors. You're talking about sub-page fragmentation.
Big vectors inherently avoid sub-page fragmentation because they're allocated directly via mmap. The only thing that matters is having unreserved address space, and 64bit gives you a lot.
What you say is true for a worst case load of millions of vectors that are larger than half of the mmap threshold size (typically roughly page size or a small multiple of it). So this might just be a semantic disagreement, but I don't think of millions of 3KB vectors as 'big' vs a smaller number of MB or GB vectors.
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.
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<T>::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.)
> A general rule of thumb when using C++ is that you shouldn't use Boost.
That's not a rule of thumb. It may be something you do, and a reason I'd never work with you. Boost is a wonderful library that IME solves far more problems than it creates. Compile times aren't a problem with modern compilers, and your scoped_ptr example is nonsense.
I don't get your reasoning (mainly because all you've provided none). I wrote games, we used Boost heavily, on the PC, Xbox360, DS, Wii and PSP. I mean really heavily. Boost.Thread, Boost.SmartPtr, Boost.Bind, Boost.Function, Boost.MultiSet, Boost.Array, Boost.PreProcessor, Boost.LexicalCast... (more)...
We turned off exceptions (BOOST_NO_EXCEPTION) because the Wii and the DS didn't support exceptions. That was it. We never had a problem with spurious assertions, nor with unexpected behaviour from a lack of assertions. Compile times were about 5 to 7 minutes for partial builds. A full build was longer (I forget), something like 15. This is a huge code base, remember.
I honestly have no idea what you're talking about. It's certainly not a "general rule of thumb".
The fact that there are people who use boost heavily is not news to me. So if you're confused by my assertion that everybody avoids boost as a general rule, well, I'm confused as to why you believe I made such an assertion.
(Note that I don't completely avoid Boost either. The thing is, the parts that are nice to use are simple enough to reimplement more situation-appropriately, and the other parts, I'll use, but I'll use them with trepidation, and if I don't feel like thinking about whether they might be useful, avoid them. For example, it's better to write a recursive descent parser than it is to use Spirit, and it's better to write your own serialization stuff than to use Boost Serialization (if only for compile times, but also, there's some disturbing complexity hidden in that library). I don't exactly know how you use LexicalCast without exceptions turned on, but if you're going in the int->string direction I generally use a printf-like function that returns a std::string.)
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.
Ah, 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.
What'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)
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.
The 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.
The reason you think this guy is using std::list incorrectly is because you're not thinking about his requirements. Instead of spending a few seconds to understand why he would keep a std::list<foo* >, you immediately ran back to HN to make a comment about it.
He's a game programmer. He's keeping pointers to instances because these entities are part of an inheritance hierarchy[0]. That level of indirection is essential to his problem and completely unavoidable. On the other hand, std::list<std::unique_ptr<foo>> wouldn't change anything at all about the particularly inefficient memory arrangement of std::list<foo* >; std::unique_ptr is, after all, just a class with one pointer member.
When smart people write things you think are obviously dumb, you should invest some additional time trying to understand the context of their statements before writing them off. You'll learn more, and you won't come off as a flippant junior developer.
> The reason you think this guy is using std::list incorrectly is because you're not thinking about his requirements.
The reasoning and requirements for him using intrusive lists was quite clear to me. The remaining article that starts at "Using intrusive lists" I found quite interesting and insightful.
My entire argument is against his evidence backing up statements like, "If you’re a programmer who uses the C++ STL std::list, you’re doing it wrong." It's unfair to improperly use std::list, compare it to a better solution, and then make a sweeping generalization. That's just outrageous.
It's clear from the subtitle of the blog ("Game design, game programming, deployment automation and more"), the title of the specific blog post, ("Avoiding game crashes related to linked lists"), and the very next paragraph of your quotation ("Based on watching the successes and failures of programmers writing games like Starcraft and Guild Wars...") that the author is talking about a very specific technique applied to a very specific sort of programming, and yet you're still complaining that he is making "a sweeping generalization"?
Stop wasting your time and ours arguing about an interpretation of his words the author never intended. Such literalistic argument-making serves only to mislead and misdirect, and it contributes nothing to the conversation.
> "Is "std::list considered harmful" in the general field of C++ or are
you only talking about the very specific game programming field you
used it for?"
> "I think it's harmful for all programming, but if you read the comments you'll find almost as many different opinions on the subject as comments!
The problem is that manually managing lists is error-prone, which is why I use a solution that automatically handles them; I think all programs, not just games, would benefit from their use."
I 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.
If you read the article with more sympathy, you will notice that he is using RAII, I think rather cleverly, to automate removal of an object from the intrusive lists contained within it. This is a interesting improvement over the venerable list.h style approach most C programmers take.
This 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.
Actually 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.
I'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.
This 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.
I 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.
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.
While 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.
I 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.
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.
Linked 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).
Reliability 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.
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.