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

21–30 of 60 posts

Re: Avoiding game crashes related to linked lists

#21

Post by nostrademons »

codeka wrote: post #19
Negitivefrags wrote: post #7

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

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.

Re: Avoiding game crashes related to linked lists

#22

Post by quotemstr »

Negitivefrags wrote: post #14
jon6 wrote: post #13

Earlier quoted context omitted.

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.

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

Re: Avoiding game crashes related to linked lists

#23

Post by quotemstr »

shrughes wrote: post #20
beder wrote: post #8

There'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 develo…

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

Re: Avoiding game crashes related to linked lists

#24

Post by shrughes »

quotemstr wrote: post #23
shrughes wrote: post #20

Earlier quoted context omitted.

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

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

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.

Re: Avoiding game crashes related to linked lists

#25

Post by btmorex »

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.

Re: Avoiding game crashes related to linked lists

#26

Post by jasonwatkinspdx »

quotemstr wrote: post #22
Negitivefrags wrote: post #14

Earlier quoted context omitted.

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.

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

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

Re: Avoiding game crashes related to linked lists

#27

Post by ioquatix »

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.

Re: Avoiding game crashes related to linked lists

#28

Post by SideburnsOfDoom »

Negitivefrags wrote: post #7

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

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

Re: Avoiding game crashes related to linked lists

#29

Post by morsch »

huhtenberg wrote: post #17
beder wrote: post #8

There'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.

Store multiple pointers to the same datum?

Re: Avoiding game crashes related to linked lists

#30

Post by pubby »

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 either when std::list and std::list> 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/intr...

Post reply on HN