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

Question

我最近在做这个问题，直接摘自IOI 2010第1天的任务3，"生活质量"，我遇到了一个奇怪的现象。

我正在设置一个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.0s)获得了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(接受)。

从这四张图中我们可以看到:

• TLE结果，图1:https://i.stack.imgur.com/9o5C2.png

• TLE结果，图2:https://i.stack.imgur.com/TJwX5.png

• 交流结果，图1:https://i.stack.imgur.com/1fo2H.png

• 交流结果，图2:https://i.stack.imgur.com/CSsZ2.png

两个for循环代码通常运行得快一点(即使在可接受的测试用例中)，与我认为单个for循环应该更快的逻辑形成对比。为什么会发生这种情况?

完整代码(AC): https://pastebin.com/c7at11Ha(请忽略所有无意义的位和东西，如using namespace std;，因为这是一个竞争性的编程比赛)。

• 注:法官服务器lqdoj.edu.vn是基于dmoj构建的。ca，全球编程竞赛平台。

Answer 1

如果你看一下汇编，你会发现差异的来源:

1. 单回路:

{
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. 将赋值分离为2个循环:

对lower的赋值现在是独立的，编译器可以使用SIMD指令，从而在第一个循环中提高性能。第二个循环与最初的程序集大致相同。