2019-2020 领悟的优化 基于c++

背景

这两年来，主要精力集中在使用c++做矩阵计算上，由此总结了一些c++的优化手段，虽然可能几年以后会对现在的水平嗤之以鼻，但至少可以记录一下自己的编程水平增长经历，以下希望随时间持续更新。

所谓代码的优化，个人认为有三个方面：更快，更省，更好看。快指的是时间少，省指的是省空间，好看指代码简洁。这三者有时候会有冲突，而我所追求的则是达到三者的平衡，有时甚至可以兼顾三者，个人的水平毕竟是有限的。对于尚未工作的我来说，更深层次的优化其实掌握得并不多，目前使用的优化，或许也仅限于单机以及平日研究所用。

底层优化

底层优化是我掌握得比较浅薄的方法。其核心在于利用计算机的金字塔物理结构，提高运算效率。CPU运算速度非常快，但数据在外存，也就是磁盘上，而计算通常都是发生在CPU，一个程序，分为计算密集型和io密集型，我通常面对的任务都是计算密集型，所以重点在于充分利用CPU。这里可以存在的优化有：

读写文件优化

通常网上教读写文件的方式是利用fstream，将文件转化为数据流，之后再按照数据类型，一个个地读入和转化数据，这里的优化就可以利用内存和缓存，先将所有的数据读入到内存，之后再进行数据的转换。两种代码如下：

int n;
ifstream infile(path);
infile>>n;

int n;
ifstream fin(path,std::ios::binary);
std::vector<char> buff=vector<char>(fin.seekg(0,ios::end).tellg());
fin.seekg(0,ios::beg).read(&buff[0],static_cast<std::streamsize>(buff.size()));
fin.close();
stringstream infile;
std::copy(buff.begin(),buff.end(),std::ostream_iterator<char>(infile));
infile>>n;
std::vector<char>().swap(buff);//释放内存

减少cache miss

减少cache miss，其核心想法就是，当CPU在计算的时候，需要的变量都在内存里。这件事其实对人脑也适用，例如大部分人其实都不太能一心两用，更不必说反复切换。如果编写了一分钟c++代码，又迅速切换到python，再迅速切换到java，这样有可能会造成用法的混乱，但是要是一个月都在编写c++，那么这个月写c++都是比较通畅的，再切换python，虽然要几天适应，但不用太久又能很熟练地使用。

图的存储

在数据结构课程中，通常说图有两种存储方式，邻接矩阵和邻接表，邻接矩阵基本不用，在c++上，大部分人都是自己定义图的存法，但在python上，使用的有coo matrix，csr matrix，他们本质上都不是“链表式”邻接表，而是数组式的存储。链表的问题就在于，分配元素时，所占的空间并不连续。当将变量放入cache时，通常都是按块往里放。例如需要读取某个图节点的所有邻居，假使用csr、coo的存法，一口气就可以把好几个邻接的坐标读进去，因为他们连续分配，但对于链式存储，那将可能每次只能读进去几个邻居，由此必然导致新的io，导致速度太慢。

矩阵存储与计算

众所周知，矩阵其实本质是数组。所以矩阵可以分为按行存储和按列存储，在c++里是可以自己规定的，其他很多语言是不能自己规定的。 A * B 的速度其实不一定比(B’* A’)’要更快。取决于是按行存还是按列存。根本原因就在于cache，矩阵不能整个放入cache时，必然会一块块往里取，不会跳取，导致计算矩阵乘法时，若两个变量不都在内存时，会导致cache miss，所以提前知道矩阵的存法，并设计乘法顺序是挺有必要的。

空间分配

虽然图用csr存很方便，但是毕竟不是链式邻接表，它插入元素有一个缺点，插入元素时，它无法一直保持原来的结构。所以构造图时，通常都是先生成coo 三元组（u,v,e），再插入图中。例如我最常用的Eigen库，若在构造了Sparse Matrix之后，再插入元素，所消耗的时间有时甚至可能比重新构造三元组再插入的要多，这和哈希表的构造有异曲同工之妙，哈希表通常会多预留一倍的空间，当插入的元素太多时，则批量重构哈希表，虽然这里的重构原因不一定一样，但这不就是编程和人生的常态吗，随着一个系统累积的毛病越来越多时，加补丁吃药亡羊补牢都是于事无补，最终还是看有没有将一切推倒重来的勇气，往往最后才能获得涅槃重生。

