Накладные расходы на массив переменной длины в C++?

Question

Глядя на этот вопрос: Почему компилятору C/C++ необходимо знать размер массива во время компиляции? Мне пришло в голову, что разработчикам компилятора следовало бы несколько раз «замочить ноги» сейчас (это часть стандарта C99, это было 10 лет назад) и обеспечить эффективные реализации.

Однако (судя по ответам) это по-прежнему считается дорогостоящим.

Меня это как-то удивляет.

Конечно, я понимаю, что статическое смещение намного лучше, чем динамическое с точки зрения производительности, и, в отличие от одного предложения, я бы не стал заставлять компилятор выполнять выделение массива в куче, поскольку это, вероятно, будет стоить еще больше [это не было измерено ;)]

Но я все еще удивляюсь предполагаемому расходы:

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

Конечно, возникает вопрос о нескольких VLA, и мне было интересно, подойдет ли выделенный стек VLA.Это означает, что VLA будет представлен счетчиком и указателем (следовательно, известных размеров), а фактическая память, взятая во вторичном стеке, используется только для этой цели (и, следовательно, на самом деле тоже стек).

[перефразируя]

Как VLA реализованы в gcc/VC++?

Неужели стоимость настолько впечатляющая?

[конец перефразирования]

Мне кажется, это может быть только лучше, чем использование, скажем, vector, даже при существующих реализациях, поскольку вы не несете затрат на динамическое распределение (за счет невозможности изменения размера).

РЕДАКТИРОВАТЬ:

Есть частичный ответ здесь, однако сравнение VLA с традиционными массивами кажется несправедливым.Если бы мы знали размер заранее, то VLA нам бы не понадобился.В том же вопросе АндрейТ дал несколько советов по реализации, но они не настолько точны, как хотелось бы.

Answer 1

Как VLA реализованы в gcc/VC++?

AFAIK VC++ не реализует VLA.Это компилятор C++, поддерживающий только C89 (без VLA, без ограничений).Я не знаю, как gcc реализует VLA, но самый быстрый способ — сохранить указатель на VLA и его размер в статической части кадра стека.Таким образом, вы можете получить доступ к одному из VLA с производительностью массива постоянного размера (это последний VLA, если стек растет вниз, как в x86 (разыменование [указатель стека + индекс*размер элемента + размер последних временных сообщений]), и первый VLA, если он растет вверх (разыменование [указатель стекового кадра + смещение от стекового кадра + индекс*размер элемента])).Всем остальным VLA потребуется еще одно косвенное обращение, чтобы получить свой базовый адрес из статической части стека.

[ Редактировать: Кроме того, при использовании VLA компилятор не может пропустить указатель стека-фрейма-базы, что в противном случае является избыточным, поскольку все смещения от указателя стека могут быть вычислены во время компиляции.Так у вас на одну бесплатную регистрацию меньше.— закончить редактирование ]

Неужели стоимость настолько впечатляющая?

Не совсем.Более того, если вы им не пользуетесь, вы за него не платите.

[ Редактировать: Вероятно, более правильным ответом будет:По сравнению с чем?По сравнению с вектором, выделенным в куче, время доступа будет таким же, но выделение и освобождение будут происходить быстрее.— закончить редактирование ]

Answer 2

Если бы это было реализовано на VС++, я бы предположил, что команда компиляторов использовала бы какой-то вариант _alloca(size).И я думаю, что затраты эквивалентны использованию переменных с выравниванием более 8 байт в стеке (например, __m128);компилятор должен где-то хранить исходный указатель стека, а для выравнивания стека требуется дополнительный регистр для хранения невыровненного стека.

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