虚拟内存对 OI 的影响

假想你写了这么四段代码：

#include <vector>
#include <bits/stdc++.h>
using namespace std;
std::vector<int> vec;
//int a[100000010];
int main() { freopen("a.out", "w", stdout), cout << 1 << endl;}//, vec.resize(1e8); }

#include <vector>
#include <bits/stdc++.h>
using namespace std;
std::vector<int> vec;
int a[100000010];
int main() { freopen("a.out", "w", stdout), cout << 1 << endl;}//, vec.resize(1e8); }

#include <vector>
#include <bits/stdc++.h>
using namespace std;
std::vector<int> vec;
//int a[100000010];
int main() { freopen("a.out", "w", stdout), vec.resize(1e8),cout << 1 << endl ; }

#include <vector>
#include <bits/stdc++.h>
using namespace std;
std::vector<int> vec;
int a[100000010];
int main() { freopen("a.out", "w", stdout), vec.resize(1e8), cout << 1 << endl; }

已知 \(10^8\) 个 int 需要占用内存 400M，那么就是说，在内存限制 600M 的情况下，前三个程序都能正确输出 1，第四个程序因为有 400M 的数组和 400M 的 vector 而因 MLE 致死。使用 NOI Linux 2.0 的 arbiter_local 进行测评，结果也确实如此。

但实际上在本地运行第四段程序的时候，无法发现使用内存超过 600M 的事实。一般有三种手段检查内存，第一种是用全局变量结尾和开头两个变量地址相减的办法测算空间（这样会测少（标准库自身会使用一部分静态空间），并且这种写法是 UB）。是第二种是使用 GNU size 测量静态空间，第三种是使用 GNU time 测量最大常驻内存大小。使用后两种方法，可以发现都不超过 400M：

minni@LAPTOP-VTBPQCQP:~/test$ make sizetest
g++ sizetest.cpp -o sizetest -O2 -g -DNF -DLOCAL -fsanitize=undefined,address -Wall -std=c++14
sizetest.cpp: In function ‘int main()’:
sizetest.cpp:6:21: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    6 | int main() { freopen("a.out", "w", stdout), vec.resize(1e8), cout << 1 << endl; }
      |              ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
minni@LAPTOP-VTBPQCQP:~/test$ cat sizetest.cpp
#include <vector>
#include <bits/stdc++.h>
using namespace std;
std::vector<int> vec;
int a[100000010];
int main() { freopen("a.out", "w", stdout), vec.resize(1e8), cout << 1 << endl; }
minni@LAPTOP-VTBPQCQP:~/test$ size sizetest
   text    data     bss     dec     hex filename
  51392   29880 400001544       400082816       17d8c780        sizetest
minni@LAPTOP-VTBPQCQP:~/test$ \time ./sizetest
0.12user 0.09system 0:00.22elapsed 98%CPU (0avgtext+0avgdata 402636maxresident)k
0inputs+8outputs (0major+15370minor)pagefaults 0swaps

而事实上他会使用到 800M，我们需要引入虚拟内存的概念：https://www.pengrl.com/p/21292/。测量虚拟内存峰值使用 system("grep VmPeak /proc/$PPID/status")（程序末尾），这是 Arbiter 所测量的空间大小。

为了能在本地发现此问题，可以使用 ulimit -v 限制虚拟内存大小，如这里限制为 600M 就写

ulimit -v 600000

注意单位是 KB，这样程序就能正常报错了：

minni@LAPTOP-VTBPQCQP:~/test$ g++ sizetest.cpp -o sizetest -O2 -g -DNF -DLOCAL -Wall -std=c++14 && ./sizetest
sizetest.cpp: In function ‘int main()’:
sizetest.cpp:6:21: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    6 | int main() { freopen("a.out", "w", stdout), vec.resize(1e8), cout << 1 << endl; }
      |              ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
已中止 (核心已转储)

对照实验：删去 vector 和 int[100000010] 的其中一个，程序都不会报错，具体的测试可以自己做。

以上，警醒我们限制虚拟内存以防止最终评测的 MLE。可使用 ulimit -v <实际空间限制> 解决该问题。

ref：https://www.luogu.com/article/epn32t2i