+++
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<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` 整个数组就可能超时)。

## 关于构造函数的补充说明

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

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