C/C++开启-O2优化后全局与局部变量版本程序结果不一致问题

程序A（使用全局变量x、y） #

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

const int maxn = 3000000 + 10;
int dp[maxn], n, maxy;
int x, y;        // <-- 全局变量x、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;
}

程序B（使用局部变量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;         // <-- 局部变量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;
}

编译指令（带-O2优化） #

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

编译信息 #

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)

问题描述 #

上述两个程序仅x、y变量的作用域不同，使用同一输入数据（约150001行的txt文件）时，开启-O2优化编译后输出结果不同；关闭-O2优化编译则结果一致。经调试观察，x、y、maxy、数组a的内容均一致，但dp数组的结果存在差异，请求排查原因。

根源分析 #

问题核心是数组越界触发的未定义行为，结合编译器优化和全局/局部变量的内存布局差异导致结果不同：

1. 数组越界风险：dp数组的合法下标范围是0到3000009（因maxn=3000010）。若输入数据中存在x >= 3000010，则u = x-1会超出dp数组的合法下标范围，触发越界访问的未定义行为。
2. 内存布局差异：
   • 程序A中，dp数组后紧跟全局变量x、y，越界访问时会读取到x的内存值；
   • 程序B中，dp数组后无x、y全局变量，越界访问时会读取到其他全局数据（如n或a数组的起始内存）；
3. O2优化的放大作用：
   • 关闭O2时，编译器内存布局松散，越界访问到的内容可能恰好一致，因此结果相同；
   • 开启O2时，编译器会对全局数据区进行紧凑布局或优化访问策略，导致两个程序越界读取的内容差异被放大，最终dp数组计算结果出现明显不同。

解决方案 #

1. 校验输入数据，确保所有x的值满足x <= maxn，避免生成非法下标；
2. 扩大dp数组的大小，预留足够边界空间；
3. 在代码中添加边界检查，比如在存入a数组前判断x-1 < maxn，拦截非法下标。

内容的提问来源于stack exchange，提问作者xaero