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

问题来由
一次在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，和第二种实现没有很大差异，很可能编译器已经帮我做了优化，操作数实际上已经被加载到寄存器中了。
第三种解释
【低效程序根源追溯——记一次刷题对性能的不满】我又把目光放在了边界值初始化上，我的版本是：