Почему массивы переменной длины не являются частью стандарта C ++?

326

Я не очень много использовал C в последние несколько лет. Когда я прочитал этот вопрос сегодня, я натолкнулся на некоторый синтаксис Си, с которым я не был знаком.

Видимо в C99 действует следующий синтаксис:

void foo(int n) {
    int values[n]; //Declare a variable length array
}

Это кажется довольно полезной функцией. Были ли когда-нибудь дискуссии о добавлении его в стандарт C ++, и если да, то почему он был опущен?

Некоторые потенциальные причины:

  • Волосатость для поставщиков компиляторов для реализации
  • Несовместим с какой-либо другой частью стандарта
  • Функциональность можно эмулировать с другими конструкциями C ++

Стандарт C ++ утверждает, что размер массива должен быть константным выражением (8.3.4.1).

Да, конечно, я понимаю, что в игрушечном примере можно использовать std::vector<int> values(m);, но это выделяет память из кучи, а не из стека. И если я хочу многомерный массив, как:

void foo(int x, int y, int z) {
    int values[x][y][z]; // Declare a variable length array
}

vectorверсия становится довольно неуклюжи:

void foo(int x, int y, int z) {
    vector< vector< vector<int> > > values( /* Really painful expression here. */);
}

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

Глядя на обсуждение, comp.std.c++становится ясно, что этот вопрос довольно спорный с некоторыми очень тяжелыми именами по обе стороны аргумента. Конечно, не очевидно, что std::vectorвсегда лучшее решение.

Андреас Бринк
источник
3
Просто из любопытства, почему он должен быть размещен в стеке? Вы боитесь проблем с производительностью выделения кучи?
Дмитрий С.
32
@Dimitri Не совсем, но нельзя отрицать, что выделение стека будет быстрее, чем выделение кучи. И в некоторых случаях это может иметь значение.
Андреас Бринк
11
Основное преимущество массивов переменной длины в том, что все данные расположены близко друг к другу, поэтому при выполнении итерации по этому массиву вы читаете и пишете байты рядом друг с другом. Ваши данные извлекаются в кеш, и процессор может работать с ним, не извлекая и не отправляя байты в / из памяти.
Кальмарий
4
Массивы переменной длины также могут использоваться для замены констант препроцессора статическими константными переменными. Также в C у вас нет других опций для VLA, и иногда необходимо написать переносимый код C / C ++ (совместимый с обоими компиляторами).
Юрий
2
в стороне, кажется, Clang ++ позволяет VLA.
user3426763

Ответы:

204

Недавно в usenet началось обсуждение этого вопроса: почему в C ++ 0x нет VLA .

Я согласен с теми людьми, которые, похоже, согласны с тем, что создание потенциально большого массива в стеке, в котором обычно мало доступного пространства, не очень хорошо. Аргумент: если вы заранее знаете размер, вы можете использовать статический массив. И если вы не знаете размер заранее, вы напишите небезопасный код.

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

Вы можете использовать std::vector, но это не совсем то же самое, так как он использует динамическую память, и заставить его использовать собственный распределитель стека не совсем легко (выравнивание также является проблемой). Это также не решает ту же проблему, потому что вектор является контейнером с изменяемым размером, тогда как VLA имеют фиксированный размер. Предложение C ++ Dynamic Array предназначено для представления решения на основе библиотеки, как альтернативы VLA на основе языка. Однако, насколько я знаю, это не будет частью C ++ 0x.

