初始化数组的不同方法及其运行时间

众所周知，在程序设计竞赛中我们往往要初始化数组。初始化数组有很多不同的写法， 那么它们哪种更快呢？我们将进行一些计时测试，比较和分析它们的运行时间。

测试环境

如无特殊说明，测试中使用 -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$ 秒¹。这说明，在前一种情况下，初始化仍然是按照 BSS 段的机制进行的，只要我们不使用数组，就不会真的进行初始化。而在后一种情况下， 编译器直接生成了初始化整个数组的代码。

对于一些 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 默认构造函数，该程序的行为是未定义的。