C/C++ 流水线 缓存以及优化_c++ 缓存优化

抄书笔记 《游戏引擎架构》第二版
游戏是软实时系统。软实时系统是指游戏软件必须在限期内完成操作——游戏中最显然的需求是没帧必须在16.6ms（以达到60FPS）或者33.3ms（以达到30FPS）内完成。软的部分是指没有人会因为帧率而死亡（相对医疗和交通系统的硬实时系统，如果不能在有限的时间内完成操作可能导致严重意外）。尽管如此，无需怀疑，游戏需要尽可能的高效运行。
一 并行范式转移
优化软件的性能，就要了解什么使软件变慢。
在早期计算机中，CPU相对较慢，因此程序员在优化代码的过程中，会集中降低任务所花费的CPU周期数目。在每一刻CPU仅仅做一项工作，因此程序员可阅读反汇编码，并计算每个指令所花的周期数目。而且由于内存访问的开销比较低，程序员常会用内存换取更少的周期。
现代计算机的情况就完全不同了。
现代计算机和游戏机都包含多个并行的运行的CPU核心，而开发软件时也要利用到这些并行能力。并行处理的范式转移也往下延伸到CPU核心本身的设计。如今的CPU都是流水线，指可以同时执行多个指令。另外，现在的GPU也是大规模并行计算引擎，可以同时并行处理数百上千个运算。
部分受并行化转移的影响，CPU性能提升的速度高于内存访问的提升速度。今天的CPU采用复杂的内存缓存方案去减低内存访问延迟。如今的口头禅“内存访问昂贵，计算周期便宜”。所有这些情况导致性能优化的原则完全与早期相反。与之前缩减所需执行指令的数目相反，现在普遍的做法是在CPU上做更多的工作，去避免访问内存。
二 内存缓存
了解内存存取模式为何影响性能，就要先了解现代处理器如何读写内存。
访问现代游戏或者PC的主系统内存是缓慢的操作，通常需要几千个处理器周期才能完成。和CPU里的寄存器相比，存取寄存器只需要数十个周期，甚至有时候只需要一个周期。为了降低读写内存的平均时间，现代的处理器会采用 高速的内存缓存。
缓存不过是另一组内存，但是CPU读写缓存的速度比读写主存快的多。缓存能达到最低的内存访问延迟。主要原因有两点：
第一，缓存内存通常采用现存最快的（以及最贵的技术）。
第二，缓存内存在物理上尽量放在最接近CPU核心的地方，通常放在同一个芯片上。
这两个原因就导致了 缓存的内存要主存的容量小很多。
内存缓存系统提升内存访问性能的方法是，将程序最常使用的数据块保存在缓存的局部拷贝。
如果CPU请求的数据已存在与缓存中，缓存就能非常快的完成请求，通常是数十个周期的数量级，这种情况叫做缓存命中；
如果数据没有放置在缓存中，那么必须从主存读入缓存，这种情况叫做 缓存命中失败。从主存中读取数据可能需要花费数千个周期，因此缓存命中失败的确会带来非常高的开销。
缓存线
为了减低缓存命中失败的冲击，缓存控制器会尝试载入多于所请求的内存。比如：假设程序尝试读入一个int变量的内容，一般占用一个机器字，如果按照架构来说32位或者64位。与其花费几千个周期去读一个字，缓存控制器会读入包含该字的更大的连续内存块。这里的理念是，如果程序顺序访问内存（这是常见情况），那么首次访问时会导致缓存命中失败的开销，但是之后的访问就时低开销的缓存命中了。
缓存的内存地址和主内存的地址为一个简单的一对多的关系。可以想象缓存的地址空间以一个重复的模式被映射到主内存地址。从主内存的地址0，一直到所有的主内存地址都被缓存覆盖。
具体的说明例子：假设内存大小是32KiB，每条缓存线是128字节。（1KiB=1024字节）那么该缓存可以存储256条缓存线（256256=32，768B=32KiB）。更进一步建设主内存为256MiB，因此主内存的大小是缓存的8192倍（2561024/32=8192）。就意味着需要把缓存的地址空间重复的重叠上主内存地址空间的8192次，才能覆盖所有物理的地址位置。
给定任何的主内存地址，都可以通过把该地址模除缓存大小去获得缓存的地址。所以对于32KiB缓存和256MiB主存，缓存地址0x0000至0x7FFF（就是32KiB）映射到主存地址0x0000至0x7FFF，但这些缓存地址也映射主内存地址0x8000至0xFFFF，0x10000至0x17FFFF……以此类推。直到最后一块地址0xFFF8000至0xFFFFFFF。
缓存只能处理和缓存线大小倍数对齐的内存地址（对齐 ，前一章笔记）。因此，缓存实际上只能以缓存线为单位进行寻址，不是以字节为单位的。考虑缓存的大小为2的M次幂字节，而内存线大小为2的n次方。可以用一个方法进行转换内存地方至缓存线索引（即把地址除以 2的n次方）。（关于缓存相关的知识点https://blog.csdn.net/qq_21125183/article/details/80590934）然后把地址分为两个部分：M-n个最低有效位为缓存索引，而余下的位告诉我们这这缓存线来自哪一块主存。块索引是以一个称为旁路转换缓冲（TLB）的特殊数据结构存储在缓存控制器中的。没有TLB的话，就无法追踪缓存线索引与主内存地址之间的一对多关系。

