1

好的,这里的示例代码比较了面向对象编程 (OOP) 解决方案与更新一堆球的面向数据设计 (DOD) 解决方案。

const size_t ArraySize = 1000;

class Ball
{
public:
    float x,y,z;
    Ball():
        x(0),
        y(0),
        z(0)
    {
    }

    void Update()
    {
        x += 5;
        y += 5;
        z += 5;
    }
};

std::vector<Ball> g_balls(ArraySize);

class Balls
{
public:
    std::vector<float> x;
    std::vector<float> y;
    std::vector<float> z;

    Balls():
        x(ArraySize,0),
        y(ArraySize,0),
        z(ArraySize,0)
    {
    }

    void Update()
    {
        const size_t num = x.size();
        if(num == 0)
        {
            return;
        }

        const float* lastX = &x[num - 1];

        float* pX = &x[0];
        float* pY = &y[0];
        float* pZ = &z[0];
        for( ; pX <= lastX; ++pX, ++pY, ++pZ)
        {
            *pX += 5;
            *pY += 5;
            *pZ += 5;
        }
    }
};

int main()
{
    Balls balls;

    Timer time1;
    time1.Start();
    balls.Update();
    time1.Stop();

    Timer time2;
    time2.Start();
    const size_t arrSize = g_balls.size();
    if(arrSize > 0)
    {
        const Ball* lastBall = &g_balls[arrSize - 1];
        Ball* pBall = &g_balls[0];
        for( ; pBall <= lastBall; ++pBall)
        {
            pBall->Update();
        }
    }
    time2.Stop();


    printf("Data Oriented design time: %f\n",time1.Get_Microseconds());
    printf("OOB oriented design  time: %f\n",time2.Get_Microseconds());

    return 0;
}

现在,这确实在 Visual Studio 中编译和运行,但我想知道是否允许我这样做,应该能够可靠地做到这一点:

const float* lastX = &x[num - 1];//remember, x is a std::vector of floats

float* pX = &x[0];//remember, x is a std::vector of floats
float* pY = &y[0];//remember, y is a std::vector of floats
float* pZ = &z[0];//remember, z is a std::vector of floats
for( ; pX <= lastX; ++pX, ++pY, ++pZ)
{
    *pX += 5;
    *pY += 5;
    *pZ += 5;
}

据我了解,std::vector 中的数据应该是连续的,但我不确定因为如果这将成为另一个平台上的问题,如果它违反标准,它是如何在内部存储的。此外,这是我能够让 DOD 解决方案超越 OOP 解决方案的唯一方法,任何其他迭代方式都没有那么好。我可以使用迭代器,但我很确定它可能只会比启用优化的 OOP 更快,也就是在发布模式下。

那么,这是做 DOD 的好方法吗(最好的方法?),这是合法的 c++ 吗?

[编辑] 好的,对于国防部来说,这是一个糟糕的例子;x,y,z 应封装在 Vector3 中。因此,虽然 DOD 在调试中比 OOP 运行得更快,但在发布时却是另一回事。同样,这是您希望如何有效使用 DOD 的一个不好的示例,尽管如果您需要同时访问大量数据,它确实显示了它的缺点。正确使用 DOD 的关键是“根据访问模式设计数据”。

4

3 回答 3

4

所有代码等的问题有点令人费解,所以让我们试着看看我是否理解你真正需要的东西:

据我了解, std::vector 中的数据应该是连续的

这是。该标准要求向量中的数据连续存储,这意味着在所有符合该标准的平台/编译器中都是如此。

这是我能够让 DOD 解决方案超越 OOP 解决方案的唯一方法

我不知道你说的 DOD 是什么意思

我可以使用迭代器,但我很确定这可能只会通过优化更快

实际上,这种情况下的迭代器(假设您在 VS 中禁用了调试迭代器)将与通过指针直接修改一样快。一个指向向量的迭代器可以用一个指向元素的普通指针来实现。再次注意,默认情况下,VS 迭代器会做额外的工作来帮助调试。

