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

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

    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.

  • 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

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

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

Tags
c++ vector data-structure
Related questions and answers
  • know if my speculations are ok, as I don't have much experience with 3d animations yet. I want to make a well decision as any option I choose would require a lot of work to get it to render and I don't want to find out in the end that I have to rewrite everything again, as a lot of other objects will be working with these data. Sorry if it's a too subjective matter, but I need some insight. I'm... that make really hard to work with when coding some functions that use them. I was thinking of making ie. SimpleMesh and HierarchyMesh objects, which will also require that the renderer can deal

  • of this then why would I be here asking this question? The reason is as shocked as I am about this. I don't like to lose. I have my own queries on how appealing this project would be to someone looking... this summer and I have a good grounding on the web side of things. I've also done some very basic c++ (what i would consider basic). My c++ skills basically comes down to different tutorials on things... i seek out to make this not just a passable project but one that'll be demo-able and I can stand proud beside. What advice can you give to someone like me that you wish someone had told you

  • Choosing an Audio API Aidan Knight

    , features seem generic. Pretty much coming down to a battle between this and BASS. I have heard good and bad things. The other libraries such as OpenAL, PortAudio, Audiere, etc. were considered, but I am looking for something more drag and drop rather than something I am going to be basically writing my own front-end for. I am curious though, I remember stumbling across another library or two a few... Free - 3000$ - 6000$ which pretty much excludes this. BASS - So far this is what I am leaning towards. Simple API, great feature list, and quite a bit more. The pricing structure looks somewhat similar

  • don't need 3D, and it is quite ...a lot of work to learn. I also don't like that it is so expensive to use for different platforms and that I can only code for it through scripting. You have to buy each... people can play my game once finished). I'd like to have it available on many mobile platforms aswell. (because I love touch input for some reason) I do know the XNA framework pretty well... etc. are far worse in Flash, than they are in XNA/WPF.) Now, I'm aware that I could make my own engine that supports each of those platforms, but quite frankly, that would be too much work plowing

  • until you pop out into an open space, known as a ' ' (space) character. You lose one life for each INITIAL collision with the X wall, and do not lose another until you have popped out and been freed from it. As an added touch i have made it so after you collide while traveling down the randomly generated map (or rather as the walls move uppward while your character stays put) the X chars you've... and traveling throug it. This is due to some odd reason for the "numb_collisions", which is used to count how many collisions have occured since initial collision (if it's 0 it means it IS the initial

  • question about it is, is this a worthwhile approach at all? If it's a bad design I want to know now before I invest too much more time making all the screens I'm going to need. How do you build up... to worry about this since it isn't an issue there. Moving to C++, this has become a fairly major problem and made me think I may have designed things incorrectly. I can't really imagine how to decouple... related to the graphics library I'm using, but is more of a conceptual thing. In C#, I coupled graphics in with alot of my classes which i know is a terrible idea. Wanting to do it decoupled

  • version of both. This is so the permanent ones can just be loaded in and are always drawn, and the temporary ones only get drawn for a frame. This way I can create moving lines for debugging, like line of sight cones etc. EDIT - the naive approach would be to duplicate this code 4 times for each vector, but surely there is a better way? I don't think this is a hard thing to do, but trying to do it has exposed a basic gap in my knowledge about what some of these lines of code do. should I just populate one big list from all the vectors and push that through? some need to be drawn

  • . state_->handleEvent(event, this); } That means that I don't really ever need more than one instance of a particular entity state; doing something like entity.setState(new StandState) is therefore highly wasteful. Then again, making each entity state a singleton hardly seems appropriate. What do you suggest I do? (The same can be said about game states, so whatever the solution... changed, then it (the representation) starts having an internal state. I would much rather have it stateless so that I require only one instance of every representation (just as before). Edit

  • to work correctly. Player movement ends up being very glitchy and repositions the player when I don't want it to. Part of the reason is probably because I feel like this is something so simple but I'm over-thinking it. If anyone thinks they can help, please take a look at the code below and help me try to improve on this if you can. I would like to refrain from using a library to handle this (as I... be crucial, let me know and I'll provide the necessary information. Finally, for anyone who can help, providing code would be very helpful and much appreciated. Thank you again for your help! Edit: I

Data information