优化和实现

优化软件时，必须了解是什么导致软件的速度不及预期。大多数情况下，开销最大的是数据移动。它也是处理数据时最耗能的部分。而计算函数结果，或用算法处理数据，耗能都较少。优先提供所需的数据，似乎就是最大的成本。在当前的架构中确实如此，但我们发现隐式、可计算的信息，往往比缓存的值或显式的状态更有用。

如果开发游戏时，将数据组织成数组，就能带来诸多优化的机会。从这种与问题无关的布局开始，我们可以挑选针对其他任务创建的工具，最坏也是将方案提升为模板或策略，然后再将其应用于新旧用例。

在 Out of the Tar Pit[#!bmospmark!#] 中提到，除非是在方案的开发末期，否则不推荐为了性能而增加状态和复杂度。通过数组解决这个问题，并在没有副作用的情况下变换这些表，能够改进整个系统的性能。它们可以在程序的许多地方应用，也不需要担心兼容问题，同时保证不会增加状态，实际增强的只有当下工作的语言。

但许多项目的祸根，延期的原因，就是坚持不过早优化。后期优化之所以如此困难，是因为许多软件里到处都是对象的实例，甚至有时候都不是必需的。实例作为处理的单元，即是面向对象设计诸多问题的起源。面向对象的开发实践，倾向于认为实例是代码的工作单元，技术与实践标准将对象的集合视为个体的集合。

假设对象是某个独特的东西，有自己的用处，那么让它做事情的指令，必然以某种方式依赖于对象。通常会通过虚表查找访问实际的操作。更大的威胁是，当原本可以分组，或是以独立值结合增量的形式表示 5 、10、乃至 100 个单独的实例，现在却当作个体序列来处理。很多情况下，某个对象存在，只是因为在开发者实现的层面，它的体量看起来与现实世界的概念匹配，而不是因为在用户可见的层面，它需要作为独特的个体元素发挥作用。我们很容易陷入这种情况：从它们是什么的角度来实现功能，而不是应该如何看待它们。

什么时候应该做优化?

什么时候应该优化？什么时候算过早？答案在另一种形式的数据里。过早优化是指在不知道是否会产生影响的情况下，优化某些内容。如果只是因为觉得它能"提高点速度"，就尝试优化，那就可能属于过早优化，因为此时还看不出有需要优化的迹象。

这里要说明，如果没有数据显示游戏运行缓慢或内存耗尽，那所有优化都是过早优化。如果应用程序没有被分析，但感觉很慢、很迟钝、不稳定，那做的任何事情都不能客观地定义为改进，而任何改进的尝试都只能算是过早优化。 只有从真实的数据着手，才能停止过早优化。如果程序看起来很慢，且已经分析过，基于数据能够明确定义什么无法接受，那么任何为改进解决方案的行为都不会视为过早，因为它已经被测量过，可以在失败、成功、进步等方面做出了评估。

鉴于我们已经确认在某些时候需要优化，且知道不做分析的话，就不是优化，下一个问题就很清楚了。应该什么时候开始分析？应该什么时候开始分析框架的工作？要有多少游戏内容才足以保证测试性能？开始测试游戏的性能峰值前，应有多少玩法实现？

考虑另一个问题。最终的产品中，性能是否是可选项？如果知道游戏有模块在某些硬件上只有 5fps，还能发布吗？如果觉得 30fps 可行，即便相当不精确，也算是个衡量标准。那怎么知道游戏在目标受众的某个硬件配置上已经不是 5fps 了？只要相信帧率有下限，内存有上限，关卡有预期的最长加载时间，或确信游戏运行时至少应该有合理的耗电量，某种意义上，我们已经达成共识：性能不是可有可无的。

若性能并非可有可无，且需要实际工作来优化，那么就问自己一组不同的问题。分析能够推迟多久？能承受多少美术资源被重做（或其他内容）？尚不确定最终能否上线时，愿意实现多少功能？在没有反馈，且同样不知道能否进入最终产品时，愿意工作多久？

反馈

写出性能较差的代码却不自知，损害的不仅是程序。由于没有人对他们的工作提出反馈，开发人员就无法进步，反而会强化并延续那些不起作用的神话和技术。Daniel Kahneman 在Think, Fast and Slow[#!DKhneman!#] 一书中有过相关论述：人们能够很好地在即时反应中学习，但当反馈时间较长，掌握技能就没那么容易了。书中提到：心理医生在与病人的互动中，有机会运用强大的直觉技能，因为他们能够观察到病人的即时反应；但在确定合适的治疗方案时，就难以建立强大的直觉，他们无法确保反馈总是完整且可用的，并且反馈往往还会滞后。决定在没有反馈的情况下工作毫无意义可言。但对许多游戏开发者，又几乎别无选择，第三方引擎为初学者提供的反馈机制非常少。除了CPU、GPU、物理、渲染等粗略的粒度之外，没有提供其他机制，能够对其引擎的不同方面做预算。他们提供了很多工具用以帮助解决性能问题，但提供的反馈往往不完整；又或无法精确匹配最终产品的形式，因为在完全优化的发布版中，内置的分析工具也常常用不了。

当下的事情必须有所反馈，不然，原本该用来打磨的时间都得用来优化了。尽可能确保反馈完整，即时。为了实现这一点，可以添加游戏性能状态的指标。及时反馈优化结果，有助于减轻沉没成本带来的谬误，进而避免干扰理性的方向决断。如果开发者相信某种行事方式有用，但事实又不尽然，那最好尽早知道。即使是最固执己见的人，在数据面前也可以变得平易近人。好奇心，对于自尊心受创的开发者来说，是一剂良药。如果没有在某种方法上投入大量时间和精力，反馈就更容易整合了，开发者会更愿意放下当下的工作，找出不同的方法。

当然还要确保反馈的正确性。比如自己一直在优化一款游戏，想保证帧率丝滑，平均帧率保持在 60fps，但客户和测试人员却不断地反馈掉帧和帧峰值问题，那有可能是分析的内容或方法有误。有时候，还是有必要在游戏运行时做性能分析。除了平均帧数，只需要再记录每帧的数据就好。

性能分析也不一定只针对帧率。慢的不是帧，是帧内执行的内容。软件开发中，有个老式但强大的方法：为系统和模块做预算。这里讨论的并非财务预算，而是时间、内存、带宽、磁盘空间，或是其他直接影响最终产品的限制。如果每帧预算是 16ms，且绝不超过它，就能保证游戏有 60fps。没有如果，没有但是。假设觉得保证关卡加载时长令人舒适，并设定了 4 秒预算，只要不超时，就不会有人抱怨。

不止是游戏，比如在线零售网站，还要注意延迟问题，它也会影响到用户。Greg Linden 在 2008 年的一次演讲中透露，延迟每增加 100 毫秒，亚马逊就会损失 1% 的销售额。根据谷歌的统计数据，有人透露，当他们在生成页面时只增加半秒的延迟，网站流量就会下降 20%。更有甚者，TABB 集团在 2008 年的评论中，提到了陡增的成本：

TABB 集团估计，如果一个经纪人的电子交易平台比竞争对手慢 5 毫秒，他可能会损失至少 1% 的流量；平均每毫秒收入为 400 万美元。高达 10 毫秒的延迟可能会导致收入损失 10%。这里开始，情况越来越差。如果经纪人比最快的慢 100 毫秒，还不如直接关掉 FIX 引擎，去当场内经纪人了。

如果延迟、吞吐量、帧时间、内存等资源会变为限制，就给它们做预算。什么会削弱业务？是否有在衡量它？多久可以不检查游戏是否超预算了？

了解极限

将预算纳入工作考量，就能在早期就为系统设置切实的预算，在开发过程中维持在一定水平上工作，避免开发后期带来困扰。没有预算的项目，帧峰值可能只在临近发布时才逐渐显现，只有那会儿，所有的系统才会共同创造出最终产品。产品发布前，没有任何迹象表现出可能的帧峰值问题，结果可能就是直接导致系统看起来很廉价。直到最终找到引发峰值问题的子系统，或许就是很久前的一次改动导致的。同时，在项目早期，资源充足，系统引起的峰值完全没法引起注意，因而躲过了监测。如果系统有预算，不合理的行为就能记录下来，并立即做出响应。这样，问题就可以在发生的时立马被逮住，定位 bug 也更容易。

无论是自己实现，还是找一个，必须有个能够持续运行的性能分析器。确保分析器能在框架时间超预算时，报告游戏的整体状态。对所有超预算的子系统做出响应，都会很有用。要想搞清楚究竟发生了什么，还需要截取问题发生时的若干帧。如果游戏中有 AI，要捕捉性能问题，就试试持续运行测试，就跟版本机构建测试版本一样。当然所有情况下，除非让真正的测试人员运行分析器，否则很难得到真实的数据。如果由测试人员使用，还得考虑如何收集数据。可以的话，看看否可以把自动生成的分析数据，送回分析（或度量）服务器，以便自动化捕获问题。

优化策略

优化不是只要打开编辑器就能马上着手的。先得有个策略。我们会在本节介绍一些。在游戏行业外，这些步骤也有相似之处。这些行业中，有些大公司(如丰田)会把优化作为其商业模式的一部分。为了确保最大的性能和增长，丰田的技术已经相当完善。其背后的驱动理念，是丰田生产方式 ，能有效减少浪费。它还有其他可用的技术，本节中介绍的步骤与它们有很多共同之处。

定义问题

定义问题。找出什么是不好的。用事实支撑定义，并假设好的解决方案最终应是什么。简单举例来说，问题是游戏以 25fps 运行，而最终需要它以 30fps 运行。坚持使用清晰、客观的语言。

重要的是，在这一步不要包含任何猜测，所以应避免如：优化什么、如何优化这类陈述。考虑从用户角度来写，而非从开发者的角度。所以它有时候也被称作：质量标准(或客户需求)。

测量

只测量有需求地部分。不同于随机测量，有针对性的测更有利于理清实际情况，毕竟不太可能在不相干的数据中找到模式。数据挖掘(data dredging, 又称 P-hacking)在这里会导致错判问题。

这个阶段，还需要对测量的质量有个概念。运行测试，然后再次运行，以确保可重复。如果改动前，无法重现结果，那要怎么能判断改动有效呢？

分析

多数非正式优化策略的第一步：猜测阶段。这时会想想哪些可能是问题所在，并提出不同的方法来解决。在非正式的优化过程中，通常先实施看起来最好的，或至少是最有趣的想法。

相对正式的策略中，会去分析前面测量的东西。有时从这一步就能看出，测量结果有没有提供足够的方向，支持提出好的优化方案。如果分析结果表明数据不够好，下一步就应该先提高获取有用数据的能力。不了解误解问题的成本时，不要着急优化。

这一步也是做预测的阶段。评估一下计划预期的的改进效果。不是轻率地猜测，要通过一些计算来背书。等计划实施后，就没法再做了，会有太多的新的知识帮我们做可靠的推断。当然，也可能经历大家口中的知识的诅咒。这一步，可以了解你在估计优化效果方面的表现，还能在着手工作之前，了解改动相对会产生的影响。

实现

多数非正式优化策略的第二步：实现阶段。这一步会做可能解决问题改动。

可以的话，先试验性地实现一下方案。程序作为问题的解决方案，是一个解决数据变换的策略。设计实验请牢记这一点。

在得出本地的版本是否有效且确实值得做前，得证明它真的有用。检查本地实验中得到的测量结果，看它是否能保证在集成版本中测得的结果有相同预期。

如果优化第一次就很完美，那实验性的实现只能作为一个证明，证明这个过程可重复，适用于其他情况。但也只能作为一个教学工具，帮助他人了解原先实现的成本，以及在相似约束条件下预期的改进。

如果不确定优化第一次就成功，还可以做一些局部试验，避免完整实施，能省下不少时间。当然，为了给第三方提供支持而实现例子，也是个不错的开始，用较小的例子展示问题，会更容易沟通。

确认

这一步可能比预想的还要关键。有些人觉得它可有可无，但其实，它对于保留做优化时，产生的有价值的信息至关重要。

撰写一份报告，说明做了什么，发现了什么。这样做有两个好处。首先，分享优化技术知识，显然可以帮到其他遇到同类问题的人。其次，撰写报告能确定是否存在测量的错误，并确保测试的每一步都与最终的变化相关。

报告中，其他人可以指出不合逻辑的跳跃性推理，进而加深对问题地理解；也有助于排除错误的假设，并加深对机器工作原理的理解。写报告也是很强的体验，能锻炼思考能力，让我们能更好地解释某些条件下发生的事情。

总结

最重要的是，保持追踪。尽量在独立的工作测试平台上优化。即便因为要处理一个错误或功能，不得不与项目的其他部分同步，也要确保测试出的时间是可重复的。记录当下做的事情，这样在做早期修改时，可以帮助理解脑子里想的是什么，或可能没想到的事情。

还有就是，继续努力提高观察能力。如果不测量，就无法取得可衡量的进展；如果没有辨别改进的工具，就无法知道是否已经取得改进。还要适时改进测量工具。要寻找看的方法。每当发现当下的工具没法满足需求时，就去找满足需求的工具，找不到的话就自己实现。如果自己没法实现，就提需求，或委托别人实现。不要沉溺于向充满希望的乐观主义，会养成坏习惯，那样会随机证明你是对的，让人学到错误的真相。

表格

多方建议表明，将数据保持为矢量能让数据处理起来更方便。虽然有时要使用 STL 之外的内容，但学习它的特点，可以避免很多问题。无论是用 std::vector，还是实现自己的动态数组，都可以为将来的优化起个好头。大部分要做的处理，都只是读取一个数组；将数组转化为另一个；或原地修改一个表。一个简单的数组，就足以应付上述情况中的大部分任务。

转移到数组，算是开个好头，再进一步，转移到数组的结构(structure-of-arrays)还能更好。不过也不一定。主要还是得考虑数据的访问模式。如果不能考虑访问模式，而改变又很耗费，那就根据其他标准做选择，例如可读性。

之所以摒弃对象的数组(arrays-of-objects)和结构的数组(array-of-structures)，是为了让内存访问更符合其任务。试想要如何组织数据，重点在于，哪些数据要加载，哪些数据要存储。CPU 是针对某些内存活动模式做优化的。许多 CPU 从读操作转到写操作时，都有一定的成本。如果能以一种非常可预测的串行方式，安排对内存的写入，或许就能帮助到 CPU 避免读写切换。例如代码 ，没有考虑到写的重要性，也没有冷热分离的例子。该代码试图更新那些既可读又可写的值，但相邻的数据却做只读操作。

代码 显著优化了性能。

如果数据的读与写之间没有强关联，那数组的结构(SoA)就更利于缓存。记住，只有当数据不总是作为一个单元被访问时，才会如此。面向数据设计的倡导者之一认为，数组的结构本质上有利于缓存，于是把x, y, z 坐标分别放进独立的 float 数组中。列表足够大时，且每个元素位于自己的数组中，使用 SIMD 就能从中获益。然而，通常如果要访问数组中某个元素的其中一个维度，很可能同时也要访问另外两个。于是，对每个元素而言，会加载不止一行，而是三行缓存的浮点数据。如果操作涉及到很多其他值，那缓冲区可能会过满。这就是为什么要考虑数据从哪来，如何关联，如何使用。面向数据设计不单单是一套，从一种风格转向另一种的简单规则。要学会看到数据间的联系。这个案例中，我们看到某些情况下，如果向量作为一个操作值，不太会被 SIMD 指令优化，那将其保持为 3、4 个 float 会更好。

还有一些其他情况，SoA 格式并不适用。如经常插入、删除数据。可以在周围保留一些，避免删除操作导致数组变换，进而减轻压力。但这样就无法避免元素在处理过程中，用到简单的同质变换。因为同质变换，往往就是这种数据布局变化的核心。

如果使用动态数组，并需要从其中删除元素，并且这些表通过一些 ID 相互引用。那就得想办法将这些表拼接在一起，方便处理。如让它们维持有序，以便压缩。如果按相同的值排序，可以实现为一个简单的合并操作，如代码 。

只要 == 操作符知道表的类型，能找到要检查的特定列，且只要表基于这个列排序，就可以了。但如果这些表被压缩在一起，却没有按相同的列排序，该怎么办？如，有很多实体引用了 modelID，且很多网格-纹理组也引用了同一个 modelID。那这里就需要将实体朝向、实体渲染数据中的 modelID 、网格-纹理组，这三个列表中匹配的行压缩在一起。最简单办法是，依次遍历每个表并寻找匹配，如代码 所示。这种方案虽然写起来很简单，但效率非常低，应极力避免。不过凡事总有例外。某些情况下，非常小的表或许用这种方式更有效率，它们能保持常驻，而对其排序可能会花更多时间。

处理添加在不同列上的数据时，还得了解连接策略(join strategies)的用法。数据库中，连接策略用于减少在多个表中查询时的总操作数。在一个列（或多个列组成的键）上连接表时，有很多处理可供选择。之前的尝试中，我们只是简单地遍历了连接中涉及的每个表。对于大小相当的表，最终会是 $O(nmo)$ 或 $O(n^3)$。对小表来说可以接受，但大表就不行了。因此需要了解数据，判断其究竟是大是小。如果太大，无法使用上文那样的常规连接，就得有替代策略了。

迭代或查找都可以用于连接，甚至还能连接一次并缓存。维护一份连接缓存，似乎可以保证表能以多种方式排序的同时，还能对其执行操作。

当然，也完全可以添加辅助数据，然后以不同的顺序来遍历表。添加连接缓存，就像数据库允许一个表有任意数量的索引一样。创建索引，并在修改表时更新。我们的案例中，会根据需求实现索引。有些表可能会突然有大量写入，插入式排序就很慢。此时，在第一次读取时排序可能更好，或者在修改时丢弃整个索引。其他情况下，排序最好在写入时做，因为写的次数不多，或常与许多读操作交错进行。

变换

现在，我们来推广一下模式(Schema)的概念，静态的模式定义允许对迭代器采取不同的方法。模式迭代器可以用于访问一组表，取代通常那种，在容器内迭代以获取元素的访问权。这表示合并工作可以在迭代过程中完成，同时生成变换所依赖的环境(context)。这种形式很适合数据处理不多的大型复杂合并，因为创建临时表占用的内存更少。而复杂的变换没法从中获益，因为它会降低下一组数据在缓存中，用于下一个周期的几率。

变换的另一方面是分离“什么”与“如何”。也就是说，将要变换的数据的收集、加载，与最终对数据执行操作的代码分开。有些语言会在基础章节中介绍 map 和 reduce ，但 C++ 中很少这么做。可能是因为列表不属于语言的基础部分，但如果没有这些，就很难引入并用到它们强大的工具。map 和 reduce，可以作为纯粹的变换与流程驱动程序(flow driven program)的基础。将大数据集变成单一的结果，听起来显然是串行。然而，只要其中的一个步骤(即 reduce)是关联的，那就可以并行处理掉相当一部分 reduce。

举例来说，一个简单的 reduce，为所有匹配的元素生成值为 0 或 1 的映射，产生一个最终的总值，再进一步处理成一个越来越少的平行归约树。第一步，对所有元素做归约(reduction)操作，获得奇偶对，并用相同的过程产生一个新列表。归约操作会一直执行，直到仅剩一个条目。当然，这种特殊归约法用处不大，因为每次归约都很琐碎，最好根据核心的数量将工作分配出去，最后做一次求和。还有一种更复杂，但同样有用的归约法：将一连串的矩阵串联起来。矩阵运算满足结合律，但不满足交换律。因此，矩阵链可以用与计算总工作量相同的方式归约。只要在归约过程中保持顺序，并且归约步骤满足结合律，就可以在许多通常看起来是串行的工作中应用并行处理。除了矩阵串联，浮点乘法也可以，例如多种颜色调制，如光、漫反射、游戏相关的着色。建立字符串、列表也都可以利用到结合律。

碰撞的空间集

碰撞检测中，通常有一个全面阶段，会大量减少碰撞检测的数量。投出射线时，通过八叉树、BSP、又或者其他空间查询加速器，找到潜在的交点，通常都会很有帮助。寻路时，也可以通过查询局部节点，帮助选择旅程的起始节点。

所有空间数据存储都是通过减少处理量来加速查询的。它们基于一些空间标准，返回缩小的集合。并且由于更短了，变换为新数据的成本也更低。

当前支持空间划分的库，需要适配任意结构。但由于我们所有的数据已经按表组织，因此，为任意表布局编写适配器就容易得多。通用算法也容易实现，并且实现可能会用于多处的代码时，也不会引入副作用。使用基于表的方法，由于不清楚其意图（也就是说，并不知道空间系统，是否用在技术层面上不属于空间的数据上），于是我们可以在意想不到的地方使用空间划分算法。例如分配音频通道，不仅可以通过它们与听众的距离，还可以通过音量和重要性。制作一个五维(甚至 n 维)空间划分系统，未来可期。只需要写一次，实现一次单元测试，就可以用了，即便用于一些奇怪的事情也值得托付。按任务进度进行空间划分或许就有点矫枉过正了，但按位置、威胁、奖励获得附近所有能当作兴趣点的实体集合，对于 AI 来说或许就非常有用了。

针对大量数据惰性求值

优化面向对象代码时，经常发现隐藏在可变成员变量中，有已完成计算的局部缓存。大多数层级更新都会用到一个技巧：脏位（dirty bit），用于表示经由树的子成员或父成员，决定该对象是否需要更新。遍历层级时，脏位会基于刚刚加载的数据触发分支，意味着无法去猜测结果。因此大多数情况下，在准备阶段会读取不必要的内存。

如果计算的开销很大，那可能想要避免渲染引擎当下使用的路线。渲染引擎中，即便每帧都执行每个场景的矩阵连接，往往也比找到必要的矩阵并计算的开销要低。

例如，Tony Albrecht 在他的 Pitfalls of Object-Oriented Programming [#!AlbrechtTony!#] 演讲的幻灯片中表示：检查脏位的作用不如不检查，检查失败时（对象不脏的情况），原本只要 12 个周期的计算与分支错误预测的代价（23-24 个周期）相形见绌。事物总是在发展，在后来的演讲 Pitfalls revisited [#!AlbrechtTonyRE!#] 中，他指出之前通过手动去虚拟化获得的改进不再有效。无论是编译器的改进，还是硬件的变化，现实总会打败经验。

如果计算的开销很大，尽量避免用大量的检查去查看数值是否需要更新，进而使游戏陷入困境。这是基于存在的处理再次发挥作用的时候，因为存在于脏表中，就意味着它需要更新。更新一个脏元素时，它可以把新的脏元素 push 到表的末端，如果能改善带宽，甚至可以预取。

必要性-只取所需

标准化数据，同时会降低遇到面向对象开发的另一个多方面问题的几率。C++ 中对象的实现，迫使不相关的数据共享高速缓存行。

对象按类收集数据，但许多对象设计上包含了多于单一职能的数据。这是因为面向对象开发，并不天然允许对象根据其职能重新组合，同时也因为 C++ 需要提供一种方法，让我们能够以一种简单的方式，保证可以重载系统级的内存分配，同时还能以面向对象编程。多数类包含的内容都不只是最低限度，或因为继承，或因为对象需要应对多种情况。除非很仔细地去布局类，否则许多只需从类中获取少量信息的操作，都会在缓存中加载许多不必要的数据。只使用极少量加载的数据，是面向对象程序员最常见的过失之一。

每次虚拟调用，都会加载包含实例的虚表指针的缓存行。如果这个函数没有使用该类中位于虚表指针之前的数据，那缓存行的利用率可能就只有不到 4% 了。这是对内存吞吐量的浪费，如果不重新考虑如何调度函数，是无法恢复的。类调用自己的虚函数时，添加一个 final 关键字会有所帮助，但如果这些函数通过基类调用，就没用了。

实践中，只有加载函数后，CPU 才能加载要处理的数据，这些数据也可能分散在为类分配的内存中。解码出虚表指向的函数指令前，它不知道自己需要什么数据。

变化的长度集

目前为止，我们用到的技术中，数据一直会隐含一个表结构。根据变换的需求，每行都可以是一个结构，又或是每张表都是一列列数据。使用流处理时，如，着色器通常会使用固定大小的缓冲区。大多数流处理的工作也有类似的限制，这里我们倾向于，两个方向都固定元素数目。

已知输入是输出的超集的过滤，或许很适合采用退火结构。先输出到多个独立向量，并在最后归并时将他们串联在一起。每个变换线程都有自己的输出向量，归并步骤会先为每个条目生成总数和起始位置，然后处理归并列表，到最终连续的存储器上。并行的前缀和(prifix sum)会比较有用，但简单的线性传递其实已经够了。

若过滤是径向排序、计数排序、或是使用类似的直方图生成偏移量的某个阶段，还可以用并行的前缀和，减少生成偏移量的延迟。前缀和是运行的值列表的总和。举例来说，径向排序输出直方图，桶计数会以所有直方图桶的总和作为起始位置。 $o_n = \sum_{i=0}^{n-1}{b_i}$ 。这样很容易以串行形式生成，但如果是并行，就必须考虑生成结果所需的最少操作。这种情况下，记住，最长链会是最后一个偏移量的值，即所有元素的总和。通常优化会以二叉树的形式求和。分而治之：先将所有奇数槽与所有偶数槽相加，然后针对前一阶段的输出，执行相同操作。

A[d] [dr] & B [d] & C [d] [dr] & D [d]
a[d] & ab [d] [drr] & c [d] & cd [d]
a & ab & abc & abcd

然后，获得最后一个元素之后，回填在生成最后元素的过程中尚未完成的其他元素。实现时，我们发现这些回填的值，可以与生成最长链的处理并行。它们没有依赖最终值，所以能交给其他进程，或巧妙运用 SIMD 管理。

a [d] & ab [d] [dr] & c [d] & abcd [d]
a & ab & abc & abcd

并行前缀和虽然能够减少延迟，但不是比线性前缀和更好的通用方案。同样的工作，线性版本用到的资源更少。所以如果能处理延迟，就简化代码，以线性方式求和。

另外，实体的数量也可能增减，这样的话，就需要能够无障碍地添加和删除。若要就地变换数据，就得处理这种情况：一个线程可以读取和使用正在删除的数据。要在通过内存分配来确定对象是否存在的系统中做到这一点，就很难删除被其他变换引用的对象。当然，还有智能指针。但在多线程环境中，智能指针需要一个 mutex 来保证每次引用和解引用都是线程安全的。这样成本就很高了，那要如何避免它呢？至少有两种方法。

不用 mutex。一种是将使用的智能指针类型绑定到某个线程上。有些游戏引擎中的智能指针，并不维护 mutex，而是存一个它们所属线程的标识。这样就可以断定，每次访问都是在同一线程上。性能方面，这些数据无需出现在发布版中，因为检查是为了防止运行时出现由编译期的决定导致的误用。例如，如果知道数据音频子系统使用，而音频子系统是在自己的单线程上运行，那就锁起来，把内存分配与音频线程关联起来。任何时候，音频系统的内存在音频线程外被访问：要么就是因为音频系统的内存暴露给外部了；要么是它在某些回调函数中做了本职外的工作。无论哪种情况，不良行为都会被断言捕获，进而可以修复代码，以应对常规问题，而不是什么特定情况。

不删除。如果在一个不断变化的系统上执行删除，通常会用到一个池(pool)。主动不删除，而是做其他事情，就能改变代码访问数据的方式。改变了数据所代表的内容。如果一个实体需要存在，比如 CarDriverAI，那在使用时，可以存在 CarDriverAI 表里，不用时也不删除，只是标记为未使用。不同于删除，这个实体仍然有效，不会在变换时崩溃，但直到有最新的 CarDriverAI 请求覆盖它前，都可以当它不存在，直接跳过。表中只有少量“死去”的实体，开销就跟维护组件池差不多。

间接连接

有时，标准化需要将表连接起来，方便创建查询。不同于 RDBMS 查询，我们能更仔细地组织查询，并通过合并排序算法合并两个表。还有一种替代方案，不一定要输出到一个表里，也可以通过传递式的变换，输入多个表，为另一个变换生成新的数据流。如，每个 entityRenderable，通过 entityID 与 entityPosition 连接，用 AddRenderCall(Renderable, Position) 变换。

数据驱动的技术

除有限状态机外，还有一些常见的数据驱动编码实践。不太明显的如回调；明显的如脚本。两种情况都会改变代码流的数据，也都会引发同虚拟调用、有限状态机中一样的缓存和管线问题。

事件订阅表的触发器能让回调更安全。与其在工作完成时启动回调，不如维护一个已完成的事件表，回调就可以在整个运行完成后被触发。例如，假设一个评分系统有来自 badGuyDies 的回调，在面向对象的消息监听中，评分器只要收到 badGuyDies 的消息，就会在内部使分数上涨。相对的，只要确认 badGuys 集全部死亡，就运行回调表中的每个回调。如果一直这样，并且每次都要检查 badGuys 后再执行，那其实可以一次性为所有杀死 badGuys 加一次分。内部状态只执行了一次读取和一次写入。这比通过多次读写累加出最后分数强得多。

对于脚本，如果有在多个实体上运行的脚本，考虑一下图形内核是如何操作分支的。有时会用预测法：做出选择之前，分支两边都会执行。这样就会减少因按需解释脚本带来的分支数量。再进一步，将 SIMD 真正构建到脚本核心中，相较于传统的逐实体的串行脚本，或许就能发现，可以在更多实体上使用脚本。如果 SIMD 操作是在整个实体集合上执行，那解释脚本几乎没有额外代价。

SIMD

只要有大量任务需要处理，如更新粒子位置的操作（见代码），SIMD 就非常有用。这个 SIMD 化的例子很简单，根据测试结果，它比结构的数组(AoS)、单纯的数组的结构(SoA) 都要快四倍以上。

许多编译器优化中，默认会做简单的矢量化，但也仅限于编译器清楚的部分。要搞清楚这些也没那么容易。

在支持 SSE 的机器上执行 SIMD 运算，能一次性向 CPU 输入更多数据。许多人一开始就把 3D 向量放到 SIMD 单元中，但其实并没有完全利用到 SIMD 管线。本例同时加载了四种不同粒子，并同时更新。这种技术同时也不需要对数据布局做什么花哨的处理，只需要为 SIMD 准备一个单纯的数组的结构，就能规避掉数据瓶颈。

数组的结构

保持运行时数据处于数据库形式的格式，除了之前提到的好处外，还有机会利用到数组的结构。SoA 已经成为一个描述对象数据访问模式的术语。可以在 SoA 对象中同时保留冷、热数据，数据会按需载入缓存，避免按容易出现意外的物理地址。

比如有一个动画的 timekey/value 类是这样：

那如果在大集合上迭代时，所有数据都得一次性载入缓存中。假设一条缓存行是 64 字节，float 4 字节，那 Keyframe 结构就是 16 字节。于是每次查询一个键的时间，都会不小心载入四个键，还有所有相关的 Keyframe 数据。如果在对一组 128 个键的 Stream 执行二分查找，就意味着可能最后加载了 64 字节数据，但在多达 5 个步骤中，只用了其中 4 字节。如果改变数据布局，让查找发生在同一个数组中，且分开存储数据，那么得到的结构会是这样：

这样做，对于 128 个键的 stream，times 总共只占 8 条缓存行，二分查找最多只需要载入其中 3 个，而数据查只需要一个。如果数据跨越了两个缓存行，但由于选择内存空间效率而非性能，因此最多也只需要两个。

这里是先有的数据库技术。DBMS 术语中，它被称为面向列的数据库，与传统的面向行的关系数据库相比，数据处理拥有更大的吞吐量。原因也很简单，因为在执行列聚合、过滤时，无关数据不会被加载。还有其他一些功能让列存储数据库更有效率，比如允许它们在一个值下收集许多键，替代键值一对一的映射。数据库一直在进步，所以值得去查阅最新的文献，看看还有什么值得迁移到自己的代码库里。