+++ date = "2020-07-06T23:00:00+08:00" draft = false tags = [] title = "Different Ways to Initialize an Array, and their Performance" authors = ["xry111"] summary = "Discuss minor performance issues introduced by array initialization in competitive programming." +++ # 初始化数组的不同方法及其运行时间 众所周知，在程序设计竞赛中我们往往要初始化数组。初始化数组有很多不同的写法， 那么它们哪种更快呢？我们将进行一些计时测试，比较和分析它们的运行时间。 ## 测试环境 | 参数 | 值 | |----------|-----------------------------| | OS | Linux-5.8.0-rc3+ | | Libc | Glibc-2.31 | | Compiler | GCC-10.1.0 | | CPU | Intel Core i7-1065G7 | | Memory | DDR4 2666 MHz (x2) | 如无特殊说明，测试中使用 `-O2` 优化开关编译程序。 ## “自动”初始化 根据[标准](/assets/std/cpp-n4659.pdf) (第 6.6.2 节) 规定， 具有静态存储期的无构造函数对象会被默认初始化为 0。换句话说， 如果我们想要把某个数组初始化为 0，只要在全局声明它即可。例如： ```c++ int arr[1000000000] = {0}; int main() { return 0; } ``` 这里放一个 `= {0}` 是为了增强可读性，不写也是可以的。 如果我们编译并执行上述程序，进行计时，会发现它几乎没有消耗 CPU 时间。 于是有些同志就可能认为“自动初始化是不消耗时间的”，然而这是假象， 这就像是说天上会掉馅饼。我们使用一下这些内存： ```c++ int arr[1000000000] = {0}; int main() { for (int i = 0; i < 1000000000; i++) arr[i] = 1; return 0; } ``` 测量其运行时间，会发现其在用户态使用了 $0.30$ 秒，内核态使用了 $0.23$ 秒。 前者是很好理解的：这就是我们将这个数组写成全 1 需要的时间。 那么内核态的时间是怎么回事呢？这正是操作系统为我们准备这个默认初始化为全 0 的数组所需的时间。 在编译生成的可执行文件中，对象 `arr` 被放置在 BSS 段中。 BSS 段中的对象不会被实际存储在可执行文件中，而是只存储其大小。 在程序开始执行时，操作系统才实际分配该对象所需的内存，并将其初始化为 0。 那么为什么不使用数组时就没有初始化时间呢？ 这是因为操作系统进一步延迟了初始化，只有实际访问某个虚拟内存页面时， 才会在物理内存准备一个全 0 页面并将其映射到被访问的虚拟内存页面。 要验证这一点，我们可以不访问 `arr` 的每个位置，而只是将每个内存页面踩一遍。 在我使用的测试平台上，页面大小是 $4096$ 字节。而 `int` 的大小是 $4$ 字节， 我们以 $4096 / 4 = 1024$ 为步长访问数组： ```c++ int arr[1000000000] = {0}; int main() { for (int i = 0; i < 1000000000; i += 1024) arr[i] = 1; return 0; } ``` 执行并测量运行时间，会发现其用户态时间为 $0.01$ 秒，而内核态时间为 $0.24$ 秒。这就说明虽然我们没有访问数组的每个元素， 但操作系统准备页面时仍然不得不对每个元素清零。 我们在竞赛中通常不考虑初始化全局对象的时间， 并不是因为这种“自动”初始化不需要时间，而是因为这些时间可以忽略不计。 根据上述实验结果，操作系统用 $0.25$ 秒即可初始化一个 $10^9$ 个 `int` 的数组。而竞赛题目的内存限制通常是 $256$ MB，只能开 $67108864$ 个 `int`， 操作系统将它们初始化为 0 只需要 $0.017$ 秒，这是可以完全忽略不计的。 ## 手动初始化 如果我们需要将数组初始化成非 0 值，就得手动初始化它。例如， 我们上面的代码其实将数组初始化成了全为 1。根据我们之前测量的结果， 不考虑操作系统进行全 $0$ 初始化的时间， 使用一个 `for` 循环进行这种初始化需要 $0.30$ 秒。 使用 `std::fill` 进行初始化会得到相同的结果，因为 `std::fill` 模板实例化并内联后和直接写一个 `for` 循环是完全等价的。 然而这个结果其实有优化的余地。首先我们进行循环展开， 即在一次循环中初始化不只一个数组元素，以减少需要执行的指令条数： ```c++ int arr[1000000000] = {0}; int main() { for (int i = 0; i < 1000000000; ) { arr[i++] = 1; arr[i++] = 1; arr[i++] = 1; arr[i++] = 1; } return 0; } ``` 这样用户态运行时间就减小到了 $0.21$ 秒。 在此基础上，我们对循环进行向量化：使用 `memcpy` 一次写入 $4$ 个数组元素， 编译器会自动将 `memcpy` 优化成向量移动指令： ```c++ int arr[1000000000] = {0}; int main() { int t[] = {1,1,1,1}; for (int i = 0; i < 1000000000; i += 4) memcpy(&arr[i], &t[0], sizeof(t)); return 0; } ``` 观察编译生成的汇编代码，会发现它使用了 SSE 寄存器 `%xmm0` 和 `movaps` 指令， 每次直接写入 $4$ 个数组元素。测量得到用户态运行时间减小到了 $0.18$ 秒。 实际上编译器也可以自动进行循环展开和向量化，它们分别可以用 `-funroll-loops` 和 `-ftree-loop-vectorize` 选项打开， 而这两个选项又会在 `-O3` 优化级别自动启用。 我们使用 `-O3` 编译最原始的那个 `for` 循环，会得到相同的结果。 如果在 `-O3` 的基础上加入 `-march=native`， 编译器还会动用本机上更大的向量寄存器。例如，在我的测试平台上， CPU 支持 AVX-512，编译器会使用 512 位的 `%zmm0` 寄存器。 但是这并不能进一步缩短运行时间 (测试结果仍为 $0.18$ 秒)。 编译器的循环展开和向量化也会作用于 `std::fill`。 ## `memset` 函数 在某些情形下 (例如将数组初始化成全 0，全 -1， 或全为一个充分大但具体值不重要的值) 时，可以使用 `memset` 函数。 我们进行一个全 -1 的初始化： ```c++ int arr[1000000000] = {0}; int main() { memset(arr, 0xff, sizeof(arr)); return 0; } ``` 测量发现它只需要 $0.12$ 秒的用户态时间，比循环展开和向量化的结果还快！ 这是因为在我们的测试平台上 `memset` 是高度优化的手写汇编代码。 另外，需要说明的是，如果你手写了一个 `for` 循环去初始化数组， 而且编译器发现可以用 `memset` 获得相同的效果，则在 `-O1` 及以上优化级别下， 会将你的 `for` 循环直接替换成 `memset`。因此，我们前面测试 `for` 循环时， 使用了整数 $1$ 而不是 $0$，以防止这种替换。 ## 动态内存分配 我们使用 `malloc` 分配一个数组，并且初始化它： ```c++ int main() { volatile int *arr = (int *) malloc(sizeof(int) * 1000000000); for (int i = 0; i < 1000000000; i++) y[i] = 0; } ``` 测量得到的时间为用户态 $0.29$ 秒，内核态时间 $0.25$ 秒， 这和静态分配是完全一样的。既然标准没有要求 `malloc` 分配初始化为 0 的内存块，为何操作系统要花时间清零呢？ 这是因为在初次 `malloc` 时需要向操作系统索要内存页面， 而操作系统是不能将“脏页”直接给你用的， 因为脏页可能含有其他程序甚至内核使用过的密钥等敏感信息，所以必须清零。 但是，如果你使用了这些内存块，再使用 `free` 将这个内存块释放掉， 然后重新用 `malloc` 分配一些内存，就可能得到 “脏”内存块。这是因为同一进程内部没有保密可言，也就没有必要，也没有意义对上次 `malloc` 和 `free` 的内存块清零。因此通常必须假设 `malloc` 会返回含有未初始化值的内存块。 对于栈上分配的数组，情况也是一样的。如果你在 `main` 函数里面直接开个巨大的数组，很可能会获得操作系统新鲜分配的， 清零的页面。但是，如果在一系列函数调用后再在栈上开数组， 就很可能得到包含之前的函数调用留下的垃圾数据的页面， 即未初始化数组。 注意，对于动态分配，我们不应依赖操作系统将内存页清零的行为， 因为语言标准规定此时得到的是含有未初始化值的数组， 而使用未初始化值是未定义的。即使操作系统真的将内存页清零， 编译器也可能在代码优化和生成的过程中产生无法预测的行为。 当然，类似 `calloc`，`new int[10]` 或者 `int a[10] = {}` 等语法构造的语义包括了清零，可以使用它们直接分配初始化为 0 的数组。 ## `std::vector` 我们也可以用 `std::vector` 代替数组： ```c++ int main() { vector a(1000000000, 1); __asm__ volatile ("":::"memory"); } ``` 最后的 `__asm__` 语句是为了防止编译器将整个 `vector` 优化掉。 它的时间效率与手写 `for` 循环，或者用 `std::fill` 初始化是一样的， 都是 `-O2` 下用户态 $0.30$ 秒，`-O3` 下用户态 $0.18$ 秒。 这里需要指出的是，许多选手 (特别是 OI 出身的选手) 对于动态内存分配导致效率低下的原因存在大量误解。 动态分配一大段内存并使用并不会导致效率低下， 影响效率的关键是动态分配的**次数**。例如， 在递归的时候将一个 `vector` 按值传递几万层就肯定会导致效率低下 (即使那个 `vector` 中没几个元素)。另外，在 OI 中，由于不开优化， `vector` 的多层抽象都会原封不动保留到目标代码中，也会导致效率低下， 导致 OI 选手对其本能的厌恶，这是可以理解的。但是不加思考地认为 `vector` 的每个环节都慢，甚至在博客或者群里以讹传讹， 就属于严重的不负责任的行为。本文的主旨正是澄清这些问题， 而不是教大家怎么初始化。毕竟正如我们之前讨论的，在比赛的内存空间限制下， 初始化的时间完全可以忽略不计 (本文为了让测量结果更可靠， 不得不使用远大于实际比赛题目限制的内存)，因此随便怎么初始化都行 (当然不能写时间复杂度与输入规模呈二次关系的初始化， 例如多组数据输入时每组都 `memset` 整个数组就可能超时)。 ## 关于构造函数的补充说明 对于一些评测系统和题目， 我们发现在代码中添加构造函数会导致运行时间数据变得非常难看。 例如： ```c++ struct node { int u, v; #if defined(HAVE_CONSTRUCTOR) && HAVE_CONSTRUCTOR node(): u(0), v(0) {} #endif }; node arr[500000000]; int main() {} ``` 我们不加 `-DHAVE_CONSTRUCTOR=1` 编译，得到的程序几乎不消耗时间。 而加了 `-DHAVE_CONSTRUCTOR=1` 后，得到的程序会消耗内核态时间 $0.24$ 秒， 用户态时间 $0.13$ 秒[^1]。这说明，在前一种情况下，初始化仍然是按照 BSS 段的机制进行的，只要我们不使用数组，就不会真的进行初始化。而在后一种情况下， 编译器直接生成了初始化整个数组的代码。 [^1]: 在编写补充说明之前，测试环境的内存升级为了 DDR4 3200 MHz， 故结果与之前的测量结果没有可比性。 对于一些 OI 题目来说，这种行为会导致总的运行时间显著增加。例如， 如果某题目规定对于 $100\\%$ 的数据有 $1 \leq n \leq 10^6$， 而对于 $50\\%$ 的数据有 $1 \leq n \leq 1000$，那么加了构造函数后， 即使对于 $n$ 较小的数据，程序在启动时也会初始化 $10^6$ 个元素。 而不加构造函数的程序实际上只会初始化 $1000$ 个元素。 洛谷等评测系统会将多组数据的运行时间叠加起来，作为总运行时间， 这就会产生可观的差距。 对此一种解决方法是使用 `= default` 显式指定默认构造函数，例如： ```c++ struct node { int u, v; node() = default; // default constructor node(int a, int b = 0) : u(a), v(b) {} // nontrivial constructor }; node arr[500000000]; int main() { node n(1, 2); } ``` 这里我们使用构造函数的目的是方便构造非 $0$ 的元素。 然而如果我们只定义上面的 `nontrivial constructor`， 则编译器会拒绝自动生成默认构造函数，导致无法声明数组。 如果我们手写一个构造函数，就会像前面讨论的一样，引入额外的初始化。 而使用 `node() = default;` 这样的默认构造函数就能解决这一问题。 但是需要注意的是，默认构造函数的行为与构造一个传统的 C 结构体是完全一致的， 它甚至不会初始化该类型局部变量的各字段 (除非该字段的类型本身有构造函数)。 例如： ```c++ int main() { node n; return n.u; } ``` 如果 `node` 使用了 `default` 默认构造函数，该程序的行为是未定义的。