引用与指针

在c++这种“优秀”的语言下，最“好用”的技能当属指针了。其实我是特别不喜欢用指针的，但我比较喜欢用引用。指针经常会出现莫名其妙的错误，犯这些错误通常在于，搞不清楚什么时候分配，什么时候回收，不知道写中止符，造成内存泄露和非法访问。但也只有用好指针才能勉强算是会c++，别的不说，我最常使用的是用指针传递数据。在没有指针的语言里，很多时候“=”都代表复制构造，会将所有值都进行复制，这样带来的是大量时间开销，弄不清指针时，最好的办法是使用引用，传递地址，而不是新建变量浪费空间。虽然这件事也不是绝对的，当需要备份或对两个变量进行操作时，还是只能复制。

利用别人的包优化

人力有尽时，大部分情况下，别人写的包都是优于自己随手写的代码的，除非算法不一样，否则按照底层优化来说，包通常都会尽可能优化的，只需要注意是否开源，然后用即可。读书人的事，叫偷吗？程序员抄代码叫代码的复用？有人用我写的代码我会非常开心，但未经我同意抄我文章，我倒是会非常不爽。以下将谈谈我对一些矩阵运算库的理解，这里倒是没有做过对比实验，完全基于我自己的感觉，同一个库，不同人用的优化层次是不太一样的，还是根据需求选择比较好。

矩阵运算库

Armadillo

Armadillo 算是我使用的第一个c++矩阵计算库，优点胜在语法简单，接近 Matlab，速度其实也还好，关键看用了什么blas。其实这些开源的矩阵运算库，可能是由于经费的原因，代码还是比较朴素的，优化的层次比较低，实际上还是在调用各种矩阵运算，只是一个壳而已。而这些壳可以套不同的线性代数库 BLAS(basic linear algebra subroutine) ，BLAS是一种接口的标准，而不是某种具体实现，具体实现在不同版本下带来巨大的速度差异，CPU下性能最好的，个人感觉是 Intel 开发的 MKL，简直是将 CPU 利用到了极致。这也就意味着Armadillo可以用MKL，也可以用各种 BLAS，从这个角度来说，使用GPU也是可以的，所以水平够的话，何必额外套层壳呢？直接用底层的库不香吗？

MKL(Intel Math Kernel Library)

MKL，Intel开发的矩阵运算库，用起来是真的香，速度也是真的快，但是要用得好，就必须好好看文档。在国内资料少的情况下，学和用也是真的难，但更难的还是配置MKL环境。以学生身份注册可以有一年免费使用完整版的机会，但这样配置起来还挺麻烦的，踩了不少坑，这里也就不说了，后来过期了是真的难受，不得不用了简化版，最核心的是 Intel 的编译器 icc 用不了，有同学知道除了充钱外，怎么能继续使用，欢迎加我微信联系我，一起探讨这个令人又爱又恨的运算库。

MKL为什么快，可以从CPU的使用情况感受到，但是其内部做了什么优化，并不是如今我的level所能感受到的，但重要吗？重要的其实只在于用就好，就像 python 众多包一样，没多少人会去看底层的代码，好用就完事了，但 MKL 实际并不那么好用，因为函数传递的往往都是指针数组，这就回到了为什么入门最好用Armadillo的原因，MKL快是真的快，但写完程序全是 bug，那能力不行的就直接劝退了不是？

MKL其实还有一个我未能解决的问题，有朝一日解决后，会再写一篇吐槽文章。

Eigen

Eigen 常有博客将这三者比较，但个人感觉三个都可以用，看个人习惯。Eigen和Armadillo一样，都是可以借用MKL加速优化的，甚至由于开源，我也尝试过，直接改 Eigen 源码搭载MKL的接口，速度可以提升不少。Eigen不够快时可以从CPU的使用情况看出原因，凡MKL一运行，大部分时候，所有CPU的核都会用上，但Eigen通常不会。

