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

问题来由

一次在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)时,步长为矩阵的列数,当列数很大时,缓存可能无法存下矩阵两行的元素,这会导致计算过程中反复的缓存不命中,降低程序性能。一种可能的优化方法是每次计算两个元素的值,如下图所示,我们先取出下一行的三个元素,接着计算当前行的两个元素,这样就可以将缓存不命中的次数减半。

总结

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

 1 total views,  1 views today

页面下部广告