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

51–60 of 68 posts

Re: Intrusive lists in Doom 3

#51

Post by pmr_ »

btown wrote: post #41
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.

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

Re: Intrusive lists in Doom 3

#52

Post by TillE »

btown wrote: post #41
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.

Anything involving pointers to arbitrary memory locations sounds great until data locality becomes an issue. Although if such data structures (especially sorted trees) are sufficiently useful, an object pool can help.

But a linked list of any kind should basically never be used when performance matters.

Re: Intrusive lists in Doom 3

#53

Post by overgard »

The thing about linked lists is their Big O time looks nice, in theory, but in reality they do not work well with how most CPU's are designed. (Because it makes the CPU cache mostly useless, and clock speeds aren't really improving, so the CPU cache is pretty much the driver of better performance at this point). I'd rather just use a vector/array and take the hit when I need to resize it, most of the time.

Re: Intrusive lists in Doom 3

#54

Post by dfkf »

sorbits wrote: post #31
nly wrote: post #23

Earlier quoted context omitted.

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.

In the worst case scenario the time complexity of a hash table equals that of its bucket, which doesn't have to be a list. So the only advantage of the map over the unordered_map seems to be the ease of use, it only needs a comparer.

Re: Intrusive lists in Doom 3

#55

Post by sbi »

nly wrote: post #19
andrea_s wrote: post #7

Does anybody know what would the performance gain be in this case?

There isn't one. std::list has the same space requirements, memory locality and capabilities of an intrusive list. Period. The naivety of an 'intrusive' list, where all your objects are always 'list ready', is that it allows the insertion and removal of elements without copying them, which is beneficial if your lists experience a lot of churn. The thing is, you can achieve this without intrusion anyway by keeping all…

Doesn't std::list generate different code for each type T, at least naively? The generated code could end up taking up more space even if the data structures on which it operates look the same in memory.

Re: Intrusive lists in Doom 3

#56

Post by [deleted] »

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…

[deleted]

Re: Intrusive lists in Doom 3

#57

Post by thechao »

dbattaglia wrote: post #34
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.

Higher- or lower- level domains, I feel, would be more accurate; when I code my c-with-templates embedded code there's no STL, so I'm quite aware of intrusive containers, even though I rarely code straight-C. My favorite variant is multiply-included linked lists---which I've seen in a number of one-off embedded JITs.

Re: Intrusive lists in Doom 3

#58

Post by nly »

dfkf wrote: post #54
sorbits wrote: post #31

Earlier quoted context omitted.

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.

In the worst case scenario the time complexity of a hash table equals that of its bucket, which doesn't have to be a list. So the only advantage of the map over the unordered_map seems to be the ease of use, it only needs a comparer.

unordered_map pretty much has to have linked buckets due to its interface and complexity requirements.

Re: Intrusive lists in Doom 3

#60

Post by forrestthewoods »

pmr_ wrote: post #51
btown wrote: post #41

Earlier quoted context omitted.

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.

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