I'm working on a client-server tile-based game. Client holds data in 3-dimensional std::vector and in each frame it compares it's content with the one that server sends (I have a separate std::vector at the client side which is filled with data sent by server).

Now the map at the client side consists of 15x11 tiles, each of which holds data about 10 objects placed on it, so I get 15*11*10 = 1650 elements in a std::vector.

I'm comparing data in both std::vectors and if something changed, I create new object / remove object / move object, depending on what are the differences. This is how I do it:

std::vector<IdAndPosition> clientIds;
std::vector<IdAndPosition> serverIds;

// Fill client ids
for(unsigned int i = 0; i < m_tiles.size(); i++)
{
    for(unsigned int j = 0; j < m_tiles[i].size(); j++)
    {
        for(unsigned int s = 0; s < m_tiles[i][j].getObjects().size(); s++)
        {
            clientIds.push_back(IdAndPosition(m_tiles[i][j].getObjectAtPosition(s)->getId(), i, j, s));
        }
    }
}

// Fill server ids
for(unsigned int i = 0; i < g_gameStateData.m_gameObjects.size(); i++)
{
    for(unsigned int j = 0; j < g_gameStateData.m_gameObjects[i].size(); j++)
    {
        for(unsigned int s = 0; s < g_gameStateData.m_gameObjects[i][j].size(); s++)
        {
            serverIds.push_back(IdAndPosition(g_gameStateData.m_gameObjects[i][j][s].second, i, j, s));
        }
    }
}

for (int i = 0; i < serverIds.size(); i++)
{
    IdAndPosition& serverId = serverIds[i];

    bool found = false;
    for(int j = 0; j < clientIds.size(); j++)
    {
        IdAndPosition& clientId = clientIds[j];

        found = serverId.id == clientId.id;
        if(found)
            break;
    }
    if(!found)
    {
        // If not found, create that object
                        // tileX        // tileY
        m_tiles[serverId.pos[0]][serverId.pos[1]].addObjectAtPosition(
            TGameObjectFactory::createGameObject(g_gameStateData.m_gameObjects[serverId.pos[0]][serverId.pos[1]][serverId.pos[2]].first),   // Game object
            serverId.pos[2]                                                                                                                 // Position at stack
        );

        // And set it's individual id
        m_tiles[serverId.pos[0]][serverId.pos[1]].getObjectAtPosition(serverId.pos[2])->setId(g_gameStateData.m_gameObjects[serverId.pos[0]][serverId.pos[1]][serverId.pos[2]].second);
    }
}

for (int i = 0; i < clientIds.size(); i++)
{
    IdAndPosition& clientId = clientIds[i];

    bool found = false;
    for(int j = 0; j < serverIds.size(); j++)
    {
        IdAndPosition& serverId = serverIds[j];

        found = serverId.id == clientId.id;
        if(found)
            break;
    }
    if(!found)
    {
        // If not found, create empty object at this position
                        // tileX        // tileY
        m_tiles[clientId.pos[0]][clientId.pos[1]].addObjectAtPosition(
            TGameObjectFactory::createGameObject(NO_GAME_OBJECT_ID),        // Empty game object (we're removing deprecated one)
            clientId.pos[2]                                                 // Position at stack
        );
    }
}

The problem is that I get a big performance drop due to calling that function (from ~90 to ~20 fps) in debug mode. I know that's quite a big amount of data to go through each frame, but I have no idea how I could design it so that it's not that slow.

I used Performance Analysis in Visual Studio 2012 in order to find out what exactly causes the biggest performance drops, and I got that result:

So it looks like [] operator for std::vector is the main reason.

There is bounds checking in the debug version of [] (in my MSVC++) which is removed in release, this might be why it is relatively so high..

This is the code I see.

const_reference operator[](size_type _Pos) const
        {   // subscript nonmutable sequence
 #if _ITERATOR_DEBUG_LEVEL == 2
        if (size() <= _Pos)
            {   // report error
            _DEBUG_ERROR("vector subscript out of range");
            _SCL_SECURE_OUT_OF_RANGE;
            }

 #elif _ITERATOR_DEBUG_LEVEL == 1
        _SCL_SECURE_VALIDATE_RANGE(_Pos < size());
 #endif /* _ITERATOR_DEBUG_LEVEL */

        return (*(this->_Myfirst + _Pos));
        }

Pretty much every line is gone in release except the last..