+++ 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 优化开关编译程序。

“自动”初始化

根据标准 (第 6.6.2 节) 规定，具有静态存储期的无构造函数对象会被默认初始化为 0。换句话说，如果我们想要把某个数组初始化为 0，只要在全局声明它即可。例如：

int arr[1000000000] = {0};

int main()
{
	return 0;
}

这里放一个 = {0} 是为了增强可读性，不写也是可以的。如果我们编译并执行上述程序，进行计时，会发现它几乎没有消耗 CPU 时间。于是有些同志就可能认为“自动初始化是不消耗时间的”，然而这是假象，这就像是说天上会掉馅饼。我们使用一下这些内存：

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$ 为步长访问数组：

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 循环是完全等价的。

然而这个结果其实有优化的余地。首先我们进行循环展开，即在一次循环中初始化不只一个数组元素，以减少需要执行的指令条数：

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 优化成向量移动指令：

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 的初始化：

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 分配一个数组，并且初始化它：

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 代替数组：

int main()
{
	vector<int> 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 整个数组就可能超时)。

关于构造函数的补充说明

对于一些评测系统和题目，我们发现在代码中添加构造函数会导致运行时间数据变得非常难看。例如：

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 显式指定默认构造函数，例如：

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 结构体是完全一致的，它甚至不会初始化该类型局部变量的各字段 (除非该字段的类型本身有构造函数)。例如：

int main()
{
	node n;
	return n.u;
}

如果 node 使用了 default 默认构造函数，该程序的行为是未定义的。

init-array-benchmark.md 13 KB History Raw