Hacker News Reader

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

View on HN

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.

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

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.

Reply on news.ycombinator.com