我个人通常在 R语言里使用c++时，会优先考虑Armadillo，在python 中使用c++时会考虑Eigen，因为有对应的库。但是R里也有RcppEigen，python 也能用Armadillo。说到底还是一个习惯问题，人往往有先入为主的概念，当阅读的论文和代码都是用某一种库时，自然而然的就会用那个库，毕竟改起来复现实验容易，复现代码很多时候并不是那么简单的事。

Eigen 在不同人的手里也会导致很大的速度区别，这些优化Eigen的手段可以在知乎上搜到，最常见的可以有，当生成变量不为输入变量时，可以将普通乘法用以下命令，加快速度：

M.noalias()=A*B;

随机数生成

这也是看别人论文+代码学会的，自己生成随机数的算法：http://xoroshiro.di.unimi.it/#shootout

复现别人代码的过程也是学习的过程，吃透越多代码，消化越多，最终转化为的是个人能力，本文的大部分内容，也是这一两年来，我从这些浩瀚的文章代码中提炼出的优化手段。但部分代码至今都还未能消化，这也是水平所限。

编译优化

编译的命令会很大程度影响速度，最常见的例子是，在c++编译时加上 -O3，将会对速度有很大提升，这份提升是编译带来的，可想而知，MKL不能用icc编译，必然效果也会差一些。下面是一些编译上优化的例子。

Eigen的附加参数

用上这两个吧，我其实也不知道为什么，反正会变快。

 -mavx -mfma

Armadillo

可以通过改变编译参数，使用不同的blas，这点可以看一下文档。使用不同blas命令不同，而且需要引入不同的路径，其实还挺麻烦的。

MKL

不能用完整版MKL时，需要用特殊的g++编译命令，引入路径，非常复杂，而且没有很明确的编译命令，甚至在linux和mac上不一致，顺序也会影响，在我多次尝试之后，命令如下：

mac
g++ main.cpp -std=c++11 -I/opt/intel/mkl/include -I/opt/intel/mkl/lib/intel64 -L/opt/intel/mkl/lib -lmkl_intel_lp64 -lmkl_intel_thread -lmkl_core -I /opt/intel/compilers_and_libraries_2019.3.199/mac/mkl/include -L /opt/intel/compilers_and_libraries_2019.3.199/mac/mkl/lib -L /opt/intel/compilers_and_libraries_2019/mac/lib

linux ubuntu
clang++ main.cpp -std=c++11 -I/opt/intel/mkl/include -I/opt/intel/mkl/lib/intel64 -I/opt/intel/lib/intel64 -lmkl_intel_lp64 -lmkl_core -lmkl_intel_thread -L/opt/intel/mkl/lib -I /opt/intel/compilers_and_libraries/linux/mkl/include -L /opt/intel/compilers_and_libraries/linux/mkl/lib -L /opt/intel/compilers_and_libraries/linux/lib -liomp5 -lpthread 

以上参数有可能有一些冗余，而且需要调整，不使用于每个电脑和服务器，这也是我平常非常不喜欢用MKL的原因之一，实在是太麻烦，太恶心人了，换个服务器就需要再不断地尝试，十分绝望，好在还有下一招。

CMake

直接写CMakeLists.txt，然后使用find的方法，找到mkl，并加上编译参数，基本可以换环境后，还能运行。使用cmake还可能会提升一定的运行速度，当基本项目框架一致时，熟练使用CMakeLists可以很好完成代码的升级和迭代（就是不断往里面套用新的库）

并行优化

我最不擅长的一部分，也是最想掌握的部分。

openmp

使用openmp优化，其实就是加一条引用omp的参数，再往c++代码中加一行并行的代码，网上资料比较多，这里并没有必要详细给例子。

thread

使用c++的多线程库thread，难点可能在于加锁等问题上，而我也会皮毛，也就把一个for循环，按照核的多少进行拆分。之后是一个可以深入学习的部分，再加入此文章中。

