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

I’m recently doing this problem, taken directly and translated from day 1 task 3 of IOI 2010, “Quality of life”, and I encountered a weird phenomenon.

I was setting up a 0-1 matrix and using that to calculate a prefix sum matrix in 1 loop:

```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];
}
}
```

and I got TLE (time limit exceeded) on 4 tests (the time limit is 2.0s). While using 2 for loop seperately:

```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];
}
}
```

got me full AC (accepted).

As we can see from the 4 pictures here:

the 2 for-loops code generally ran a bit faster (even in accepted test cases), contrasting my logic that the single for-loop should be quicker. Why does this happened?

Full code (AC) : https://pastebin.com/c7at11Ha (Please ignore all the nonsense bit and stuff like `using namespace std;`, as this is a competitive programming contest).

• Note : The judge server, lqdoj.edu.vn is built on dmoj.ca, a global competitive programming contest platform.

If you look at assembly you’ll see the source of the difference:

1. Single loop:
```{
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];
}
```

In this case, there’s a data dependency. The assignment to `b` depends on the value from the assignment to `lower`. So the operations go sequentially in the loop – first assignment to `lower`, then to `b`. The compiler can’t optimize this code significantly because of the dependency.

1. Separation of assignments into 2 loops:

The assignment to `lower` is now independent and the compiler can use SIMD instructions that leads to a performance boost in the first loop. The second loop stays more or less similar to the original assembly.