问题标签 [data-oriented-design]

我对面向数据的设计有所了解，例如，您拥有一个包含多个对象的类，而不是为单个对象创建一个类，例如：

你将会拥有：

（我希望这是对面向数据设计的正确解释）但是，有没有像数据驱动的方式来做这件事或什么？

我有 N 个数组结构：

我有 M 程序来更新这些数组结构：

是否有一种设计模式可以迭代 SoA 集合中所有相同类型的数组？

我可以考虑编写一个模板函数并为具有这些属性的每个数组结构调用它。是这样吗？这通常可以很好地扩展吗？

在 Richard Fabian 的Data Oriented Design中，他给出了一个基于组件的游戏对象示例，其中对象可以具有的不同属性被分成不同的数组，并通过处理这些数组中的数据来创建功能。他举了一个渲染的例子：

我感到困惑的是这段代码是如何对缓存友好的。据我了解，面向数据的设计通过将特定操作所需的相关数据保存在连续内存中来实现更好的性能，因此当您迭代数据进行更新时，您将减少缓存未命中的数量。然而，在这个例子中，渲染需要来自 3 个不同“组件”的信息，因此在每次迭代中，您将访问不同的数据数组，更不用说如果任何组件需要与每个组件交互，则必须查找 ID 可能会影响性能别人的数据。

我正在开发一个非常简单的 2D 游戏来练习面向数据的设计。如果我要在我的游戏中模拟一个基本行为，比如让对象按照上面给出的模式移动，它会是这样的：

然后在物理更新中，我会用相应的 in更新每个Positionin 。positionsArrayVelocityvelocitiesArray

缓存将这个操作所需的数据组合到一个结构中不是更好吗：

所以您拥有更新所有连续存储的位置所需的数据？

很长一段时间以来，我一直对 C++ 的性能感兴趣。

很多事情不断出现，无论是在会议上还是在书中：

不要使用虚函数，将数据保存在缓存、分支等中。

有许多带有视频游戏示例的基准测试可以显示性能差异。问题是，这些例子总是很简单。

这在超过 20 行的代码中如何真正起作用？在 AAA 视频游戏、金融等领域。

如果我有 100 种类型的对象，它们具有不同的更新、不同的行为和其他乐趣，那么通过多态性或函数指针来设置很容易。

现在，按照给出的建议来制作强大的代码，上述选项是不可能的。因此，我们更愿意拥有 100 个我们将单独更新的阵列。我们可以很好地访问缓存，函数可能是内联的等等。总之，原则上性能会更好。

因此，我必须在每一帧调用 100 个数组和 100 个不同的函数。表格根据发生的情况动态变化，新玩家出现，怪物死亡等。一些数组将有 0 个元素处于活动状态，其他 10 个......我会调用没有工作的函数（没有活动元素的数组）但我没有选择，我必须有一个标志或查看元素是否在我的数组中处于活动状态。

我最终得到这样的结果：

当然，毫无疑问会有一个函数来管理对对象的所有更新调用，一个用于行为等，但为了简化它，如上所述。

留在电子游戏中，如果一个玩家的 x 动作导致了 y 个怪物的到来，那么有几种类型的怪物具有不同的功能。因此，我们将把怪物放在我们的桌子上，这一次处理这些怪物的功能将起作用。

我们可以使用 ECS 模式或衍生模式，但它们可能具有非常不同的行为（指导它们或其他的 ia）、不同的组件，因此需要不同的函数来处理它们。它们将在代码中被硬调用，因为我们没有多态性或函数指针，我们必须在每一帧检查它们是否有要处理的东西。

真的是这样做的吗？假设我有 500 种类型？1000？

编辑：

很多评论，所以我会在这里回复你。

正如 Federico 所说，我想知道这些建议是否对书籍有益，但在实践中则不然。

我看过的几个资源：

https://www.agner.org/optimize/#testp 好几本书

www.youtube.com/watch?v=WDIkqP4JbkE&t Scott Meyers 谈记忆

https://people.freebsd.org/~lstewart/articles/cpumemory.pdf 关于内存

www.youtube.com/watch?v=rX0ItVEVjHc&t 面向数据的编程

https://www.dataorientdesign.com/dodbook/ 面向数据的设计书籍

还有其他资源，但它已经让您了解我的基础

在我的程序中，我收集了一些代表一些文件的“条目”。它看起来像这样：

假设我想按属性之一（路径、类型、大小或修改时间）对条目进行排序。有什么方法可以将所有向量“链接”在一起，以便在对其中一个向量进行排序时，其他向量的元素将以完全相同的方式排序？

