4

我找不到一个对 CPU 缓存友好的框架实现，这意味着系统在每个游戏循环周期中遍历的数据都存储在连续的内存中。

Let's see, systems traverse on specific entities that satisfy their conditions, i.e. the entity should contain A, B, C components to be processed by X system. This means that I need a contiguous memory that contains all entities and components (not references, as far as references are not cache friendly, and you will have lots of cache misses) in order to obtain them from RAM as much fast as it is possible during the processing of X system. But right after the processing of X system, Y system starts to operate on a set of entities that satisfy to its conditions e. g.all entities containing A and B. This means that we deal with the same set of entities as X system plus some other entities that have A and B. This means that we have two contiguous memories which have duplicate data. First of all data duplication is very bad for known reasons. And also this, in its turn, means that we need a synchronization, which again is not CPU cache friendly as far as you need to find some entities from one vector and update with the new data which is contained in another vector.

This is just one of my thoughts. There are other, more realistic, thoughts for Entity Component System Framework data model, but in each model I could figure out there is the same problem: during each game loop cycle you can not prevent lots of cache misses because of not contiguous data.

Can anyone please suggest an implementation, article, example just something on this topic, that can help me understand what data model should be used to obtain cache friendly design, as this is one of the most critical things in game performance.

4

3 回答 3

7

我会选择 junkdog 的答案（因为我写了链接的文章；）），但这是另一个不同的，接受它：

如果你想要缓存友好的设计，你需要列出：

  1. 您的微处理器
  2. 您的处理器架构
  3. 您的总线架构
  4. ...
  5. 您的每个子帧工作集大小
  6. 所有游戏对象的总工作集/RAM
  7. 您的特定游戏中的互连数量
  8. ... ETC

根据这些要求的严格/松散程度，您将对您的设计做出不同的简单（或困难）决定。游戏开发者经常重写内存管理。他们这样做不是因为他们很愚蠢，而是因为每个项目（重新）优化（这是 AAA 标题？还是 AA 标题？图形更重要？还是网络延迟？）很容易/值得。 ..等）和每个硬件（在PC上，目标硬件每个月都会改变）

我建议你选择一套硬件，创建一个简单的基于 ES 的游戏，然后开始尝试设计一个缓存友好的内存使用 - 并公开记录它，使其全部开源，看看你是否能让其他人感兴趣在运行你的基准测试。

于 2014-11-01T20:28:09.013 回答
4

Adam Martin/t=machine 最近发布了实体系统的数据结构：连续内存- 这是我所知道的唯一一篇专门处理 ECS 中的内存布局的文章。

您没有指定语言，但在 java 世界中，entreri和artemis-odb（通过 PackedComponents / 也免责声明：我的端口）处理 Adam 所说的“迭代 1：每个 ComponentType 的 BigArray”。

于 2014-05-06T18:55:57.667 回答
2

从理论上讲，我认为这个问题需要付出太多的努力才能证明完美解决它所花费的时间是合理的。过去我自己已经在这方面花费了太多时间，想出复杂的解决方案只是为了回到一个更简单的解决方案。我们最大的热点不一定来自实体/组件遍历的非强制缓存未命中。许多系统将为可以加速的特定实体承担大量工作，并且许多组件通常会大到足以减少尝试以适合多个邻居的方式对它们进行排序的好处。缓存行。

也就是说，如果您只是想以一种能够提供缓存友好的内存访问模式的方式对组件进行排序，但仅适用于一个或两个没有重叠冲突的关键系统，并且可能适用于绑定的最小和最多的组件类型为了提供最大的帮助，在这里和那里进行一些后处理很容易。我建议您寻找它来响应您的热点。

并且通常只是一些基本的排序将帮助您减少所有系统的缓存未命中份额，而不管它们处理的组件组合是什么。如果您从这样的代表开始（我使用的）：

在此处输入图像描述

在运行游戏状态并偶尔删除和添加组件一段时间后，您最终会得到如下内容：

在此处输入图像描述

您可以解开混乱并将其整理如下：

在此处输入图像描述

这可以通过基数排序非常便宜地完成，基于拥有它们的实体索引作为线性时间的键对元素进行排序。通过一个体面的实现，您通常可以偷偷摸摸，而不会注意到帧速率有任何问题。我以与上面的数据表不同的方式绘制图表（只是为了清楚哪个组件属于哪个实体），但想法相同。只需根据实体索引（实体 ID）对组件数组进行基数排序，更新链接（使用并行数组映射前后索引，使用实体索引作为键与组件数据一起排序），现在一切一切都很好，整洁，没有与零星的访问模式纠缠在一起。

这可能不会为对特定实体组合感兴趣的系统提供一组完全连续的组件（可能存在上图中的一些间隙），但至少它不会在内存中来回反复，可能不得不将内存区域加载到缓存行中，只是为了驱逐它，然后再回来重新加载它，在这些情况下，很可能会连续访问许多组件。

如果这还不够好，那么考虑到特定实体具有系统对特定查询感兴趣的组件，您可以针对系统想要的那些特定实体将组件排序到数组顶部，关闭任何差距，现在您对系统具有完美的连续性，专门处理包含运动和渲染组件的实体。这也可以在线性时间内完成，并在这里和那里进行后期处理，可以在移除和添加多个组件后定期应用。

我从来没有发现有必要走这么远。我只是不时对实体 ID 进行广义排序，以普遍改进所有系统的访问模式（但没有针对任何给定系统的最佳解决方案）。您的用例可能需要一个最佳版本，但我建议只关注具有真正受益的大热点的关键系统。

于 2017-12-21T12:17:24.887 回答