Этот вопрос получил довольно замораживающий прием в SO, поэтому я решил удалить его там и попробовать здесь. Если вы думаете, что он здесь не подходит, пожалуйста, по крайней мере, оставьте комментарий к предложению, как найти пример, который я ищу ...
Можете ли вы привести пример , когда использование C99 VLA дает реальное преимущество перед чем-то вроде современных стандартных механизмов C ++ RAII с использованием кучи?
Пример, за которым я следую, должен:
- Получите легко измеримое (возможно, 10%) преимущество в производительности по сравнению с использованием кучи.
- Не найдется хорошего обходного пути, для которого вообще не нужен весь массив.
- На самом деле выгода от использования динамического размера вместо фиксированного максимального размера.
- Маловероятно, чтобы вызвать переполнение стека в нормальном сценарии использования.
- Будьте достаточно сильны, чтобы соблазнить разработчика, которому нужна производительность, включить исходный файл C99 в проект C ++.
Добавим некоторые пояснения по контексту: я имею в виду VLA, как подразумевается под C99 и не входит в стандарт C ++: int array[n]
где n
переменная. И я приведу пример использования, где он превосходит альтернативы, предлагаемые другими стандартами (C90, C ++ 11):
int array[MAXSIZE]; // C stack array with compile time constant size
int *array = calloc(n, sizeof int); // C heap array with manual free
int *array = new int[n]; // C++ heap array with manual delete
std::unique_ptr<int[]> array(new int[n]); // C++ heap array with RAII
std::vector<int> array(n); // STL container with preallocated size
Некоторые идеи:
- Функции, принимающие varargs, которые естественным образом ограничивают количество элементов до чего-то разумного, но не имеют никакого полезного верхнего предела уровня API.
- Рекурсивные функции, где ненужный стек нежелателен
- Много небольших распределений и выпусков, где куча накладных расходов будет плохой.
- Обработка многомерных массивов (например, матриц произвольного размера), где производительность критична, и ожидается, что небольшие функции будут много встроены.
- Из комментария: параллельный алгоритм, где распределение кучи имеет накладные расходы на синхронизацию .
В Википедии есть пример, который не соответствует моим критериям , потому что практическое различие в использовании кучи кажется несущественным, по крайней мере, без контекста. Это также неидеально, потому что без дополнительного контекста кажется, что количество элементов вполне может вызвать переполнение стека.
Примечание: я специально для примера кода или предложения алгоритма, который выиграл бы от этого, для меня, чтобы реализовать пример самостоятельно.
alloca()
, действительно затмитmalloc()
в многопоточной среде из-за конфликта блокировки в последнем . Но это реальная растяжка, поскольку маленькие массивы должны просто использовать фиксированный размер, и большие массивы, вероятно, все равно будут нуждаться в куче.alloca
, который, я думаю, в основном одно и то же). Но эта многопоточная вещь хороша, редактирование вопроса, чтобы включить его!malloc
поведение соответствует стандарту C.Ответы:
Я только что взломал небольшую программу, которая генерирует набор случайных чисел, перезапускающихся с одного и того же начального числа каждый раз, чтобы убедиться, что они «честные» и «сопоставимые». По ходу дела он вычисляет минимальные и максимальные значения. И когда он сгенерировал набор чисел, он подсчитывает, сколько из них выше среднего
min
иmax
.Для ОЧЕНЬ маленьких массивов это показывает явное преимущество по сравнению с VLA
std::vector<>
.Это не реальная проблема, но мы можем легко представить себе что-то, где мы будем читать значения из небольшого файла вместо использования случайных чисел и делать некоторые другие, более значимые вычисления подсчета / мин / макс с таким же кодом ,
Для ОЧЕНЬ малых значений «числа случайных чисел» (x) в соответствующих функциях
vla
решение выигрывает с огромным запасом. По мере увеличения размера «выигрыш» становится меньше, и при достаточном размере векторное решение оказывается БОЛЕЕ эффективным - не слишком много изучал этот вариант, поскольку, когда мы начинаем иметь тысячи элементов в VLA, это не так. на самом деле, что они должны были сделать ...И я уверен, что кто-то скажет мне, что есть какой-то способ написания всего этого кода с кучей шаблонов, и заставит его делать это без запуска больше, чем RDTSC и
cout
биты во время выполнения ... Но я не думаю, что это действительно точка.При запуске этого конкретного варианта, я получаю разницу около 10% между
func1
(VLA) иfunc2
(std :: vector).Это скомпилировано с:
g++ -O3 -Wall -Wextra -std=gnu++0x -o vla vla.cpp
Вот код:
источник
std::vector
.func3
который используетv.push_back(rand())
вместоv[i] = rand();
и устраняет необходимостьresize()
. Это занимает около 10% больше по сравнению с тем, который используетresize()
. [Конечно, в процессе, я обнаружил, что использованиеv[i]
является основным фактором, влияющим на время, которое занимает функция - я немного удивлен этим].std::vector
реализации, которая будет использовать VLA /alloca
, или это просто предположение?vector
реализации.Относительно VLA против вектора
Считаете ли вы, что Вектор может использовать преимущества самих VLA? Без VLA Вектор должен указывать определенные «масштабы» массивов, например, 10, 100, 10000 для хранения, так что вы в конечном итоге выделяете массив из 10000 элементов для 101 элемента. С VLA, если вы измените размер до 200, алгоритм может предположить, что вам нужно только 200 и может выделить массив из 200 элементов. Или он может выделить буфер, скажем, n * 1.5.
В любом случае, я бы сказал, что если вы знаете, сколько элементов вам понадобится во время выполнения, VLA будет более производительным (как показал тест Mats). Он продемонстрировал простую двухпроходную итерацию. Подумайте о симуляциях Монте-Карло, где случайные выборки берутся многократно, или манипуляции с изображениями (например, фильтры Photoshop), когда вычисления выполняются для каждого элемента несколько раз, и вполне возможно, что каждое вычисление для каждого элемента включает в себя просмотр соседей.
Этот дополнительный указатель перехода от вектора к его внутреннему массиву складывается.
Отвечая на главный вопрос
Но когда вы говорите об использовании динамически размещаемой структуры, такой как LinkedList, сравнение не проводится. Массив обеспечивает прямой доступ, используя арифметику указателей на его элементы. Используя связанный список, вы должны пройтись по узлам, чтобы добраться до определенного элемента. Таким образом, VLA выигрывает руки в этом сценарии.Согласно этому ответу , это зависит от архитектуры, но в некоторых случаях доступ к памяти в стеке будет быстрее из-за доступности стека в кэше. При большом количестве элементов это может быть сведено на нет (потенциально причина уменьшения отдачи, которую Матс видел в своих тестах). Тем не менее, стоит отметить, что размеры кэша значительно растут, и вы, возможно, увидите, что это число будет расти соответственно.
источник
std::vector
нужны весы массивов? Зачем ему нужно место для элементов 10К, когда ему нужно только 101? Кроме того, в вопросе никогда не упоминаются связанные списки, поэтому я не уверен, откуда вы это взяли. Наконец, VLA в C99 распределяются по стеку; они являются стандартной формойalloca()
. Все, что требует хранения в куче (оно возвращается после того, как функция вернется) или arealloc()
(размер массива сам по себе) в любом случае будет запрещать VLA.Причиной использования VLA является прежде всего производительность. Ошибочно пренебрегать примером вики как имеющим только «несущественное» различие. Я легко вижу случаи, когда именно этот код мог иметь огромную разницу, например, если бы эта функция вызывалась в узком цикле, где
read_val
была функция ввода-вывода, которая очень быстро возвращалась в какой-то системе, где скорость была критической.Фактически, в большинстве мест, где VLA используются таким образом, они не заменяют вызовы кучи, а вместо этого заменяют что-то вроде:
Суть любой локальной декларации в том, что она очень быстрая. Строка
float vals[n]
обычно требует только пару инструкций процессора (может быть, только одну). Она просто добавляет значение вn
указатель стека.С другой стороны, выделение кучи требует обхода структуры данных, чтобы найти свободную область. Время, вероятно, на порядок дольше, даже в самом удачном случае. (Т.е. просто процесс помещения
n
в стек и вызоваmalloc
- это, вероятно, 5-10 инструкций.) Вероятно, намного хуже, если в куче есть какое-то разумное количество данных. Меня совсем не удивит случай, когдаmalloc
в реальной программе скорость будет в 100-1000 раз медленнее.Конечно, при сопоставлении вы также оказываете некоторое влияние на производительность
free
, вероятно, схожее по величине сmalloc
вызовом.Кроме того, существует проблема фрагментации памяти. Множество небольших выделений имеют тенденцию фрагментировать кучу. Фрагментированные кучи и тратят впустую память и увеличивают время, необходимое для выделения памяти.
источник
int vla[n]; if(test()) { struct LargeStruct s; int i; }
смещение стекаs
не будет известно во время компиляции, и также сомнительно, если компилятор переместит хранилищеi
из внутренней области в фиксированное смещение стека. Таким образом, требуется дополнительный машинный код из-за косвенного обращения, и это также может поглотить регистры, важные для аппаратного обеспечения ПК. Если вам нужен пример кода с включенным выводом сборки компилятора, задайте отдельный вопрос;)s
иi
при вводе функции, до того, какtest
будет вызван илиvla
выделен, так как выделения дляs
и неi
имеют побочных эффектов. (И, фактически,i
может даже быть помещен в регистр, что означает отсутствие «выделения» вообще.) Компилятор не гарантирует порядок размещения в стеке или даже то, что стек используется.