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

41–50 of 68 posts

Re: Intrusive lists in Doom 3

#41

Post by btown »

Narishma wrote: post #33

They moved away from intrusive lists to vectors in the BFG edition for performance reasons. More about that here: http://fabiensanglard.net/doom3_documentation/DOOM-3-BFG-Tec...

Very interesting post - it seems that, like many things in computing, intrusive lists make a lot of sense until you start thinking about cache locality. Perhaps on machines of the time, branch prediction was slow enough that conditional code would be a limiting factor... but on modern architectures, it's all about that cache, 'bout that cache, no thrashing.

Re: Intrusive lists in Doom 3

#42

Post by magoghm »

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.

You're not alone. I spent almost 20 years programming with intrusive lists before I ever heard about non-intrusive lists. Of course, they weren't known as "intrusive lists", everybody called them "linked lists".

Re: Intrusive lists in Doom 3

#43

Post by barrkel »

eps wrote: post #2

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…

It depends on whether you have generic code (e.g. map, filter, sort etc.) that you want to apply to the list, vs efficiency concerns, or whether your code needs to iterate through the list from an item.

There's no one true way here. I personally find having a library of operations like map and filter more productive for most code that I write, rather than needing to specialize them per structure.

Re: Intrusive lists in Doom 3

#44

Post by quotemstr »

ars wrote: post #3

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…

That's great until you start caring about address space use or total process commit charge. All you've done is build a dubious special-purpose heap allocator.

Re: Intrusive lists in Doom 3

#45

Post by ant6n »

pushrax wrote: post #36
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…

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.

Re: Intrusive lists in Doom 3

#46

Post by bane »

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.

Yeah, I was expecting some secret magic and it was just a basic linked-list like was used to weed out incoming freshman at my university who couldn't understand pointers.

Re: Intrusive lists in Doom 3

#47

Post by jokoon »

pushrax wrote: post #36
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…

so it's a preallocation technique, a little like an object pool

Re: Intrusive lists in Doom 3

#48

Post by astrobe_ »

It's funny how this technique looks like something coming from a newbie programmer. This reminds me parallel areas. Looks like done by a profane, but hey, it's actually cache-efficient these days.

Re: Intrusive lists in Doom 3

#49

Post by logicallee »

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…

Your contribution would be very welcome here and upvoted, if you kept it factual (your points #1 and #2 are interesting and fine; your speculation that the author heard this elsewhere is almost okay, if you had elaborated.)

But in your last two paragraphs you switch to using the language of trolls ('disgusting example', 'stupid', 'you deserve each other'). no need - you went from being an obvious upvote to an obvious downvote and probably risk being hellbanned. (Where you see your contributions but nobody else does - then nobody can see you no matter how good your points are.)

see commenting guidelines: https://news.ycombinator.com/newsguidelines.html

I hope you will read that and be a positively contributing part of this community.

Re: Intrusive lists in Doom 3

#50

Post by latitude »

CrLf wrote: post #29
sharpneli wrote: post #26

Earlier quoted context omitted.

What about modifying the elements while keeping them on multiple lists? With intrusive list you need only modify any element on a single place (A bullet location as an example). How could you achieve this with std::list?

If you're storing pointers to elements in the list, you only have to change the pointed object.

OK, then.

I'll give you a pointer to an element and you remove it from all containers that it is currently on, in O(1).

The only way to do that is to keep a bunch of iterators in the item itself, which is virtually identical to the intrusive container model except it involves more pointers, more heap allocations and introduces an extra invariant into the data model (the iterator stored in the item must point at a list that actually contains said item). And the only benefit you get for all this pain and suffering is that you don't have to do any "funny" casting via container_of() contraptions.

Point being is that once data items sit in more than one container, intrusive container model generally results in a simpler code that is also more efficient.

Post reply on HN