游戏编程中的高效率缓存替换

题目：游戏编程中的高效率缓存替换

在内存有限的游戏中，自定义的媒体缓存被用来扩展场景的数据量，同时只使用很小的内存区域而不是一次性将所有媒体装入内存。使用缓存系统时，最困难的因素是：当缓存填充达到其上限时，选择适当的替换页面（victim page）来腾空。当缓存未命中时，页面替换算法的选择至关重要——这种选择和你游戏的硬件内存使用的性能与效率直接相关。不好的算法往往会破坏游戏的性能，而实现得好的算法在不影响其性能的同时，还能成倍地提高游戏质量。流行的缓存替换算法（如最近最少使用算法，LRU）在它们的目标环境下工作得很好，但在需要更多的数据来准确地选择替换页面的情形下，它们往往显得力不从心。本文将介绍年龄和成本指标可以作为评估值，应用于构建最符合游戏需求的高速缓存替换算法。

1 　概述

当从主存请求数据时，操作系统将读出的数据放到一个临时的内存区域中（称为高速缓存或缓存，cache），它可以以比主存更快的速度进行存取。高速缓存本身有一个预定义的尺寸，它被分割成较小的称为页面的内存集合。当内存存取时，缓存本身会被填满，此时，操作系统必须从缓存中选择一个页面来存放新来的页面数据。这种情况被称为高速缓存未命中。当需要的页面数大大超过缓存的大小时（通常为2倍或更多），缓存抖动（thrash）就发生了，也就是说，为了给新来的整个数据集腾出空间，整个缓存都将被丢弃。缓存抖动被认为是任何缓存算法的最坏情况，也是任何缓存替换性能测试的焦点。

存储器处理程序要从主存获取信息时，每次都有相关的消耗。通常是因为采用了额外的、靠近处理器本身的内存芯片，所以从缓存读取的消耗较小。因而，如果发生缓存未命中，在决定清除存储器的哪个页面时，其中的一个主要目标是：选择一个在缓存中并不需要有效槽的页面。例如，如果在故障发生的过程中随机选择一个页面来删除，但是，这个页面被删除后恰好立即被需要，这将引起另外一个从主存重新获取数据的性能开销。我们的目标是建立一个算法，它能最好地描述要从缓存删除的理想页面，以减少缓存未命中和性能负担。

