鲲鹏开发重点4：菊厂人的冰箱，怎么从超市预取鸡蛋

鲲鹏开发重点4：菊厂人的冰箱，怎么从超市预取鸡蛋

Cache Miss 之 编译器和ARMV8预取指令

 （老古、大何）

目录

鲲鹏开发重点4：冰箱从超市预取鸡蛋的场景

菊厂人的梦想：冰箱自己从超市预取鸡蛋

突破关键：冰箱从超市下单到收单的时延

EC算法：看我的软硬件预取测试数据

编译器：变参接口和ARMV8预取指令

编译器：内置接口有哪些限制

参考资料

菊厂人的梦想：冰箱自己从超市预取鸡蛋

老古设想了菊厂人喜欢的一个场景，清晨起床，打开冰箱，准备取两个鸡蛋做早餐，却发现鸡蛋用完了，你此时的表情肯定会瞬间冻结，犹豫完再无奈地去趟超市购买，一路上，太阳当空照，花儿对你笑，你是笑还是不笑？

菊厂上班族看到这，都希望冰箱能自己从超市预取鸡蛋，那该有多妙！

突破关键：冰箱从超市下单到收单的时延

发生在CPU里面的Cache miss也是类似的场景，如果把CPU内部的Core看成你，把Cache看成冰箱，把内存看成超市，把数据看成鸡蛋，那么Core计算的时候没有在cache中拿到数据，那么Core就要到DDR内存中拿取数据，访存时延将成为算法的瓶颈，Cache miss对算法性能的影响将非常大。Cache访问时延一般是纳秒级到十纳秒级，内存访问时延一般是百纳秒级。

（图片来源：Spring 2018 :: CSE 502  stony brook）

未来的冰箱应该拥有自动上网购买鸡蛋的功能，要么冰箱主动发一个提醒给手机，要么授权冰箱可以直接给京东下单。

CPU内部的Cache已经集成了自动下单功能，就是硬件Cache在Core需要时自动把数据从内存预取进来。如果硬件预取失效，还有一种软件方式，就是Core执行软件中嵌入的cache预取指令，主动通知cache提取内存中的数据。硬件预取失效多是不知道软件需要什么数据，需要多少数据，不了解数据访问的规律，硬件预取是根据部分数据Cache miss后才会触发，是亡羊补牢的机制，所以硬件把握数据规律是难点。而软件预取指令虽然灵活，也需要程序员充分了解数据访问规律和CPU Core的执行时间，安排预取指令需要恰如其分，不能早也不能晚。

需要强调的是，如果你在数据使用前的一行代码添加预取指令，根本就没有价值，CPU core仍然会停顿大约100ns，所以，只有至少提前这100ns，才保证数据从内存已经预取到cache中了。就好像你中午12点订美团外卖的午餐，不可能订完就立马吃上，还得等餐厅做好再送过来，也许15分钟，也许半小时，所以，一定要预留足够的时间。

EC算法：看我的软硬件预取测试数据

我们有一个EC算法的测试数据，关闭Cache硬件预取功能后，在软件中添加预取指令前后的对比数据如下：

（以上数据来源于一个中间优化版本）

由于此EC算法对数据的引用具有良好的空间局部性（如果一个存储位置被引用，那么将来他附近的位置也会被引用），不具有时间局部性(被引用过一次的存储位置在未来会被多次引用)。存储的部分软件是对数据进行遍历校验的，只引用一次，计算一个异或值而已。

对于这样的非时间局部性数据无需驻留在cache中，我们应该在预取指令中选择strm方式：

KEEP   Retained or temporal prefetch, allocated in the cache normally.

STRM Streaming or non-temporal prefetch, for data that is used only once.

编译器：变参接口和ARMV8预取指令

编译器提供的内置接口是一个变参接口，__builtin_prefetch ( const void *addr,  ... ）补齐参数__builtin_prefetch ( const void *addr,  int rw,  int locality ）； 

第一个参数是数据存放地址；

第二个参数是数据用途，数据用来“读”填0，用来“写”填1；

第三个参数是数据局部性控制，0，数据不具备时间局部性，无需驻留在cache，阅后即焚；3，数据具有时间局部性，应该驻留在所有层级的cache中；1和2，cache层级递减。

（来源：附录参考资料）

编译器会根据你编译时的CPU类型来选择不同的CPU汇编指令，编译器内置接口具备更强的可移植性，但是具体到执行环境上的CPU，需要在预取地址的选择上进行调整，毕竟CPU的执行速度是不一样的。

ARMV8预取指令定义如下:

（来源：附录参考资料）

几个参数变化的内置函数对应的实际汇编指令如下：

0、  __builtin_prefetch(buf);

          50:        f9800020         prfm pldl1keep, [x1]

1、      __builtin_prefetch(buf,1);      

           50:        f9800030         prfm pstl1keep, [x1]

2、     __builtin_prefetch(buf,0);

          50:        f9800020         prfm pldl1keep, [x1]

3、     __builtin_prefetch(buf,0,0);

          50:        f9800021         prfm pldl1strm, [x1]

4、     __builtin_prefetch(buf,0,1);

          50:        f9800024         prfm pldl3keep, [x1]

5、     __builtin_prefetch(buf,0,2);

          50:        f9800022         prfm pldl2keep, [x1]

6、     __builtin_prefetch(buf,0,3);

          50:        f9800020         prfm pldl1keep, [x1]

编译器：内置接口有哪些限制

这个编译器内置接口有一些限制，并不是CPU用户手册上所有的操作类型都可以实现，下面标红的并没有实现。

编译器同事从源码上也证实了这个限制

所以，如果要支持CPU用户手册上的方式，而编译器内置接口不能提供的方式，就只有在C语言中使用内联汇编__asm__ __volatile__（“”）方式，直接填汇编指令。

举一个产品开发中预取next指针的例子：

Perf工具抓到热点，是一条“ldr x19，[x19]“指令，

对应到源码，发现函数64%的开销花在“curNode = curNode->next”上。

优化的办法，就是在循环体中提前预取curNode->next，通过在源码中嵌入编译器内置接口__builtin_prefetch(&curNode->next, 0, 1)。

这个预取是Core给cache一个暗示，执行预取指令花费4个时钟周期，让Cache去取下一次迭代需要的数据，Core就并行的执行下去了。当Core执行到for循环下一个迭代的时候，curNode->next数据已经搬移到Cache中了，如果迭代执行太快，小于Cache预取数据的时延，这个预取距离就不合适，达不到预取效果。但是，我们举的这个例子是有效果的，函数热点通过Cache并行提取数据的手段消除了，整个函数的开销从原来的12%下降到6%，效果明显。

参考资料

DDI0487D_a_armv8_arm.pdf

DUI0472M_armcc_user_guide.pdf

Using_the_GNU_Compiler_Collection_7_3.pdf

Temporal and Spatial Locality.pdf