Йоханнес Шауб - Литб
источник
22
+1 и принято. Один комментарий, хотя, я думаю, что аргумент безопасности немного слаб, так как есть много других способов вызвать переполнение стека. Аргумент безопасности может использоваться для поддержки позиции, согласно которой вы никогда не должны использовать рекурсию и что вы должны выделять все объекты из кучи.
Андреас Бринк
17
Итак, вы говорите, что, поскольку существуют другие способы вызвать переполнение стека, мы могли бы также поощрять большее их количество?
Джалф
3
@ Андреас, договорились о слабости. Но для рекурсии требуется огромное количество вызовов, пока стек не будет израсходован, и если это так, люди будут использовать итерацию. Однако, как говорят некоторые люди в потоке usenet, это не аргумент против VLA во всех случаях, поскольку иногда вы определенно можете знать верхнюю границу. Но в этих случаях, из того, что я вижу, статический массив может быть в равной степени достаточным, поскольку в любом случае он не будет тратить много места (если это произойдет , тогда вам фактически придется спросить, достаточно ли велика область стека снова).
Йоханнес Шауб -
10
Также посмотрите на ответ Мэтта Остерна в этой теме: Спецификация языка VLA, вероятно, будет значительно более сложной для C ++, из-за более строгих совпадений типов в C ++ (пример: C позволяет присваивать T(*)[]a T(*)[N]- в C ++, это недопустимо, поскольку C ++ не знает о «совместимости типов» - она ​​требует точных совпадений), параметров типов, исключений, «против», «деструкторов» и прочего. Я не уверен, окупятся ли преимущества VLA от всей этой работы. Но тогда я никогда не использовал VLA в реальной жизни, поэтому я, вероятно, не знаю хороших вариантов их использования.
Йоханнес Шауб -
1
@AHelps: Возможно, для этого лучше всего подойдет тип, который ведет себя примерно так, vectorно требует фиксированного шаблона использования LIFO и поддерживает один или несколько статически распределенных буферов для потока, которые обычно имеют размер в соответствии с наибольшим общим выделением потока когда-либо использовался, но который мог быть явно урезан. Обычное «распределение» в общем случае потребовало бы не что иное, как копирование указателя, вычитание указателя из указателя, сравнение целых чисел и добавление указателя; для де-выделения просто потребовалась бы копия указателя. Не намного медленнее, чем VLA.
Суперкат
217

(Справочная информация: у меня есть некоторый опыт реализации компиляторов C и C ++.)

Массивы переменной длины в C99 были в основном ошибкой. Чтобы поддержать VLA, C99 должен был пойти на следующие уступки здравому смыслу:

  • sizeof xбольше не всегда константа времени компиляции; иногда компилятор должен генерировать код для оценки sizeof-экспрессии во время выполнения.

  • Разрешение двухмерного Власа ( int A[x][y]) требуется новый синтаксис для объявления функций , которые используют 2D Влас в качестве параметров: void foo(int n, int A[][*]).

  • Менее важно в мире C ++, но чрезвычайно важно для целевой аудитории программистов встраиваемых систем на C, объявление VLA означает разбрасывание произвольно большого куска вашего стека. Это гарантированное переполнение стека и сбой. (Каждый раз, когда вы объявляете int A[n], вы неявно утверждаете, что у вас есть 2 ГБ стека, чтобы сэкономить. В конце концов, если вы знаете, что « nздесь определенно меньше 1000», то вы просто объявите int A[1000]. Подстановка 32-разрядного целого числа nдля 1000- это допуск что вы понятия не имеете, каким должно быть поведение вашей программы.)

Хорошо, теперь давайте перейдем к разговору о C ++. В C ++ мы имеем такое же сильное различие между «системой типов» и «системой ценностей», как в C89… но мы действительно начали полагаться на него так, как это не делает C. Например:

template<typename T> struct S { ... };
int A[n];
S<decltype(A)> s;  // equivalently, S<int[n]> s;

Если бы nне была константа времени компиляции (т. AЕ. Если бы она была изменяемого типа), то что это за тип S? Будет ли Sтип также определяться только во время выполнения?

Как насчет этого:

template<typename T> bool myfunc(T& t1, T& t2) { ... };
int A1[n1], A2[n2];
myfunc(A1, A2);

Компилятор должен сгенерировать код для некоторой реализации myfunc. Как должен выглядеть этот код? Как мы можем статически генерировать этот код, если мы не знаем тип A1во время компиляции?

Хуже того, что если во время выполнения окажется, что n1 != n2, так что !std::is_same<decltype(A1), decltype(A2)>()? В этом случае вызов myfunc даже не должен компилироваться , потому что вывод типа шаблона должен завершиться неудачей! Как мы можем подражать этому поведению во время выполнения?

По сути, C ++ движется в направлении внедрения все большего количества решений во время компиляции : генерация кода шаблона, constexprоценка функции и так далее. Тем временем C99 был занят внедрением традиционных решений времени компиляции (например sizeof) во время выполнения . Имея это в виду, действительно ли он даже имеет смысл затрачивать никаких усилий , пытаясь интегрировать Власа C99 стиле в C ++?

