Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Avoiding game crashes related to linked lists

codeofhonor.com

Post reply on HN
Print view View original

51–60 of 60 posts

Re: Avoiding game crashes related to linked lists

#51

Post by jemfinch »

pubby wrote: post #49
jemfinch wrote: post #38

Earlier quoted context omitted.

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 , 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…

> 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…

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.

Re: Avoiding game crashes related to linked lists

#52

Post by pubby »

jemfinch wrote: post #51
pubby wrote: post #49

Earlier quoted context omitted.

> 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…

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…

Shot him a quick email for clarification:

> "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."

Re: Avoiding game crashes related to linked lists

#53

Post by ggchappell »

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.

Re: Avoiding game crashes related to linked lists

#54

Post by gsg »

phaedrus wrote: post #45
gsg wrote: post #39

Earlier quoted context omitted.

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 .

Given a pointer to an object, remove from an intrusive list is three memory accesses: only tiny vectors will give faster operations than that.

Insertion favors intrusive lists even more: allocation and copy free!

Re: Avoiding game crashes related to linked lists

#55

Post by jasonwatkinspdx »

exDM69 wrote: post #33
jasonwatkinspdx wrote: post #26

Earlier quoted context omitted.

64bit memory spaces are pretty hard to fragment to that degree, but it could be a concern on smaller embedded systems still.

It's the physical memory that fragments, not the virtual address space. So it's about the amount of physical memory available, not address sizes.

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.

Re: Avoiding game crashes related to linked lists

#56

Post by jasonwatkinspdx »

anonymous wrote: post #35
jasonwatkinspdx wrote: post #26

Earlier quoted context omitted.

64bit memory spaces are pretty hard to fragment to that degree, but it could be a concern on smaller embedded systems still.

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.

Re: Avoiding game crashes related to linked lists

#57

Post by shrughes »

omnigoat wrote: post #41
shrughes wrote: post #24

Earlier quoted context omitted.

Um, compile times are still a problem with modern compilers. And regarding scoped_ptrs: you want what, fewer assertions? Okay... that's very counterproductive of you.

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. W…

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.)

Re: Avoiding game crashes related to linked lists

#58

Post by Evbn »

ggchappell wrote: post #53

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 th…

And yet the classic old "code a linked list" problem is now a reviled and banned interview question at enlightened tech firms....

Re: Avoiding game crashes related to linked lists

#59

Post by cpeterso »

EA 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/n227...

And a github repository that is still maintained:

https://github.com/paulhodge/EASTL

Re: Avoiding game crashes related to linked lists

#60

Post by Luyt »

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.

Post reply on HN