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

Intrusive lists in Doom 3

gpfault.net

Post reply on HN
Print view View original

61–68 of 68 posts

Re: Intrusive lists in Doom 3

#61

Post by ambrop7 »

simias wrote: post #38
ambrop7 wrote: post #16

I really prefer intrusive data structures, for the exact reasons outlined in the article. I've myself written many implementations of intrusive structures. But now I'd like to present the greatest of them, a super-generic implementation of an intrusive AVL tree in C. See [1], and example [2]. - It relies on a user-defined concept of a "link". In particular, this means the structure can be in an array and linked with…

> The implementation is made generic by include files which rely on macros a lot. Other than the macro madness, I think this is better then C++ templates, due to easy #if, where in templates one would need to jump through hoops due to non-existence of static_if. And either throw away type safety completely or end up with a huge macro soup (which is even worse to debug than template soup). I also don't understand your…

Well I don't want to get into a flame-war regarding intrusive/containing or C/C++, but I will say that type safety and intrusive/container are orthogonal things. One can have a type-unsafe container as well as a type-safe (generic!) intrusive structure. See my code for proof :) I think we'll agree that it's not too complicated and easy to use.

Implementation: https://github.com/ambrop72/aprinter/blob/master/aprinter/st...

Usage: https://github.com/ambrop72/aprinter/blob/master/aprinter/sy... (the BusyEventLoop keep track of QueuedEvent objects).

If you wonder what's the purpose of the Accessor, it's for when you can't use the simple member-pointer based interface due to C++'s eager evaluation, and can hack around it with forward declaration of a custom Accessor class, followed by the complete definition later.

I think Boost intrusive structures are type safe too, but I'm not 100% sure. But Boost is another matter altogether.

Re: Intrusive lists in Doom 3

#62

Post by failrate »

"There can be a lot of projectiles, they appear and disappear quickly, and every time that happens we incur the cost of allocating/deallocating memory multiple times."

I write a lot of shoot-em-ups (both 2d and 3d). I never do this. I preallocate all of the bullet entities on level initialization and never destruct them during runtime. If the number is large enough, I do sort them by status (alive or dead) and exit processing when I encounter a dead projectile, but usually that's unnecessary.

Re: Intrusive lists in Doom 3

#63

Post by desdiv »

ant6n wrote: post #45
pushrax wrote: post #36

Earlier quoted context omitted.

> the prev/next pointer is in the ListNode, not in the object itself, so it's obviously a dereference... The ListNode is embedded in the Point, so their storage is actually combined. The memory layout would be something like 0x0 x 0x4 y 0x8 next 0xc prev 0x10 owner with the total structure being 20 bytes if pointers are 32-bit. > Aren't ListNode just a way to index a list ? Isn't this Point2D just "marked" to be on a…

If you use a std::List , doesn't it uses nodes like T data p next p previous p owner anyway? It shouldn't create a pointer to the data, just like a std::vector isn't an array of pointers to T.

Let's say I have a bunch of Bullet objects, and each Bullet belongs to multiple lists. In that case, std::list doesn't work and I have to use std::list instead, thus the extra pointer dereference.

Re: Intrusive lists in Doom 3

#64

Post by SamReidHughes »

ant6n wrote: post #45
pushrax wrote: post #36

Earlier quoted context omitted.

> the prev/next pointer is in the ListNode, not in the object itself, so it's obviously a dereference... The ListNode is embedded in the Point, so their storage is actually combined. The memory layout would be something like 0x0 x 0x4 y 0x8 next 0xc prev 0x10 owner with the total structure being 20 bytes if pointers are 32-bit. > Aren't ListNode just a way to index a list ? Isn't this Point2D just "marked" to be on a…

If you use a std::List , doesn't it uses nodes like T data p next p previous p owner anyway? It shouldn't create a pointer to the data, just like a std::vector isn't an array of pointers to T.

Only without the owner pointer. But intrusive lists don't need an owner pointer either.

Re: Intrusive lists in Doom 3

#65

Post by btown »

forrestthewoods wrote: post #60
pmr_ wrote: post #51

Earlier quoted context omitted.

You can strike the intrusive. Your comment is valid for all kinds of linked lists.

Hell it's valid for everything period. Even vectors! Splitting struct a into hot/cold chunks is pretty common. Minimize the sise of data being iterated on to maximize cache usage. Can result in big wins.

Huh, hadn't heard of hot/cold struct splitting before. This paper seems to indicate it has a nontrivial effect even in Java code: http://research.microsoft.com/en-us/um/people/trishulc/paper...

Re: Intrusive lists in Doom 3

#66

Post by dietrichepp »

simias wrote: post #37
mahouse wrote: post #11

I am somewhat confused by this article since to me it sounds like the writer has wanted the reader to think intrusive lists are "trickier and weird", when they have been my bread and butter during all my C work... And I guess I am not alone.

They are trickier though because you either have to create a new type for each list and all all accompanying functions to work on that type (the PointListNode in the article) or you can make it more generic by discarding type safety and using tricks like "container_of" (that's actually my preferred approach when writing C, at least it lets me use the linux kernel's list.h and I don't have to reinvent the wheel). In C…

The problem with std::list is that it's almost always worse than the alternatives. I would recommend using std::vector as the "default" container, and then use another container if the performance of std::vector is not good enough. Or, put another way, I think std::list is a premature optimization, because you are saying that insertions and deletions are frequent enough that you need them to be O(1), even at the expense of extra memory usage and tons of cache misses for simple traversal.

The std::vector container will outperform std::list surprisingly often. Just think of std::vector as your default container.

Re: Intrusive lists in Doom 3

#68

Post by enjoy-your-stay »

failrate wrote: post #62

"There can be a lot of projectiles, they appear and disappear quickly, and every time that happens we incur the cost of allocating/deallocating memory multiple times." I write a lot of shoot-em-ups (both 2d and 3d). I never do this. I preallocate all of the bullet entities on level initialization and never destruct them during runtime. If the number is large enough, I do sort them by status (alive or dead) and exit p…

Do you pre-allocate all bullets per shooter? Or have one big bucket that all shooters use?

I take it that having a finite number of bullets in the game at any time is obviously an acceptable trade-off.

Post reply on HN