|
|
背景
这两年来，主要精力集中在使用c++做矩阵计算上，由此总结了一些c++的优化手段，虽然可能几年以后会对现在的代码嗤之以鼻，本文仅记录一下自己的编程时的体悟，以便将来回顾。（实际上写完文章不久，看了一下优化的书，发现自己研究得还是太浅显了，优化之路还很长，写自己所能掌握的优化，是达到工作效率和运行时间平衡的关键，随意使用自己所无法理解的手段，有可能导致无法查出的bug）
所谓代码的优化，个人认为有三个方面：更快，更省，更好看。快指的是时间少，省指的是省空间，好看指代码简洁。这三者有时候会有冲突，而我所追求的则是达到三者的平衡，有时甚至可以兼顾三者。毕竟编程年头有限，学的比较杂，更深层次的优化其实掌握得并不多，目前使用的优化，或许也仅限于单机以及平日研究，尚未达到很高的境界。
代码始终会有bug，也很难达到完美。要实现无可挑剔的代码很难，所以才有自顶向下逐步求精，在这个过程中，可以总结许多有效的经验，这些经验往往是普适性的，这个过程必然是漫长的，我将一步步记录，想必也会很有意思。
利用计算机原理优化
这是我尚未能深入的方法。其核心在于利用计算机的金字塔物理结构，提高运算效率。CPU运算速度非常快，但数据在内存或者磁盘上，而计算通常都是发生在CPU，数据也并非直接送入CPU，而是经过多级传递，所以重点在于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);//释放内存
提前分配
上述文件转化代码，一口气将数据读入内存，虽然会有加速，但影响更大的其实在于可以根据读入内容，提前分配空间。对于一个数组的新建元素，可以使用push_back，但若可以提前预知大小，先分配空间，再来填元素，在大型数据上，将产生数量级的时间差。
对于以上读文件数据代码，下一步优化空间在于提前根据数据内容，分配好空间。更进一步，则是限制输入数据的格式，批量转化。在实验中，反复读取的数据，也可以通过此类型的预处理序列化存储好，可以节约大量时间。
减少cache miss
减少cache miss就是当CPU在计算的时候，需要的变量都在cache里。这件事其实对人脑也适用，例如大部分人其实都不太能一心两用，更不必说反复切换。如果编写了一分钟c++代码，又迅速切换到python，再迅速切换到java，这样有可能会造成用法的混乱，但若是一个月都在编写c++，那么这个月写c++都是比较通畅的，再切换python，虽然要几天适应，但不用太久又能很熟练地使用。
要想减少cache miss就需要注意对数据结构的连续设计，同时声明和引用不能距离太远，这些算是比较细节的问题。
图的存储
通常图有两种存储方式，邻接矩阵和邻接表，邻接矩阵基本不用（这里指稠密版，稀疏版其实就是邻接表），在c++上，大部分人都是自己定义图的存法，但在python上，使用的有coo matrix，csr matrix，他们本质上都不是“链表式”邻接表，而是数组式的存储。链表的问题就在于，分配元素时，所占的空间并不连续。当将变量放入cache时，通常都是按块往里放。例如需要读取某个图节点的所有邻居，假使用csr、coo的存法，一口气就可以把好几个邻接的坐标读进去，因为他们连续分配，但对于链式存储，那将可能每次只能读进去几个邻居，由此必然导致新的io，导致速度太慢。
矩阵存储与计算
众所周知，矩阵其实本质是数组。所以矩阵可以分为按行存储和按列存储，在c++里是可以自己规定的，其他很多语言是不能自己规定的。 A\cdot B 的速度其实不一定比 (B^\top \cdot A^\top)^\top 要更快。取决于是按行存还是按列存。根本原因就在于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 用不了。
说到科技被卡脖子，优化真的不能做的太好，要做到极致依赖就会比较多。有位老师说的好，别人的软件或者代码升级并不一定意味着是往你所想要的方向升级，有可能安全性更高，准确性越高，但是所需要的效率就可能降下来了。正如5G虽然升级了，但是实际并未能符合人们的期望，人们想要的是更稳定，更快，更便宜的网络，但显然兼顾方方面面是没那么容易的。
MKL为什么快，可以从CPU的使用情况感受到，但是其内部做了什么优化，并不是如今我的层次所能理解背后原因的，但重要吗？重要的其实只在于用就好，就像 python 众多包一样，没多少人会去看底层的代码，好用就完事了，但 MKL 实际并不那么好用，因为函数传递的往往都是指针数组，这就回到了为什么入门最好用Armadillo的原因，MKL快是真的快，但写完程序全是 bug，那能力不行的就直接劝退了不是？
MKL的long使用还是我心头一根刺，有待其他研究的同学一起讨论。
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;其他优化的手段还有例如向量对齐、加附加的优化参数、提前声明静态的矩阵类型。这些优化都不仅仅是在 Eigen 中使用的，其他库也有相应的优化，需要具体情况具体分析，说到底还是一个编程经验。
说到具体情况具体分析，不同的库对于不同运算的支持能力会不一样，例如Eigen做LU分解比较难，特别是矩阵不是正方形时。
随机数生成
这也是看别人论文+代码学会的，自己生成随机数的算法：http://xoroshiro.di.unimi.it/#shootout
复现别人代码的过程也是学习的过程，吃透越多代码，消化越多，最终转化为的是个人能力，本文的大部分内容，也是这一两年来，我从这些浩瀚的文章代码中提炼出的优化手段。但部分代码至今都还未能消化，这也是水平所限。好在，我们想要用这些很高级的优化算法和方法，很多时候都不需要自己实现，把自己需要的部分剥离出来即可。
编译优化
编译的命令会很大程度影响速度，最常见的例子是，在c++编译时加上 -O3，将会对速度有很大提升，这份提升是编译带来的，可想而知，MKL不能用icc编译，必然效果也会差一些。下面是一些编译上优化的例子。
这里其实也是想说，虽然高级语言大家都可以用，但是编译是可以有不同编译的手段和写法的。似乎比较少知道有实验室或者是组是做编译优化的，虽然有这样的课，但总感觉教得比较浅显，学的也比较浅显。也不知道编译器的研究有没有列入什么研究清单。要是能开发出国内开源的强力编译器，那我认为值得充钱一用（借壳改名不可取）。
Eigen的附加参数
-mavx -mfmaArmadillo
可以通过改变编译参数，使用不同的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的原因之一，实在是太麻烦，太恶心人了，换个服务器就需要再不断地尝试，十分绝望，好在还有下一招，就是写CMakeLists。但经过我个人实验时的感觉来说（我已经不能再测试icc了，无法再比较）即使是使用CMakeLists，也没有icc快。
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等。当每次推翻所有代码重构，而不留下一丝一毫时，那就像是在一直生产垃圾，但若每次推翻时都能积攒下一些组件时，那我认为这样写代码是在挖矿，积攒的代码都是金子。同理，读别人的代码什么都没留下时，又何必浪费时间呢？ |
|
窥视卡
雷达卡
发表于 2022-12-18 18:42
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
显身卡