Как работает VLA?

#cpp #c

int N;
...
int arr[N];


В чем особенность данной реализации (C99)?

Почему в С++ (хотя g++, clang поддерживает) это не работает?
    

Ответы

Ответ 1

По какой-то непонятной причине, когда заходит речь о VLA, не передний план чаще всего
выходят рассуждения о возможности создания массивов заранее неизвестного размера в
локальной памяти, т.е. в стеке. Это вызывает недоумение, ибо на самое деле возможность
локального объявления таких массивов - это совершенно побочное и второстепенное свойство
VLA, никакой существенной роли в функциональности VLA не играющее. Как правило, выпячивание
этой возможности и кроющихся за ней подводных камней делается слепыми критиками VLA
с целью увести обсуждение от сути вопроса.

А суть вопроса заключается в том, что поддержка VLA - это в первую и главную очередь
мощное расширение системы типизации языка. Это введение в язык С такой фундаментально
новой концептуальной группы типов, как variably modified types (для целей данного изложения
переведу как "вариабельные типы"). Все наиболее важные внутренние реализационные детали
VLA привязаны именно к его типу, а не к самому объекту как таковому. Именно введение
в язык вариабельных типов является пресловутым айсбергом VLA, а возможность создавать
объекты таких типов в локальной памяти - это не более чем незначительная (и необязательная)
верхушка этого айсберга.  

Например, всякий раз, когда в программе объявляется тип

/* Внутри блока */
int n = 10;
...
typedef int A[n];


характеристики этого вариабельного типа - значение n - фиксируется в тот момент,
когда управление проходит по данному typedef-объявлению. Изменение значения n после
объявления псевдонима A уже не повлияет на характеристики типа A. С точки зрения реализации
это означает, что с вариабельным типом A будут ассоциирована скрытая внутренняя переменная,
описывающая размер массива. Эта скрытая переменная инициализируется в момент прохода
управления по объявлению типа.

Это наделяет данное typedef-объявление необычным интересным свойством - оно не просто
порождает выполнимый код, оно порождает критически необходимый выполнимый код. По этой
причине в языке C появляется доселе невиданное свойство (знакомое нам из С++): язык
С запрещает передачу управления извне области видимости сущности вариабельного типа
внутрь этой области видимости

/* Внутри блока */
int n = 10;
goto skip; /* ОШИБКА: недопустимая передача управления */

typedef int A[n];
skip:;


Подчеркну еще раз, что в вышеприведенном коде нет определения ни одного VLA-массива,
а есть лишь объявление typedef-псевдонима для вариабельного типа. Однако передача управления
через такое typedef-объявление не допускается.

При определении фактического VLA-массива кроме собственно выделения памяти под элементы
массива происходит создание точно таких же скрытых переменных, хранящих размеры массива.
Сам массив реализуется через обычный указатель, а выделение памяти делается механизмом
вроде alloca

/* Внутри блока */
int n = 10, m = 20;
typedef int A[n][m];
A a;
a[5][6] = 42;

/* ... транслируется в ... */

int n = 10, m = 20;
size_t _internal_A1 = n, _internal_A2 = m;
int *a = alloca(_internal_A1 * _internal_A2 * sizeof(int)); 
a[5 * _internal_A2 + 6] = 42;


(Разумеется, в дополнение к этому будет сгенерирован код для освобождения выделенной
памяти при завершении блока, в котором определен массив a). 

Однако и в таком случае следует понимать, что эти скрытые переменные ассоциируются
не столько с самим массивом, сколько с его вариабельным типом. Если в коде объявлено
несколько VLA-массивов и/или вариабельных типов с идентичными характеристиками времени
выполнения, они в принципе могут пользоваться одними и теми же скрытыми переменными
для хранения своих размеров.

Из этого следует одно важное замечательное следствие: дополнительная информация о
размерах массива, ассоциированная с VLA-массивом, не является встроенной в объектное
представление самого массива, а хранится "рядом": совершенно отдельным, независимым
образом. Это приводит к тому, что объектное представление VLA с любым количеством измерений
является полностью совместимым с объектным представлением классического "фиксированного"
массива с тем же количеством измерений и теми же размерами. Например

