32

我了解什么是可变长度数组以及它们是如何实现的。这个问题是关于它们为什么存在的。

我们知道 VLA 只允许在功能块(或原型)内使用,并且它们基本上不能在堆栈上的任何地方(假设正常实现):C11,6.7.6.2-2:

如果一个标识符被声明为具有可变修改类型,它应该是一个普通标识符(如 6.2.3 中定义的),没有链接,并且具有块范围或函数原型范围。如果标识符被声明为具有静态或线程存储持续时间的对象,则它不应具有可变长度数组类型。

让我们举一个小例子:

void f(int n)
{
    int array[n];
    /* etc */
}

有两种情况需要注意:

  • n <= 0f必须注意这一点,否则行为未定义:C11,6.7.6.2-5(强调我的):

    如果 size 是一个不是整数常量表达式的表达式:如果它出现在函数原型范围的声明中,则将其视为被替换为*; 否则, 每次对其进行评估时,它的值都应大于零。可变长度数组类型的每个实例的大小在其生命周期内不会改变。如果大小表达式是运算sizeof符操作数的一部分,并且更改大小表达式的值不会影响运算符的结果,则未指定是否计算大小表达式。

  • n > stack_space_left / element_size: 没有标准的方法来查找剩余的堆栈空间(因为只要涉及标准,就没有堆栈这样的东西)。所以这个测试是不可能的。唯一明智的解决方案是为 预定义最大可能大小n,例如N,以确保不会发生堆栈溢出。

换句话说,程序员必须确定0 < n <= N一些N选择。但是,该程序n == N无论如何都应该可以工作,因此不妨将数组声明为 constant sizeN而不是 variable length n

我知道引入 VLA 是为了替换alloca(如本答案中所述),但实际上它们是同一件事(在堆栈上分配可变大小的内存)。

所以问题是为什么allocaVLA 存在并因此存在,为什么它们没有被弃用?在我看来,使用 VLA 的唯一安全方法是使用有界大小,在这种情况下,采用最大大小的普通数组始终是一个可行的解决方案。

4

6 回答 6

71

由于我不完全清楚的原因,几乎每次在讨论中出现 C99 VLA 的话题时,人们开始主要讨论将运行时大小的数组声明为本地对象的可能性(即在堆栈上创建它们) ”)。这是相当令人惊讶和误导的,因为 VLA 功能的这一方面 - 支持本地数组声明 - 恰好是 VLA 提供的一种相当辅助的次要功能。它在 VLA 可以做的事情中并没有真正发挥任何重要作用。大多数时候,地方 VLA 声明及其伴随的潜在陷阱的问题被 VLA 批评者强行放到了前台,他们将其用作“稻草人”,旨在破坏讨论并将其陷入几乎不相关的细节中。

C 中 VLA 支持的本质首先是对语言类型概念的革命性定性扩展。它涉及引入诸如可变修改类型之类的全新类型。实际上,与 VLA 相关的每个重要实现细节实际上都附加到它的类型上,而不是附加到 VLA 对象本身。正是在语言中引入了可变修改的类型,这构成了众所周知的 VLA 蛋糕的大部分,而在本地内存中声明此类类型的对象的能力只不过是在蛋糕上的一个微不足道且相当无关紧要的糖霜。

考虑一下:每次在自己的代码中声明这样的内容

/* Block scope */
int n = 10;
...
typedef int A[n];
...
n = 5; /* <- Does not affect `A` */

可变修改类型的大小相关特征A(例如 的值n)在控制通过上述 typedef 声明的确切时刻最终确定。对 的值进行的任何更改n(在此声明的下方A)都不会影响A. 停下来想一想这意味着什么。这意味着该实现应该与A一个隐藏的内部变量相关联,该变量将存储数组类型的大小。这个隐藏的内部变量是n在运行时在控件传递A.

这给了上面的 typedef-declaration 一个相当有趣和不寻常的属性,这是我们以前从未见过的:这个 typedef-declaration 生成可执行代码(!)。此外,它不仅会生成可执行代码,还会生成至关重要的可执行代码。如果我们不知何故忘记初始化与这种 typedef 声明相关的内部变量,我们将得到一个“损坏”/未初始化的 typedef 别名。该内部代码的重要性是该语言对此类可变修改的声明施加一些不寻常限制的原因:该语言禁止将控制权从其范围之外传递到其范围内

