环境

• Ubuntu 22.04
• gcc 11.4.0
• Window 11
• Microsoft Visual Studio Community 2022 (64-bit) - Current Version 17.6.2

运行速度

一个C程序 test1.c 如下：

int array[30000][30000];

int main() {
	for (int i = 0; i < 30000; i++)
		for (int j = 0; j < 30000; j++) {
			array[i][j] = 12345;
		}

	return 0;
}

编译：

gcc test1.c -o test1

运行并查看运行时间：

time ./test1
./test1  1.28s user 1.75s system 99% cpu 3.035 total

用时1.28秒。

修改一下代码，把循环里i和j的顺序交换一下：

int array[30000][30000];

int main() {
	for (int j = 0; j < 30000; j++)
		for (int i = 0; i < 30000; i++) {
			array[i][j] = 12345;
		}

	return 0;
}

运行结果如下：

time ./test2        
./test2  15.92s user 1.59s system 99% cpu 17.533 total

可见，运行时间从原先的1.28秒暴涨到15.92秒。

其实，我们能猜到，引起性能下降的原因，一定与数组在内存中的存储方式有关。

以二维数组为例：在C语言中，是按“先列后行”来存储的，也就是按 arr[0][0] ， arr[0][1] ， arr[0][2] ，……，arr[1][0] ， arr[1][1] ， arr[1][2] ，……这样的顺序连续存储的。

写一个程序来检验如下：

#include <stdio.h>

int arr[3][3];

int main() {
	printf("size of int = %ld\n\n", sizeof(int));

	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++) {
			printf("arr[%d][%d] address: %p\n", i, j, &arr[i][j]);
		}

	return 0;
}

运行结果如下：

size of int = 4

arr[0][0] address: 0x5585c16fb040
arr[0][1] address: 0x5585c16fb044
arr[0][2] address: 0x5585c16fb048
arr[1][0] address: 0x5585c16fb04c
arr[1][1] address: 0x5585c16fb050
arr[1][2] address: 0x5585c16fb054
arr[2][0] address: 0x5585c16fb058
arr[2][1] address: 0x5585c16fb05c
arr[2][2] address: 0x5585c16fb060

可见，int 类型的size是4，而数组中每两个相邻元素，其地址编码相差也是4。

计算机访问连续内存地址的速度，要远远快于非连续地址。这也是数组要比链表访问速度更快的原因。

注：Java程序也类似。

文件大小

全局变量

再来看一下 test1.c ：

int array[30000][30000];

int main() {
	for (int i = 0; i < 30000; i++)
		for (int j = 0; j < 30000; j++) {
			array[i][j] = 12345;
		}

	return 0;
}

经过编译后，生成的 test1 文件大小为16KB。

ll test1*
-rwxr-xr-x 1 root root 16K 11月 19 19:07 test1
-rw-r--r-- 1 root root 150 11月 19 18:51 test1.c

如果把数组大小改变，编译后的文件大小不变。

这是为什么呢？按理说，array是一个全局变量，是在编译期静态的生成的，应该会占据可执行文件的空间，但这里却似乎并没有影响。

我猜测是因为编译器做了一些优化。虽然声明了全局数组，但是没有赋初值，所以编译器并没有为数组分配空间。

如果有赋初值，则编译后的文件就会随着数组大小而显著变化。

创建文件 test11.c 如下：

int array[300][300] = {123};

int main() {
}

编译后，生成的文件大小为368KB：

ll test11*
-rwxr-xr-x 1 root root 368K 11月 19 20:06 test11
-rw-r--r-- 1 root root   45 11月 19 20:06 test11.c

创建文件 test12.c 如下：

int array[3000][3000] = {123};

int main() {
}

编译后，生成的文件大小为35MB：

ll test12*
-rwxr-xr-x 1 root root 35M 11月 19 20:08 test12
-rw-r--r-- 1 root root  47 11月 19 20:07 test12.c

可见，数组大小扩大100倍，文件大小也扩大了100倍。

局部变量

对于局部变量，是运行期（调用对应函数时）在栈上分配内存的，所以数组大小并不会影响文件大小：

int main() {
	int array[30000][30000] = {123};
}

这里不管数组大小如何变化，编译后生成的可执行文件都是16KB。

未初始化数组的内容

另一个好玩的问题是，如果定义了数组，但没有初始化，那么数组的内容是什么？

全局变量

对于全局变量，其内容会被自动初始化为0。

#include <stdio.h>

int array[300][300];

int main() {
	printf("%d\n", array[5][5]);
}

运行结果如下：

0

这应该是在load可执行文件时，将其内存初始化。

局部变量

#include <stdio.h>

int main() {
	int array[300][300];
	printf("%d\n", array[5][5]);
}

运行结果如下：

0

可见，局部变量的内存也被初始化为0（在调用对应函数，在栈上分配内存时）。

但这不是100%确定的。在MicroSoft Visual Studio下，其运行结果为：

-858993460

总而言之，变量最好先初始化，再使用。