软件性能工程

矩阵相乘例子学习

pe-matrix

使用python编写：

pe-py
计算时间需要6小时

语言优化

• 使用Java编写需要46分钟
• 使用c编写需要19分钟

解析

• python是解析性语言，运行指令需要经过解析、执行，需要的时间也会越多
• Java是介于解析语言与编译语言之间，经过优化，Java会比python跑得更快
• C是之间运行字节码，因此速度最快

For Loop优化

原来的循环如下：

pe-for

修改顺序为：

pe-for-opt

性能表现如下：

pe-for-perf

可见for的顺序不同，性能会有非常大的差异

分析：

• CPU访问cache非常快

• CPU访问内存非常慢

• 如果访问数据都在cache中，则缓存命中，否则不命中

• CPU访问数据具有局部性，因此局部性的数据更容易放进cache中

• 下面分析下不同for的内存表现：

pe-for-an
pe-for-an-opt

从上图可见，在内存访问的连续性来说，ikj会更优

可以通过命令查看程序的缓存命中率：

valgrind --tool=cachegrind ./mm

编译优化

pe-matrix-compiler

并行优化

pe-matrix-pall

运行时间为3s

缓存使用优化

• register: 1 cycle
• L1-cache: 4 cycles,
• L2-cache: 10 cycles,
• L3-cache: 50 cycles,
• DRAM: 150 cycles

pe-matrix-multi

如果内循环计算一行C

• 4096个数据吸入C
• 4096个数据从A读入
• 4096 * 4096 = 16, 777, 216 从B读入

而遗憾的是CPU L1缓存只有32k

这会导致在计算一个内循环，数据会不断的从内存读入，cache的缓存会不断的被刷走，导致运算低效

解决思路

通过减少内循环的计算量，从而减少数据被刷走的机率

pe-matrix-multi-2

如上图，如果内循环只计算C 64 * 64

• 64 * 64 = 4096会写入C
• 64 * 4096 = 262, 144会从A读入
• 64 * 4096 = 262, 144会从C读入
• 总共需要访存 528, 384

可见通过减少计算C的维度，可以大大减少访存的数量

pe-matrix-multi-3
pe-matrix-s-size

递归优化

还没看懂，先贴出来

pe-matrix-split
pe-matrix-split-time

SIMD编译优化

现代CPU不仅仅提供SISD，还会提供SIMD的指令操作

通过clang和llvm的编译优化 -march=native -ffast-math可以把某些指令并行化

优化后的时间为0.7s

下面看看例子总的优化对比

pe-matrix-perf

代码简单优化技巧

数据结构

• 通过增加数据结构的字段，来加快访问速度

pe-link

例如通过增加链表的尾指针，来加快访问链表结尾的速度

• 预计算

pe-bomin

例如计算伯努利分布，可以通过先把结果在程序运行之前算出来，构造出一个数据表，那么在程序运行的时候就可以直接拿到结果了

• 缓存

  通过把结果缓存起来，可以加快程序运行的速度，例如使用LRU算法或者redis之类的中间件

• 稀疏表示

pe-sparsit

例如一个稀疏矩阵，大部分数据都是零，而零乘以任何数都是零，是没用的计算，通过构造稀疏数据结构，既可以节省计算时间，也可以节省存储空间

例如CSR技术

pe-csr

逻辑优化

• 常量计算

  例如const double area = pi * 3

  可以通过编译器，直接计算出结果，来减少运行时的开销

• 公共表达式共用

pe-exp

例如表达式a - b已经计算过一次了，那么d就可以直接取结果，来减少多一次的计算

• 使用更廉价的计算符

  例如计算两个圆是否相交

pe-cycle

计算开根号是复杂的

那么可以两边平方来优化

pe-square

• 更快的返回

pe-fast-path

例如计算x和y的距离，来加快运算的返回

• if条件优化

pe-if

例如' '是更常见的一个符号，则可以提前判断，来减少if的运算

循环优化

• 表达式运算外提

pe-hoisting

• 循环平铺

pe-for-unroll

减少了循环判断和++操作

• 局部平铺

pe-for-part-unroll

• 循环融合

pe-for-confus

函数优化

• inline

• 减少尾递归

pe-tail-recur

• 减少递归

pe-coarsening

二进制操作优化

pe-x
pe-neg

• 设置k位

  y = x | (1 << k)
  

• 清除k位

  y = x & ~(1 << k)
  

• 反转k位

  y = x ^ (1 << k)
  

• 取头字节

  (x & mask) >> shift
  

• 交换两个整数

  x = x ^ y;
  y = x ^ y;
  x = x ^ y;
  

• 取两数最小的一个

  min = y ^ ((x ^ y) & -(x < y));
  

计算机体系结构

流水线增加吞吐量

pe-pipe-line

乱序执行，解决流水线的冲突和冒险

pe-issue

分支预测

pe-predit-if

CPU遇到跳转指令的时候，由于会出现两个分支的代码，而CPU不想等待判断结果出来，为了效率，而执行下一个指令，因此，CPU会预判一条路径执行下去，如果判断对了，则提高了效率，否则，CPU会把执行的中间结果清理，并执行对的分支

并行优化

pe-quick-sort

• 快排的总工作量是 O(n log n)
• 最大的串行工作量 n + lg n = n
• 并行度 = n log n / n = log n

可见如果要再优化快排的并行度，需要把partition并行化

题外话：使用堆来实现栈的功能

• 当程序进入一个函数，会把部分寄存器的信息保存
• 把参数入栈
• 栈的指针下移
• 函数返回时，会恢复寄存器
• 栈指针上移

假设我要用堆连存储某个函数的栈的信息

• 可以new出一片足够大的区域
• 指针不下移，而是移动到堆的地址
• 函数返回时，不上移栈指针，而是从堆的地址切回到栈的地址

归并排序优化

pe-merge-sort

• 总工作量：n log n
• 串行最大工作 n + log n
• 并行化：log n

问题出在merge的时间复杂度为n

通过二分并行处理merge：

pe-merge-bin
pe-merge-bin-code

可得：

串行时间：log n ^2

编译器优化

TBD

性能测量

pe-sort

这式一个排序算法的测量时间分布图

发现图像会出现非常奇怪的抖动。

他的原因是CPU随着计算的时间，会呈现出发热，此时计算机为了降温，所以把CPU的始终频率调低，导致排序出现上面的图形

问题的调整

pe-question

一般来说，要解决问题，必先发现问题

稳定的重现后，才可以比较容易的调整

最后把问题解决

测量时的问题

计算机的状态是不稳定的

• 无可预知的后台进程
• 中断
• 代码和数据的对齐
• CPU运行时的调度
• 超频
• 竞争
• 网络状态
• 磁盘访问和内存访问的错误和重试

测量工具

• gettimeofday
• gdb
• gprof
• perf
• cachegrind

测量结果

取最小值

访存优化

栈

• 申请和释放都是O(1)

堆

• 会引起内部碎片和外部碎片
• 大小不固定
• 多线程竞争
• 不同内存片位于不同的页表

pe-memory

管理

pe-single-heap
pe-multi-heap
pe-multi-heap-2
pe-heap

GC

• 通过智能指针
• 通过构造内存引用图，后台进程不断扫描，并清理没有引用的内存