本文档译自 gamesfromwithin.com 的文章"Data-Oriented Design Now And In The Future"，作者 Noel，原文参见此处
概述 - Overview
最近有很多关于面向数据设计的讨论（和批评）。我想解决一些已经提出的问题，但在此之前，我将从我最近的《Game Developer Magazine》发表开始。如果你有任何你想解决的问题，写下评论，我会尽力回答我所能回答的一切。
去年我写了一篇关于面向数据的设计的基础介绍（请见2009年9月的《游戏开发者》）。自从那片篇文章以后，面向数据的设计在游戏开发中获得了很多关注，并且很多团队都在开始为性能敏感的系统考虑数据方面的东西。
快速回顾一下，面向数据设计的主要目标是在现代硬件平台上实现高性能。具体来说，这意味着需要充分利用内存访问、多核心和删除任何不必要的代码。面向数据设计的另一个好处是代码变得更加模块化，更容易测试。
面向数据的设计将注意力集中在可用的输入数据和需要生成的输出数据。不必过度关注代码（像传统的计算机科学那样），而是将它视为用来把输入数据有效地转换为输出数据的东西。
应用面向数据设计 - Applying Data-Oriented Design
将这些思想应用到一个已经在大部分同构数据上工作的完整系统是非常容易的。游戏中的大多数粒子系统可能都是这样设计的，因为它们的主要目标之一是以非常高效，高帧率的方式处理大量粒子。声音是另一个自然地考虑数据的系统。
那么，是什么阻止我们将其应用于游戏代码库中所有对性能敏感的系统呢？主要是我们思考代码的方式。我们需要真正地准备好观察数据，并愿意将代码分成不同的阶段。让我们举一个例子，看看在为数据访问进行优化时，如何重构代码。
清单1显示了通用游戏AI一个比较典型的更新函数伪代码。糟糕的是，该函数可能是虚函数，不同类型的实体可能以不同的方式实现它。让我们暂时忽略这一点，把注意力集中在它具体做了什么。特别地，伪代码中指出，在 Entity 的一部分 Update 逻辑中，它执行许多光线投射和条件查询，并根据这些结果更新一些状态。换句话说，我们面对的是面向对象编程中常见的典型的树型遍历代码结构。
// 清单1
void AIEntity::Update(float dt)
{
DoSomeProcessing();
if (someCondition && Raycast(world))
DoSomething();
if (someOtherCondition && BunchOfRayCasts(world))
DoSomethingElse();
UpdateSomeOtherStuff();
}
光线投射是游戏中的 Entity 非常常见的操作。这能允许它们感知周围的物体并使他们能够对周围环境做出正确的反应。不幸的是，光线投射是非常重量级的操作，并且有可能会访问很多不同区域的内存：空间数据结构、其他实体表示、碰撞网格中的多边形等等。
此外，Entity 的 Update 函数很难在多个核上并行化。很难弄清楚在这个函数里有多少数据会被读/写，并且其中的一些数据（比如关于世界的数据结构）可能难以保护或只能以高昂的代价防止来自多个线程的同时读写。
如果我们稍微重新组织一下，就可以显著提高性能和做到并行化。
打破和重组 - Break Up And Batch
在不观察 Entity 的 Update 中任何具体细节的情况下，我们就已经注意到十分引人注目的光线投射相关的东西。光线投射和 Entity 的其他操作相比更具独立性，并且它相当重量级，而且可能有很多次，所以它是分解为单独步骤的完美候选者。
清单2 显示了分解后的 Entity Update 代码。Update 函数现在被分为两个不同的阶段：第一个阶段做一部分和光线投射无关的事情，然后根据情况决定需要执行哪些光线投射。
// 清单2
void AIEntity::InitialUpdate(float dt, RayCastQueries& queries)
{
DoSomeProcessing();
if (someCondition)
AddRayCastQuery(queries);
if (someOtherCondition)
AddBunchOfRayCasts(queries);
}
void AIEntity::FinalUpdate(const RayCastResults& results)
{
UpdateSomeOtherStuff(results);
}
负责更新游戏的代码批量处理所有AI实体（见清单3）。在这里并不是给每个 Entity 依次调用 InitialUpdate() 函数、光线投射相关函数和 FinalUpdate() 函数，而是一次遍历所有的 AI Entity 并为他们调用 InitialUpdate() 并添加所有光线投射请求作为输出数据。 一旦收集了所有的光线投射请求，就可以一次性处理它们并存储其结果。最后，它执行最后一个步骤，即使用每个 Entity 的光线投射结果调用 FinalUpdate()。
// 清单3
RayCastQueries queries;
for (int i = 0; i < entityCount; ++i)
entities[i].InitialUpdate(dt, queries);
// Other update that might need raycasts
RayCastResults results;
for (int i = 0; i < queries.count; ++i)
PerformRayCast(queries[i], results);
for (int i = 0; i < entityCount; ++i)
entities[i].FinalUpdate(results);
通过从 Update 函数中删除光线投射调用，我们显著缩短了调用树。这些函数更独立，更容易理解，并且由于更好的缓存利用率，可能效率更高。你还可以看到，现在可以将所有光线投射请求发送到一个核心，而另一个核心可以忙于更新不相关的内容（或者将所有光线投射分布到多个核心，这取决于你的粒度级别），这让我们更容易地并行化。
注意，在对所有 Entity 调用 InitialUpdate() 之后，我们可以对其他可能也需要光线投射的游戏对象进行一些处理，并将请求全部收集起来。这样，我们可以批量处理所有的光线投射，并一次性计算它们。多年来，图形硬件制造商一直在研究应该如何批量处理渲染调用，避免一次仅绘制单个多边形。这是类似的道理，通过在一次调用中批量处理所有光线投射，我们有可能获得更高的性能。
继续划分 - Splitting Things Up
通过这种方式重新组织代码，我们真的获得了很多提升吗？我们对所有 AI Entity 进行两次遍历，所以从内存的角度来看，情况会不会更糟？最终，你还是需要衡量它，并将两者进行比较。在现代硬件平台中，我的预期是性能会更好，因为即使我们遍历了两次 Entity，我们也能更好地使用代码缓存，并按顺序访问它们（这样CPU就可以预取下一个了）。
如果我们对 Update 函数的更改仅限于此，而其余代码是通常的树型的深度遍历代码，那么我们可能不会有太多收获，因为每次 Update 的其他部分都可能会突破缓存限制。我们可能需要将相同的设计原则应用到 Update 函数的其余部分，以便开始看到性能改进。但至少，有了这个小的改变，我们也使并行化变得更容易了。
我们现在能做到的一件事，就是通过改变我们的数据来改变我们使用它们的方式，而这是大幅提高性能的关键。例如，在看了 Entity 是如何在两个单独的过程中更新的之后，你可能会想到，在第一次更新中，只会有一部分存储在 Entity 中的数据被使用到，而第二次更新将（用光线投射结果）访问更特定的数据。
此时，我们可以将 Entity 类分成两组不同的数据。在这一点上，最困难的事情之一是以某种有意义的方式命名这些数据。它们不再代表真实的物体或真实世界的概念，而是一个概念的不同方面，并纯粹根据数据的处理方式进行分解。因此，以前的 AI Entity，现在可以变成 EntityInfo（包含位置、方向和一些高级数据）和 AIState（具有当前目标、命令、要遵循的路径、目标敌人等）。
整个 Update 函数现在在第一个阶段中只处理 EntityInfo 结构，在第二个阶段中只处理 AIState 结构，使其更加缓存友好和高效。
实际上，第一个阶段和第二个阶段都必须访问一些公共数据（例如当前状态：逃跑、忙碌、探索、空闲等）。如果只是少量数据，最好的解决方案可能是简单地在两个结构（EntityInfo 和 AIState）上都复制这些数据（这与计算机科学中的所有常识背道而驰）。如果公共数据较大或是读写的，那么为其提供单独的数据结构可能更有意义。
在这一点上，引入了一些不同的复杂性：跟踪不同结构间的所有关系。在调试时，这可能特别具有挑战性，因为属于同一逻辑实体的一些数据并非存储在同一结构中，而且在调试器中会更难处理。不过，充分利用索引和句柄会让这个问题更轻松一些（见 《游戏开发者》 2008年9月刊中的管理数据关系）。
条件执行 - Conditional Execution
到目前为止，事情很简单，因为我们假设每个 AI Entity 都需要更新和一些光线投射查询。但是，这不是很现实，因为 Entity 的行为可能非常突发：有时需要大量光线投射，有时它们又处于空闲状态，暂时不需要任何光线投射。我们可以通过在第二个阶段的 Update 函数中添加条件执行来处理这种情况。
按条件执行更新的最简单方法是向 FirstUpdate() 函数添加一个额外的输出参数，以指示 Entity 是否需要第二次更新。如果需要任何光线投射查询，那我们也会获得该获得的信息。然后，在第二步中，我们只更新那些需要第二次更新的 Entity 列表中的 Entity。
这种方法最大的缺点是，第二次更新从线性遍历内存变为跳过部分 Entity，这可能会影响缓存性能。所以我们原本以为的性能优化结果却让事情变慢了。除非我们能获得显著的性能改进，否则通常最好简单地为所有 Entity 做这项工作，无论它们是否需要。当然，如果平均只有不到10%或20%的 Entity 需要光线投射，那么就有必要避免对所有 Entity 都进行第二次更新并承担带来的性能惩罚。
如果在第二次更新中要更新的 Entity 数量相当少，另一种方法是将第一次更新中的所有必要数据复制到一个新的临时缓冲区中。然后，第二次更新可以在没有任何性能损失的情况下按顺序处理该数据，并且完全抵消了复制数据对性能的影响。
最后，另一种选择是当执行的条件在帧与帧之间保持相当的相似时，可以将需要光线投射的 Entity 重新定位在一起。通过这种方式，复制是最小化的（在需要光线投射时将 Entity 交换到数组中的新位置），并且我们仍然可以获得连续的第二次更新的好处。为此，所有 Entity 都需要能够可重定位，这意味着我们需要使用句柄（及其他间接形式）或更新所有引用的方式来表示已改变位置的 Entity 。
不同的模式 - Different Modes
如果 Entity 可能有几种完全不同的执行模式，该怎么办？即使是同一类型的 Entity，通过线性调用 Update 函数遍历它们也可能最终为每个 Entity 使用了完全不同的代码，这将导致较差的代码缓存性能。
在这种情况下，我们可以采取几种方法：
- 如果不同的执行模式也对应到 Entity 数据的不同部分，我们可以将它们视为完全不同的 Entity，并将这些数据组件分开成单独类型。这样，我们就可以分别遍历每个类型并获得所有性能优势。
- 如果数据基本相同，只是对它们执行的代码有所不同，我们可以将所有 Entity 保留在同一个内存块中，但重新排列它们，使处于相同模式的 Entity 相邻。同样，如果你可以重新排布数据，这是非常简单和高效的（当状态发生变化，只需要交换几个 Entity）。
- 别管它！面向数据的设计最终要考虑数据及其对程序的影响。这并不意味着你必须总是优化它的方方面面，特别是如果收益不够显著，那么就没必要增加复杂性。
面向数据设计的未来 - The Future
从数据的角度来考虑程序并进行这些优化是否合理利用了我们的时间？随着硬件的改进，这些优势会在不久的将来消失吗？就我们目前所知，答案肯定是否定的。单CPU内核的高效内存访问是一个非常复杂的问题，当我们增加更多的内核时，情况会变得更糟。此外，CPU中晶体管的数量（这是功率的粗略衡量标准）继续以比存储器访问时间快得多的速度增长。这告诉我们，除非有新的技术突破，否则我们将在很长一段时间内面临这个问题。这就是我们现在需要解决的问题，并围绕它构建我们的技术。
我希望能在未来看到一些东西，让面向数据的设计变得更容易。我们都可以梦想一种新的语言，它将神奇地做到出色的内存访问和轻松的并行化。但要取代C/C++和所有现有的库总是很难实现的。从历史上看，游戏技术的最佳进步都是渐进式的，而不是抛弃现有的语言、工具和库（这就是为什么我们今天仍然 stuck with C++）。
目前有两件事可以做，并与我们现有的代码库一起工作。我知道很多开发人员都在他们的项目中使用类似的系统，但如果能够公开发布一个通用的实现，我们就可以在它们之上进行构建了。
语言 - Language
尽管函数式语言可能是最理想的，无论是从头创建还是重用现有的，我们可以暂时扩展C语言以满足我们的需求。我希望看到一组C扩展，其中函数有明确定义的输入和输出，函数内部的代码不允许访问任何全局状态或调用函数外部的任何代码（在同一作用域中定义的本地辅助函数除外）。这可以通过预处理器或修改后的C编译器来完成，因此它仍然与现有的库和代码非常兼容。
void FirstEntityUpdate(input Entities* entities, input int entityCount,
output RayCastQueries* queries, output int queryCount);
函数之间的依赖关系可以通过将一些函数的输出绑定到其他函数的输入来表示。这可以在代码中完成，也可以通过使用 GUI 工具来帮助开发人员可视化地管理数据关系。这样我们就可以为每一帧中涉及的所有函数构建一个依赖关系图。
调度器 - Scheduler
一旦我们有了每个函数的依赖关系，我们就可以从中创建一个有向无环图（DAG），这将为我们提供每一帧如何处理数据的全局视图。此时，我们可以将该任务交给调度程序，而不是手动运行函数。
调度器拥有关于所有函数以及可用内核数量的完整信息（如果我们想使用前一帧执行的信息）。它可以通过 DAG 确定重要的路径，并优化任务调度，以便始终处理最关键的部分。如果临时内存缓冲区对当前平台来说是一个限制，调度器还可以将这一点加入考虑，多付出一些性能来减少内存占用。
就像语言一样，调度器将是一个非常通用的组件，并且可以公开使用。开发者可以将其作为一个起点，在此基础上，为自己的特定游戏和平台添加自己的规则。
结语 - The End
即使我们还没有准备好创建这些可重复使用的组件，每个参与创建高性能游戏的开发者现在都应该考虑游戏中的数据。随着下一代主机和电脑的出现，数据在未来只会变得越来越重要。
本文最初发表于2010年9月的《游戏开发者》杂志。