问题标签 [data-oriented-design]

我正在阅读这篇文章，这个人继续谈论每个人都可以如何从混合面向数据的设计和 OOP 中受益匪浅。但是，他没有显示任何代码示例。

我用谷歌搜索了这个，找不到任何关于这是什么的真实信息，更不用说任何代码示例了。有没有人熟悉这个术语并可以提供一个例子？这可能是其他东西的不同词吗？

任何人都想过如何编写一个完全无分支的内存管理器（在 C++ 中）？我已经编写了一个池、一个堆栈、一个队列和一个链表（从池中分配），但我想知道编写一个无分支的通用内存管理器有多合理。

这一切都是为了帮助创建一个真正可重用的框架，以进行可靠的并发、有序 CPU 和缓存友好的开发。

编辑：无分支是指不进行直接或间接函数调用，也不使用 ifs。我一直在想我可能可以实现一些东西，首先将请求的大小更改为零以进行错误调用，但实际上并没有更多。我觉得这不是不可能的，但是这个练习的另一个方面是在所说的“不友好”处理器上对其进行分析，看看是否值得像这样努力避免分支。

我已经开始进行自己的“数组结构”编码，但想知道是否有人知道已经存在的库或模板，用于在内存受限的硬件上进行密集的数据转换。

我想我正在寻找的是一种“内存中”容器，它允许我将插入排队直到一个同步点，并在迭代中“删除”。它不必是实际的删除（带有移动东西的开销），标记为已删除也可以。此外，为了缓存预热等性能，容器可能在很大程度上必须是连续的。连续块而不是完全连续块也可以，但是基于链表的容器不会因为内存或速度而减少它，因为数组通常由非常小的元素组成。

这就是为什么我假设某种表类适合，因为容器就像一个按主键排序的表。

虽然意义很好，但使用 std::vector 的想法实际上是不可能的，因为在迭代期间删除某些内容会因为访问数组的末尾和开头（计数）而弄乱缓存。

此外，没有理由不能对相同的数据进行多个迭代器的操作，因此将交换作为删除操作会导致其他迭代器跳过某些元素。这就是我提到排队插入的原因。

插入和删除改变了容器的形状，所以我假设它们可以通过同步操作来处理，但是插入删除的动作可以在当前内容的迭代过程中排队。

还有一个关于什么是面向数据的设计的问题，还有一篇经常被引用的文章（我已经读了五六遍了）。我理解这个的一般概念，特别是在处理例如 3d 模型时，您希望将所有顶点保持在一起，而不是用法线污染您的脸等。

但是，除了最琐碎的情况（3d 模型、粒子、BSP 树等）之外，我确实很难想象面向数据的设计是如何工作的。有没有什么好的例子真正包含面向数据的设计并展示了这在实践中是如何工作的？如果需要，我可以浏览大型代码库。

我特别感兴趣的是“有一个就有很多”的口头禅，我似乎无法与这里的其他人联系起来。是的，敌人总是不止一个，但是，你仍然需要单独更新每个敌人，因为他们现在的移动方式不同了，是吗？上述问题的已接受答案中的“球”示例也是如此（实际上，我在对该答案的评论中提出了这个问题，但尚未得到答复）。仅仅是渲染只需要位置而不需要速度，而游戏模拟需要两者，而不需要材料吗？还是我错过了什么？也许我已经理解了它，这是一个比我想象的要简单得多的概念。

任何指针将不胜感激！

目前我想为控制台优化我的 3d 引擎。更准确地说，我希望对缓存更加友好，并让我的结构更加面向数据，但也希望保持我漂亮的用户界面。

例如：

所以用户可以在他的代码中使用接口指针。

但是
在我的引擎中，我目前存储指向场景节点的指针。

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

对这个...

因此，如果我想应用 DOP，我会在这里看到两个问题。首先，我如何在不让用户使用 ID、索引等的情况下保持我漂亮的用户界面？

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

目前我的想法是实现一种handle_vector，您可以从中获得持久“指针”的句柄：

因此，当实习生 std::vector 调整大小时，它会更新其句柄。“句柄”存储指向实际对象的指针，并且“->”运算符被重载以实现良好的包装。但这种方法对我来说听起来有点复杂？！

你怎么看？如何保持良好的界面，但在内存中保持连续思考以更好地使用缓存？

谢谢你的帮助！

相对

使用示例

我认为第二种情况具有更好的空间局部性，因为所有数据都是交错的，并且应该同时加载到缓存中。在这两种情况下，我将同时处理所有球体。有输入吗？

我需要从中创建中小型静态哈希表。通常，这些将有 5-100 个条目。创建哈希表时，所有键哈希都是预先知道的（即键已经是哈希。）目前，我创建了一个 HashMap，我对键进行排序，所以我得到 O(log n) 查找，其中 3-5平均查找我关心的尺寸。维基百科声称带有链接的简单哈希表平均会导致整个表的 3 次查找，所以这对我来说还不值得麻烦（即，将 hash%n 作为第一个条目并进行链接。）鉴于我知道所有预先散列，似乎应该有一种简单的方法来获得快速、静态的完美散列——但我找不到一个好的指针。即摊销 O(1) 访问，没有（很少？）额外开销。我应该如何实现这样的静态表？

内存使用很重要，所以我需要存储的越少越好。

编辑：请注意，如果我必须手动解决一次碰撞，这很好。即，如果我可以做一些平均具有直接访问和最坏情况 3 间接访问的链接，那很好。这并不是说我需要一个完美的哈希。

在回答这个问题之前，也请考虑分支预测。

在某些情况下，我可以在函数指针的帮助下将条件语句替换为对函数的调用。类似这样的事情。（对于类似类型的场景，您可以考虑基于组件的编程而不是继承）

同一个类可以这样写。

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

现在让我知道在这种情况下哪个是更好的实践和“更好的优化代码”。（顺便说一句，我不喜欢“过早的优化是万恶之源”的说法，因为优化有它的好处，所以我请考虑优化我的代码！）

PS：即使在汇编代码中，我也不介意有人详细概述“分支预测有多糟糕”。

更新：分析后（类似上述代码），
如果条件在这种情况下成功。有人可以给出原因吗？功能调用代码可以预取，因为没有分支代码，对吧？但在这里它看起来是另一种方式..分支代码获胜！:O 在 Intel Mac Osx、GCC O3/Os 优化上进行了分析。

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

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

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

那么，这是做 DOD 的好方法吗（最好的方法？），这是合法的 c++ 吗？

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

我试图使用面向数据的设计来定位我的代码以尽可能有效地使用缓存，这是我第一次考虑这样的事情。我想出了一种方法来循环在屏幕上绘制精灵的相同指令，发送到函数的向量包括所有游戏实体的位置和精灵。

我的问题是条件语句是否摆脱了指令缓存中的绘图函数并因此破坏了我的计划？或者我在做什么通常是疯了？