我想保持类似数据的数组连续进行处理。为简化起见，假设我想将 s 数组与ints 数组分开，char这样当我想显示字符时，我可以连续循环遍历所有字符，而无需获取整数。现在两个数组的前 32 个索引都属于一个对象，接下来的 32 个索引属于另一个对象。我希望能够对数组应用一种“蓝图”或“千篇一律”，以将数组的每个“拥有”部分组合在一起。我的第一个想法是给每个对象一个链接到它的数组部分的成员变量，就像这样

但我发现这样一个对象的大小在 32 位版本上是 8 个字节，在 64 位版本上是 16 个字节。它正在存储指针。这些地址在编译时是已知的，所以我想我应该能够用硬编码地址替换指针。模板非常适合让编译器解决这种问题，所以我尝试了这个：

但是我得到一个编译器错误，指出需要一个编译时常量表达式。做了一些研究，我发现 stackoverflow 上的另一个答案可以解释原因：Reference as a non-type template argument。它声称引用变量不是 id 表达式（类似于字符串文字）并且不能用作模板参数。那么有没有办法解决这个问题？还是有更好的方法来完成我想做的事情？为了便于测试，我为这种情况提供了一些完整的代码：

作为附加说明，每个对象可能并不总是“拥有”数组中相同数量的元素，我希望有一种方法让具有相似数据的不同对象拥有不同大小的数组部分，但是当我在编译时已经知道所有对象实例时，仍然知道存在哪些成员，而不会浪费 RAM 存储指针。

我最近一直在为 C 中的一个项目制作自定义哈希映射。

我的哈希图目前是这样工作的：

• 密钥通过Fowler–Noll–Vo 1a 散列函数进行散列以最小化冲突

• 如果项目数超过桶数，则发出重新哈希，其中桶数加倍

• 每个存储桶都包含一个必须在堆上分配的项目数组。这意味着每次创建哈希映射时，都会1 + numberOfBuckets完成堆分配。

我目前对这个哈希映射的一个问题是，创建它对于我的用例来说太慢了（我必须创建很多，在数百万的范围内）。

提高创建速度的一个简单解决方案是仅在需要时分配存储桶，但这实际上只会延迟分配，并且性能增益将是最小的。

还想到的一个想法是每个桶只有一个固定大小的项目数组。这样，如果操作正确，我只需要为每个映射分配一个大堆。但是，存储桶数组存在不可解决溢出的轻微风险，尤其是在较小的大小时。我计算过，从 32 个桶和 18 个项目的固定容量开始，这个概率大约是 10^(-19)（如果我的数学是正确的），并且桶越多它会变得更小。因此，发生该错误的可能性基本上可以忽略不计。

特别是本着面向数据设计的精神，我发现哈希映射的这个概念非常有趣，但我找不到任何关于忽略可忽略的错误风险是否是一种可以、现在或什至应该使用的编程实践一点也不。我真的很想知道这是否是任何地方的已知做法，以及是否可以在哈希映射之外的其他地方找到它。

我正在用 C++ 编写一个共享库，并且（主要是教育性的）目标是让库完成的每一点堆分配都生活在一个连续的块中，在库的特定部分初始化时分配。我在开始时用一个实现了这一点malloc，它实现了两个堆栈（一个大且不可弹出用于持久内存，一个具有额外的机器作为辅助运行时堆栈）和一个用于半持久数据的二进制伙伴系统。

鉴于这种自我强加的约束，在这变成 XY 情况之前，我将描述我要解决的问题。我的图书馆有这些项目，可以有一些属性、结构，比如A和B. 我有更多类似 ECS 的数据扁平化，而不是具有单独继承的 OO 方法。项目只是 id，我记账谁在单独的数组中拥有每个属性。所以，如果我有 5 个项目，也许 {1, 3, 4, 5} 有属性 A 而 {2, 3, 4} 有属性 B，代码可能看起来像：

这些数组都可以按照我的约束进行分配，通过给它们一个固定的大小并通过空终止来“动态地”改变程序相关的大小，如数组中所示（我意识到这只是稀疏的临时实现数组。我喜欢它，因为我知道编写程序时的大小）。现在，我的库需要的功能如下。我希望我的用户能够创建项目实例（最多为某个最大数量），并在事后添加/删除属性。

为此，我希望我的用户按名称而不是繁琐的 id 来引用项目。然后我需要在我的 API 中公开以下函数

我需要将名称存储在内存中，因为我想向脚本（当前是 Lua）公开类似的功能。想到的解决方案是某种关联映射，将字符串作为键，将项目 ID 作为值。std::unordered_map由于它在地图本身和std::string作为键的动态分配，我一直在避免。目前我正在做的就是定义一个const char** itemNames写入CreateItem的对象，并通过它们进行基本的线性搜索，char在char每个条目上进行比较。我没有对它进行基准测试，也不认为它会特别麻烦，但我问这个问题是希望有一个更优雅的解决方案，它更适合并且（理论上）更有效。