标签: data-oriented-design

在许多关于面向数据的设计的着作中起着突出作用的一个特征是,在很多情况下,而不是AoS(结构数组):

struct C_AoS {
  int    foo;
  double bar;
};

std::vector<C_AoS> cs;
...
std::cout << cs[42].foo << std::endl;

在SoA(数组结构)中安排一个数据更有效:

struct C_SoA {
  std::vector<int>    foo;
  std::vector<double> bar;
};

C_SoA cs;
...
std::cout << cs.foo[42] << std::endl;

现在我正在寻找的是一个解决方案,它允许我在不改变调用接口的情况下在AoS和SoA之间切换,即我可以用最小的努力并且没有额外的运行时成本(至少到了过度的间接点),cs[42].foo;无论我正在使用哪种数据排列,都要调用.

我应该注意上面的示例语法是理想的情况,这可能是不可能的,但我也对近似近似非常感兴趣.任何接受者？

在常规的面向对象实践中,并不是罕见的对象具有多个不相关的成员属性.当物体被处理时,在不同的通道中进行处理并不罕见,这些通道针对其属性的不同部分.

在这方面,创建对象集合的典型方法似乎不是非常有效的方法.考虑到计算机访问内存的方式和缓存行的平均大小,很有可能缓存内存正在填充不需要的内容,但恰好是相邻的,因此最终浪费缓存容量并增加停顿和执行的延迟.

更糟糕的是使用多态和动态分配对象的做法,没有内存池和自定义分配器.在这种情况下,不仅缓存会被不需要的数据填充,而且由于动态内存分配使用的任意地址,预取程序也无法正常工作.

拯救是回到OOP之前的时间并选择数据导向,这似乎是开发性能关键应用程序,操作系统等的首选.但为什么不使用两者的混合版本呢？排序的数据面向对象的编程？

在那么久的提议之后,让我们来看看手头的问题.我没有足够大的项目来测试这个概念的效率,所以社区的理论专业知识非常受欢迎.

如果不是存储自己的数据成员的对象,它们只存储对集合的引用,其数据成员按顺序存储在它们自己的容器中,并且它们的成员方法从这些容器返回数据,这样就不需要数据结束的几率应该减少在前往CPU的路上,并且增加近期"未来"所需的数据几率.逻辑假设是这种方法将提高预取器效率,缓存命中率和使用效率,并且还将减少自动和手动并行化中涉及的延迟.

你怎么看？

后期编辑:如果我们考虑结构和类填充,应用"数据方向模式"可能会更有利,如果"模型"有一个char和一个int数据成员,以OOP方式它将被填充,这只会污染进一步缓存,但是面向数据的存储模式可以顺序存储所有chars和所有ints,没有空间和缓存浪费.

目前我想为控制台优化我的3D引擎.更确切地说,我希望更多的缓存友好,并使我的结构更加面向数据,但也希望保持我不错的用户界面.

例如:

bool Init()
{
  // Create a node
  ISceneNode* pNode = GetSystem()->GetSceneManager()->AddNode("viewerNode");

  // Create a transform component
  ITransform* pTrans = m_pNode->CreateTransform("trans");
  pTrans->SetTranslation(0,1.0f,-4.0f);
  pTrans->SetRotation(0,0,0);

  // Create a camera component
  ICamera* pCam = m_pNode->CreateCamera("cam", pTrans);
  pCam->LookAt(Math::Vec3d(0,0,0));

  // And so on...
}

因此用户可以在他的代码中使用接口指针.

但
在我的引擎中,我目前存储指向场景节点的指针.

boost::ptr_vector<SceneNode> m_nodes

因此,在面向数据的设计中,最好使用数组结构而不是结构数组.所以我的节点来自......

class SceneNode
{
private:
  Math::Vec3d m_pos;
};

std::vector<SceneNode> m_nodes;

对...

class SceneNodes
{
  std::vector<std::string> m_names;
  std::vector<Math::Vec3d> m_positions;
  // and so on...
};

所以如果我想申请DOP,我会在这里看到两个问题.首先,如何在不让用户使用ID,索引等的情况下保持良好的用户界面？

