盒子
盒子
文章目录
  1. 来由
  2. 优化理论
  3. 优化策略
    1. 程序设计
    2. 类和子程序设计
    3. 与操作系统的交互
    4. 代码编译
    5. 硬件
    6. 代码调整
  4. 其他
    1. 缓存
    2. 性能剖析工具
    3. 降内存
    4. 常见的低效之源
  5. 参考

程序优化总结分享

来由

目前主要的工作任务就是对软件进行加速,即在不影响(少影响)精度的前提下,提高程序的执行速度,降低资源的消耗

对近期工作进行总结,并编写ppt在组内分享,这里再记录一下

优化理论

  • 不要优化. 不成熟的优化是万恶之源,提高代码效率的同时一般会降低其可读性,可维护及可扩展性,需要仔细权衡,在无法确定真的需要的情况下不要进行盲目的优化
  • 先实现,再优化. 其一是就算计算再快,结果不正确也没有任何意义;其二是提前优化缺乏前瞻性,即你无法知道其全局的瓶颈在哪里,此时进行优化最好的情况也只能获得局部最优解
  • 20/80定律. 在这里就是少部分代码占据大部分的时间和资源消耗
  • 找到热点,迭代实验. 通过增加时间打印或者利用性能剖析工具,找到最耗时的模块,针对性进行优化,完成之后则另一个模块成为新的瓶颈,如此迭代测试,方能见成效
  • 实践是检验真理的唯一标准. 很多时候理论是可行,但实际往往是另一回事,在程序优化方面,只有亲自实践才能确定你的思路是否有效

优化策略

主要从六个方面来进行优化

程序设计

设计框架时优先考虑整体性能,然后再为单个的子系统和类设置要达到的资源占用目标
如考虑并行设计,每一个线程处理的数据量是否平均,其耗时与资源占用如何,需要在编码前有一定的了解

类和子程序设计

针对问题选择合适的数据结构和算法

数据类型决定了程序内存消耗,算法决定了程序的执行速度

  • 示例1: 基因注释功能中查找overlap,即对bam文件中每条reads,在基因注释文件gtf中查找与之相交的基因,再进行其他处理;一般对gtf文件构建线段树,线段树的具体实现 二叉搜索树 VS 红黑树,由于二叉搜索树是非平衡的,极端情况下甚至会退化成链表,查找最坏需要O(N)的时间复杂度,而红黑树是自平衡的,平均时间复杂度为O(log(N)),因此数据结构选择红黑树能达到更好的效率
  • 示例2: barcode序列编码成整型,如长度为10的ACGT序列可以编码成int32,只要4个字节,而使用string来存储至少需要32字节
  • 示例3: 计算一组数的中值,即50分位点的数值,可采用以下三种方式
    1. vector + sort() 使用数组存储数据,排序之后取中间的数值,由于排序需要O(NlogN),这也是整个算法的时间复杂度
    2. vector + nth_element() 使用标准库中的 nth_element 方法,可以降低时间复杂度到O(N)
    3. map + for 假如数据有不少重复,可采用条形图的方式,使用 map(有序) 来统计个数,一次for循环遍历个数即可,空间复杂度比存储全部数据要低不少,时间复杂度虽为O(N),但此处的N为 map 的key的个数,比前面的总数N要小很多

与操作系统的交互

包括磁盘IO,网络IO,动态库,外部设备等

主要考虑磁盘IO问题

  • 尽量使用内存. 能不读写磁盘就不读写,数据量不大的情况全部放入内存,毕竟读内存比读磁盘要快1000倍
  • 纯文本转二进制,减小写盘数据量. 如果确实需要输出一些中间文件,可考虑将纯文本转成二进制,或采用序列化/反序列化方案来降低数据量
  • 考虑异步/多线程读写. 如多线程并行读写,异步主要指在数据计算的时候进行拷贝操作,典型的如GPU编程中多流的应用,在处理第二批数据时,将第一批已经处理结束的数据拷贝回CPU,同时将第三批数据拷贝至GPU,达到掩盖数据IO的目的
  • 更换硬盘

代码编译

  • 选择优秀的编译器软件
  • 设置合适的编译优化参数. 如gcc的优化参数 O1 O2 O3的选择
  • 编写出编译器能够有效转化以转换成高效可执行代码的源码. 需要对编译器原理有一定了解
  • 编译器的局限性. 如C指针的内存别名问题(可使用restrict限定符来解决)
1
2
3
4
5
6
7
// 编译器不敢进行优化,只能次序执行两条指令,原因就是假如xp yp指向同一地址,
// 那么非次序执行的情况下结果会出现异常
void twiddle(long* xp, long* yp)
{
*xp += *yp;
*xp += *yp;
}

