如何用Cache在C++程序中进行系统级优化（二)?

上篇文章，我们主要介绍了Cache和在编写Cache友好型代码的使用经验，本文我们继续以实战的模式介绍如何通过Cache进行系统级优化。

▲数据集中存放
Cache和内存速度差异这么大，所以要尽量少访问内存，可以的话，尽量将数据合并存放在一起，利用Cache预取，一次将尽可能多的数据从内存加载到Cache。比如金融业务中通常存在用户、订单、资金信息，每次处理订单时，都需要查询用户、资金信息，如果设计数据结构时，能将这些信息在内存中连续存放，就可以实现访问一次内存获取到所有数据，避免多次访问零碎内存。

▲Cache Line对齐
默认情况下，内存地址会按照数据大小对齐，这样有些数据结构可能会跨Cache行存放，占用多行Cache，从而影响性能，所以在一些关键数据结构上，可以手动设置成按Cache Line对齐，避免占用多行Cache。按Cache Line对齐代码示例如下：

在上面代码中，定义了两个宏CACHE_LINE_SIZE，和CACHE_LINE_ALIGN。CACHE_LINE_SIZE表示Cache行大小，大多数情况下为64。CACHE_LINE_ALIGN是根据各平台编译器提供的语法，定义的按CACHE_LINE_SIZE对齐的宏。接着又定义了XXX类型的变量x，XXX为任意数据类型，可以为基础类型比如int，也可以是自定义类型。这样定义以后，变量x的地址就是64的整数倍。如果采用C++11语法就更简单了，C++11提供了关键字alignas来设置数据的对齐方式：alignas(CACHE_LINE_SIZE) XXX x。

▲数组按行访问

C++中数组在内存中是按行存放的，因此在访问多维数组时，尽量按行访问，避免按列访问。因为按列访问，会导致跳跃式访问内存，数据量大的时候，会导致频繁的Cache换入换出，对Cache很不友好。

▲Cache伪共享
不同线程的数据尽量放到不同的Cache Line，避免多线程修改同一行Cache，导致Cache需要在多核之间进行同步。由于这种共享不是程序本意，而是由于底层Cache按块存取机制导致的，又称为Cache伪共享。
比如，在编写多线程程序时，会有一些线程指标统计的工作，为了避免线程竞争，一般会定义一个数组，每个线程修改其中一个元素，需要统计信息时，将所有元素相加得到结果。代码示例：

如上，将变量counter设置为按Cache行大小对齐，这样数组threads_info的每个元素都会占用单独的一行Cache，多个线程修改各自的counter，就不会存在Cache行竞争，避免Cache同步。

▲软件预取
在某些场景中，可以在代码里，通过CPU提供的预取指令，进行软件预取，更高效的使用缓存。Windows下可以使用VC++提供的_mm_prefetch函数，Linux下可以使用GCC提供的__builtin_prefetch函数。

▲指令预取
程序中的热点函数尽量放在一起，方便指令预取，减小指令缓存的占用，同时，模块间的函数调用，可以通过调整编译器链接顺序，来调整指令位置。

另外，如果程序经常执行跳转指令，将不利于指令预取，我们可以采用软件分支预测方法，帮助编译器生成更优化的指令。Linux下一般使用如下代码实现：

likely和unlikely是C++宏，likely宏的意思是告诉编译器之后的分支执行概率较大，unlikely刚好相反。在上例中，因为使用了unlikely，编译器认为if分支执行概率小，因此在生成指令时，会将else分支的指令放在前面，以减少程序执行时的指令跳转，使指令尽可能顺序执行。

▲高精度计时
在做程序优化时，需要一个高精度时间测量方法，来避免测量本身带来的开销和干扰。Intel CPU提供了rdtsc和rdtscp指令，用于获取CPU时钟周期，其中rdtscp能避免乱序执行问题，保证在rdtscp之前的所有程序指令执行完以后，才会被执行，从而能更精确的获取时间。利用这些指令封装的获取时间函数定义如下：

在实际使用中，函数rdtscp1()需要放在被测代码之前，获取程序起始执行时间，函数rdtscp2()放在被测代码之后，用于获取结束时间。函数汇编指令中的CPUID用于指令序列化，避免前面或后面的指令由于乱序执行而提前或推迟执行，从而影响到测试代码。需要注意的是，这两个函数返回的是CPU时钟周期，在换算为时间时，还需要除以CPU的频率。另外这些函数返回的值，是CPU加电后的线性时间，而不是真实时间。

有些优化比如数据结构定义，对齐方式等，在编码时就可以考虑到，但是软件的规模性和复杂性，决定了很多优化需要等到程序运行起来，根据性能分析之后，才能找到问题点，制定解决方案。作者推荐一个检测工具perf，它是Linux内核自带的工具，通过统计硬件事件或随时间采样等方式，可以检测CPU、Cache、系统调用、磁盘IO等系统的方方面面，再配合其他工具，绘出程序执行的热力图、火焰图等，可以更快定位出程序的热点代码，再进行重点优化。程序优化任重而道远，本文只揭开其冰山一角，与读者分享。

参考资料
1. 《深入浅出DPDK》
2. https://en.wikipedia.org/wiki/CPU_cache
3. https://www-ssl.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-32-ia-64-benchmark-code-execution-paper.pdf

4. http://www.brendangregg.com/perf.html