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

1–10 of 68 posts

Re: Intrusive lists in Doom 3

#2

Post by eps »

Just like that old joke -

  There are two ways to wash dishes -
  after a meal or before it.
Same with data containers, there are two mindsets. Either data is primary and can be optionally organized into containers or containers are primary and they essentially own the data that's put in them. STL model is of latter and "intrusive" lists are of former. I leave it up to you to decide which one is an ass-backward approach in the name of type safety :)

Re: Intrusive lists in Doom 3

#3

Post by ars »

Instead of allocating each element of the list individually you can do this one better.

Allocate an array of elements. The prev and next don't point to memory but to indexes in the array.

How do you handle empty elements? Have a special flag that means "this element is blank" and use prev and next to point to the empty elements in the list! (So you are essentially storing two interleaved lists as the same time.)

Also store the first empty (and first full) element separately of course.

You will need to initialize the memory before you use it, filling all the prev and next pointers for the empty elements.

When you "allocate" an element you just update the prev and next pointers of all 5 elements, as needed.

If you think about it - malloc also needs to store a list of unused memory areas, so despite being a bit more complex you can speed things up quite a bit by doing this.

An optimization: Since filling all the empties can allocate memory, even if you might never use it, have an optimization that if the next pointer is 0 (or -1) that implicitly means the next array index, but an uninitialized index.

By doing this you can allocate a 1GB array without worry, and allow the OS to only fault in pages as needed (i.e. there is no need to ever resize the array).

Re: Intrusive lists in Doom 3

#5

Post by forrestthewoods »

I like intrusive lists. Another consideration is that a std::vector is as fast to iterate over as intrusive list of Foos. The memory access pattern is the same. (Note: typed FooPtr instead of Foo Asterisk because the single asterisk italicized everything)

Another perk is that an element can remove itself from the list without actually having to know anything about the list. This makes a lot of shutdown code super easy and clean.

I do like intrusive lists to be inherited I think. That makes the interface for adding or removing objects from lists super clean. It also eliminates the extra obj pointer since the obj root address is known at compile time. Storing one object in multiple intrusive lists gets a little hairy and you need a tag parameter but that's a relatively rare need in my experience so it's fine.

One thing I don't like is lack of good debugging info in visual studio. For c++ at least their customization tools are seemingly nOT powerful enough to handle intrusive lists well. Not being able to clearly see all objects in the watch window is wildly frustrating. Things that make code harder to debug make me very, very cranky.

Re: Intrusive lists in Doom 3

#8

Post by SamReidHughes »

You can also make these using this structure:

    template 
    struct node { node *next, *prev; };

    template 
    struct intrusive_list : private node { };
Your type foo then subclasses the node type, and in some places intrusive_list has to statically cast them back down.

This means you don't need that messy "T *owner;" pointer anywhere.

The downside is that if you want your type to be a member of multiple intrusive lists, you have to make spurious parent classes and inherit from those.

Re: Intrusive lists in Doom 3

#10

Post by valleyer »

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).
Post reply on HN