问题标签 [data-oriented-design]

想想不同类型的集合，如Position, Color, Name. 可以使用集合中的相同键连接这些实例。密钥是 64 位长度的全局唯一标识符。目前，我使用哈希映射，但这并不理想。

我尝试将集合分开，但正如您所看到的，同时也需要多个集合的收集实例。当然，我也需要不时添加或删除单个元素，但这些情况对性能并不重要。

现在我想优化对单个集合的迭代。因此，我尝试将集合连续存储，这是面向数据设计理念的一部分。但是，我仍然需要非常快速地访问各个实例。直接使用数组是行不通的，因为这会分配太多内存，而且并非一种类型的所有实例都有另一种类型的对应物。另一方面，哈希映射对于迭代来说不是最优的。

我认为数据结构必须在内部使用数组。我应该在这里使用哪种数据类型？C++标准库中是否实现了这样的数据结构？

Please see the following link, page 22 onwards:

http://research.scee.net/files/presentations/gcapaustralia09/Pitfalls_of_Object_Oriented_Programming_GCAP_09.pdf

the above link suggests if I have an object containing vectors/arrays like this:

and the code below iterates through a vector of MyClass and performs some Math on std::vector b:

when we retrieve each MyClass object all the data from both of the arrays will be loaded in to the cache line. Is this true? I didnt think the data a would be loaded in to the cache line because the address for accessing b would be calculated and loaded.

I am trying to get an idea how much of a MyClass object is loaded in to the cache in comparison to the useful data required for processing?

I can understand if the very first b element shared the same cache line as the very last a elementbut I didnt think the whole object would get loaded in to the L2/L3 cache just to process one part of the object?

来自 C/C++ 的背景，关于减少缓存未命中的对象的内存布局是至关重要的，尤其是在控制台上工作时。面向数据的设计通常比面向对象的设计更受青睐，以帮助保持相关对象在内存中彼此靠近（尤其是在性能关键区域）。

最近，我一直在做一些 Javascript 开发，我想知道 Javascript 社区内的普遍共识是什么。

由于我在 Javascript 方面的经验有限，在进行分析时，我经常会惊讶地看到完全出乎意料的结果。Javascript对象/结构的内部内存布局和实现因浏览器而异，我想知道是否值得尝试优化。

