Optimization Vector of vector of object seems slow

Question

I'm creating a multiplayer video game for fun, I have a server and a client running. I would like to optimized as much as I can the process on the server. The server lag when we receive to much information from different clients at the same time.

I would like to check with you if what I have done could be optimized, I feel like it easily could.

There we go with the code :

We have a map :

std::vector< std::vector < caseMap > >  _map;

A simple object caseMap :

struct caseMap
{
    int                     areaId;
    bomb                    *bombs;
    Bonus                   *bonus;
    int                     underEffect;
    int                     effectOwnerId;
    std::list< player* >    players;
};

We access a lot of time to map case following this operation : ( example when a player die )

this->_map[pl->getPosY()][pl->getPosX()].players.erase(itp);

There is my question and solution : - We could have one vector only instead of two, and have a little formula to retrieve the actual case we are looking for.

But is it heavy to use it the way I do right now ? I thought accessing by [] was big O constant, so it should not be super heavy.

Can I use some const reference at some point ?

Should I use a different object such as std::map ?

I'm a bit confused if you guys can refresh my brain on c++ code. Thank you :)

The look up time is constant. You're wasting your time on little things. "Premature optimization is the root of all evil" -- Donald Knuth. — jcoffland, Sep 17 '15 at 10:58
Profile and measure first, to select what's actually needs to be optimized. — πάντα ῥεῖ, Sep 17 '15 at 11:01
You need to know that there is a big overhead associated with STL data structures: a std::vector of 10 items costs (a little bit more) than the memory used by the 10 items alone, this is due to the data structures used by STL bookkeeping and also used by operator new[]/malloc() bookkeepint. In general "nesting" STL classes (e.g. vector) is not a good idea if there is a large number of elements because the overhead will become significant (that said, I agree with @jcoffland) — BrunoLevy, Sep 17 '15 at 11:21
How did you come to the conclusion that you spend a lot of time *there*? Are you keeping a list there to look up which players are on a given field of the map? How many players are you dealing with? — Markus Mayr, Sep 17 '15 at 11:22
How to optimize this rather depends on the wider architecture. What strikes me is you dereference a lot of pointers. Pointers can mean non-contiguous storage and non-contiguous can be considerably slower than contiguous in some circumstances. The questions that immediately spring to mind are; Could `list `be replaced by `vector`? Do you have to use pointers for players? Or can you store the *actual* player objects in your `caseMap`> aka `vector players`? — Galik, Sep 17 '15 at 12:34
Thank you for your comments guys. I would like to optimized as much as I can, and you answered well my question. It's a constant. I will change the vector< vector <> > thing into vector<> just to make it look better ( and because it will not hurt ). I'm not dealing with a lot of players, just 2 and I have some roll back sometimes... It's an other topic, sometimes the client flood, so I will fix this. I would like to thank you guys for your reply. May I ask, is there any good way/solution to have an over view of resource consumption etc... with visual studio 2012 ? To handle the vector thng — Bertrand Barraud, Sep 17 '15 at 13:05

score 0 · Accepted Answer · edited May 23 '17 at 11:51

With std::vector the lookup time is always constant. And the constant is very small. Adding more elements to the vector is O(1) amortized time, as was pointed out in the comments. But note that the worst case append time is O(n). This is not generally a problem though. If you know you will need more space than you can preallocate it by calling std::vector::reserve() to make it slightly faster. But this too is usually an unnecessary optimization.

std::map has O(ln(x)) lookup and insert times so it would be slower in most cases.

If you are having performance problems this lookup is not why. You should leave this code as it is. Trying to do something fancy will likely result in slower code and a maintenance mess.

"Premature optimization is the root of all evil" -- Donald Knuth

See the question whats-the-best-free-c-profiler-for-windows for several options for profiling your code. Finish your code. Then profile it and concentrate on optimizing the parts that matter.

Another good quote:

"Make it right. Then make it fast."

This is one of the hardest lessons for young programmers to learn and for some old ones too. You think you're doing the right thing and really making the code awesome but you are mostly spinning your wheels optimizing things that don't really matter and creating future code maintenance problems.

Adding elements to the end of an `std::vector` is not `O(N^2)`. Adding one element is `O(1)` (amortized, see http://cs.stackexchange.com/questions/9380/why-is-push-back-in-c-vectors-constant-amortized ), adding N elements is `O(N)`. `reserve()` is still a good idea, of course. — Markus Mayr, Sep 21 '15 at 05:51
Thank you both for your answers, it's good to talk about it, I always though I was maybe going the wrong way and it's nice to hear advice from more experienced programmers. Thank you. — Bertrand Barraud, Sep 22 '15 at 06:23
@Markus Mayr, Good point. Adding an element to the end of ``std::vector`` is still O(N) worst case. Not that it really matters. — jcoffland, Sep 22 '15 at 23:03

Optimization Vector of vector of object seems slow

1 Answers1