其次,当一些向量调整大小而不让用户界面指针指向必杀技时,如何处理属性的重定位？

目前我的想法是实现一种handle_vector,你可以从中获得持久性"指针"的句柄:

typedef handle<ISceneNodeData> SceneNodeHandle;
SceneNodeHandle nodeHandle = nodeHandleVector.get_handle(idx);

因此,当实习生std :: …

在这张幻灯片中 (幻灯片15之后)建议使用

void updateAims(float* aimDir, const AimingData* aim, vec3 target, uint count)
{
     for(uint i = 0; i < count; i++)
     {
          aimDir[i] = dot3(aim->positions[i], target) * aim->mod[i];
     }
}

因为它的缓存效率更高.

如果我上课怎么样？

class Bot
{
    vec3 position;
    float mod;
    float aimDir;

    void UpdateAim(vec3 target)
    {
         aimDir = dot3(position, target) * mod;
    }
 };

 void updateBots(Bots* pBots, uint count, vec3 target)
 {
      for(uint i = 0; i < count; i++)
            pBots[i]->UpdateAim(target);
  }

我将该类的所有对象存储在一个线性数组中.

因为它们都在同一个数组中会有缓存未命中吗？为什么第一种方法会更好？

我正在测试读取多个数据流如何影响CPU缓存性能.我正在使用以下代码来对此进行基准测试.基准测试读取顺序存储在内存中的整数,并按顺序写入部分和.从中读取的顺序块的数量是变化的.来自块的整数以循环方式读取.