Как уже отмечали все остальные авторы, C ++ предоставляет множество механизмов выделения кучи ( std::unique_ptr<int[]> A = new int[n];или std::vector<int> A(n);являющихся очевидными), когда вы действительно хотите донести идею: «Я понятия не имею, сколько ОЗУ мне может понадобиться». А C ++ предоставляет изящную модель обработки исключений для решения неизбежной ситуации, когда объем необходимой вам оперативной памяти больше, чем у вас. Но, надеюсь, этот ответ дает вам хорошее представление о том, почему VLA в стиле C99 не очень подходят для C ++ - и даже не совсем подходят для C99. ;)


Для получения дополнительной информации по этой теме см. N3810 «Альтернативы для расширений массивов» , документ Bjarne Stroustrup за октябрь 2013 года о VLA. POV Бьярне очень отличается от моего; N3810 больше фокусируется на поиске хорошего синтаксиса C ++ для вещей и на препятствовании использованию сырых массивов в C ++, тогда как я больше сосредоточился на последствиях для метапрограммирования и системы типов. Я не знаю, считает ли он последствия метапрограммирования / системы типов решенными, разрешимыми или просто неинтересными.


Хорошая запись в блоге, которая затрагивает многие из этих пунктов, - «Законное использование массивов переменной длины» (Chris Wellons, 2019-10-27).

