有效使用高速缓存的设计与编码

有效使用存储器是指使其始终装满很可能要使用的数据和指令。

指令和数据沿层次结构向上移动，它们移入比低级别速度更快，但也更小和更昂贵的存储器。 为使每一台给定的机器达到可能的最佳性能，所以程序员必须最有效的利用每一级别上可用的存储器。

实现有效存储的一个障碍就是“存储器是按固定长度的块分配的”这一实际情况，例如高速缓存行和实内存页面通常并不对应于程序或数据结构中的边界。 设计时未考虑存储器层次结构的程序和数据结构通常不能有效利用分配给它的存储器，在小系统或高负载系统中会对性能产生不利影响。

考虑存储器层次结构意味着理解和适应在高速缓存或虚拟内存环境下有效编程的常规原则。 重新封装技术可以在不重新编码的情况下产生重大改进，所有新代码在设计时应该考虑有效利用存储器的问题。

讨论有效利用分层的存储器时，有两个术语是必不可少的：引用的局部性和工作集。

• 程序的引用的局部性是指在给定的时间间隔中，它的指令执行的地址和数据引用集群在存储器的一小块区域中的程度。
• 在同一时间间隔中程序的工作集是指使用中的存储块集合，或者更精确地说，是占有那些块的代码或数据。

引用的局部性好的程序具有最小工作集，因为正在使用的块中紧紧填满了执行代码或数据。 功能相当但引用的局部性差的程序具有较大的工作集，因为需要更多的块来容纳较大范围的访问地址。

因为将每个块装入到层次结构的某一给定级别需要大量的时间，在分层的存储器系统中有效编程的目标就是以某种方式设计和封装代码，这种方式要保持工作集和实际一样小。

下图说明了在子例程级别上好与坏的实践情况。 程序的第一个版本是按照可能的编写序列封装的。 第一个子例程 PriSub1 包含程序的入口点。 它始终使用主子例程 PriSub2 和 PriSub3。 程序中一些不常用的函数需要辅助子例程 SecSub1 和 SecSub2。 在极少情况下需要错误子例程 ErrSub1 和 ErrSub2。

程序的初始版本引用的局部性较差，因为在通常情况下运行会占用三个内存页面。 次子例程和错误子例程将程序的主路径分为物理上分开的三段。

程序的改进版本使主子例程彼此相邻，后面放上运行次数较少的函数。 必要的错误子例程（极少使用）位于可执行程序末端。 现在只需要一次磁盘读取和只占用一个（而不是前面需要的三个）内存页面就可处理程序的最普通函数。

记住引用的局部性和工作集是相对于时间而定义的。 如果程序按阶段运行，其中每一阶段占用大量时间并且使用不同的子例程集，那么请尝试将每一阶段的工作集减至最小。