指令缓存和数据缓存
在为游戏引擎或者任何性能关键系统编写高性能代码时，必须意识到数据和代码都会置于缓存内。
指令缓存（I—cache）：会预载即将执行的机器码
数据缓存（D-cache）：用来加速从内存读写数据
大多数处理器会在物理上独立分开这两种缓存，因为不希望读一个指令会导致一些合法数据被踢出缓存，反之也是这样的。优化代码时，必须同时考虑数据缓存一级指令缓存的性能。

组关联和替换策略
之前的说的缓存线和主内存地址之间的简单的映射被称为直接映射 缓存。即主内存中每个地址仅映射至单条缓存线。
例子：用32KiB缓存，128字节缓存线，主存地址0x203将映射至第四条缓存线（因为0x203为515，而【512/128】=4）。然而在例子中有8192个独立的缓存线大小主存映射到第四条缓存线。具体来说，第四条缓存线映射至主存地址0x200至0x27F，以此类推。
当发生缓存命中失败的时，CPU必须把对应的缓存线从主内存载入缓存。如果该缓存线没有合法的数据，那么只需要拷贝数据进去就可以了。但是如果该缓存线已经包含了数据（来自另一个主内存块），就必须覆盖写入它。这个操作叫做逐出数据或者把数据从缓存中踢走。
直接缓存的问题在于，他可以导致病态的情况。比如，两个不相关的内存块可能来回不断的互相逐出。如果主内存地址能够映射到两个或者更多的不同缓存线，就可能获取更好的平均性能。在2路组关联缓存中，每个主内存映射至两个缓存线，4路组关联缓存比两路的性能更好，同样8路或者16路比4路更好。
问题在于，如果有超过一个缓存路之后，发生缓存命中失败，缓存控制器应该逐出哪一路，并且应该保留哪些路在缓存中？这个问题的答案是根据CPU设计而异的，成为CPU替换策略。常见的策略是逐出去最老的数据。

写入策略
缓存控制器如何处理写入成为他的写入策略。
最简单的缓存写入设计成为透写式缓存。在这种设计中，将数据写入缓存时，会立即把数据同时写入主内存。然而，在另一种称为回写式的缓存设计中，数据会先写入缓存中，在某些情况才会把缓存线回写到主内存。这些情况包括：一条曾写过新数据的缓存线需要被逐出缓存，以供主内存载入新的缓存线；程序明确要求清除缓存。

多级缓存
命中率测量度程序命中缓存的频繁程序，而不是被缓存命中失败而带来巨大的开销。命中率越高，程序运行的越好。缓存延迟与命中率存在一个基本的权衡关系。缓存越大，命中率越高，但是同时更大的缓存不能置于CPU越近的地方，因为更大的缓存会比更小的慢。
多数游戏机至少采用两级缓存。CPU首先尝试在一级缓存找数据，l1缓存比较小，但有非常低的访问延迟，如果数据不在l1，就尝试更大的但是更慢的二级缓存。仅当数据不在二级缓存，才会支付访问主内存的成本。因为主内存的延迟相对于CPU的时钟频率来说非常高，有些PC甚至包含三级缓存。

缓存一致性：MESI 和MOESI
当多个CPU核心共享单个主内存的时候，事情就会很复杂。通常每个核心都有他们独立的一级缓存，但是多个核心共享二级缓存以及主内存。
当出现多个核心的时候，系统必须维持缓存一致性。需要确保数据在多个缓存一级主内存里保持匹配。并不需要每一刻都维持一致性，最重要的是运行时程序不能展示出缓存中的内容是不同步的。
这两种常见的缓存一致性协议：MESI 和MOESI