Quuxplusone
источник
15
Я согласен, что VLA были просто неправы. Гораздо более широко реализованный и гораздо более полезный вариант alloca()должен был быть стандартизирован в C99. VLA - это то, что происходит, когда комитет по стандартам выпрыгивает впереди реализации, а не наоборот.
Безумный ученый
10
Изменяемая система типов - отличное дополнение IMO, и ни один из ваших пунктов не нарушает здравый смысл. (1) стандарт C не различает «время компиляции» и «время выполнения», так что это не проблема; (2) *Необязательно, вы можете (и должны) написать int A[][n]; (3) Вы можете использовать систему типов без фактического объявления каких-либо VLA. Например, функция может принимать массив изменяемого типа, и ее можно вызывать с двумерными массивами без VLA разных размеров. Однако вы делаете правильные очки в последней части вашего сообщения.
ММ
3
«Объявление VLA означает сжатие произвольно большого куска вашего стека. Это гарантированное переполнение стека и сбой. (Каждый раз, когда вы объявляете int A [n], вы неявно утверждаете, что у вас есть 2 ГБ стека в запасе», эмпирически false. Я только что запустил программу VLA со стеком, намного меньшим 2 ГБ, без какого-либо переполнения стека.
Джефф,
3
@Jeff: Каково было максимальное значение nв вашем тестовом примере, и каков был размер вашего стека? Я предлагаю вам попробовать ввести значение, по nкрайней мере, такое же большое, как размер вашего стека. (И если у пользователя нет возможности контролировать значение nв вашей программе, тогда я предлагаю вам просто передать максимальное значение nпрямо в объявление: объявлять int A[1000]или что-то еще, что вам нужно. VLA только необходимы и только опасны, когда максимальное значение nне ограничено какой-либо маленькой константой времени компиляции.)
Quuxplusone
2
Так как alloca () может быть реализована с использованием таких встроенных функций, по определению верно, что alloca () может быть реализована на любой платформе как стандартная функция компилятора. Нет причин, по которым компилятор не может обнаружить первый экземпляр alloca () и организовать типы меток и выпусков, которые будут встроены в код, и нет причин, по которым компилятор не может реализовать alloca () с использованием кучи, если это не может быть сделано со стеком. Что трудно / непереносимо , так это реализует alloca () поверх компилятора C, так что он работает в широком спектре компиляторов и операционных систем.
Безумный ученый
26

Вы всегда можете использовать alloca () для выделения памяти в стеке во время выполнения, если хотите:

void foo (int n)
{
    int *values = (int *)alloca(sizeof(int) * n);
}

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

Краткое примечание. Как упоминалось на справочной странице Mac OS X для alloca (3), «функция alloca () зависит от машины и компилятора; ее использование не рекомендуется». Просто чтобы ты знал.

PfhorSlayer
источник
4
Кроме того, областью применения alloca () является вся функция, а не только блок кода, содержащий переменную. Таким образом, используя его внутри цикла, он будет постоянно увеличивать стек. VLA не имеет этой проблемы.
sashoalm
3
Однако VLA, имеющие область действия включающего блока, означают, что они значительно менее полезны, чем alloca () с областью действия всей функции. Подумайте: if (!p) { p = alloca(strlen(foo)+1); strcpy(p, foo); } это не может быть сделано с VLA, именно из-за их области применения.
Безумный ученый
1
Это не отвечает на вопрос ОП почему . Более того, это Cпохоже на решение, а не на самом деле C++.
Адриан Ш
13

В своей собственной работе я понял, что каждый раз, когда я хотел что-то вроде автоматического массива переменной длины или alloca (), мне было все равно, что память физически расположена в стеке процессора, просто из некоторый распределитель стека, который не подвергался медленным переходам в общую кучу. Так что у меня есть объект для каждого потока, которому принадлежит некоторая память, из которой он может выдвигать / выталкивать буферы переменного размера. На некоторых платформах я позволяю этому расти через mmu. Другие платформы имеют фиксированный размер (обычно сопровождаемый стеком процессоров фиксированного размера, потому что нет MMU). Одна платформа, с которой я работаю (портативная игровая консоль), в любом случае имеет очень маленький стек процессоров, потому что она находится в дефицитной, быстрой памяти.

Я не говорю, что вставка буферов переменного размера в стек процессора никогда не нужна. Честно говоря, я был удивлён, когда обнаружил, что это не стандартно, так как кажется, что концепция достаточно хорошо вписывается в язык. Для меня, однако, требования «переменный размер» и «должны быть физически расположены в стеке процессора» никогда не встречались вместе. Речь шла о скорости, поэтому я создал свой собственный «параллельный стек для буферов данных».

Эрик
источник
12

Существуют ситуации, когда выделение динамической памяти очень дорого по сравнению с выполняемыми операциями. Примером является матричная математика. Если вы работаете с небольшими матрицами, скажем, от 5 до 10 элементов и выполняете много арифметических операций, служебные данные malloc будут действительно значительными. В то же время, делая размер постоянной времени компиляции, кажется очень расточительным и негибким.

Я думаю, что C ++ настолько небезопасен сам по себе, что аргумент «стараться не добавлять больше небезопасных возможностей» не очень силен. С другой стороны, поскольку C ++ является, пожалуй, наиболее эффективными функциями языка программирования во время выполнения, что делает его еще более полезным: люди, которые пишут программы, критичные к производительности, будут в значительной степени использовать C ++, и им потребуется как можно больше производительности. Перемещение вещей из кучи в стек - одна из таких возможностей. Уменьшение количества блоков кучи - другое. Разрешение VLA в качестве членов объекта будет одним из способов достижения этого. Я работаю над таким предложением. Правда, это немного сложно реализовать, но кажется вполне выполнимым.

Бенгт Густафссон
источник
12

Кажется, это будет доступно в C ++ 14:

https://en.wikipedia.org/wiki/C%2B%2B14#Runtime-sized_one_dimensional_arrays

Обновление: это не сделало это в C ++ 14.

Виктор Сер
источник
интересный. Херб Саттер обсуждает это здесь в разделе « Динамические массивы» : isocpp.org/blog/2013/04/trip-report-iso-c-spring-2013-meeting (это ссылка на информацию из Википедии)
умолчанию
1
«Массивы и dynarray размера во время выполнения перенесены в техническую спецификацию Array Extensions», написанную 78.86.152.103 в Википедии 18 января 2014 года: en.wikipedia.org/w/…
strager
10
Википедия не является нормативной ссылкой :) Это предложение не вошло в C ++ 14.
ММ
2
@ViktorSehr: Какой статус у этого C ++ 17?
einpoklum
@einpoklum Понятия не имею, используйте boost :: container :: static_vector
Виктор
7

Это рассматривалось для включения в C ++ / 1x, но было исключено (это исправление к тому, что я сказал ранее).

В любом случае это было бы менее полезно в C ++, так как мы уже должны std::vectorвыполнить эту роль.