/* Block scope */
int n = 10;
goto skip; /* Error: invalid goto */

typedef int A[n];

skip:;

再次注意,上面的代码没有定义任何 VLA 数组。它只是为可变修改的类型声明了一个看似无辜的别名。然而,跳过这样的 typedef 声明是非法的。(我们已经熟悉 C++ 中这种与跳转相关的限制,尽管在其他上下文中)。

typedef需要运行时初始化的代码生成与“经典”语言中的typedef内容有很大不同。typedef(它也恰好对在 C++ 中采用 VLA 的方式构成了重大障碍。)

当声明一个实际的 VLA 对象时,除了分配实际的数组内存之外,编译器还会创建一个或多个隐藏的内部变量,这些变量保存所讨论的数组的大小。人们必须明白,这些隐藏变量与数组本身无关,而是与它的可变修改类型相关联。

这种方法的一个重要且显着的结果如下:与 VLA 相关的有关数组大小的附加信息并未直接构建到 VLA 的对象表示中。它实际上存储在数组之外,作为“sidecar”数据。这意味着(可能是多维的)VLA 的对象表示与具有相同维度和相同大小的普通经典编译时大小数组的对象表示完全兼容。例如

void foo(unsigned n, unsigned m, unsigned k, int a[n][m][k]) {}
void bar(int a[5][5][5]) {}

int main(void)
{
  unsigned n = 5;
  int vla_a[n][n][n];
  bar(a);

  int classic_a[5][6][7];
  foo(5, 6, 7, classic_a); 
}

上述代码中的两个函数调用都是完全有效的,并且它们的行为完全由语言定义,尽管我们传递了一个 VLA,其中需要一个“经典”数组,反之亦然。当然,编译器无法控制此类调用中的类型兼容性(因为至少有一种涉及的类型是运行时大小的)。但是,如果需要,编译器(或用户)拥有在调试版本的代码中执行运行时检查所需的一切。

(注意:像往常一样,数组类型的参数总是隐式调整为指针类型的参数。这适用于 VLA 参数声明,就像它适用于“经典”数组参数声明一样。这意味着在上面的示例中,参数a实际上具有 type int (*)[m][k]。这种类型不受 值的影响n。我特意为数组添加了一些额外的维度,以保持它对运行时值的依赖。)

VLA 和“经典”数组作为函数参数之间的兼容性也得到了以下事实的支持:编译器不必为可变修改的参数附带任何关于其大小的附加隐藏信息。相反,语言语法强制用户公开传递这些额外信息。在上面的例子中,用户被迫首先包含参数nm然后k进入函数参数列表。如果不声明n,首先mk用户将无法声明a(另请参阅上面关于 的注释n)。这些由用户显式传递给函数的参数将带来有关a.

再举一个例子,通过利用 VLA 支持,我们可以编写以下代码

#include <stdio.h>
#include <stdlib.h>

void init(unsigned n, unsigned m, int a[n][m])
{
  for (unsigned i = 0; i < n; ++i)
    for (unsigned j = 0; j < m; ++j)
      a[i][j] = rand() % 100;
}

void display(unsigned n, unsigned m, int a[n][m])
{
  for (unsigned i = 0; i < n; ++i)
    for (unsigned j = 0; j < m; ++j)
      printf("%2d%s", a[i][j], j + 1 < m ? " " : "\n");
  printf("\n");
}

int main(void) 
{
  int a1[5][5] = { 42 }; 
  display(5, 5, a1);
  init(5, 5, a1);
  display(5, 5, a1);

  unsigned n = rand() % 10 + 5, m = rand() % 10 + 5;
  int (*a2)[n][m] = malloc(sizeof *a2);
  init(n, m, *a2);
  display(n, m, *a2);
  free(a2);
}

这段代码旨在提醒您注意以下事实:这段代码大量使用了可变修改类型的有价值的属性。没有 VLA 就不可能优雅地实现。这就是为什么在 C 中迫切需要这些属性来替换以前在它们的位置使用的丑陋的 hack 的主要原因。然而同时,在上述程序中,甚至没有在本地内存中创建一个 VLA,这意味着这种流行的 VLA 批评向量根本不适用于这段代码。

