C++ – How to Troubleshoot Strange Problems in C++ Optimized(-O2) Programs

c++

Program A, with global variables x and y:

#include <cstdio>
#include <vector>
using namespace std;

const int maxn = 3000000 + 10;
int dp[maxn], n, maxy;
int x, y;        // <-- Global variables `x` and `y`
vector<int> a[maxn];

int main() {
    freopen("demo.txt", "r", stdin);
    freopen("demo.out", "w", stdout);

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        //int x, y;
        scanf("%d %d", &x, &y);
        a[y].push_back(x-1);
        maxy = max(maxy, y);
    }
    for (int i = 1; i <= maxy; i++) {
        dp[i] = dp[i - 1];
        if (a[i].size() == 0) continue;
        for (int j = 0; j < a[i].size(); j++) {
            int u = a[i][j];
            dp[i] = max(dp[i], dp[u] + i - u);
        }
    }
    printf("%d\n", dp[maxy]);
    
    return 0;
}

Program B, almost the same with program A, but with local variables x and y (x and y can be considered as the two endpoints of an interval that $x < y$).

#include <cstdio>
#include <vector>
using namespace std;

const int maxn = 3000000 + 10;
int dp[maxn], n, maxy;
//int x, y;
vector<int> a[maxn];

int main() {
    freopen("demo.txt", "r", stdin);
    freopen("demo2.out", "w", stdout);

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int x, y;         // <-- Local variables `x` and `y`
        scanf("%d %d", &x, &y);
        a[y].push_back(x-1);
        maxy = max(maxy, y);
    }
    for (int i = 1; i <= maxy; i++) {
        dp[i] = dp[i - 1];
        if (a[i].size() == 0) continue;
        for (int j = 0; j < a[i].size(); j++) {
            int u = a[i][j];
            dp[i] = max(dp[i], dp[u] + i - u);
        }
    }
    printf("%d\n", dp[maxy]);
    
    return 0;
}

Compile instruction (with -O2 optimized):

g++ demo.cpp -o demo.exe -O2 -std=c++14

Compile information:

Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=C:/mingw64/bin/../libexec/gcc/x86_64-w64-mingw32/8.1.0/lto-wrapper.exe
Target: x86_64-w64-mingw32
Thread model: posix
gcc version 8.1.0 (x86_64-posix-seh-rev0, Built by MinGW-W64 project)

Those two programs get the different results with the same input!

With the same input data, I've watched the variables of x, y, maxy, a[i], and all of them got the same data. And the array element dp[i] got the different data. I don't know why, the variable dp[i] and x, y are unrelated!

And if I compile them without -O2 instruction, that is g++ demo.cpp -o demo.exe -std=c++14, they get the same output!

The big input data comes here: https://ww0.lanzouq.com/iesib26alt6f

It's a txt file, with about 150001 lines.

BTW:
This program is a solution to this question, However, you can ignore this information. The issue I've gotten seems to be no relation with that question.

Best Answer

your input file at line 3076 contains

0 437122

then in your code you are doing an out of bounds access when doing

a[y].push_back(x-1); // a[y][last] = -1
...
int u = a[i][j];
dp[i] = max(dp[i], dp[u] + i - u);  // dp[u] = dp[-1]

out of bounds access is undefined behavior, it just happened not to crash with -O0 and crashes with -O2, likely due to different layout of globals.

you could detect this bug with an assert.

assert(u >= 0 && u < maxn);

alternatively you can use std::array<int,maxn> dp; and hope your standard library has asserts on bracket operator in debug mode like MSVC does.

Related Question