我在 jsPerf 上创建了一个简单的测试用例 ( http://jsperf.com/object-vs-data ) 来比较两种方法的性能，虽然它在 Chrome 上显示了性能提升，但在 Safari 上没有明显的加速。

在 Javascript 中，我是否应该关注对象的内存布局？还是更像是“以一种方式实现，然后在需要时进行优化”类型的东西？

第二个选项似乎有点浪费（就开发时间而言），特别是如果有一些好的指导方针可以遵循。

谢谢~

补充信息：这基本上是我在 Javascript 中实现这两种方法的方式。上面的 jsPerf 测试用例是这样实现的。

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

以下是在 Intel Core 2 Quad CPU Q9550 @ 2.83GHz 上拆分 1-80 路的时间：

8 个流之后的速度提升对我来说是有意义的，因为处理器具有 8 路关联 L1 缓存。24 路关联 L2 缓存反过来解释了 24 个流的颠簸。如果我得到的效果与为什么一个循环比两个循环慢这么多？，其中多个大分配总是在同一个关联集中结束。为了比较，我在最后一个大块中完成分配的时间包括在内。

但是，我并不完全理解从一个流到两个流的颠簸。我自己的猜测是它与预取到 L1 缓存有关。阅读Intel 64 and IA-32 Architectures Optimization Reference Manual似乎 L2 流式预取器支持跟踪多达 32 个数据流，但没有为 L1 流式预取器提供此类信息。L1 预取器是否无法跟踪多个流，或者这里还有其他东西在起作用？

背景

我正在对此进行调查，因为我想了解将游戏引擎中的实体组织为数组结构样式中的组件如何影响性能。目前看来，转换所需的数据在两个组件中而不是在 8-10 个组件中对于现代 CPU 来说并不重要。但是，上面的测试表明，有时避免将某些数据拆分为多个组件可能是有意义的，如果这将允许“瓶颈”转换仅使用一个组件，即使这意味着某些其他转换必须读取它是不感兴趣。

在一个块中分配

如果改为分配多个数据块，则仅以跨步方式分配和访问一个数据块时的时间如下。这不会将凹凸从一个流变为两个，但为了完整起见，我将其包括在内。

这是修改后的代码：

编辑 1

我确保 1 对 2 拆分的差异不是由于编译器展开循环并以不同方式优化第一次迭代。使用__attribute__ ((noinline))我确保工作函数没有内联到主函数中。我通过查看生成的程序集验证了它没有发生。这些改变之后的时间是一样的。

我有一个这样的树结构：一个模型有一个根节点，每个节点有任意数量的子节点和任意数量的网格。

在我的应用程序中，很多时间都花在遍历这棵树并进行诸如视图截头体剔除和矩阵乘法之类的计算上。目前，它是幼稚的实现，其中每个节点都有子节点和网格的向量，并且树是递归遍历的。这是非常缓慢的。

我一直在研究面向数据的设计，我喜欢它对缓存非常友好的想法。我一直在想这样的事情：

现在我需要遍历树以获得可见网格的列表。在每个节点上，我必须检查该节点是否可见。以下分支：

• 节点可见。它下面的所有子节点和网格也是可见的。不要深入这个分支。检查相同深度的其他节点。
• 节点不可见。此节点或其下方的子节点或网格不可见。不要深入这个分支。检查相同深度的其他节点。
• 该节点是部分可见的。一些节点和/或一些网格是可见的。必须深入层次结构。

树是静态的。一旦模型被加载到应用程序中，树就永远不会改变。所以不知何故，我必须能够使用这些信息来获得一个有效的结构。

我很困惑如何解决这个问题。

几个问题；

1. 如何在内存中布局节点？是第一个索引的根节点吗？其他节点是根据深度添加的吗？
2. 如何在不使用递归的情况下迭代树？我不想访问每个节点，除非我真的必须这样做。例如，如果 depth=2 的节点不可见，则不应测试其所有网格和子节点（及其网格），而应完全跳过。

在许多关于面向数据设计的著作中发挥突出作用的一个特征是，在许多情况下，而不是 AoS（结构数组）：

在 SoA（数组结构）中排列数据更有效：

现在我正在寻找一种解决方案，它允许我在不改变调用接口的情况下在 AoS 和 SoA 之间切换，也就是说，我可以用最少的努力并且没有额外的运行时成本（至少到过度间接的程度），调用例如cs[42].foo;，无论我使用哪种数据排列。

我应该注意，上面的示例语法是理想的情况，这很可能是不可能的，但我也会对近似值非常感兴趣。有接盘侠吗？

我正在编写一个物理引擎，并且很难找到一种设计数据存储的好方法。

我想要的功能：

• 有一个代表 PhysicsBody 的类
• 有一个代表碰撞体积的类（比如说一个盒子）
• 每个物理体可以附加一个以上的碰撞体积
• 可能有没有碰撞体积的物理体
• 可选：没有物理实体的 CollisionVolume。（想想触发量）

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

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

我发现这种方法的问题：

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

我努力寻找解决方法，但最终改为存储指针：

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

还有其他更好的解决方案吗？显然，性能是关键。

我想将面向数据的设计（基于例如这篇文章）应用于我的简单物理引擎。我专注于优化碰撞测试，因为它是其中最昂贵的部分。

我已经将可能与玩家碰撞的边界球体组织成单一的vector：

我在单个函数/方法中测试与它们的冲突。在那一点上，一切对我来说都很清楚。

问题是，我还有一些更通用的结构，例如：

我想以相同的方式创建不是一个好习惯std::vector<Polygon>，因为嵌套vector( points) 将在内存中占据很多位置（保留它）。

另一方面，我不能假设总是有 2、3、4 或 10 个点（差异很大，最多大约 20，但通常要少得多）。

而且我不想从Polygon一般结构切换到例如三角形系列（因为在许多计算中它比分离三角形更快）。

那我该怎么办？我想本着面向数据设计的精神，在我的Polygon.

我必须摆脱内部vector（points）吗？如果有怎么办？

假设我有一个看起来像这样的 HTML 结构。每个左上下文字段和右上下文字段都是相关的，并且在后端应该可以将左链接到其右同事。

并且用户可以根据需要添加任意数量的附加行。我将如何将值发布到 PHP 文件？

我是否应该将所有行包装成一个巨大的形式，然后调用.serializeArray()？还是每行一个表格？

从面向数据的方法来看，处理这个问题的最佳方法是什么？我会将数据发送到后端，但我想让后端开发人员尽可能轻松地访问数据。

现在，在阅读 Internet 中的不同资源时，如果您正在按顺序处理大型数组，那么数组结构似乎是一种非常高效的数据存储方式。

例如在 C++ 中

允许更快地处理大型数组（感谢 SIMD）比

GPU 是为大规模并行计算而设计的处理器。SIMD 是这里的“必备”。所以结论是数组结构在这里最有用。

但 ...

• 我从来没有在任何地方看到过这样的 GLSL 着色器（我只是觉得不对劲）：

  或类似的东西也很少见：

  每个人，包括我，似乎都更喜欢这样写 GLSL：

  /li>

• 此外，在阅读有关顶点数组数据的原始 OpenGl Wiki 时，我想知道，突然间，应该首选交错数据：

  作为一般规则，您应该尽可能使用交错属性。

问题：尝试在 GLSL 着色器中使用数组结构有意义吗？

什么是真的？GPU 是否针对我们喜欢编写着色器的方式进行了高度优化，但实际上并没有任何区别？