接下来要考虑的是两种方法的内存布局不同,这意味着如果在稍后阶段您需要访问 allx和从单个元素yz在第一种情况下,它们很可能落在单个缓存行中,而在三个向量方法中,它需要从三个不同的位置提取内存。

于 2012-02-15T18:05:31.673 回答
1

是的,你可以这样做。

向量容器被实现为动态数组;与常规数组一样,向量容器的元素存储在连续的存储位置,这意味着不仅可以使用迭代器访问它们的元素,还可以使用指向元素的常规指针的偏移量来访问它们的元素http://cplusplus.com/reference/stl/vector/

于 2012-02-15T18:04:13.413 回答
1

正如已经指出的那样,vector 在 C++11 之前通常是连续的,现在通过一个新data方法来保证,该方法实际上返回一个指向它使用的内部数组的直接指针。这是您的 ISO C++ 标准报价:

23.2.6 类模板向量【向量】

[...] 向量的元素是连续存储的,这意味着如果 v 是一个向量,其中 T 是 以外的某种类型bool,那么它服从&v[n] == &v[0] + n所有的标识0 <= n < v.size()

也就是说,我想加入主要是因为您进行基准测试和使用“DOD”的方式:

因此,虽然 DOD 在调试中比 OOP 运行得更快,但在发布时却是另一回事。

这种句子没有多大意义,因为 DOD 并不是对所有事情都使用 SoA 的同义词,尤其是在这会导致性能下降的情况下。

面向数据的设计只是一种通用的设计方法,您可以在其中考虑如何提前存储和有效访问数据。在使用这种思维方式进行设计时,它成为首先要考虑的事情之一。相反的是,比如说,设计一个架构试图找出它应该提供的所有功能以及对象和抽象以及纯接口等,然后将数据作为实现细节留待以后填写。国防部一开始会将数据作为设计阶段要考虑的基本事项,而不是事后才填写的实施细节。它在性能是客户要求的基本设计级别要求而不仅仅是实现奢侈品的性能关键型案例中很有用。

在某些情况下,数据结构的有效表示实际上会带来新功能,在某种程度上允许数据本身设计软件。Git 就是这样一个软件的一个例子,它的特性实际上在某种程度上围绕变更集数据结构展开,它的效率实际上导致了新特性的构思。在这些情况下,软件的功能和用户端设计实际上是从其效率演变而来的,从而打开了新的大门,因为效率允许以交互方式完成以前认为计算成本太高而无法以任何合理数量完成的事情。时间。另一个例子是 ZBrush,它通过允许人们在几十年前认为不可能的事情来重塑我的 VFX 行业,就像使用雕刻刷交互式地雕刻 2000 万个多边形网格,以实现在 90 年代末和 2000 年代初从未见过的如此详细的模型。另一个是体素锥追踪,它甚至允许在 Playstation 上编写的游戏也可以使用漫反射的间接照明;如果没有这种面向数据的技术,人们仍然认为需要几分钟或几小时来渲染单个帧,而不是每秒 60 多帧。因此,有时有效的国防部方法实际上会在软件中产生人们以前认为不可能的新功能,因为它打破了类比音障。另一个是体素锥追踪,它甚至允许在 Playstation 上编写的游戏也可以使用漫反射的间接照明;如果没有这种面向数据的技术,人们仍然认为需要几分钟或几小时来渲染单个帧,而不是每秒 60 多帧。因此,有时有效的国防部方法实际上会在软件中产生人们以前认为不可能的新功能,因为它打破了类比音障。另一个是体素锥追踪,它甚至允许在 Playstation 上编写的游戏也可以使用漫反射的间接照明;如果没有这种面向数据的技术,人们仍然认为需要几分钟或几小时来渲染单个帧,而不是每秒 60 多帧。因此,有时有效的国防部方法实际上会在软件中产生人们以前认为不可能的新功能,因为它打破了类比音障。