/* Внутри блока */
unsigned n = 5;
int a[n][n + 1][n + 2]; /* VLA */
int (*p)[5][6][7]; /* Указатель на "классический" массив */

p = &a;
/* Присваивание корректно, т.к. размеры массивов совпадают */

(*p)[1][2][3] = 42;
/* Поведение определено: `a[1][2][3]` получает значение 42 */


Или на примере часто возникающей необходимости передачи массива в функцию

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

Объявления VLA-массивов не допускают указания инициализаторов, что также предотвращает
использование VLA в составных литералах

int n = 10;
int a[n] = { 0 }; /* ОШИБКА: нельзя указывать инициализатор */


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

Пользуясь ценными свойствами VLA мы можем написать, например, следующий код

#include 
#include 

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 в локальной памяти (!), то есть это популярное
направление критики VLA в этом коде совершенно не применимо.        

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

/* На уровне файла */
int n = 100;
void foo(int a[n++]) {}

void bar(int m, int a[++n][++m]) {}

int hello(void) { return printf("Hello World\n"); }
void baz(int a[hello()]) {}


Выражения, использованные объявлениях VLA внутри объявлений функций, будут честно
вычисляться, вместе со своими побочными эффектами, при каждом вызове функции. Обратите
внимание, что несмотря на тот факт, что параметры типа "массив" будут трансформированы
в параметры типа "указатель", это не отменяет необходимости вычисления выражения, использовавшегося
для задания размера массива в исходном объявлении. В данном примере каждый вызов функции
baz будет сопровождаться выводом строки "Hello World\n".



Упоминание тэга [C++] в вопросе неправомерно. В популистских контекстах зачастую
можно услышать утверждения о том, что в некоторых компиляторах (GCC) VLA поддерживаются
и в С++ коде. На самом деле тот факт, что некоторые компиляторы в С++ режиме разрешают
указывать неконстантные выражения в качестве размеров языковых массивов, совсем не
свидетельствует о поддержке VLA в стиле C99 на территории С++ кода. С и С++ существенно
разные языки и поддержка C99 VLA в С++ затруднительна или даже невозможна. Простые
эксперименты показывают, что поведение псевдо-VLA в GCC C++ фундаментально отличается
от стандартного поведения C99 VLA. Например вот такой код

#include 

int main(void)  
{
  int n = 10;
  typedef int A[n];
  n = 20;
  A a;
  printf("%zu\n", sizeof a / sizeof *a);
} 


выведет 10 в режиме С (как и должно быть), но выведет 20 при компиляции в режиме
GNU C++. Очевидно, концепция "typedef, порождающего выполнимый код" не согласуется
с фундаментальным идеями языка С++.


Ответ 2

VLA - это попытка упросить жизнь программисту, что бы он мог создавать массивы "интуитивным
способом" (я специально взял в кавычки).

VLA обычно реализуется через alloca и выделяется на стеке. То есть, для компилятора
это просто немного поменять регистр указателя стека. То есть, очень и очень быстро.
С другой стороны, стек не безразмерный и такой массив ограничен 1 или 8 мегабайтами
(настройки по умолчанию в большинстве компиляторов и ОС для 32 и 64 битных систем).


  Почему в С++ (хотя g++, clang поддерживает) это не работает?


В С++ есть vector, который и является тем самым правильным массивом и необходимости
в VLA нет. В g++ оно есть, потому что так оказалось проще - в противном случае нужно
было бы добавлять дополнительное условие в компилятор, дополнительные тесты и плюс
можно использовать си исходники в плюсовом коде с меньшей болью. Хотя думаю, на самом
деле это просто бага, а потом выдали за фичу.


Ответ 3

VLA в С99 - это попытка бэкпортировать std::vector из C++ обратно в C.

Работает примерно также, но прячет все детали за "магией" компилятора.

При наличии std::vector смысла в VLA для С++ нет никакого.

Но добавляет неожиданные проблемы, например, в связи с тем, что sizeof(arr) не может
быть вычислен на этапе компиляции, на что могут рассчитывать шаблоны.