c++ - 高效迭代大量数据

Question

简介

首先，我必须说这是针对在线游戏服务器完成的，它会跟踪 map 中的每个对象，无论是玩家还是 AI(NPC 或任何你想称呼的对象)。

它不仅要跟踪他们，还要在玩家之间通知他们附近的玩家。我已经解决了这个问题，目前我正在使用一种非常有效的多线程方法。

我的问题

我将所有这些对象存储在一个哈希表中。我们可以认为该哈希表是一个 unordered_map ，尽管我实际上使用的是 rde::hash_map ，因为它在插入和获取(自测)时速度更快，但需要更多 RAM(现在不是问题)。

事实是，该映射存储对象的唯一 ID(64 位)以及对象指针，类似于: rde::hash_map<UInt64, Object*>

我的问题是:

我的应用程序(服务器)必须在一个循环(在线程内)中运行，该循环必须每 ~50 毫秒调用一次，以保持运行顺畅。循环代码如下所示:

void loop()
{
    UInt32 prev = clock();
    UInt32 prevSleep = 0;
    while (1)
    {
        UInt32 diff = clock() - prev;
        prev = clock();

        maps.update() // Suppose map is a class, which stores the objects map

        if (diff <= 50 + prevSleep)
        {
            prevSleep = 50 + prevSleep - diff;
            sleep(prevSleep);
        }
        else
            prevSleep = 0;
    }
}

现在，切中要点，函数 map::update()这是导致循环增加到 4500 毫秒值的原因。

每次调用更新时， map 对象必须检查是否有新对象被添加到存储中，如果添加了一个对象，该对象必须通知所有其他对象它被添加了，我通过(伪代码) :

foreach obectsToBeAdded as joiner:
    foreach objectsList as object:
        joiner->notify(object);
        object->notify(joiner);

稍后，必须调用每个对象的内部更新，我通过(又是伪代码)来完成:

foreach objectsList as object:
    object->update();

而且，如果这还不够，必须将上述循环扩展为:

foreach objectsList as object:
    object->update()
    
    // Visit all the other objects
    // Called once every 1 sec for the object, not on every call
    foreach objectsList as other:
        if other != object:
            object->visit(other)

我尝试对此进行优化

将第一个循环(添加和通知)与更新循环合并，如下:

foreach objectsList as object:
    foreach objectsToBeAdded as joiner:
        object->notify(joiner)
        joiner->notify(object)

    object->update()

    // Called once every 1 sec for the object, not on every call
    foreach objectsList as other:
        if other != object
            object->visit(other)

这在对象数量不大的情况下有效，一旦它增加，循环就开始花费 4 秒，这远远超过了我正在寻找的 50 毫秒。

我的问题

还有其他方法可以进一步优化吗？我考虑过使用八叉树来跟踪 map 中的对象位置，但后来得出的结论是这只会使问题恶化。

我还将每个 map 划分为一个实体的 35 个单位(35 是“视野范围”，LOS)，因此给定的 rde::hash_map只包含彼此可以看到的单元，因此需要更新。只要对象数量少就可以工作...

我还能做什么？谢谢!

注意事项

所有这些 foreach是使用迭代器的循环，比如 rde::hash_map<...>::iterator来自 objects.begin()至 objects.end()

其他优化，例如在没有玩家(真实用户，而非 NPC)时不更新，在给定 map 上没有玩家时释放内存等，已经被考虑在内。

Answer 1

除了空间分割之外，我想到的第一个优化是让对象只了解它们附近的变化(例如使用四叉树):是否每个对象都必须了解每个变化？为什么不告诉每个对象，'每一帧，我都会运行你的 update 方法。在您的 update 方法中，您可以查找您想要的所有内容(例如，可能有一个缓冲区，其中包含本帧/最近帧中发生的所有更改)并根据需要更新自己'。这样，您就不会花费 CPU 周期来通知对象实际上不需要知道或关心的事情。

此外，您是否对程序运行了 CPU 分析器，并验证了热点(花费最多 CPU 时间的地方)是否在您认为的位置？

查看评论以进一步讨论:

 |
 |
\|/
 V