MKL & CUDA

MKL确实是能利用多核CPU并行最佳的方法之一。CUDA则是使用GPU。

以上，并行提速能做的事很多，但还不是我如今的境界所能掌控的，未来需要提升的还很多。

算法优化

知识就是力量。算法有用吗？视情况而定，重点在于瓶颈在哪。有一种观点是，算法没啥用，差不多就好，堆算法太慢，堆钱快，速度不够快，内存不够大，用钱堆GPU，堆内存，堆磁盘，堆设备就好，但是当一个代码在几十上百核的服务器运行的时间，还没有换一个算法，在普通个人计算机上计算效果要好，速度要快时，我不禁想问，这些钱用在刀刃上了吗？文章开篇所说，时间、空间、代码美观度，三者若要同时达到最佳，那必须要有一个相对最好的算法，这是刨除外物之后，能力的最深层表现。

矩阵结构

可以优化的矩阵结构通常两种，稀疏或低秩。也算是我核心研究内容，涉及的算法远不是一篇小文能讲清，知道好用即可。

空间换时间

不能达到时间空间兼顾时，由于空间便宜，时间宝贵，通常都是采取时间换空间的手段。

Alias Method

Alias Method是对不等权重O(1)时间的采样算法，代价是需要付出构造Alias Table的时间。介绍最清楚的文章当属这篇《Darts, Dice, and Coins: Sampling from a Discrete Distribution》 。对于如此经典算法，我只能说，好用！之前的博文中有写过代码。

Sqrt

求平方根并不是空间换时间的优化方法，这里是一个引子，想说越基础的操作，速度可以是瓶颈。传说有一个神奇的值0x5f3759df，没人知道这个值是从哪里来的，但可以快速计算平方根。我们刚开始编程所熟知的方法是二分查找，实在太慢。连分数法也是一种方法。还可以空间换时间。最后是利用神奇的值的快速开方算法。可以参考博客开平方的七种算法我也是偶然看到的。

时间换空间固然美，但最优解确是两者兼顾。确实是妙不可言。看起来这样简单的问题没有什么很大提升，但实际复杂的问题往往由简单的问题构成。每一点提升都至关重要，在没有这样最优算法时，往往能做的就只有空间换时间，例如机器学习中的激活函数Sigmoid。

Sigmoid

Sigmoid函数不算复杂，但如果不从基础函数定义，是否能加速呢？目前我看到的方法就是以空间换时间。由于sigmoid函数自身特点，往外延伸，很快接近0，1，在一定范围之后，直接将值赋值为0，1即可，在此范围内，则可以划分为n个小区间存好，之后求值就成为了单次读取即可得到值的算法。

以上都是非常简单的例子，像这样的基础算法实在太多，例如Partial Sum、桶排序等等。往往我们都只需要将这件事放在心上，看情况去使用即可。

代码优化

多读，多写，多重构，就会感觉到以前写的代码有多垃圾。

c++11

lambda表达式

大部分编程语言都能用，用了就短，短就简洁，缺点是，别人可能看不懂。

auto

避免迭代变量赋值，当模版套模版时，使用起来其实还挺方便的。

批量操作

以前写R语言时，默认观点时减少写for循环，R不写for循环可以很大程度提高速度，c++则不一定，但至少代码是短的。说起来容易，做起来总是难的，也挺看个人经验。

总结

本文蜻蜓点水式回顾了2019-2020年我所比较常使用的一些优化技巧。其实每个部分都适合展开长篇大论，限于篇幅和水平，浅尝辄止。代码优化并非一蹴而就，通常在实现一个项目时，我往往会逐步优化，至少让代码先跑起来，再逐渐替换写的不好的部分。这也就意味着，可以积攒以上优化的组件，例如CMakeList、随机数生成、Sigmoid函数计算、Alias Method等。当每次推翻所有代码重构，而不留下一丝一毫时，那就像是在一直生产垃圾，但每次推翻都能积攒下一些组件时，那我认为这样写代码是在挖矿，积攒的代码都是财富。同理，读别人的代码什么都没留下时，又何必浪费时间呢？