性能优化技巧总结

0.前言

本文是我的性能优化经验的一点总结，主要是通过各种优化竞赛积累下的经验，有些方法也适用于工程中。写这篇文章本意是作为自己的备忘录，如果能够给初学者朋友们一点帮助那就更好了。

本文应该会持续更新，我会把学到的优化方法和技巧都记录下来。

1.使用工具分析程序，找到热点

优化的前提是抓住重点，找到程序热点。

工欲善其事，必先利其器

vtune：intel平台的话vtune已经十分好用了
gperftools：谷歌的性能优化工具集
perf：linux内核性能分析工具
nsight compute\system：cuda性能分析
返璞归真，手动插桩

2.预处理（减少重复计算）

首先应当仔细阅读代码，理清代码结构，尽可能的通过预处理等手段减少不必要的计算，比如将循环中多次计算提前一次性算出等。这一步是很有必要的，因为大多数情况下程序的baseline都有许多重复计算，同时这一步也是后续优化的基础。

3.优化算法，降低时间复杂度

优化计算密集型程序最有效的方法就是降低时间复杂度了，当然这一步是相当困难的，但有些算法或者算法的某个部分是可以降低时间复杂度的。针对算法的优化虽然困难，但是成效通常是显著的，在很多比赛中是否优化算法往往是胜负的关键。

4.合适的并行策略

并行不是简单的#pragma omp parallel for就可以的，这部分值得单独写好几篇文章，简单的提几点技巧，在并行过程中要尽量保证：

增大并行粒度，充分利用硬件资源
保证负载均衡，避免某个核心计算工作工作过多而其他的核心空闲的情况
尽可能减少通信开销，可以采用局部变量这种空间换时间的方法

另外，根据情况选择合适的并行模型也很重要，很多情况下openmp已经够用，但多节点的情况下，MPI显然更适合，而std::thread能够更灵活的解决问题。

5.访存优化

访存优化：访存优化实在太常见也太重要了，其内容可以展开写一系列文章，这里只提供一些简单的思路和技巧

理解cache的重要性：访问cache的时延远远小于访问RAM的时延。
利用时间局部性和空间局部性来充分利用cache。

保证数组的访存连续，这是最基本要做到的，一般是在循环中保证数组是行访问（cpp）。
AOS转SOA：将array of struct 转换为struct of array，这样会有利于进行向量化
循环分块：将循环数据切分成小的块，提高cache命中率。
数据对齐：从内存中访问对齐的数据效率要高一些。
计算与访存重合overlap，隐藏访问延迟

6.向量化

向量化也是性能优化的常用手段，通常编译器会自动进行向量化，但是往往很难达到256/512位向量化。在比赛中为了极限压榨性能，可以手动进行256或者512位向量化。

Intel® Intrinsics Guide

7.线程绑定

CPU绑定是对进程或线程设置相应的CPU Affinity，确保进程或线程只会在设置有相应标志位的CPU上运行，进而提高应用程序对CPU的使用效率。如果应用进程可以在多个CPU上运行，操作系统会在CPU之间频繁切换应用，引起CPU缓存失效，降低缓存的命中率，导致CPU使用效率下降。使用CPU绑定技术可以在一定程度上会避免CPU Cache失效，提升系统性能。

比如如果使用openmp并行，可以使用以下命令进行绑定export OMP_PROC_BIND=true。

https://lab.cs.tsinghua.edu.cn/hpc/doc/faq/binding/

openmp_document.pdf