В чем вообще смысл VLA?

По не совсем понятным мне причинам почти каждый раз, когда в обсуждении всплывает тема C99 VLA, люди начинают говорить преимущественно о возможности объявления массивов run-time size локальными объектами (т.е. создания их «на стеке "). Это довольно удивительно и вводит в заблуждение, поскольку этот аспект функциональности VLA — поддержка объявлений локальных массивов — оказывается скорее вспомогательной, вторичной возможностью, предоставляемой VLA. На самом деле это не играет существенной роли в том, что может сделать VLA. В большинстве случаев вопрос о местных декларациях VLA и сопутствующих им потенциальных ловушках выдвигается на передний план критиками VLA, которые используют его как «соломенное чучело», предназначенное для того, чтобы сорвать дискуссию и увязнуть в маловажных деталях.

Суть поддержки VLA в C заключается, прежде всего, в революционном качественном расширении языковой концепции type. Он предполагает введение таких принципиально новых видов типов, как вариабельно изменяемые типы. Практически каждая важная деталь реализации, связанная с 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 довольно интересное и необычное свойство, чего мы раньше не видели: это объявление typedef генерирует исполняемый код (!). Более того, он генерирует не просто исполняемый код, а критически важный исполняемый код. Если мы каким-то образом забудем инициализировать внутреннюю переменную, связанную с таким объявлением typedef, мы получим «сломанный»/неинициализированный псевдоним typedef. Важность этого внутреннего кода является причиной того, что язык накладывает некоторые необычные ограничения на такие вариабельно изменяемые объявления: язык запрещает передачу управления в их область видимости из-за пределов их области видимости.

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

typedef int A[n];

skip:;

Еще раз обратите внимание, что приведенный выше код не определяет никаких массивов VLA. Он просто объявляет, казалось бы, невинный псевдоним для вариабельно изменяемого типа. Тем не менее, недопустимо перепрыгивать через такое объявление typedef. (Мы уже знакомы с такими ограничениями, связанными с переходом, в C++, хотя и в других контекстах).

Генерирующий код typedef, typedef, требующий инициализации во время выполнения, является значительным отклонением от того, что typedef есть в "классическом" языке. (Это также представляет собой серьезное препятствие на пути внедрения VLA в C++.)

Когда кто-то объявляет фактический объект 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 на самом деле имеет тип int (*)[m][k]. На этот тип не влияет значение n. Я намеренно добавил в массив несколько дополнительных измерений, чтобы сохранить его зависимость от значений времени выполнения.)

Совместимость между VLA и "классическими" массивами как параметрами функций также поддерживается тем фактом, что компилятору не нужно сопровождать вариабельно изменяемый параметр какой-либо дополнительной скрытой информацией о его размере. Вместо этого синтаксис языка заставляет пользователя передавать эту дополнительную информацию в открытом виде. В приведенном выше примере пользователь был вынужден сначала включить параметры n, m и k в список параметров функции. Без объявления n, m и k пользователь не смог бы объявить 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.

Глядя на комментарии и ответы, мне кажется, что 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;
}

Несмотря на все замечания, которые вы упомянули о VLA, лучшая часть VLA заключается в том, что компилятор автоматически обрабатывает управление хранилищем и сложности вычислений индексов массивов, границы которых не являются константами времени компиляции.
Если вам нужна локальная динамическая память распределение, то единственным вариантом является VLA.

Я думаю, что это может быть причиной того, что VLA принят в C99 (необязательно на C11).

Я хочу прояснить одну вещь: существуют существенные различия между alloca и VLA. Это сообщение указывает на различия:

• Память, возвращаемая alloca(), действительна до тех пор, пока сохраняется текущая функция. Срок жизни памяти, занимаемой VLA, действителен до тех пор, пока идентификатор VLA остается в области действия.
• Например, вы можете alloca() памяти в цикле и использовать память вне цикла, VLA исчезнет, ​​потому что идентификатор выходит за пределы области действия, когда цикл завершается.

Ваш аргумент, по-видимому, заключается в том, что, поскольку необходимо проверить размер VLA, почему бы просто не выделить максимальный размер и не выполнить выделение во время выполнения.

Этот аргумент упускает из виду тот факт, что память является ограниченным ресурсом в системе, разделяемым между многими процессами. Память, расточительно выделенная в одном процессе, недоступна никакому другому (а может и есть, но за счет свопинга на диск).

По тому же аргументу нам не нужно было бы выделять массив во время выполнения, когда мы могли бы статически выделить максимальный размер, который может потребоваться. В конце концов, исчерпание кучи лишь немногим предпочтительнее, чем переполнение стека.

Распределение стека (таким образом, выделение VLA) выполняется ОЧЕНЬ быстро, просто требуется быстрая модификация указателя стека (обычно это одна инструкция ЦП). Нет необходимости в дорогостоящем выделении/освобождении кучи.

Но почему бы просто не использовать вместо этого массив постоянного размера?

Предположим, вы пишете высокопроизводительный код и вам нужен буфер переменного размера, скажем, от 8 до 512 элементов. Вы можете просто объявить массив из 512 элементов, но если в большинстве случаев вам требуется только 8 элементов, то перераспределение может повлиять на производительность из-за влияния на расположение кеша в памяти стека. Теперь представьте, что эту функцию нужно вызывать миллионы раз.

Другой пример: представьте, что ваша функция (с локальным VLA) является рекурсивной, вы заранее знаете, что в любой момент общий размер всех рекурсивно выделенных VLA ограничен (т.е. массивы имеют переменный размер, но сумма всех размеров ограничена). В этом случае, если вы используете максимально возможный размер в качестве фиксированного размера локального массива, вы можете выделить гораздо больше памяти, чем требуется в противном случае, что сделает ваш код медленнее (из-за промахов кеша) и даже вызовет переполнение стека.