4 ms·

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

• btown 12y ago
  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.
  • pmr_ 12y ago
    You can strike the intrusive. Your comment is valid for all kinds of linked lists.
    • forrestthewoods 12y ago
      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.
      • btown 12y ago
        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/papers/definition_distr.pdf http://research.microsoft.com/en-us/um/people/trishulc/paper...
  • TillE 12y ago
    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.