这些类型的算法被称为牺牲（victim）页面确定或页面替换算法，它们是20世纪60年代和70年代的一个热门话题，并在最近最少使用（LRU）算法（以及其他工作集系统）的引入后达到高峰。自那时起，为了解决LRU在特定问题领域使用时的一些问题，产生了这些算法的衍生算法。例如，[O'Neil93]描述的一个被称为LRU-K的LRU分支，被认为能在软件数据库系统中更有效地工作。自适应替换缓存（ARC）是IBM开发的一个算法，它被使用在硬件控制器以及其他流行的数据库系统中[Megiddo03]（见文末的“参考文献”，以获取更多信息）。

在游戏开发中，程序员必须和硬件和软件层的缓存打交道，尤其是在游戏机领域，程序员不停地努力增加游戏内容，同时还得满足内存限制。如同许多其他的为解决一个具体问题而定做的替换算法，有些共同的游戏和图形系统需要一个更类似于内存模式和使用模式的替换系统。本精粹将介绍两种缓存页面指标，它们可以以更好地融入视频游戏开发环境的方式交织在一起。

2　缓存替换算法

缓存替换系统自产生起就是一个活跃的研究领域，由此产生了大量的被自定义调整来解决问题空间下各种情况的不同算法。为了有一个参照基准，这里会涉及一些最常用的算法。 Belady的Min（OPT）

最有效的替换算法将永远是取代那些被缓存逐出后，将在最长的一段时间不再需要的页面。在工作系统中，执行这一类算法需要预先知道系统的使用情况，而这是不可能确定的。在已知随时间变化的输入的测试情形下，执行OPT的结果可用做测试其他算法的基准。

在线程之间有生产者和消费者结构的多线程环境中，如果生产者线程比消费者线程超前好几帧，就有可能使用生产者的信息来得到接近于OPT的结果。 最近最少使用（LRU）

LRU算法取代在最长的时间内还没有使用的页面。当一个新的页面加载到缓存中时，按每页来保存描述了给定页面有多久没被使用的数据。一旦缓存未命中，被替换的页面就是那个在最长的时间跨度内未曾被使用的页面。LRU做了一些很酷的事情，但很容易过度抖动。也就是说，在缓存中，你将始终有一个最旧的页面，这意味着除非你很小心，否则当工作量很大时，实际上可能会清除所有缓存。 最近使用的（MRU）

MRU替换刚刚被替换的页面，也就是说缓存中的最新页面。MRU将不会取代整个缓存，在严重抖动时，它将永远选择去取代同一个页面。虽然没有像LRU那么流行和鲁棒，但MRU有它的用途。

在[Carmack00]，John Carmack列出了一个不错的、介于LRU和MRU的纹理缓存页面替换的混合系统。简而言之，它的使用形式是，大部分时间内用LRU，当达到每一帧都必须驱逐一个条目（entry）时，就切换到MRU替换策略。如前所述，LRU的问题是，如果没有足够的可用空间，它将可能抖动整个缓存。在缓存开始抖动的那一点，系统就切换到MRU，并在内存中创建一个页面暂存区而让大多数缓存安然无恙。如果在各帧之间使用的纹理数量相对较低，这可能是有用的。当用户处理额外需要的页面是可用缓存大小两倍的情形时，此方法就退化了，这可能使渲染过程停止。 不经常使用的（NFU）

NFU页面替换算法改变了访问启发式，为缓存中的每个页面保存一个访问计数器。任何在当前时间间隔内被访问的页面，它们的计数器（从零开始）将增加1，其结果是一个关联页面有多频繁地被使用的数字限定词。然后，要替换一个页面，必须在当前时间间隔内寻找那个有最小计数器的页面。

这个系统最严重的问题是：计数器指标不跟踪访问模式。也就是说，一个在加载时被频繁使用、而以后再也没被用的页面，可能和在同一时间间隔内每隔一帧就被使用的页面有相同的数量。区分这两个使用模式所需的信息是无法从一个单一的变量得到的。下一小节中提出的年龄指标是一个改变了如何表达计数器的NFU的变形，于是，在抖动时，用户就可以从它获取额外的信息。

如果需要一个更综合的算法清单，在你最爱的搜索引擎中搜索“Page Replacement Algorithms”（页面替换算法），或者参阅你在大学用过的操作系统教科书。

3　年龄和成本指标

为了说明这一点，本精粹的剩余部分参照了在当代硬件上大多数游戏面临的一个问题，那就是设计一个自定义的纹理缓存。要做到这一点，用户将保留一个静态的一维数组缓存页面，可以用来加载和卸载数据。假设用户正在使用一个多维纹理缓存，即放在缓存的数据来自纹理，因为各种大小的多纹理可以容纳在一个单一的缓存页面中，所以从这个意义上讲，缓存是多维的。例如，如果缓存页面可容纳一个256×256的纹理，那么，你还可以支持4个64×64的纹理、16个32×32的纹理等，包括可以和谐地存在于同一个页面的每个尺寸的倍数。

即使在这个简单的例子中，你也已经奠定了让标准替换函数表现不佳的基础。考虑多维缓存的情况，你需要插入一个新的256×256的页面到一个缓存，而这个缓存只是用一些32×32的纹理完全填满。简单的LRU/MRU方案不具备必要的数据来合适地计算哪个缓存页面是最佳替换页面。同时，因为访问模式在很大程度上远不止依赖于页面最后被替换的时间，所以它也不能合适地计算哪组32×32的纹理需要被清空。因此，在这种情况下，为了更好地分析最佳替换页面，本文提出了一套新的替换指标。 年龄算法

OPT算法知道一个页面在缓存中的使用数量，并替换那个在最远的时间才会被使用的页面。大多数替换算法尽其所能地用各种数据访问模式来效仿这一算法。为了最好地预测未来的用法，年龄算法通过保留一个在前几帧中使用情况的概念来模拟这个过程。也就是说，你需要掌握，在一个时间窗口内一个页面被访问了多少次。为了完成这项任务，在缓存中的每个页面保留一个32位的整数变量，当一个页面首次进入缓存时，此变量被初始化为1（0x00000001）。

对于每一帧，在缓存中的所有活跃页面左移一位，标志着它随着时间的折旧。如果一个活跃的页面在此帧被使用，那么年龄变量的最低有效位设置为1，否则设置为0。这个移位（Shift）和设置模式允许你对过去的32帧保留一个使用评估。

例如，一个每两帧被使用一次的页面将有一个年龄变量0xAAAAAAAA（010101010…01），而一个首次加载时被大量使用但以后再也没有被用的页面，将有年龄变量0xFFFF0000（1111…1100000…00）。

为表明年龄变量随着时间的变化，在一个8帧的时间窗口，考虑一个在第一、第三、第四和第八帧被使用的页面。年龄变量将进行如下改变：

第1帧 — 00000001（使用）

第2帧 — 00000010（不使用）

第3帧 — 00000101（使用）

第4帧 — 00001011（使用）

第5帧 — 00010110（不使用）

第6帧 — 00101100（不使用）

第7帧 — 01011000（不使用）

第8帧 — 10110001（使用）

有了这样的信息结构，你可以计算出指定窗口的年龄百分比费用（APC）。通过用页面被使用过的帧数（位为1的个数）除以年龄变量中的总帧数，得到一个页面被使用及未被使用的平均帧数。这些数据可以用汇编和处理器启发式得到，而不需要高级代码。虽然可以用自己的方式表达这个数据，但是，提出的APC作为一个单位化的在[0，1]之间的单一值存在，如“年龄和成本”一部分所述，此值可以作为一个相对于其他指标的标量。

当使用年龄来确定目标替换页面时，你企图选择在一定的时间内还没有被使用的页面，及一般不常使用的页面。例如，在一个时间窗口，每帧都被使用的一个页面将有一个100%的APC，它将几乎是不可能被取代的，而一个有25%的APC的页面被取代的机会会较高。

我喜欢年龄变量是因为它有一些隐性的好处。

※ 它不利于旧的纹理，迫使纹理去证明它们是被场景所需要的。一旦证明了这一事实，它们就被保留。一旦获得一个50%以上的APC，它就会很难从缓存中释放。

※ 它建立了一个暂存区。还没有证明它们是有用的新的纹理被转化为暂存区，这是一件好事，因为新的纹理往往是暂时的，在下一帧消失的概率较高。

※ 这是一个修改的NRU（最近没有使用）方法。在很短的时间内，有较高可见频率的纹理，可以很容易地跳到50%的APC，但然后再掉下来，在多帧后，它们的APC缓慢回落。年龄提供了访问变量的一个修改了的表示法，并允许额外的分析。因此，如果APC>60%，但纹理在最近的X帧没有被使用过，那么可以检查此情况并早些清除该纹理。

迄今为止提出的APC变量是强大的，但并非没有毛病——缓存中的多个页面可以有完全不同的访问模式，但具有相同的APC值。也就是说，0xAAAAAAAA和0xFFFF0000有相同的使用比例，但很容易看到，这两个年龄变量的使用模式明显不同。随后的基本年龄变量的二进制数据的分析模式可以帮助区分这些有相似APC值的页面（如分析子窗口来得到二级APC值），但这也存在类似的问题。 扩展的年龄算法

前面提出的年龄算法假设：你想要保持相当低的用来推断页面信息的内存消耗。因此，在一个32帧的窗口，对每帧存储一个使用/未使用的标志。应当指出的是，在所需页面数额相当大的情况下，年龄算法就像任何其他的算法一样退化。例如，如果有在每一帧都被使用的50个纹理，但只有12个缓存页面来放置它们，这样在缓存中就不会有足够的空间来同时保留整个内存占用，每一帧都将抖动整个缓存，且替换每个页面。

在这种情况下，页面和纹理的不断加载或者重新加载，会使每个页面都有一个设置成1的年龄计数器值，因此，这将缺乏任何其他有助于具体替换页面识别的信息。为了帮助解决这一问题，年龄变量可以每帧存储，比只是一个使用/未用位更多的信息，且事实上存储纹理的使用数量。因此，你可以存储一系列数字，每个数字存储该页面在这一帧中被使用的频度，而不是只在一个32位的整数变量储存一个0/1。这将类似于一个[1，18，25，6，0，0，…，1]，而不是01001010011…1的清单。在退化的情况下，这一额外的信息特别有用，因为你现在有更多的数据来协助替换页面的识别。

例如，考虑同时加载到缓存的两个页面（TextureA和TextureB），TextureA被使用在场景中50%的物体上，而TextureB只使用在10%的物体上。在这一点，两个页面有相同的APC值，但很显然，你可以确定这两个页面有着非常不同的使用数量。当必须找出一个替换页面时，应该考虑到，在当前帧TextureA被使用了较多次的事实，增加了它将在随后帧也被使用的可能性，因此，较少使用的纹理（TextureB）应该被替代。

通过存储这一额外的每帧数据，你提供了其他的统计分析操作，来帮助确定从缓存清除的最佳页面。

※ 用时间窗口内的非零帧的数量除以总帧数，APC变量仍然可以从扩展的年龄算法得到。

※ 在给定的帧窗口寻找最少使用的页面，将找出一般而言最少使用的页面，这将有助于确定替换页面。

※ 利用MAX分析，你可以确定在窗口内访问最多的页面，来帮助它们避免从缓存中 清除。

※ 在你的窗口内，找到AVG的使用和得到类似于APC的第二个简单化了的变量一样简单。

取决于你的实现需要和数据格式，简单的年龄算法或者扩展的年龄算法都是可行的。最好的主意就是坐下来分析你的数据来决定，对你的游戏，哪个是最有效的和最有用的方法。 做替换的成本

大多数替换页面识别算法只使用一个单一的启发式。也就是说，它们的算法是专门针对导致最少的缓存页面未命中的访问模式而量身定做的。例如，LRU只保留最旧页面的信息。然而，自定义软件缓存常常有涉及缓存未命中的第二个启发式——用新数据填充缓存页面的成本。对于大多数硬件缓存，都有一个恒定的成本。这个成本与存储器处理程序访问主存及读取所需数据相关。

然而，对于你的软件需要，这个成本通常可以在页面本身之间波动。因此，替换页面识别考虑到，实际上用一个给定内存块来填充一个页面的性能打击量是很明智的。这个性能消耗（或只是消耗）可以有多种来源，它可以用一个外部数据集来手动定义（例如，一个定义哪些纹理被真正使用的XML文件），或者它可以用填充页面的实际费用来定义。

考虑到在前面的示例中，传入的纹理页面是通过从光盘驱动器连续传送而生成的。因为较大的纹理有更多的信息要从媒体中传送，而较小的或简单的纹理只是那些消耗的一小部分，所以较大的纹理有较长的、涉及把它们放到缓存的性能时间。在这种情况下，在替换页面识别过程中，考虑涉及有可能取代内存中一个页面的成本将是非常明智的。如果你替换的页面具有较高的相关成本，且接下来的几帧需要该页面，那么将导致不必要的开销。相反，如果替换了一个有较低成本的页面，错误地把它从缓存中删除的性能打击则低得多。概括地说，把成本作为页面替换的一个变量让你可以回答问题“清除5个较小的纹理给1个大纹理腾出空间会更便宜吗？”

回顾一下，成本可让用户关注将一个给定页面重新装入缓存会如何损害性能。如果需要，这个系统的一个扩展允许替换页面识别功能更加关心缓存未命中的性能成本，而不是帧之间的连贯性。

就成本本身而言，它具有其他缓存替换算法的相同问题。当抖动发生时，你在缓存中找到并清除最便宜的纹理。因为总有一个便宜的页面存在，如果负荷足够大，整个缓存可能抖动。该算法也有这样的问题：它可以把非常昂贵的页面无限期地留在缓存。如果像天空盒纹理这样的东西被装载到缓存，那么这是一个很好的特性，因为天空盒在每一帧都将是活跃的，而且由于它的大尺寸，我们不太可能想把它从缓存中删除。在大多数情况下，这是一个糟糕的特征，需要不断地关注。

和其他启发式相结合，成本是一个功能强大的同盟。通过用替换指标来偏向访问模式算法的替换识别，你允许缓存找到一个在页面替换需求和抖动之间的折中。此外，访问模式的识别帮助消除纯粹的成本指标所涉及的问题，当高费用的项目到达已经不再需要的状态时，让它们最终从缓存中清除。 年龄和成本（A&C）

前面的例子假定：在纹理缓存的每个页面有一个相关的APC和相对成本（RC），它们在每一帧被更新。本示例假定：RC是一个更重要的指标，并允许该值是一个没有上限的整数变量。例如，如果通过从磁盘连续传送纹理至缓存，RC值可能是纹理尺寸除以从媒体连续传送一小部分纹理所花费的时间。把APC当作一个在（0，1）之间的单位化的浮点变量。

在一个简单的实现中，用户可以组合这两个值成一个单一的结果，其中，APC作为RC的一个标量，从而使ThrashCost=RC×APC。总的来说，这表现为一个非常好的、用来识别适当的替换页面的启发式。为了证实这一点，我已经提供了几个APC/RC比率的例子及替换模式的说明。对以下的数据，假定RC的最高值可能是10。

正如在此表所见的，使用简单的RC × APC值可能会导致页面有不同的APC/RC值，但具有相同的ThrashCost。这将意味着，APC/RC关系为0.5/100的纹理A，可以和APC/RC为1.0/50的纹理B有相同的成本。这里的问题是你如何确定要取代的页面。从理论上讲，这两个页面的任何一个都是一个有效的目标，都包含相同的潜在替代数值权重。纹理A有较高的成本，如果下一帧需要它，替换它将更加昂贵。纹理B的成本较低，但有一个100%的APC值，因此立即需要此页面的可能性将很大。

在实践中，我发现：当多个页面返回相同的值时，替换一个有较低APC值的效果要好得多。事实上，这就是要使用年龄指标的原因。通过分析使用模式和成本，你可以看到，虽然页面更加昂贵，但是它较少地被使用，它错误地被缓存抖动的概率就较低。在这些情况下，重新扫描缓存来找到一个有较高ThrashCost及较低APC值的页面是一个好主意。如果没有找到，可以安全地假设，为了缓存，这个页面可能需要被替换掉。然而，取决于你的系统，更好的被替换页面可能会有所不同。

此表中提到了另一个需要讨论的实例。如上所述，A&C系统有能力引入一个可能成为静态的页面。如果你的缓存包含从每一个镜头角度都可见的纹理，如天空盒纹理或虚拟角色的皮肤贴图，这也可能是一件好事。但是，如果缓存引入太多这样的页面，有效的工作空间就会大规模地缩小，造成更多的缓存未命中和缓存的整体低效率。在这种情况下，对这些静态纹理生成一个单独的缓存也许是明智的。

4　结论

对任何高性能环境，定制媒体缓存系统是至关重要的。由于外存媒体的使用增加，在游戏环境中，有一个精确的控制模型的需要也增加了。由于旧的替换算法考虑到操作系统的内存管理和硬件内存访问模式而设计，它们缺乏一些关键的、允许它们评估可能存在的更复杂情形的属性。年龄和成本的结合引入了大量的其他信息，而且只需要非常低的开销，这很适合游戏环境并且运作良好。成本指标引入了页面载入的整体性能的概念，对于随时需要的外在系统，页面载入可以成为一个主要瓶颈。年龄指标允许一个更基于每帧的使用模式的视角，这比传统的指标更容易地和游戏模拟的概念相联系，它也包含了足够的、在任何特定环境的临界情形下创建有效替换情形的可用信息。由于缓存替换需求在模拟过程中改变，这也允许大量的定制和二次分析，来评估最好的替换页面而获得最佳的效果。

利用这一组强大指标的优势是：缓存页面替换性能的全面增加，从而促成一个较低的抖动开销和填充缓存所需费用。在每天结束的时候，这真是你所想要的。

5　致谢

对于在“扩展的年龄算法”一节的指标，由衷地感谢Blue Shift的John Brooks，以及他让所有这些得以进行的帮助。

6　参考文献

[Carmack00] Carmack, J. “Virtualized Video Card Local Memory Is the Right Thing,” Carmack .Plan file, March 07, 2000.

[Megiddo03] Megiddo, Nimrod and Modha, Dharmendra S. “ARC: A Self-Tuning, Low Overhead Replacement Cache,” USENIX File and Storage Technologies (FAST), March 31, 2003, San Francisco, CA.

[O’Neil93] O’Neil, Elizabeth J. and others. “The LRU-K Page-Replacement Algorithm for Database Disk Buffering,” ACM SIGMOD Conf., pp. 297–306, 1993.

本文节选自《游戏编程精粹 7 》。

内容简介

本书是游戏编程精粹系列的最新一本，内容涉及通用编程、数学和物理、人工智能、音频、图形学、网络和多人游戏、脚本和数据驱动系统等内容，具有较强的先进性和通用性。随书附带光盘中提供了本书的源程序、演示程序以及需要的各种游戏开发的第三方工具。

因此，无论你是一个刚刚起步的游戏开发新手，还是资深业界专家，都能够在本书中找到灵感，增强洞察力及开发的技能。将书中介绍的开发经验和技巧应用于实际项目中，将缩短开发时间，提高效率。

本文转载自异步社区。

原文链接：https://www.epubit.com/articleDetails?id=NC7E3EF92F2C00001147BC0B21BE0EFE0