#include <iostream>
#include <vector>
#include <chrono>
using std::vector;
void test_with_split(int num_arrays) {
    int num_values = 100000000;
    // Fix up the number of values. The effect of this should be insignificant.
    num_values -= (num_values % num_arrays);
    int num_values_per_array = num_values / num_arrays;
    // Initialize data to process
    auto results = vector<int>(num_values);
    auto arrays = vector<vector<int>>(num_arrays);
    for (int i = 0; i < num_arrays; ++i) {
        arrays.emplace_back(num_values_per_array);
    }
    for (int i = 0; i < num_values; ++i) {
        arrays[i%num_arrays].emplace_back(i);
        results.emplace_back(0);
    } …

由于 Unity ECS，我最近阅读了很多有关 ECS 的文章。

ECS架构有很多明显的优势：

ECS 是面向数据的：数据倾向于线性存储，这是系统访问它的最佳方式。在体面的 ECS 实现中，数据是按顺序存储和处理的，对于任何给定的系统处理它的组件集几乎没有中断。

ECS 非常分割：它自然地将数据与行为分开，强制执行“组合而非继承”（google it）等。

ECS 对并行处理和多线程非常友好：由于事物的结构方式，许多实体和组件可以避免冲突并与其他系统并行处理。

然而，ECS 的缺点（与 OOP 或实体组件 [没有系统] 相比，直到最近在包括 Unity 在内的游戏引擎中很常见）很少被谈论，如果有的话。它们存在吗？如果他们这样做了，他们是什么？

有人想过如何编写一个完全没有分支的内存管理器(用C++编写)吗？我写了一个池,一个堆栈,一个队列和一个链表(从池中分配),但我想知道编写一个免费的通用内存管理器是多么合理.

这有助于构建一个真正可重用的框架,用于执行可靠的并发,有序CPU和缓存友好的开发.

编辑:无分支我的意思是不进行直接或间接的函数调用,也不使用ifs.我一直在想我可能会实现一些事情,首先将请求的大小更改为零,以便进行错误的调用,但实际上并没有更多的东西.我觉得这不是不可能的,但是这个练习的另一个方面就是在所说的"不友好"的处理器上进行分析,看看是否值得尽可能地努力避免分支.

在回答这个问题之前,请考虑分支预测.

我有一些场景,我可以在函数指针的帮助下用函数调用替换条件语句.这样的事情.(对于类似类型的senario,您可以考虑基于组件的编程而不是继承)

     class Shape
     {
        float Area()
        {
            if(type == SQUARE)
             {
                return length*length;
             }
            else if(type == RECTANGLE)
            {
             return length*breadth;
            }
        } 
     }

同一个类可以这样写.

       class Shape
     {
        void SetAreaFunction(void *funcptr)//this function is used to set the current AreaFunc
        {
             CurrentAreaFunc = funcptr ;//this holds the pointer to current area func
        }
        float SqauareArea();//this will return square area
        float RectangleArea();//this will return rectangle area 
        float Area()
        {
            currentAreaFunc();
        } 
     }

如果考虑上述情况,两者都会得到相同的结果.但是,我正在考虑性能开销.在第二种情况下,我通过函数调用避免了分支预测问题.

现在让我知道哪种更好的做法和"更优化的代码"在这种情况下.(顺便说一句,我不喜欢"早熟优化是万恶之源"的说法,因为优化有其优点所以我考虑优化我的代码!)

PS:我不介意是否有人详细介绍了即使在汇编代码中"分支预测有多糟糕".

更新:分析后(类似上面的代码),
如果条件成功在这种senario.Can任何人给出一个理由？功能调用代码可以预取,因为没有分支代码吗？但在这里它看起来是另一种方式..分支代码获胜!:O简介英特尔Mac Osx,GCC O3/Os优化.

因此,有这个规则试图if从高重复循环中提取语句:

for( int i = 0 ; i < 10000 ; i++ )
{
    if( someModeSettingOn )  doThis( data[i] ) ;
    else  doThat( data[i] ) ;
}

他们说,最好将其分解,将if语句放在外面:

if( someModeSettingOn )
  for( int i = 0 ; i < 10000 ; i++ )
    doThis( data[i] ) ;
else
  for( int i = 0 ; i < 10000 ; i++ )
    doThat( data[i] ) ;      

(如果您说"Ho!不要自己优化!编译器会这样做!")确定优化器可能会为您执行此操作.但是在典型的C++废话中(我不同意他的所有观点,例如他对虚拟功能的态度)Mike Acton说:"为什么要让编译器猜测你知道的东西？对我来说,最好的点是那些胶粘物.

那么为什么不使用函数指针呢？

FunctionPointer *fp ;
if( someModeSettingOn …

我正在编写物理引擎,并且很难找到设计数据存储的好方法.

我想要的功能:

• 有一个代表PhysicsBody的类
• 有一个表示碰撞体积的类(让我们说一个盒子)
• 每个物理主体可以再附加一个碰撞体积
• 可能没有碰撞体积的物理体
• 可选:没有物理实体的CollisionVolume.(想想Trigger Volumes)

现在我基本上有两个循环.一个更新模拟中的物理实体.它会更新它们的位置/速度/旋转.第二个循环对所有碰撞体积执行碰撞检测.它只是一个嵌套的for循环,用于检查每对碰撞体积之间的碰撞.(我知道它可以做得更好,但这是一个单独的主题)

我知道理想的方法是将对象存储在连续的数组中.

std::vector<PhysicsBody> m_bodies;
std::vector<CollisionVolume> m_colliders;

我用这种方法发现的问题:

• 它很难维护PhysicsBody - > CollisionVolume的关系.例如,如果我想从我的向量中删除CollisionVolume,我会将它与最后一个交换并弹回.数据被移动,如果我将一个索引存储到PhysicsBody中的CollisionVolume,它就不再有效了.
• 每当我销毁一个PhysicsBody时,析构函数将检查是否有任何碰撞量附加到它上面,并从物理系统中适当地删除它.问题是向量将制作内部副本并销毁它们,当发生这种情况时,它会通过删除不应被删除的碰撞卷而造成严重破坏.
• CollisionVolume实际上是一个基类(并非必须),而其他类派生类似于盒子/球体,什么不是.我可能不会使用继承并提出一些其他复杂的设计,但这是需要记住的.

我努力寻找解决方法,但最终存储了指针:

std::vector<PhysicsBody*> m_bodies;
std::vector<CollisionVolume*> m_colliders;

我想出的最小化缓存未命中的最佳解决方案是重载新/删除并将这些对象存储在内存池中,仅用于物理系统.

还有其他更好的解决方案吗？显然,表现是关键.