C语言 VLA有什么意义?

9gm1akwq  于 2023-10-16  发布在  其他
关注(0)|答案(6)|浏览(203)

我理解什么是可变长度数组以及它们是如何实现的。这个问题是关于它们为什么存在。
我们知道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(强调地雷):

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

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

换句话说,程序员必须确保0 < n <= N用于某些N选择。然而,程序应该对n == N起作用,所以最好用常量大小N而不是变量长度n来声明数组。
我知道引入VLA是为了取代alloca(在this answer中也提到了),但实际上它们是一样的(在堆栈上分配可变大小的内存)。
所以问题是为什么alloca和VLA存在,为什么它们没有被弃用?在我看来,使用VLA的唯一安全方法是使用有界大小,在这种情况下,使用具有最大大小的普通数组始终是可行的解决方案。

s6fujrry

s6fujrry1#

由于我不完全清楚的原因,几乎每次在讨论中出现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` */

X1 m0n1x型的尺寸相关特性(例如,n的值)在控制通过上述typedef声明的确切时刻被最终化。n的值的任何更改都不会影响A的大小。停下来想想这意味着什么。这意味着该实现应该将A与一个隐藏的内部变量相关联,该变量将存储数组类型的大小。这个隐藏的内部变量是在运行时,当控件传递到A的声明时,从n初始化的。
这给了上面的typedef声明一个非常有趣和不寻常的属性,这是我们以前从未见过的:这个typedef声明生成可执行代码(!此外,它不仅生成可执行代码,还生成 * 至关重要 * 的可执行代码。如果我们忘记了初始化与这样的typedef声明相关的内部变量,我们最终会得到一个“坏掉的”/未初始化的typedef别名。这种内部代码的重要性是语言对这种声明施加一些不寻常限制的原因:该语言禁止从其作用域外部将控制传递到其作用域中

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

typedef int A[n];

skip:;

再次注意,上面的代码没有定义任何VLA数组。它只是声明了一个看似无辜的别名,用于 * 已修改类型 *。然而,跳过这种类型定义声明是非法的。(我们已经熟悉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,其中需要一个“经典”数组,反之亦然。当然,编译器不能控制这种调用中的类型兼容性(因为至少有一个涉及的类型是运行时大小的)。但是,如果需要,编译器(或用户)拥有在调试版本的代码中执行运行时检查所需的一切。

(Note通常,数组类型的参数总是隐式地 * 调整 * 为指针类型的参数。这适用于VLA参数声明,就像它适用于“经典”数组参数声明一样。这意味着在上面的示例中,参数a实际上具有类型int (*)[m][k]。此类型不受n值的影响。我故意向数组添加了一些额外的维度,以保持它对运行时值的依赖性。)
VLA和“经典”数组作为函数参数之间的兼容性也得到了以下事实的支持,即编译器不必为一个 * 已修改 * 参数附带任何关于其大小的额外隐藏信息。相反,语言语法迫使用户公开传递这些额外的信息。在上面的示例中,用户被迫首先将参数nmk包含到函数参数列表中。如果不先声明nmk,用户将无法声明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中迫切需要这些属性来取代以前在其位置上使用的丑陋黑客的主要原因。然而,与此同时,在上述程序中,甚至没有在本地内存中创建一个VLA,这意味着这种流行的VLA批评向量根本不适用于此代码。
基本上,上面的最后两个例子是对VLA支持点的简要说明。

vm0i2vca

vm0i2vca2#

看看注解和答案,在我看来,当你知道通常你的输入不是太大(类似于知道你的递归可能不是太深),但你实际上没有上限时,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;
}
r6l8ljro

r6l8ljro3#

尽管你提到了关于VLA的所有观点,VLA最好的部分是编译器自动处理存储管理和边界不是编译时常数的数组的索引计算的复杂性。
如果你想要本地动态内存分配,那么唯一的选择就是VLA。
我认为这可能是C99采用VLA的原因(C11可选)。
有一件事我想明确的是 * 有一些显着的差异alloca和VLA*。This post指出了这些差异:

  • 只要当前函数持续存在,alloca()返回的内存就有效。只要VLA的标识符仍在作用域中,VLA占用的内存的生存期就是有效的。
  • 例如,您可以在循环中alloca()内存,并在循环外使用内存,VLA将消失,因为当循环终止时,标识符将超出范围。
igetnqfo

igetnqfo4#

您的论点似乎是,既然必须对VLA的大小进行绑定检查,为什么不分配最大大小并完成运行时分配呢?
这种说法忽略了一个事实,即内存是系统中的有限资源,在许多进程之间共享。在一个进程中浪费地分配的内存对任何其他进程都不可用(或者可能是,但代价是交换到磁盘)。
通过同样的参数,当我们可以静态分配可能需要的最大大小时,我们不需要在运行时malloc数组。最后,堆耗尽只是稍微优于堆栈溢出。

xzlaal3s

xzlaal3s5#

VLA不必分配任何内存或仅分配堆栈内存。它们在编程的许多方面都非常方便。
一些示例
1.用作函数参数。

int foo(size_t cols, int (*array)[cols])
{
    //access as normal 2D array
    prinf("%d", array[5][6]);
    /* ... */
}

1.动态分配2D(或更多)阵列

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]);
    /* ... */
ar5n3qh5

ar5n3qh56#

堆栈分配(一个如此VLA分配)是非常快的,只需要快速修改堆栈指针(通常是一个单一的CPU指令)。不需要昂贵的堆分配/释放。
但是,为什么不使用一个常量大小的数组呢?
假设你正在编写一个高性能的代码,你需要一个可变大小的缓冲区,比如说8到512个元素。你可以只声明一个512个元素的数组,但是如果大多数时候你只需要8个元素,那么过度分配会影响性能,因为它会影响堆栈内存中的该高速缓存位置。现在想象一下这个函数必须被调用数百万次。
另一个例子,假设你的函数(带有一个局部VLA)是递归的,你事先知道在任何时候所有递归分配的VLA的总大小都是有限的(即数组具有可变大小,但所有大小的和是有界的)。在这种情况下,如果你使用最大可能的大小作为固定的本地数组大小,你可能会分配比其他情况下所需的更多的内存,使你的代码变慢(由于缓存未命中),甚至导致堆栈溢出。

相关问题