Why aren't linked lists more common data structures for enemies?

Question

I was recently listen to a talk that Jonathan Blow gave, you can find it here. In the talk, he was talking about what data structures he (and he seemed to imply many others) use, and why. Which is to say that he simply used arrays to store data, and use the naive approach to find data in it, meaning iterate through the array until you found what you wanted, assuming it wasn't in a performance critical place in the code. He gave the example of loading data from a wad file in doom, which while fast, still took that naive approach (at least according to the talk, I haven't looked at the source code since I have not a clue to where I should begin). The reason he gave for this was because while it may be slightly slower to do things the naive way, it's not much, and in many cases, not noticeable, so it's better to optomize how much work you can get done in your lifetime, than to make things a millisecond faster, again, assuming it's not in your physics engine or something like that.

All this seems well and good, except I have one question, why not linked lists rather than arrays? Sure, if you had to make your own linked list class, I would be on board, but in c++ anyway, assuming your using STL, you only need to declare the type as a list, rather than as a vector, and use iterators to loop over it, rather than looping an index.

The advantages of using a linked list though seem much greater, for example, if you can be guaranteed that nothing is going to be removed from it while your iterating, you don't need to have locks around it, because adding data doesn't have the possibility of moving everything (or is that a bad assumption). Also, in general, moving data is slow, although this could potentially be avoided if you know the size of your data by reserving the space.

Another advantage is when you do remove data, you just tell the list to remove it, and it just needs to change a few pointers, and call a destructor, which can be done pretty quickly. But to remove something from an array/vector, you have to either shift everything back one, or possibly add a flag saying that it has been deleted. (Or, another possibility if you don't care about the order of the data, is move the data at the end index, to the data in the now deleted position). Either way, this seems like it is a lot of extra, unneeded work, or potentially too slow.

I did take a look around and found this, which claimed that a lot of older developers didn't want to use STL because it wasn't mature enough. Also, older games AFAIK, used C rather than C++, which also doesn't have STL. And I could see a case there for using arrays rather than linked lists, because you would have to make your own (which while simple enough to do, could potentially lead to many more errors).

I also read that it's a bad idea to create iterators in Java (due to the garbage collector), but that idea seems moot in languages such as C++, where there isn't a garbage collector, and I would imagine that linked list iterators are pretty lightweight (admittedly probably not as lightweight as vector iterators though). Or is this also a bad assumption, and it's better/faster just to use an index in your loop, and increase that.

Answer 1

My answer to this question would be the same as my answer to this other question: When should vector/list be used?

Basically, cache-coherency-related performance gains from having everything be contiguous in memory is more valuable than "Big O" algorithm theoretical performance from linked lists.

Answer 2

Usually for performance reasons. Take a look at the example of the WAD file that you gave. You know at the time that you pack that level how many elements of the array/list that you are going to have. Therefore you can allocate one chunk of memory, fill it in once via DMA from the media to the structure and keep moving. As you walk the array you can take advantage of the cache of the CPU as it will be loading in the next elements that you are going to be iterating on. As for removing the data, it's a WAD file describing a level, what exactly are you going to remove?

That's not to say that linked lists aren't useful, just that there are a lot of uses for a plain old array particularly when it comes to streaming in resources for a level.

Another issue is overhead. Are you loading in thousands or tens of thousands (vertices in a model / world) of elements? Great that 32 bit pointer to the next element, or 64 bits if it's doubly linked just increased your memory footprint by 33% without actually buying you anything because you're still never going to remove a vertex from the middle of a model.

Also take a look at the Electronic Arts version of the STL EASTL http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html

Answer 3

Arrays are dependable, static in size and are never prone to run time degradation and fragmenting. I believe that using complex structures like linked lists smells of optimizing before measuring and over-engineering before need, and those are a sin if ever there was one.

This is, of course, in the arena of small budget development where wasted effort that doesn't directly improve the end user experience means hamburger on the table instead of steak. Or to put it another way, Jonathan is optimizing for user experience and not run time performance.