在派生类中访问成员模板函数中的元素时,unordered_map的性能较低

Question

我正在尝试在游戏引擎项目上实现基于组件的架构.每个GameObject都有unordered_map一个指向Component基类的指针.此时,我只有一个组件派生类,即Transform类.我想实现这个基于组件的体系结构,类似于Unity的约定:我想通过调用成员模板函数来获取游戏对象的一个​​组件GetComponent<Transform>().

以下是标题:

Component.h

enum type{
    TRANSFORM   // more will be added later
};

class Component // base class
{
public:
    Component() : _owner(NULL) {}
    virtual ~Component(){}
    static type Type;

protected:
    GameObject* _owner;
};

Transform.h

class Transform : public Component
{
public:
    Transform();
    ~Transform();
    static type Type;

    void Rotate(float deg);

    // to be encapsulated later on
    Vector2D _position;
    float _rotation;
    Vector2D _scale;
};

GameObject.h

class GameObject
{
public:
    GameObject();
    ~GameObject();

    void Update();
    //and more member functions

    template<class T>
    T* GetComponent();
private:
    // some more private members
    unordered_map<type, Component*> _componentList; // only 1 component of each type
};

template<class T>
T* GameObject::GetComponent()
{       
    return static_cast<T*>(_componentList[T::Type]);
}

---

我的初始实现用于std::vector保持Component*和应用程序以60 fps运行(我还有一个帧速率控制器,它只是将FPS限制为60).当我改为unordered_map访问那些组件指针时,性能下降到15 FPS.

我只绘制两个四边形,此时我GetComponent<Transform>()每帧只调用6次,因此场景中没有太多事情发生.

---

我尝试了什么？

我试图用const char*,std::string,type_info最后enum type作为键值unordered_map,但没有真正的帮助:所有实现了我15-16 FPS.

是什么导致这个性能问题？我该如何隔离这个问题？

_{我希望我提供了足够的细节,如有必要,请随时索取更多代码}

Answer 1

免责声明：虽然下面的信息无论如何都应该成立，但考虑到在如此简单的情况下性能存在如此巨大的差异，第一个基本的健全性检查是首先确保构建优化已开启。有了这个……

unordered_map最终被设计为一个相当大规模的容器，预先分配可能大量的桶。

请参阅此处： std::unordered_map 内存使用率非常高

这里： C++ STL unordered_map 如何解决冲突？

虽然计算哈希索引是微不足道的，但是对于像从实体中检索组件接口这样频繁访问的内容，如此小的访问内存量（以及之间的跨度）unordered_maps很容易变成缓存缺失瓶颈。

对于实体组件系统，通常没有那么多与实体关联的组件——可能有几十个顶级，而且通常只有几个。因此，std::vector实际上是一个更合适的结构，主要是在引用局部性方面（每次从实体中获取组件接口时通常可以重复访问的小数组）。虽然不太重要，std::vector::operator[]但也是一个普通内联的函数。

如果您想做得比std::vector这里更好（但我只建议在分析并确定您需要它之后这样做），前提是您可以推断出一些常见情况上限，N即实体中通常可用的组件数量，如下所示可能会工作得更好：

struct ComponentList
{
    Component* components[N];
    Component** ptr;
    int num;
};

首先设置为ptr并components随后通过 访问它们ptr。插入新元件会增加num。当num >= 4（罕见情况）时，更改ptr为指向具有更大大小的动态分配的块。销毁时ComponentList，如果 则释放动态分配的内存ptr != components。如果您存储的元素少于N元素，这会浪费一点内存（尽管std::vector通常也使用初始容量及其增长方式来实现这一点），但它会将您的实体和提供的组件列表变成完全连续的结构，除非num > N. 因此，您可以获得最佳的参考位置，甚至可能比您开始时更好的结果（我假设从帧速率的显着下降中，您经常从循环中的实体中获取组件，这并不罕见在 ECS 中）。

考虑到从实体访问组件接口的频率，并且通常是在非常紧密的循环中，这可能是值得的。

std::vector尽管如此，考虑到数据的典型规模（实体中可用的组件数量），您最初的选择实际上是更好的选择。对于非常小的数据集，基本的线性时间顺序搜索通常优于更复杂的数据结构，并且您通常希望更多地关注内存/缓存效率。

我尝试使用 const char*、std::string、type_info 和最后的 enum 类型作为 unordered_map 的键值，但没有任何帮助：所有实现都使我获得了 15-16 FPS。

就这一点而言，对于键，您需要可以在恒定时间内进行比较的东西，例如整数值。在这种情况下，一种可能很方便的可能性是一个内部字符串，它只存储一个int以在方便和性能之间取得平衡（允许客户端通过 a 构建它们，string但int在组件查找期间通过 an 比较它们）。