c++ - 为什么这段代码非常慢？与缓存行为有关的任何事情吗？

Question

我开始进行一些面向数据的设计实验。我最初开始做一些 oop 代码，发现有些代码非常慢，不知道为什么。这是一个例子:我有一个游戏对象

    class GameObject
    {
    public:
          float m_Pos[2];
          float m_Vel[2];
          float m_Foo;

          void UpdateFoo(float f){
             float mag = sqrtf(m_Vel[0] * m_Vel[0] + m_Vel[1] * m_Vel[1]);
             m_Foo += mag * f;
          }
     };

然后我使用 new 创建了 1,000,000 个对象，然后循环调用 UpdateFoo()

        for (unsigned i=0; i<OBJECT_NUM; ++i)
        {
           v_objects[i]->UpdateFoo(10.0);
        }

完成循环大约需要 20 毫秒。当我注释掉 float m_Pos[2] 时发生了奇怪的事情，所以对象看起来像这样

    class GameObject
    {
    public:
          //float m_Pos[2];
          float m_Vel[2];
          float m_Foo;

          void UpdateFoo(float f){
             float mag = sqrtf(m_Vel[0] * m_Vel[0] + m_Vel[1] * m_Vel[1]);
             m_Foo += mag * f;
          }
     };

然后循环突然需要大约 150 毫秒才能完成。如果我在 m_Vel 之前放任何东西，速度会快得多。我尝试在 m_Vel 和 m_Foo 之间或除了 m_Vel 之前的位置之外的其他地方放置一些填充....慢。

我在 vs2008 和 vs2010 的发布版本 i7-4790 上进行了测试知道这种差异是如何发生的吗？它是否与任何缓存一致行为有关。

这里是整个样本:

    #include <iostream>
    #include <math.h>
    #include <vector>
    #include <Windows.h>

    using namespace std;

    class GameObject
    {
    public:
        //float m_Pos[2];
        float m_Velocity[2];
        float m_Foo;

        void UpdateFoo(float f)
        {
          float mag = sqrtf(m_Velocity[0] * m_Velocity[0] + m_Velocity[1] * 
                            m_Velocity[1]);
          m_Foo += mag * f;
         }
    };



     #define OBJECT_NUM 1000000

     int main(int argc, char **argv)
     {
       vector<GameObject*> v_objects;
       for (unsigned i=0; i<OBJECT_NUM; ++i)
       {
          GameObject * pObject = new GameObject;
          v_objects.push_back(pObject);
       }

       LARGE_INTEGER nFreq;
       LARGE_INTEGER nBeginTime;
       LARGE_INTEGER nEndTime;
       QueryPerformanceFrequency(&nFreq);
       QueryPerformanceCounter(&nBeginTime);

       for (unsigned i=0; i<OBJECT_NUM; ++i)
       {
           v_objects[i]->UpdateFoo(10.0);
       }

       QueryPerformanceCounter(&nEndTime);
       double dWasteTime = (double)(nEndTime.QuadPart-
                       nBeginTime.QuadPart)/(double)nFreq.QuadPart*1000;

       printf("finished: %f", dWasteTime);

       //   for (unsigned i=0; i<OBJECT_NUM; ++i)
       //   {
       //       delete(v_objects[i]);
       //   }
     }

Answer 1

then I create 1,000,000 of objects using new, and then loop over calling UpdateFoo()

你的问题就在这里。不要单独分配一百万个将要使用通用分配器重复处理的小东西。

尝试将对象连续存储或存储在连续 block 中。一个简单的解决方案是将它们全部存储在一个大的 std::vector 中。要在固定时间内删除，您可以交换要删除的元素和最后一个元素并弹出。如果您需要稳定的索引，您可以留下一个空洞以便在插入时回收(可以使用自由列表或堆栈方法)。如果您需要不会失效的稳定指针，deque 可能是结合“漏洞”想法的一个选项，使用空闲列表或单独的索引堆栈来回收/覆盖。

您也可以只使用一个空闲列表分配器并对其使用 placement new，同时小心地使用相同的分配器释放并手动调用 dtor，但与数据结构方法相比，这会变得更加困惑，并且需要更多的练习才能做好。相反，我建议只寻求将您的游戏对象存储在一些大容器中，这样您就可以重新控制所有内容将驻留在内存中的位置以及由此产生的空间局部性。

I tested on vs2008 and vs2010 in release build, i7-4790 Any idea how this difference could happen? Is it related to any cache coherent behavior.

如果您正确地进行基准测试和构建项目，当 GameObject 较小时，分配器可能会产生更多的内存碎片，从而导致更多的缓存未命中。这似乎是最有可能的解释，但如果没有一个好的分析器就很难确定。

也就是说，与其进一步分析它，不如推荐上述解决方案，这样您就不必担心分配器在何处分配内存中的每一个小东西。