By

About 10 years ago, I worked at Gameloft as a game server developer.
We used C++ to develop an online MMO-RPG game, where thousands of players connected simultaneously.

One day after a game update, our QA team reported a bug: players experienced significant lag when performing actions.
The game client team investigated and informed me that the lag originated from the server.

I added some logs and eventually found the problematic code.
It’s a call to get the size of a list, which looked something like this:

std::list<int> items;
... // do someting with items
int count = items.size();

Can you see the problem?

The size() function’s time complexity was O(N), not O(1)! until C++11
So why didn’t I catch this issue in tests before it went live?

  • First, it’s only noticeable when the list contains a large number of items.
  • Second, We tested under Windows, compiling the code with MSVC. The default STL library in MSVC implemented size() as an O(1) function.However our production server ran on linux and was compiled with GCC.

Yes MSVC was ahead of its time in this regard.

Contents