Avoiding game crashes related to linked lists • Hacker News Board

Re: Avoiding game crashes related to linked lists

#31

Post by jd » Mon, Sep 10, 2012, 12:23 PM UTC

pubby wrote: post #30

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…

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

Re: Avoiding game crashes related to linked lists

#32

Post by shrughes » Mon, Sep 10, 2012, 1:17 PM UTC

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.

That's not the only reason. Another is simplicity.

Re: Avoiding game crashes related to linked lists

#33

Post by exDM69 » Mon, Sep 10, 2012, 1:37 PM UTC

jasonwatkinspdx wrote: post #26

quotemstr wrote: post #22

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

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.

Re: Avoiding game crashes related to linked lists

#34

Post by jheriko » Mon, Sep 10, 2012, 1:56 PM UTC

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

Re: Avoiding game crashes related to linked lists

#35

Post by anonymous » Mon, Sep 10, 2012, 2:10 PM UTC

jasonwatkinspdx wrote: post #26

quotemstr wrote: post #22

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

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.

Re: Avoiding game crashes related to linked lists

#36

Post by gsg » Mon, Sep 10, 2012, 2:35 PM UTC

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…

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.

Re: Avoiding game crashes related to linked lists

#37

Post by bradleyjg » Mon, Sep 10, 2012, 2:42 PM UTC

pubby wrote: post #30

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…

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.

Re: Avoiding game crashes related to linked lists

#38

Post by jemfinch » Mon, Sep 10, 2012, 2:44 PM UTC

pubby wrote: post #30

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…

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 his problem and completely unavoidable. On the other hand, std::list> wouldn't change anything at all about the particularly inefficient memory arrangement of std::list; 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.

[0] http://www.codeofhonor.com/blog/tough-times-on-the-road-to-s...

Re: Avoiding game crashes related to linked lists

#39

Post by gsg » Mon, Sep 10, 2012, 2:49 PM UTC

nostrademons wrote: post #21

codeka wrote: post #19

Earlier quoted context omitted.

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

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.

Re: Avoiding game crashes related to linked lists

#40

Post by gsg » Mon, Sep 10, 2012, 2:55 PM UTC

jheriko wrote: post #34

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

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