来由

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

对近期工作进行总结,并编写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章