为什么在与前缀和矩阵相关的问题中 1 个 for 循环比 2 个 for 循环慢？

Question

最近在做this problem, taken directly and translated from day 1 task 3 of IOI 2010, "Quality of life"，遇到一个奇怪的现象

我正在设置一个 0-1 矩阵并使用它在 1 个循环中计算前缀和矩阵：

for (int i = 1; i <= m; i++)
{
    for (int j = 1; j <= n; j++)
    {
        if (a[i][j] < x) {lower[i][j] = 0;} else {lower[i][j] = 1;}
        b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1] + lower[i][j];
    }
}

并且我在 4 次测试（时间限制为 2.0 秒）中得到了 TLE（超出时间限制）。单独使用 2 个 for 循环时：

for (int i = 1; i <= m; i++)
{
    for (int j = 1; j <= n; j++)
    {
        if (a[i][j] < x) {lower[i][j] = 0;} else {lower[i][j] = 1;}
    }
}

for (int i = 1; i <= m; i++)
{
    for (int j = 1; j <= n; j++)
    {
        b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1] + lower[i][j];
    }
}

给了我完整的 AC（已接受）。

从这里的4张图片可以看出：

TLE结果，图1：https://i.stack.imgur.com/9o5C2.png
TLE 结果，图 2：https://i.stack.imgur.com/TJwX5.png
AC结果，图1：https://i.stack.imgur.com/1fo2H.png
AC结果，图2：https://i.stack.imgur.com/CSsZ2.png

2 个 for 循环代码通常运行快一点（即使在可接受的测试用例中），这与我认为单个 for 循环应该更快的逻辑形成对比。为什么会这样？

完整代码 (AC)：https://pastebin.com/c7at11Ha（请忽略所有废话和诸如 using namespace std; 之类的东西，因为这是一个竞争性编程竞赛）。

注：评委服务器lqdoj.edu.vn is built on dmoj.ca，全球编程竞赛平台

Answer 1

如果您查看 assembly，您会发现差异的来源：

单循环：

{
    if (a[i][j] < x)
    {
        lower[i][j] = 0;
    }
    else
    {
        lower[i][j] = 1;
    }
    b[i][j] = b[i-1][j] 
            + b[i][j-1]
            - b[i-1][j-1]
            + lower[i][j];
}

在这种情况下，存在数据依赖性。对 b 的赋值取决于对 lower 的赋值。所以操作在循环中按顺序进行 - 首先分配给 lower，然后分配给 b。由于依赖关系，编译器无法显着优化此代码。

将赋值分成 2 个循环：

现在对 lower 的赋值是独立的，编译器可以使用 SIMD instructions，从而在第一个循环中提高性能。第二个循环或多或少与原始程序集保持相似。

为什么在与前缀和矩阵相关的问题中 1 个 for 循环比 2 个 for 循环慢？

Why is 1 for-loop slower than 2 for-loops in problem related to prefix sum matrix?

c++

performance

for-loop

prefix-sum