硬件

  • 购买新的硬件设备. 如固态硬盘替换机械硬盘,百兆光纤升级为千兆,采购更高主频和核数的CPU等
  • GPU/TPU/FPGA/ASIC. 假如CPU能力已经达到饱和,可以考虑使用硬件加速

代码调整

  • 调整判断次序. 在if-then-else/switch case 中将最可能出现的情况放到前面,减少判断次数
  • 知道答案后提前退出
  • 查询表代替复杂表达式. 使用查询表而非临时计算,有时候可以作为降维打击了
  • 循环
    1. 将判断外提
    2. 合并多个循环
    3. 展开. 如 k * 1 展开, k * k 展开(引入k个临时变量)
    4. 哨兵值. 如在数组中查找某个值,则每次循环都需要检查数组是否越界,那么在数组末尾添加想要查找的值,则无需判断越界问题,因为肯定会返回,当然最后需要对结果所在的索引位置进行额外的判断
    5. 削减强度. 用多次轻量级运算代替一次代价高额的运算,如移位代替整数的 *2 /2
  • 尽量减少数组引用,引入临时变量. 很多时候内存访问开销很大,引入临时变量,当全部计算完再写入内存
  • 删除公共子表达式. 提前计算好,直接使用
  • 减少过程调用. 这里主要指函数调用的开销,可以使用 inline
  • 使用低级语言重写代码. C++对应的低级语言就是汇编,python对应的就是C了
  • 理解现代处理器,利用指令级并行. 现在主流的CPU都是SIMD模式,即单指令多数据,每条指令可以操作多个数据,如intel的SSE指令集AVX,其向量长度为32字节,意味着一条指令同时可以操作8个int32数据,利用好可以达到很高的加速比

其他

缓存

使用缓存,以空间换时间

  • 示例1: 注释模块处理 bam 文件,由于bam已序,我发现不少相邻的reads 注释的结果是一样的,通过使用缓存可以降低计算量
  • 示例2: 可视化库plotly.js 中计算color,它将输入color计算为输出color,当需要显示的点数达到几M时,它的for 循环需要10s才能完成,通过简单的统计分析,我发现几M个点真正不重复的只有几百个,而相同的输入导致相同的输出,这里增加缓存可以将耗时降低到几百毫秒,可谓优秀;不过这是针对我们特定的数据集,它作为一个通用的库,自然要考虑更全面一些

优化前

1
2
3
4
5
6
7
if(isArrayColorIn || isArrayOpacityIn) {
for(var i = 0; i < len; i++) {
colori = getColor(colorIn, i);
opacityi = getOpacity(opacityIn, i);
colorOut[i] = calculateColor(colori, opacityi);
}
} else colorOut = calculateColor(rgba(colorIn), opacityIn);

优化后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
if(isArrayColorIn || isArrayOpacityIn) {
var cache = {};
for(var i = 0; i < len; i++) {
if (cache[colorIn[i]])
{
colorOut[i] = cache[colorIn[i]];
continue;
}
colori = getColor(colorIn, i);
opacityi = getOpacity(opacityIn, i);
colorOut[i] = calculateColor(colori, opacityi);
cache[colorIn[i]] = colorOut[i];
}
} else colorOut = calculateColor(rgba(colorIn), opacityIn);

性能剖析工具

win下vs的性能探查器, linux下可使用 gprof/valgrind

可以清晰的看到函数调用层次,时间占比等,帮助我们定位瓶颈所在

降内存

  • 削弱运算强度. 如double转float
  • 对数据进行编码. 如ACGT每字符可编码为2bit
  • 预留内存. 如果可以提前知道数据的长度,可使用 reserve/resize 提前预留内存
  • 传值 vs 传引用. 函数调用时,如果传值,则会发生内存拷贝
  • 警惕内存泄漏
  • 内存复用. 内存的频繁申请和释放是很耗时的,因为需要操作系统去查找合适的内存空间,特别是实时计算过程,最好在程序或服务启动时分配好需要的内存

常见的低效之源

  • 不必要的输入输出. 如磁盘IO,而这些设备是我们无法控制的
  • 分页. 一般页面大小是4k,考虑二维数组的访问,假如是行存储方式,且每行长度超过4k数据,如果每次按列访问元素,则每次都需要加载新的内存页,这无疑会导致低效率
  • 系统调用. 考虑一个第三方库,它虽然实现了你想要的功能,但也有可能其进行了一些对你来说不必要的操作,如对输入数据的判断,一些异常情况的处理等,假如可以保证我们的数据没有问题,那么这些操作就是可以避免的,此时可以手动实现我们想要的功能,来替换一些库的调用
  • 错误. 如数据库没有建立索引导致查询低效,编译器没有开启优化等操作

参考

  • <代码大全>第25,26章
  • <深入理解计算机系统>第6章