c++ - パフォーマンスの低下-おそらく設計が不適切な方法

Question

私はクライアントサーバータイルベースのゲームに取り組んでいます。クライアントはデータを3次元で保持しstd::vector、各フレームでそのコンテンツをサーバーが送信するコンテンツと比較します（サーバーから送信さstd::vectorれたデータで満たされた別のコンテンツがクライアント側にあります）。

これで、クライアント側のマップは15x11タイルで構成され、各タイルには10個のオブジェクトが配置されたデータが保持されるため、で15 * 11 * 10=1650要素を取得し std::vectorます。

両方のデータを比較していてstd::vector、何かが変更された場合は、違いに応じて、新しいオブジェクトを作成/オブジェクトを削除/オブジェクトを移動します。これが私のやり方です：

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
        );
    }
}

問題は、デバッグモードでその関数（〜90から〜20 fps）を呼び出すために、パフォーマンスが大幅に低下することです。各フレームを通過するのにかなりの量のデータがあることは知っていますが、それほど遅くならないようにどのように設計できるかわかりません。

Visual Studio 2012のパフォーマンス分析を使用して、最大のパフォーマンス低下の正確な原因を突き止めました。その結果は次のとおりです。ここに画像の説明を入力してください

だから、それが主な理由のよう[] operatorに見えます。std::vector

score 3 · Accepted Answer

パフォーマンス分析を行っているコードは、すべてのアイテムに対して線形 O(n) 検索を実行しているように見え、その全体が O(n^2) になります。

何を達成しようとしているのかよくわかりませんが、その理由は std::vector の演算子が遅いためではなく、実行回数が非常に多いためです。

最初はすべての clientIds をマップに配置することをお勧めします。これにより、順序が O(nlogn) に減少します。他にも最適化を行う必要があるかもしれません。たとえば、できることなら外側のマップのすべての要素を調べないようにします。

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

    found = serverId.id == clientId.id;
    if(found)
        break;
}

score 3 · Accepted Answer

リリースで削除された（私のMSVC ++の）デバッグバージョンには境界チェックがあり[]ます。これが比較的高い理由かもしれません..

これは私が見るコードです。

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));
        }

最後の行を除いて、ほとんどすべての行がリリースでなくなっています..

c++ - パフォーマンスの低下-おそらく設計が不適切な方法

2 に答える 2

Related

Reference