问题来由

一次在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,这说明确实是数组初始化对性能的影响。

总结

我一共提出了四种解释,四种从理论角度都是可能的,但只有第四种得到了实验的证实,绕了这么大弯路总算得到了答案。

03-24 00:57