低效程序根源追溯——记一次刷题对性能的不满

问题来由
一次在Leetcode上遇到一道DP题,题号72。一般DP题的状态转移方程需要从多个候选中选出最小值,我用下面的代码实现了状态转移方程:

**第一种** for (int i = size1-1; i >= 0; i--) { for (int j = size2-1; j >= 0; j--) { if (word1[i] == word2[j]) { min = ops[i+1][j+1]; } else { min = 1 + ops[i+1][j+1]; } if (min > 1 + ops[i+1][j]) { min = 1 + ops[i+1][j]; } if (min > 1 + ops[i][j+1]) { min = 1 + ops[i][j+1]; } ops[i][j] = min; } }

但这种写法用时80ms,只击败了不到6%的提交。我对这种低效非常不满,将官方题解提交后发现耗时仅16ms,状态转移方程部分代码如下:
**第二种** for (int i = 1; i < n + 1; i++) { for (int j = 1; j < m + 1; j++) { int left = D[i - 1][j] + 1; int down = D[i][j - 1] + 1; int left_down = D[i - 1][j - 1]; if (word1[i - 1] != word2[j - 1]) left_down += 1; D[i][j] = min(left, min(down, left_down)); } }

我猜测是状态转移方程部分的代码实现低效导致程序整体性能偏差,为此我对这部分代码开展了研究。
分支对性能的影响
我的第一个想法和分支有关,重新翻阅了CSAPP后,摘出原书P358的下面一段话
现代处理器采用了一种称为分支预测的技术,处理器会猜测是否选择分支,同时还预测分支的目标地址。使用投机执行的技术,处理器会开始取出位于它预测的分支会跳到的地方的指令,甚至在它确定分支预测是否正确之前就开始执行这些操作。如果过后分支预测错误,会将状态重新设置到分支点的状态,并开始取出和执行另一个方向上的指令。
采用这种方法,如果分支预测失败,就必须抛弃已经执行的结果,转而重新执行一系列计算,这种方式会增加程序执行的时间。换句话说,为了更好的性能,编写程序时应当尽量避免使用分支。
解释差异
在官方实现中,使用三个变量存下了可能值,对于需要判断当前字符是否相等的情况,必须使用一个分支。在我的实现中,将通过条件分支去获得三个可能值中最小值的方式改为了通过C++库函数min获得。如果min函数的实现没有用到分支,那么这种性能差异便可使用分支预测去解释,因此我又去cppreference上查了min函数的possible implementation,发现是通过三目运算符 ? :实现的,我将官方题解改为:
**第三种** for (int i = 1; i < n + 1; i++) { for (int j = 1; j < m + 1; j++) { int left = D[i - 1][j] + 1; int down = D[i][j - 1] + 1; int left_down = D[i - 1][j - 1]; if (word1[i - 1] != word2[j - 1]) left_down += 1; left_down = down < left_down ? down : left_down; D[i][j] = left < left_down ? left : left_down; // D[i][j] = min(left, min(down, left_down)); } }

两次执行,一次耗时12ms,一次耗时16ms,说明用min和三目运算符方式性能差异不大,我们可以直接讨论三目运算符。进一步,难道三目运算符不需要用到分支?为了解答这个问题,我们可以利用objdump反汇编可执行程序,去查看汇编码,但是我太懒了,直接借鉴了这位朋友的博客。我们可以看到,三目运算符可能会翻译成多种形式的汇编,如果两个操作数都是常数,是可以不使用分支的。但第三种实现中,操作数放在寄存器中,编译器无法根据编译时不确定的值去生成不用分支的汇编码。我将第一种实现用三目运算符改写了:
**第四种** for (int i = size1-1; i >= 0; i--) { for (int j = size2-1; j >= 0; j--) { min = word1[i] == word2[j] ? ops[i+1][j+1] : 1 + ops[i+1][j+1]; min = min > 1 + ops[i+1][j] ? 1 + ops[i+1][j] : min; min = min > 1 + ops[i][j+1] ? 1 + ops[i][j+1] : min; ops[i][j] = min; } }

一次执行68ms,一次执行80ms,和第一种差异不大,这表明三目运算符最后还是被翻译成了使用分支的汇编码,使用if-else还是三目运算符对性能影响不大。
另一种解释
在第二种实现中将数组中元素值存在变量中,在汇编层面就是把值放在寄存器中,之后的运算只需使用寄存器,由于寄存器访问的快速,程序照理是会表现出更好的性能。为此,我将第一种实现又改写为:
**第五种** for (int i = size1-1; i >= 0; i--) { for (int j = size2-1; j >= 0; j--) { int right_down = word1[i] == word2[j] ? ops[i+1][j+1] : 1 + ops[i+1][j+1]; int right = 1 + ops[i][j+1]; int down = 1 + ops[i+1][j]; right_down = right_down < right ? right_down : right; ops[i][j] = right_down < down ? right_down : down; } }

一次执行72ms,一次执行68ms,和第二种实现没有很大差异,很可能编译器已经帮我做了优化,操作数实际上已经被加载到寄存器中了。
第三种解释
【低效程序根源追溯——记一次刷题对性能的不满】我又把目光放在了边界值初始化上,我的版本是:
for (int i = 0; i < size1; i++) { ops[i][size2] = size1 - i; } for (int j = 0; j < size2; j++) { ops[size1][j] = size2 - j; }

官方题解是:
for (int i = 0; i < n + 1; i++) { D[i][0] = i; } for (int j = 0; j < m + 1; j++) { D[0][j] = j; }

我猜测是循环内部的减法导致我的版本性能更差,因此我将官方题解改为:
for (int i = 0; i < n + 1; i++) { D[n-i][0] = n-i; } for (int j = 0; j < m + 1; j++) { D[0][m-j] = m - j; }

三次执行平均用时14ms,无明显变化我的猜测又被推翻了。
最后一次解释
排除了这么多可能,我将眼光放在了创建DP数组上,我的实现:
int ops[600][600] = {0};

官方实现:
if (n*m == 0) return n + m; vector> D(n + 1, vector(m + 1));

当n,m较小时,官方解法是能节省很大的空间。我将我的实现改为:
if (size1 * size2 == 0) return size1 + size2; vector> ops(size1 + 1, vector(size2 + 1));

两次执行平均用时12ms,这说明确实是数组初始化对性能的影响。
总结
我一共提出了四种解释,四种从理论角度都是可能的,但只有第四种得到了实验的证实,绕了这么大弯路总算得到了答案。

    推荐阅读