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

41–50 of 60 posts

Re: Avoiding game crashes related to linked lists

#41

Post by omnigoat »

shrughes wrote: post #24
quotemstr wrote: post #23

Earlier quoted context omitted.

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

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

Re: Avoiding game crashes related to linked lists

#42

Post by gsg »

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…

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.

As for std::list... it's useless.

Re: Avoiding game crashes related to linked lists

#43

Post by gsg »

morsch wrote: post #29
huhtenberg wrote: post #17

Earlier quoted context omitted.

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?

Then for deletion you need to traverse every data structure in which you store said pointers.

Re: Avoiding game crashes related to linked lists

#44

Post by gsg »

kevingadd wrote: post #5
xtdx wrote: post #2

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

There's a better trick: point the link structure at itself. This avoids any need to test for null.

Re: Avoiding game crashes related to linked lists

#45

Post by phaedrus »

gsg wrote: post #39
nostrademons wrote: post #21

Earlier quoted context omitted.

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.

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.

Re: Avoiding game crashes related to linked lists

#46

Post by cygx »

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 .

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

Re: Avoiding game crashes related to linked lists

#47

Post by SeanDav »

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…

If you bothered doing a bit of research rather than jumping on some sort of bandwagon you would have realized:

- "this guy" is actually a highly experienced and competent programmer.

- He programs games, with often very specific domain requirements and challenges. Try to understand context before making sweeping generalizations.

Re: Avoiding game crashes related to linked lists

#48

Post by pubby »

bradleyjg wrote: post #37
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.

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.

Re: Avoiding game crashes related to linked lists

#49

Post by pubby »

jemfinch wrote: post #38
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…

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

Re: Avoiding game crashes related to linked lists

#50

Post by pubby »

SeanDav wrote: post #47
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…

If you bothered doing a bit of research rather than jumping on some sort of bandwagon you would have realized: - "this guy" is actually a highly experienced and competent programmer. - He programs games, with often very specific domain requirements and challenges. Try to understand context before making sweeping generalizations.

Where did I make a sweeping generalization? I definitely where the author made some!
Post reply on HN