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

31–40 of 68 posts

Re: Intrusive lists in Doom 3

#31

Post by sorbits »

nly wrote: post #23
sorbits wrote: post #18

Earlier quoted context omitted.

> C++ programmers don't like non-zero-cost abstractions I think you’re confusing zero cost with zero overhead. What C++ programmers like is that the compiler does not add overhead, for example calling `a[10]` will read the word at address `a + 10` and return that. No bounds checks are inserted, no function call is done to lookup the element in some implementation defined sparse data structure, etc. But C++ programmer…

std::map is implemented using a tree and not a hash table because it's specified as an ordered data structure.

I am quite sure (based on interviews I’ve read) that Alexander Stepanov’s primary concern was having a data structure with known (fixed) complexity rather than a sorted container. The latter is just a nice side-effect.

Re: Intrusive lists in Doom 3

#32

Post by nly »

sharpneli wrote: post #28
nly wrote: post #27

Earlier quoted context omitted.

I don't know what you mean. How do you keep an object on multiple lists with only one pair of pointers?

That's the point of intrusive lists. You add a pair of pointers for every list the object is in. So when you do your physics pass using the "moving objects" list the value of the bullet is automatically updated in the "renderable objects" list without having to go trough renderable objects separately. It was explained in the original article "If you want your structure to be in two lists at the same time, you have to…

For games and other micro-optimised uses yeah... super-fine control over where you put your pointer pairs with respect to other data members and cache lines could be warranted. If you're optimising at that level then fine, I'd do it (with Boost Intrusive). Otherwise I'd pick up Boost Multi_Index with a couple of 'sequenced' (linked node) or random_access (vector of pointers) indices. This is non-intrusive and has the construction and overhead you want.

I just wanted to spell out that in most use cases intrusion is a sucky trade-off with no benefit.

Re: Intrusive lists in Doom 3

#34

Post by dbattaglia »

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.

I think they are more likely to feel "tricky and weird" when coming from a higher level language like c++ or Java that has linked list data structures in their standard library.

Re: Intrusive lists in Doom 3

#35

Post by flohofwoe »

valleyer wrote: post #10
Todd wrote: post #6

This approach is more common in lower level software where each allocation is carefully managed. The Linux kernel uses them, for example: http://www.makelinux.net/ldd3/chp-11-sect-5 as does the Windows kernel: http://msdn.microsoft.com/en-us/library/windows/hardware/ff5...

And BSD / OS X. Check out queue(3).

And on AmigaOS, pretty much everything in Exec (the OS kernel) was held together by doubly-linked-lists (of the intrusive kind). Coming from C I'd say that std::list is the 'strange kind' of lists, and intrusive lists are the 'common kind'. On the other hand I haven't been using lists for years, since growable arrays (like std::vector) are almost always faster.

Re: Intrusive lists in Doom 3

#36

Post by pushrax »

jokoon wrote: post #21

I don't understand. Is it really well explained ? Aren't ListNode just a way to index a list ? Isn't this Point2D just "marked" to be on a certain list ? Why does he say "less dereferencing" ? > Dereference the appropriate "next" pointer, get the next object from memory. the prev/next pointer is in the ListNode, not in the object itself, so it's obviously a dereference... I did not understand it very well... I can un…

> 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 certain list ?

The list itself is formed entirely by the ListNodes themselves. There is no backing array to index into; the storage for points (and nodes, which are contained in points) is created with an individual malloc per point. The way you reference a list is by holding a reference to the head, which is just a regular ListNode.

Re: Intrusive lists in Doom 3

#37

Post by simias »

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 you don't have much of a choice to make a generic container but in C++ the templated std::list is much safer.

I'm a bit wary of that article to be honest, it's interesting but it oversells the intrusive list a bit IMO and I can definitely imagine inexperienced C++ coders deciding to use intrusive lists instead of the STL because of it. But at any rate that would be very premature optimization in my book. Even if intrusive lists happen to be faster in a certain use case (and I'd like to see benchmarks before I believe it) I'd feel much more comfortable using std::list while developing/debugging.

Re: Intrusive lists in Doom 3

#38

Post by simias »

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

I'm not saying intrusive lists are never useful but saying that intrusive lists are generally better than the STL is just terrible advice.

I'm not a huge fan of C++ but if there's something I miss dearly when writing C it's generic containers.

Re: Intrusive lists in Doom 3

#39

Post by gsg »

showHNshow wrote: post #25

The article contains many false claims and its main statement that intrusive lists are better than non-intrusive ones is simply wrong. Outright wrong: 1) There is no additional dereferencing needed when using his 'ListNode' implementation, since the object is stored directly in the ListNode. 2) If you want objects to be non-pointer members of ListNodes of several lists, you can achieve that with both intrusive and no…

How exactly can the same object (not a copy) be an element of two non-intrusive lists?

Re: Intrusive lists in Doom 3

#40

Post by julbaxter »

> " Every time a new projectile is created it has to be added to a bunch of lists. 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." Lists can be pre-allocated though
Post reply on HN