philsquared
источник
42
Нет, std :: vector не размещает данные в стеке. :)
Кос
7
«стек» - это деталь реализации; компилятор может выделять память из любого места, если соблюдены гарантии времени жизни объекта.
ММ
1
@MM: Ярмарка достаточно, но на практике мы еще не можем использовать std::vectorвместо, скажем, alloca().
einpoklum
@einpoklum с точки зрения получения правильного вывода для вашей программы, вы можете. Производительность - это вопрос качества реализации
ММ
1
Качество реализации @MM не является переносимым. и если вам не нужна производительность, вы в первую очередь не используете c ++
приятель
3

Используйте для этого std :: vector. Например:

std::vector<int> values;
values.resize(n);

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

Димитрий С.
источник
4
Основное применение для массивов переменной длины - это оценка полиномов произвольной степени. В этом случае ваш «небольшой недостаток производительности» означает «код работает в пять раз медленнее в типичных случаях». Это не мало.
AHelps
1
Почему бы тебе просто не использовать std::vector<int> values(n);? Используя resizeпосле строительства, вы запрещаете неподвижные типы.
LF
1

C99 позволяет VLA. И это накладывает некоторые ограничения на то, как объявлять VLA. Подробнее см. 6.7.5.2 стандарта. C ++ запрещает VLA. Но g ++ это позволяет.

Цзинго Яо
источник
Можете ли вы предоставить ссылку на стандартный абзац, на который вы указываете?
Винсент
0

Подобные массивы являются частью C99, но не частью стандартного C ++. как уже говорили другие, вектор всегда является гораздо лучшим решением, поэтому, возможно, поэтому массивы переменного размера не входят в стандарт C ++ (или в предложенный стандарт C ++ 0x).

Кстати, для вопросов о том, «почему» стандарт C ++ таков , модерируемая группа новостей Usenet comp.std.c ++ - это то место, куда можно обратиться


источник
6
-1 Вектор не всегда лучше. Часто да. Всегда нет. Если вам нужен только небольшой массив, вы находитесь на платформе, где пространство кучи медленное, а реализация векторной библиотеки в вашей библиотеке использует пространство кучи, тогда эта функция вполне может быть лучше, если она существует.
Патрик М
-1

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

template <int X>
void foo(void)
{
   int values[X];

}

Редактировать: Вы можете создать вектор, который использует распределитель стека (alloca), так как распределитель является параметром шаблона.

Эдуард А.
источник
18
Если вы знаете значение во время компиляции, вам вообще не нужен шаблон. Просто используйте X прямо в функции, не связанной с шаблоном.
Роб Кеннеди
3
Иногда вызывающий знает во время компиляции, а вызывающий не знает, для этого хороши шаблоны. Конечно, в общем случае никто не знает X до времени выполнения.
Qwertie
Вы не можете использовать alloca в STL-распределителе - выделенная память из alloca будет освобождена при разрушении кадра стека - вот когда возвращается метод, который должен выделить память.
Оливер
-5

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

void varTest(int iSz)
{
    char *varArray;
    __asm {
        sub esp, iSz       // Create space on the stack for the variable array here
        mov varArray, esp  // save the end of it to our pointer
    }

    // Use the array called varArray here...  

    __asm {
        add esp, iSz       // Variable array is no longer accessible after this point
    } 
}

Опасностей здесь много, но я объясню несколько: 1. Изменение размера переменной на полпути убило бы позицию стека 2. Превышение границ массива уничтожило бы другие переменные и возможный код 3. Это не работает в 64-битной среде build ... нужна другая сборка для этого (но макрос может решить эту проблему). 4. Специфично для компилятора (могут возникнуть проблемы при перемещении между компиляторами). Я не пробовал, поэтому я действительно не знаю.

Алан
источник
... и если вы хотите это сделать сами, возможно, используйте класс RAII?
einpoklum
Вы можете просто использовать boost :: container :: static_vector thou.
Виктор Сер
Это не имеет аналогов для других компиляторов, которые имеют более сырую сборку, чем MSVC. VC, вероятно, поймет, что espизменилось, и настроит свой доступ к стеку, но, например, в GCC вы просто сломаете его полностью - по крайней мере, если вы используете оптимизацию и, -fomit-frame-pointerв частности.
Руслан