3.8.5 变长数组

历史上，C 语言只支持大小在编译时就能确定的多维数组（对第一维可能有些例外）。程序员需要变长数组时不得不用 malloc 或 calloc 这样的函数为这些数组分配存储空间，而且不得不显式地编码，用行优先索引将多维数组映射到一维数组，如公式（3.1）所示。ISO C99 引入了一种功能，允许数组的维度是表达式，在数组被分配的时候才计算出来。

在变长数组的 C 版本中，我们可以将一个数组声明如下：

int A[expr1][expr2]

它可以作为一个局部变量，也可以作为一个函数的参数，然后在遇到这个声明的时候，通过对表达式 expr1 和 expr2 求值来确定数组的维度。因此，例如要访问 n × n 数组的元素 i，j，我们可以写一个如下的函数：

int var_ele(long n, int A[n][n], long i, long j) {
    return A[i][j];
}

参数 n 必须在参数 A[n][n] 之前，这样函数就可以在遇到这个数组的时候计算出数组的维度。GCC 为这个引用函数产生的代码如下所示：

int var_ele(long n, int A[n][n], long i, long j)
n in %rdi, A in %rsi, i in %rdx, j in %rcx

1  var_ele:
2      imulq %rdx, %rdi           Compute n · i
3      leaq (%rsi,%rdi,4), %rax   Compute x_A + 4(n · i)
4      movl (%rax,%rcx,4), %eax   Read from M[x_A + 4(n · i) + 4j]
5      ret

正如注释所示，这段代码计算元素 i，j 的地址为 x_A + 4(n · i) + 4j = x_A + 4(n · i + j)。这个地址的计算类似于定长数组的地址计算（参见 3.8.3 节），不同点在于 1）由于增加了参数 n，寄存器的使用变化了；2）用了乘法指令来计算 n · i（第 2 行），而不是用 leaq 指令来计算 3i。因此引用变长数组只需要对定长数组做一点儿概括。动态的版本必须用乘法指令对 i 伸缩 n 倍，而不能用一系列的移位和加法。在一些处理器中，乘法会招致严重的性能处罚，但是在这种情况中无可避免。

在一个循环中引用变长数组时，编译器常常可以利用访问模式的规律性来优化索引的计算。例如，图 3-38a 给出的 C 代码，它计算两个 n × n 矩阵 A 和 B 乘积的元素 i，k。GCC 产生的汇编代码，我们再重新变为 C 代码（图 3-38b）。这个代码与固定大小数组的优化代码（图 3-37）风格不同，不过这更多的是编译器选择的结果，而不是两个函数有什么根本的不同造成的。图 3-38b 的代码保留了循环变量 j，用以判定循环是否结束和作为到 A 的行 i 的元素组成的数组的索引。

/* Compute i,k of variable matrix product */
int var_prod_ele(long n, int A[n][n], int B[n][n], long i, long k) {
    long j;
    int result = 0;

    for (j = 0; j < n; j++)
        result += A[i][j] * B[j][k];

    return result;
}

a）原始的 C 代码

/* Compute i,k of variable matrix product */
int var_prod_ele_opt(long n, int A[n][n], int B[n][n], long i, long k) {
    int *Arow = A[i];
    int *Bptr = &B[0][k];
    int result = 0;
    long j;
    for (j = 0; j < n; j++) {
        result += Arow[j] * *Bptr;
        Bptr += n;
    }
    return result;
}

b）优化后的 C 代码

图 3-38　计算变长数组的矩阵乘积的元素 i，k 的原始代码和优化后的代码。编译器自动执行这些优化

下面是 var_prod_ele 的循环的汇编代码：

Registers: n in %rdi, Arow in %rsi, Bptr in %rcx
           4n in %r9, result in %eax, j in %edx

1  .L24:                          loop:
2      movl (%rsi,%rdx,4), %r8d  Read Arow[j]
3      imull (%rcx), %r8d        Multiply by *Bptr
4      addl %r8d, %eax           Add to result
5      addq $1, %rdx             j++
6      addq %r9, %rcx            Bptr += n
7      cmpq %rdi, %rdx           Compare j:n
8      jne .L24                  If !=, goto loop

我们看到程序既使用了伸缩过的值 4n（寄存器 %r9）来增加 Bptr，也使用了 n 的值（寄存器 %rdi）来检查循环的边界。C 代码中并没有体现出需要这两个值，但是由于指针运算的伸缩，才使用了这两个值。

可以看到，如果允许使用优化，GCC 能够识别出程序访问多维数组的元素的步长。然后生成的代码会避免直接应用等式（3.1）会导致的乘法。不论生成基于指针的代码（图 3-37b）还是基于数组的代码（图 3-38b），这些优化都能显著提高程序的性能。