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

问题来由

一次在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<vector<int>> D(n + 1, vector<int>(m + 1));

当n，m较小时，官方解法是能节省很大的空间。我将我的实现改为：

if (size1 * size2 == 0) return size1 + size2;
vector<vector<int>> ops(size1 + 1, vector<int>(size2 + 1));

两次执行平均用时12ms，这说明确实是数组初始化对性能的影响。但是这种差异不能简单地归因于开辟更大空间带来的开销，还要考虑到二维数组在内存中按行存储，当计算数组中下标为(i,j)的元素时，需要访问数组中三个位置的元素，用图可表示为：

当访问元素(i,j+1)时，步长为1，具有良好的空间局部性，但是当访问下一行的两个元素(i+1,j)和(i+1,j+1)时，步长为矩阵的列数，当列数很大时，缓存可能无法存下矩阵两行的元素，这会导致计算过程中反复的缓存不命中，降低程序性能。一种可能的优化方法是每次计算两个元素的值，如下图所示，我们先取出下一行的三个元素，接着计算当前行的两个元素，这样就可以将缓存不命中的次数减半。

总结

我从四个角度提出了四种解释，四种解释都是可能的，大家在考虑自己程序性能差的原因时不妨从这些角度出发，最后再用实验证实。