如果认为 AoS 表示更有效,国防部的思维方式仍可能导致设计采用 AoS 表示。AoS 通常在您需要随机访问的情况下表现出色,例如,所有或大多数交错字段都很热并且经常一起访问和/或修改。

此外,这只是我对它的看法,但在我看来,国防部不必预先达到最有效的数据表示。它真正需要的是预先设计出最有效的界面设计,以留出足够的喘息空间,以便根据需要进行优化。一个似乎缺乏国防部思维方式所提供的远见的软件的一个例子是一个视频合成软件,它代表这样的数据:

class IPixel
{
public:
    virtual ~IPixel() {}
    ...
};

只需看一眼上面的代码,就可以发现在如何设计高效的数据表示和访问方面存在严重缺乏远见。对于初学者,如果您考虑 32 位 RGBA 像素,假设 64 位指针大小和对齐方式,虚拟指针的成本将是单个像素大小的四倍(64 位 vptr + 32 位像素数据 + 32 -用于对齐 vptr 的填充位)。所以任何应用国防部思维的人通常都会避开像瘟疫这样的界面设计。然而,它们可能仍然受益于抽象,例如能够对具有许多不同像素格式的图像使用相同的代码。但在那种情况下,我希望这样:

class IImage
{
public:
   virtual ~IImage() {}
   ...
};

...这将 vptr、虚拟调度、可能的连续性丢失等的开销降低到整个图像(可能是数百万像素)的水平,而不是按像素付费。

通常,DOD 的思维方式确实倾向于导致更粗略而不是细化的界面设计(整个容器的界面,例如表示像素容器的图像界面,有时甚至是容器的容器)。主要原因是如果你有这样的代码库,你就没有太多的喘息空间来集中优化:

在此处输入图像描述

因为现在假设你想多线程同时处理许多球。你不能不单独使用球重写整个代码库。作为另一个示例,假设您要将球的表示从 AoS 更改为 SoA。这将需要重写Ball以使用以前的设计Balls与整个代码库保持一致。Ball如果你想在 GPU 上处理球,类似的事情。因此,通常国防部的思维方式倾向于采用更粗略的设计,例如Balls

在此处输入图像描述

在第二种情况下,您可以应用并行处理球所需的所有优化,用 SoA 表示它们等 - 任何您想要的,而无需重写代码库。但话虽如此,实现仍可能使用 AoSBalls私下存储每个人:Ball

class Balls
{
public:
    ...
private:
    struct Ball
    {
        ...
    };
    vector<Ball> balls;
};

... 或不。在这一点上几乎没有那么重要,因为您现在可以自由地更改Balls您喜欢的所有私有实现,而不会影响代码库的其余部分。

最后,对于您的基准测试,它有什么作用?它基本上是循环通过一堆单精度浮点数并添加5到它们。在这种情况下,无论您存储一个浮点数组还是一千个数组,都没有任何真正的区别。如果您存储更多数组,那么不可避免地会增加一些开销而没有任何好处,如果您要做的只是遍历所有浮点数并向它们添加 5。

要使用 SoA 表示,您不能只编写对所有字段执行完全相同的操作的代码。当您实际上需要对每个字段执行不同的操作时,SoA 通常在非平凡输入大小的顺序访问模式中表现出色,例如使用具有高效 SIMD 指令(手写或由您的优化器)一次转换 4 个以上的球,而不是简单地添加5到一大堆漂浮物。当并非所有字段都很热时,它们尤其出色,例如物理系统对粒子的 sprite 字段不感兴趣(加载到缓存行而不使用它是浪费的)。因此,要测试 SoA 和 AoS 代表之间的差异,您需要一个足够真实的基准来查看实际差异。

于 2018-01-06T14:28:14.813 回答