2.5 Cache预取
以上章节讲到了多种和Cache相关的技术，但是事实上，Cache对于绝大多数程序员来说都是透明不可见的。程序员在编写程序时不需要关心是否有Cache的存在，有几级Cache，每级Cache的大小是多少；不需要关心Cache采取何种策略将指令和数据从内存中加载到Cache中；也不需要关心Cache何时将处理完毕的数据写回到内存中。这一切，都是硬件自动完成的。但是，硬件也不是完全智能的，能够完美无缺地处理各种各样的情况，保证程序能够以最优的效率执行。因此，一些体系架构引入了能够对Cache进行预取的指令，从而使一些对程序执行效率有很高要求的程序员能够一定程度上控制Cache，加快程序的执行。
接下来，将简单介绍一下硬件预取的原理，通过英特尔NetBurst架构具体介绍其预取的原则，最后介绍软件可以使用的Cache预取指令。
2.5.1 Cache的预取原理
Cache之所以能够提高系统性能，主要是程序执行存在局部性现象，即时间局部性和空间局部性。
1）时间局部性：是指程序即将用到的指令/数据可能就是目前正在使用的指令/数据。因此，当前用到的指令/数据在使用完毕之后可以暂时存放在Cache中，可以在将来的时候再被处理器用到。一个简单的例子就是一个循环语句的指令，当循环终止的条件满足之前，处理器需要反复执行循环语句中的指令。
2）空间局部性：是指程序即将用到的指令/数据可能与目前正在使用的指令/数据在空间上相邻或者相近。因此，在处理器处理当前指令/数据时，可以从内存中把相邻区域的指令/数据读取到Cache中，这样，当处理器需要处理相邻内存区域的指令/数据时，可以直接从Cache中读取，节省访问内存的时间。一个简单的例子就是一个需要顺序处理的数组。
所谓的Cache预取，也就是预测数据并取入到Cache中，是根据空间局部性和时间局部性，以及当前执行状态、历史执行过程、软件提示等信息，然后以一定的合理方法，在数据/指令被使用前取入Cache。这样，当数据/指令需要被使用时，就能快速从Cache中加载到处理器内部进行运算和执行。
以上介绍的只是基本的预取原理，在不同体系架构，甚至不同处理器上，具体采取的预取方法都可能是不同的。以下以英特尔NetBurst架构的处理器为例介绍其预取的原则。详细内容请参见［Ref2-1］。
2.5.2 NetBurst架构处理器上的预取
在NetBurst架构上，每一级Cache都有相应的硬件预取单元，根据相应原则来预取数据/指令。由于篇幅原因，仅以一级数据Cache进行介绍。
1.一级数据Cache的预取单元
NetBurst架构的处理器上有两个硬件预取单元，用来加快程序，这样可以更快速地将所需要的数据送到一级数据Cache中。
1）数据Cache预取单元：也叫基于流的预取单元（Streaming prefetcher）。当程序以地址递增的方式访问数据时，该单元会被激活，自动预取下一个Cache行的数据。
2）基于指令寄存器（Instruction Pointer，IP）的预取单元：该单元会监测指令寄存器的读取（Load）指令，当该单元发现读取数据块的大小总是相对固定的情况下，会自动预取下一块数据。假设当前读取地址是0xA000，读取数据块大小为256个字节，那地址是0xA100-0xA200的数据就会自动被预取到一级数据Cache中。该预取单元能够追踪的最大数据块大小是2K字节。
不过需要指出的是，只有以下的条件全部满足的情况下，数据预取的机制才会被激活。
1）读取的数据是回写（Writeback）的内存类型。
2）预取的请求必须在一个4K物理页的内部。这是因为对于程序员来说，虽然指令和数据的虚拟地址都是连续的，但是分配的物理页很有可能是不连续的。而预取是根据物理地址进行判断的，因此跨界预取的指令和数据很有可能是属于其他进程的，或者没有被分配的物理页。
3）处理器的流水线作业中没有fence或者lock这样的指令。
4）当前读取（Load）指令没有出现很多Cache不命中。
5）前端总线不是很繁忙。
6）没有连续的存储（Store）指令。
在该硬件预取单元激活的情况下，也不一定能够提高程序的执行效率。这取决于程序是如何执行的。
当程序需要多次访问某种大的数据结构，并且访问的顺序是有规律的，硬件单元能够捕捉到这种规律，进而能够提前预取需要处理的数据，那么就能提高程序的执行效率；当访问的顺序没有规律，或者硬件不能捕捉这种规律，这种预取不但会降低程序的性能，而且会占用更多的带宽，浪费一级Cache有限的空间；甚至在某些极端情况下，程序本身就占用了很多一级数据Cache的空间，而预取单元为了预取它认为程序需要的数据，不适当地淘汰了程序本身存放在一级Cache的数据，从而导致程序的性能严重下降。
2.硬件预取所遵循的原则
在Netburst架构的处理器中，硬件遵循以下原则来决定是否开启自动预取。
1）只有连续两次Cache不命中才能激活预取机制。并且，这两次不命中的内存地址的位置偏差不能超过256或者512字节（NetBurst架构的不同处理器定义的阈值不一样），否则也不会激活预取。这样做的目的是因为预取也会有开销，会占用内部总线的带宽，当程序执行没有规律时，盲目预取只会带来更多的开销，并且并不一定能够提高程序执行的效率。
2）一个4K字节的页（Page）内，只定义一条流（Stream，可以是指令，也可以是数据）。因为处理器同时能够追踪的流是有限的。
3）能够同时、独立地追踪8条流。每条流必须在一个4K字节的页内。
4）对4K字节的边界之外不进行预取。也就是说，预取只会在一个物理页（4K字节）内发生。这和一级数据Cache预取遵循相同的原则。
5）预取的数据存放在二级或者三级Cache中。
6）对于UC（Strong Uncacheable）和WC（Write Combining）内存类型不进行预取。
2.5.3 两个执行效率迥异的程序
虽然绝大多数Cache预取对程序员来说都是透明的，但是了解预取的基本原理还是很有必要的，这样可以帮助我们编写高效的程序。以下就是两个相似的程序片段，但是执行效率却相差极大。这两个程序片段都定义了一个二维数组arr1024，对数组中每个元素都进行赋值操作。在内循环内，程序1是依次对ai, ai, ai… ai进行赋值；程序2是依次对a0, a1, a2 … a[1023] [i]进行赋值。
程序1:
for(int i = 0; i < 1024; i++) {
for(int j = 0; j < 1024; j++) {
arr[i][j] = num++;
}
}
程序2:
for(int i = 0; i < 1024; i++) {
for(int j = 0; j < 1024; j++) {
arr[j][i] = num++;
}
}通过图2-8可以清晰地看到程序1和程序2的执行顺序。程序1是按照数组在内存中的保存方式顺序访问，而程序2则是跳跃式访问。对于程序1，硬件预取单元能够自动预取接下来需要访问的数据到Cache，节省访问内存的时间，从而提高程序1的执行效率；对于程序2，硬件不能够识别数据访问的规律，因而不会预取，从而使程序2总是需要在内存中读取数据，降低了执行的效率。
2.5.4 软件预取
从上面的介绍可以看出，硬件预取单元并不一定能够提高程序执行的效率，有些时候可能会极大地降低执行的效率。因此，一些体系架构的处理器增加了一些指令，使得软件开发者和编译器能够部分控制Cache。能够影响Cache的指令很多，本书仅介绍预取相关的指令。
软件预取指令
预取指令使软件开发者在性能相关区域，把即将用到的数据从内存中加载到Cache，这样当前数据处理完毕后，即将用到的数据已经在Cache中，大大减小了从内存直接读取的开销，也减少了处理器等待的时间，从而提高了性能。增加预取指令并不是让软件开发者需要时时考虑到Cache的存在，让软件自己来管理Cache，而是在某些热点区域，或者性能相关区域能够通过显示地加载数据到Cache，提高程序执行的效率。不过，不正确地使用预取指令，造成Cache中负载过重或者无用数据的比例增加，反而还会造成程序性能下降，也有可能造成其他程序执行效率降低（比如某程序大量加载数据到三级Cache，影响到其他程序）。因此，软件开发者需要仔细衡量利弊，充分进行测试，才能够正确地优化程序。需要指出的是，预取指令只对数据有效，对指令预取是无效的。表2-1给出了预取的指令列表。
预取指令是汇编指令，对于很多软件开发者来说，直接插入汇编指令不是很方便，一些程序库也提供了相应的软件版本。比如“mmintrin.h”提供了如下的函数原型：
void _mm_prefetch(char *p, int i);
p是需要预取的内存地址，i对应相应的预取指令，如表2-2所示。
接下来，我们将以DPDK中PMD（Polling Mode Driver）驱动中的一个程序片段看看DPDK是如何利用预取指令的。
DPDK中的预取
在讨论之前，我们需要了解另外一个和性能相关的话题。DPDK一个处理器核每秒钟大概能够处理33M个报文，大概每30纳秒需要处理一个报文，假设处理器的主频是2.7GHz，那么大概每80个处理器时钟周期就需要处理一个报文。那么，处理报文需要做一些什么事情呢？以下是一个基本过程。
1）写接收描述符到内存，填充数据缓冲区指针，网卡收到报文后就会根据这个地址把报文内容填充进去。
2）从内存中读取接收描述符（当收到报文时，网卡会更新该结构）（内存读），从而确认是否收到报文。
3）从接收描述符确认收到报文时，从内存中读取控制结构体的指针（内存读），再从内存中读取控制结构体（内存读），把从接收描述符读取的信息填充到该控制结构体。
4）更新接收队列寄存器，表示软件接收到了新的报文。
5）内存中读取报文头部（内存读），决定转发端口。
6）从控制结构体把报文信息填入到发送队列发送描述符，更新发送队列寄存器。
7）从内存中读取发送描述符（内存读），检查是否有包被硬件传送出去。
8）如果有的话，从内存中读取相应控制结构体（内存读），释放数据缓冲区。
可以看出，处理一个报文的过程，需要6次读取内存（见上“内存读”）。而之前我们讨论过，处理器从一级Cache读取数据需要3～5个时钟周期，二级是十几个时钟周期，三级是几十个时钟周期，而内存则需要几百个时钟周期。从性能数据来说，每80个时钟周期就要处理一个报文。
因此，DPDK必须保证所有需要读取的数据都在Cache中，否则一旦出现Cache不命中，性能将会严重下降。为了保证这点，DPDK采用了多种技术来进行优化，预取只是其中的一种。
而从上面的介绍可以看出，控制结构体和数据缓冲区的读取都没有遵循硬件预取的原则，因此DPDK必须用一些预取指令来提前加载相应数据。以下就是部分接收报文的代码。
while (nb_rx < nb_pkts) {
rxdp = &rx_ring[rx_id]; //读取接收描述符
staterr = rxdp->wb.upper.status_error;
//检查是否有报文收到
if (!(staterr & rte_cpu_to_le_32(IXGBE_RXDADV_STAT_DD)))
break;
rxd = *rxdp;
//分配数据缓冲区
nmb = rte_rxmbuf_alloc(rxq->mb_pool);
nb_hold++;
//读取控制结构体
rxe = &sw_ring[rx_id];
……
rx_id++;
if (rx_id == rxq->nb_rx_desc)
rx_id = 0;
//预取下一个控制结构体mbuf
rte_ixgbe_prefetch(sw_ring[rx_id].mbuf);
//预取接收描述符和控制结构体指针
if ((rx_id & 0x3) == 0) {
rte_ixgbe_prefetch(&rx_ring[rx_id]);
rte_ixgbe_prefetch(&sw_ring[rx_id]);
}
……
//预取报文
rte_packet_prefetch((char *)rxm->buf_addr + rxm->data_off);
//把接收描述符读取的信息存储在控制结构体mbuf中
rxm->nb_segs = 1;
rxm->next = NULL;
rxm->pkt_len = pkt_len;
rxm->data_len = pkt_len;
rxm->port = rxq->port_id;
……
rx_pkts[nb_rx++] = rxm;
}