The cost of performance vs. productivity: an example

Sometimes, as programmers, we find it hard to strike the balance between the need to do things fast and to make things run fast. I strongly believe in the second option. 

I just started a personal project, a game, Rogue-like. The basis of such a game is always some sort of matrix, in which the character is moved. My conditions for this project are to write the game in C++, using as much of C++11 as possible, for learning reasons.

So the first idea was to create a Matrix class, which should be a vector of vectors; this idea fell quite fast, I didn’t really like it and didn’t feel like using this method for doing a Matrix. So, obviously, I thought of rolling my own. Unfortunately, I can’t really add the code (WordPress really thinks it’s too smart for its own good, and decided that my template code is really XML).

I created a Matrix template class, and only ran the initialization code. First I used a std::vector for keeping the matrix data, then I used a simple T*. For the data themselves, I used an Entity class and a NullEntity derived from Entity that sets the entity name to “NULL”.  A matrix of 5000×5000 items was created. Below we have the creation times:

Container type Item type (T) Run time
STL vector shared_ptr 1410-1440 ms
STL vector C++ pointer 290-310 ms
C++ vector (T*) shared_ptr 1010-1030 ms
C++ vector (T*) C++ pointer 100-110 ms

So for 25 million items, the time cost of using a shared pointer is about 900ms (or 1100 ms in the case of reallocation done with the STL vector). This means that creating a little over 25000 items will take 1 ms.

The benefits of using shared_ptr are quite big: I would be able to reuse safely these objects in the program and the lifetime would be well controlled. Not having to check for every possible copy of every object is an improvement in development time. This and the fact that each cell should not have only one entity, but a stack of entities makes me think that the cost may be worth it. Is the cost acceptable? I don’t know. I shall think about it. But I certainly don’t like the fact that the running time jumps an order of magnitude.

Of course, I should optimize in different areas. I should not have in memory a 5000×5000 matrix, so my numbers should become acceptable. But early optimization can be the death of any project, therefore I shall go the C++11/STL way nonetheless. The optimization should be made at a higher level, at design level: for example, we should not have a matrix but a sparse matrix, and we should not have all the data in memory at one time. But this kind of decisions I shall make after I have at least something working, not now.

As a PS, an optimization trick: What’s the difference between:

and

Answer: around 10 ms for 25 million items.

PS: Looking at how difficult it is to post code with wordpress makes me seriously think about creating my own publishing platform.

Comments

The cost of performance vs. productivity: an example — 2 Comments

  1. Curiosity question: are those times for a release build? Because if it’s for Debug, it’s not really worth looking into.

    As a general rule for successful games nowadays: the approach of doing anything that is not speed critical in C++ is counter-productive. Consider adding a scripting language for the game logic (Lua, Python, whatever works for you). Then again, you’re trying to learn C++11, not scripting or game design.

    As for the example, I would say that it seems normal. But it’s not the complete picture. Because once you start factoring in the difficulty of managing the various relationships between classes and their disposal, you will need to add check-ups in various places to make sure you don’t get NULL, or not try to remove data managed by some other component.

    Also, don’t take this the wrong way, but consider using something more standard (boost has a matrix; I haven’t used it, but it should be ok). I tried writing my own classes to have MY version of STL. When I saw how much slower my code was running I realized there’s no point in doing that 🙂

    • There’s barely anything that optimization can do here – 25 million constructor calls do that to you.

      Adding scripting language for my game would be an option, sometimes far in the future when I’ll really have something working. But this one I’m doing for C++11.

      As I stated as well, the contents of the matrix will be different from simple Entity *, so I’ll go for the abstraction; anyway, for close future I’m going for something more intelligent, like a sparse matrix.

      And when it comes to boost, the love story between me and boost is an impossible one. If I wanted tons of code I don’t know or understand in my project I would’ve gone for C# or Java (and call that code ‘framework’). But I’m going C++ for good reasons.