基本上,上面最后两个示例是对 VLA 支持意义的简明说明。

于 2019-01-12T20:09:19.923 回答
21

查看评论和答案,在我看来,当您知道通常您的输入不太大(类似于知道您的递归可能不太深)时,VLA 很有用,但实际上您并没有上限,并且您通常会忽略可能的堆栈溢出(类似于通过递归忽略它们),希望它们不会发生。

它实际上也可能完全不是问题,例如,如果您有无限的堆栈大小。

也就是说,这是我发现它们的另一个用途,它实际上并没有在堆栈上分配内存,而是使使用动态多维数组更容易。我将通过一个简单的例子来演示:

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    size_t n, m;

    scanf("%zu %zu", &n, &m);

    int (*array)[n][m] = malloc(sizeof *array);

    for (size_t i = 0; i < n; ++i)
        for (size_t j = 0; j < m; ++j)
            (*array)[i][j] = i + j;

    free(array);
    return 0;
}
于 2015-01-19T10:32:56.053 回答
12

尽管您提到了有关 VLA 的所有要点,但 VLA 最好的部分是编译器自动处理边界不是编译时常量的数组的存储管理和索引计算的复杂性。
如果您想要本地动态内存分配,那么唯一的选择是 VLA。

我认为这可能是 C99 采用 VLA 的原因(C11 可选)。


我想澄清的一件事是和 VLA之间存在一些显着差异alloca这篇文章指出了不同之处:

  • alloca()只要当前函数存在,内存返回就有效。只要 VLA 的标识符仍在范围内,VLA 占用的内存的生命周期就有效。
  • 例如,您可以alloca()在循环中存储并在循环外使用内存,VLA 将消失,因为当循环终止时标识符超出范围。
于 2014-03-20T10:50:01.433 回答
8

您的论点似乎是,既然必须绑定检查 VLA 的大小,为什么不只分配最大大小并完成运行时分配。

该论点忽略了这样一个事实,即内存是系统中的有限资源,在许多进程之间共享。在一个进程中浪费分配的内存对任何其他进程都不可用(或者可能是,但以交换到磁盘为代价)。

通过同样的论点,当我们可以静态分配可能需要的最大大小时,我们不需要在运行时 malloc 数组。最后,堆耗尽仅比堆栈溢出略好。

于 2014-03-20T11:13:01.640 回答
2

VLA 不必分配任何内存或仅分配堆栈内存。它们在编程的许多方面都非常方便。

一些例子

  1. 用作函数参数。
int foo(size_t cols, int (*array)[cols])
{
    //access as normal 2D array
    prinf("%d", array[5][6]);
    /* ... */
}
  1. 动态分配二维(或更多)数组
inr foo(size_t rows, size_t cols)
{
    int (*array)[cols] = malloc(rows * sizeof(*array));
    /* ... */
    //access as normal 2D array
    prinf("%d", array[5][6]);
    /* ... */
于 2022-01-07T20:16:24.120 回答
1

堆栈分配(VLA 分配)非常快,只需要快速修改堆栈指针(通常是单个 CPU 指令)。不需要昂贵的堆分配/释放。

但是,为什么不直接使用一个固定大小的数组呢?

假设您正在编写一个高性能代码,并且您需要一个可变大小的缓冲区,比如说 8 到 512 个元素。您可以只声明一个 512 个元素的数组,但如果大多数时候您只需要 8 个元素,那么由于影响堆栈内存中的缓存位置,过度分配会影响性能。现在想象这个函数必须被调用数百万次。

另一个例子,假设你的函数(使用本地 VLA)是递归的,你事先知道在任何时候所有递归分配的 VLA 的总大小都是有限的(即数组具有可变大小,但所有大小的总和是有界的)。在这种情况下,如果您使用最大可能大小作为固定的本地数组大小,您可能会分配比其他所需更多的内存,从而使您的代码变慢(由于缓存未命中),甚至导致堆栈溢出。

于 2021-01-05T03:17:15.367 回答