避免缓存命中失败
不能避免缓存命中失败，因为数据最终必须会来往于主内存。然而，高性能计算的诀窍在于编排内存的数据以及代码，令算法产生最小的缓存命中失败率。
避免数据缓存命中失败的最佳办法就是，把数据编排进连续的内存块中，尺寸越小越好，并且要顺序访问这些数据。这样就可以把数据缓存命中失败的次数减少至最少。当数据是连续的（不会在内存中跳来跳去），那么单次命中失败就会把尽可能多的相关数据载入单个缓存线。如果数据量少，更有可能塞进耽搁缓存线（或最少量的缓存线）。并且当顺序存储数据时（既不会在联系的内存块中跳来跳去），就能造成最少次缓存瞑汇总给你失败，因为CPU不需要吧相同区域的内存重新载入缓存线。
要避免指令缓存命中失败，他的基本原理和数据缓存的情况一样。但是，两者的实践方法不一样。最容易时间的是保持高性能循环的代码量越少越少。并且避免在最内层的循环中调用函数。这样可以确保整个循环体能在运行的所有时间中保留在指令缓存中。
如果循环需要调用函数，最好能令被调用的函数位于金街循环体代码的地方。由于编译器和链接器决定了代码的内存布局，部分程序员可能会觉得自己对指令缓存命中失败几乎无法控制。然而，多数C/C++链接器都有一些简单的规则，熟悉并运用他们就能控制代码的内存布局。
1）耽搁函数的机器码几乎总是置于连续的内存中，在绝大多数情况下，链接器不会把一个函数切开，并在中间放置菱格函数。（内联函数除外，之后会有解释）
2）编译器和链接器按函数在翻译单元源代码（.cpp文件）中的出现次序排列内存布局
3）位于一个翻译单元内的函数总是置于连续内存中。即链接器永远不会把已编译的翻译单元切开，中间插入其他翻译单元的代码。在Visual C++编译器中可以使用函数级链接/Gy选项，那么编译的输出单位为函数，链接时各个函数并不一定以翻译单元内的次序进行布局。事实上，还可以在链接时使用/ORDER选项自定义函数的布局次序。
综上，通过了解的避免缓存命中失败的原理，可以使用下面的经验法则：
1）高效能代码的体积越小越好，体积以机器码指令数目为单位。（编译器和链接器会负责把函数置于连续内存中）
2）在性能关键的代码段落中，避免调用函数。
3）若要调用某函数，就把该函数置于最接近函数调用的地方。最好是紧接着调用函数的前后，而不要把函数置于另一个翻译单元（因为这样会完全无法控制两个函数的距离）
4）谨慎的使用内联函数。内联小型函数能增进效能。然而过多的内联函数会增大代码体积。使性能关键的代码再也不能完全装进缓存。假设有一个处理大量数据的紧凑循环，如果循环内的代码不能完全装进缓存，每个循环迭代便会产生至少两次指令缓存命中失败。遇到这种情况，最好重新思考算法及其代码实现，看看能不能减少关键循环中的代码量。

三 指令流水线以及超纯量CPU
近些年对并行处理的转移不止应用至多核心CPU的计算机，也用于核心本身。有两个紧密相关的架构技术能增强CPU内的并行性：指令流水线以及超纯量架构。
CPU指令流水线的工作方式如下，当执行一个机器语言指令时，CPU必须以多个步骤执行。
首先，必须从内存读取指令（最好是从指令缓存中读取）。
然后，指令必须被解码，之后再被执行。
如果指令需要访问数据，还需要执行一个内存访问的周期。
最后寄存器的内容可能需要回写到内存。
每个步骤由CPU独立的电路执行，这些电路连接到另一组电路去组成一个流水线。CPU为了在所有的时间保持这些电路都在忙碌运作，当流水线第一个阶段结束就尽快传送新的指令至流水线。
流水线的延迟：是指完成一个指令所需的时间。这等于流水线中所有阶段的延迟之和。流水线的带宽和吞吐量就是测量单位时间内能执行多少个指令的指标。流水线的带宽取决于它最慢的阶段。如果木桶装多少水，取决于木桶最短的那块木板。
超纯量处理器包含多组冗余的电路，这些电路可能属于流水线中的部分或者全部阶段。这样可以让CPU并行处理多个指令。比如如果CPU含有两个整数算数逻辑单元，那么两个整数指令可以同时执行。
需要注意：不同的数据类型通常在CPU芯片上不同的电路上工作。比如：整数算数可能由一个电路执行，而浮点数由另一个电路执行。这些CPU架构与超纯量架构相似，相似的地方在于整数乘法，浮点数乘法与SIMD矢量乘法能全部同时执行。但对于真正的超纯量，CPU需要有多个整数/浮点数/或者矢量单元。
数据依赖
流水线停顿