Хороший пример массива переменной длины C [закрыто]

9

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

Можете ли вы привести пример , когда использование C99 VLA дает реальное преимущество перед чем-то вроде современных стандартных механизмов C ++ RAII с использованием кучи?

Пример, за которым я следую, должен:

  1. Получите легко измеримое (возможно, 10%) преимущество в производительности по сравнению с использованием кучи.
  2. Не найдется хорошего обходного пути, для которого вообще не нужен весь массив.
  3. На самом деле выгода от использования динамического размера вместо фиксированного максимального размера.
  4. Маловероятно, чтобы вызвать переполнение стека в нормальном сценарии использования.
  5. Будьте достаточно сильны, чтобы соблазнить разработчика, которому нужна производительность, включить исходный файл 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.
  • Рекурсивные функции, где ненужный стек нежелателен
  • Много небольших распределений и выпусков, где куча накладных расходов будет плохой.
  • Обработка многомерных массивов (например, матриц произвольного размера), где производительность критична, и ожидается, что небольшие функции будут много встроены.
  • Из комментария: параллельный алгоритм, где распределение кучи имеет накладные расходы на синхронизацию .

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

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

Хайд
источник
1
Немного умозрительно (так как это молоток, ищущий гвоздь), но, возможно alloca(), действительно затмит malloc()в многопоточной среде из-за конфликта блокировки в последнем . Но это реальная растяжка, поскольку маленькие массивы должны просто использовать фиксированный размер, и большие массивы, вероятно, все равно будут нуждаться в куче.
chrisaycock
1
@ chrisaycock Да, очень много молотка в поисках гвоздя, но молотка, который действительно существует (будь то C99 VLA или не-вообще-в-любом-стандарте alloca, который, я думаю, в основном одно и то же). Но эта многопоточная вещь хороша, редактирование вопроса, чтобы включить его!
Гайд
Один недостаток VLA состоит в том, что нет механизма для обнаружения сбоя распределения; если недостаточно памяти, поведение не определено. (То же самое верно для массивов фиксированного размера - и для alloca ().)
Кит Томпсон
@KeithThompson Ну, нет никакой гарантии, что malloc / new также обнаружит ошибку выделения, например, см. Справочную страницу malloc для Linux для Linux ( linux.die.net/man/3/malloc ).
Гайд
@hyde: И это спорно ли для Linux mallocповедение соответствует стандарту C.
Кит Томпсон,

Ответы:

9

Я только что взломал небольшую программу, которая генерирует набор случайных чисел, перезапускающихся с одного и того же начального числа каждый раз, чтобы убедиться, что они «честные» и «сопоставимые». По ходу дела он вычисляет минимальные и максимальные значения. И когда он сгенерировал набор чисел, он подсчитывает, сколько из них выше среднего minи max.

Для ОЧЕНЬ маленьких массивов это показывает явное преимущество по сравнению с VLA std::vector<>.

Это не реальная проблема, но мы можем легко представить себе что-то, где мы будем читать значения из небольшого файла вместо использования случайных чисел и делать некоторые другие, более значимые вычисления подсчета / мин / макс с таким же кодом ,

Для ОЧЕНЬ малых значений «числа случайных чисел» (x) в соответствующих функциях vlaрешение выигрывает с огромным запасом. По мере увеличения размера «выигрыш» становится меньше, и при достаточном размере векторное решение оказывается БОЛЕЕ эффективным - не слишком много изучал этот вариант, поскольку, когда мы начинаем иметь тысячи элементов в VLA, это не так. на самом деле, что они должны были сделать ...

И я уверен, что кто-то скажет мне, что есть какой-то способ написания всего этого кода с кучей шаблонов, и заставит его делать это без запуска больше, чем RDTSC и coutбиты во время выполнения ... Но я не думаю, что это действительно точка.

При запуске этого конкретного варианта, я получаю разницу около 10% между func1(VLA) и func2(std :: vector).

count = 9884
func1 time in clocks per iteration 7048685
count = 9884
func2 time in clocks per iteration 7661067
count = 9884
func3 time in clocks per iteration 8971878

Это скомпилировано с: g++ -O3 -Wall -Wextra -std=gnu++0x -o vla vla.cpp

Вот код:

#include <iostream>
#include <vector>
#include <cstdint>
#include <cstdlib>

using namespace std;

const int SIZE = 1000000;

uint64_t g_val[SIZE];


static __inline__ unsigned long long rdtsc(void)
{
    unsigned hi, lo;
    __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
    return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 );
}


int func1(int x)
{
    int v[x];

    int vmax = 0;
    int vmin = x;
    for(int i = 0; i < x; i++)
    {
        v[i] = rand() % x;
        if (v[i] > vmax) 
            vmax = v[i];
        if (v[i] < vmin) 
            vmin = v[i];
    }
    int avg = (vmax + vmin) / 2;
    int count = 0;
    for(int i = 0; i < x; i++)
    {
        if (v[i] > avg)
        {
            count++;
        }
    }
    return count;
}

int func2(int x)
{
    vector<int> v;
    v.resize(x); 

    int vmax = 0;
    int vmin = x;
    for(int i = 0; i < x; i++)
    {
        v[i] = rand() % x;
        if (v[i] > vmax) 
            vmax = v[i];
        if (v[i] < vmin) 
            vmin = v[i];
    }
    int avg = (vmax + vmin) / 2;
    int count = 0;
    for(int i = 0; i < x; i++)
    {
        if (v[i] > avg)
        {
            count++;
        }
    }
    return count;
}    

int func3(int x)
{
    vector<int> v;

    int vmax = 0;
    int vmin = x;
    for(int i = 0; i < x; i++)
    {
        v.push_back(rand() % x);
        if (v[i] > vmax) 
            vmax = v[i];
        if (v[i] < vmin) 
            vmin = v[i];
    }
    int avg = (vmax + vmin) / 2;
    int count = 0;
    for(int i = 0; i < x; i++)
    {
        if (v[i] > avg)
        {
            count++;
        }
    }
    return count;
}    

void runbench(int (*f)(int), const char *name)
{
    srand(41711211);
    uint64_t long t = rdtsc();
    int count = 0;
    for(int i = 20; i < 200; i++)
    {
        count += f(i);
    }
    t = rdtsc() - t;
    cout << "count = " << count << endl;
    cout << name << " time in clocks per iteration " << dec << t << endl;
}

struct function
{
    int (*func)(int);
    const char *name;
};


#define FUNC(f) { f, #f }

function funcs[] = 
{
    FUNC(func1),
    FUNC(func2),
    FUNC(func3),
}; 


int main()
{
    for(size_t i = 0; i < sizeof(funcs)/sizeof(funcs[0]); i++)
    {
        runbench(funcs[i].func, funcs[i].name);
    }
}
Матс Петерссон
источник
Вау, моя система показывает 30% улучшение по сравнению с версией VLA std::vector.
chrisaycock
1
Ну, попробуйте с диапазоном размеров около 5-15 вместо 20-200, и вы, вероятно, получите улучшение на 1000% или более. [Также зависит от параметров компилятора - я отредактирую приведенный выше код, чтобы отобразить параметры моего компилятора на gcc]
Матс Петерссон,
Я просто добавил, func3который использует v.push_back(rand())вместо v[i] = rand();и устраняет необходимость resize(). Это занимает около 10% больше по сравнению с тем, который использует resize(). [Конечно, в процессе, я обнаружил, что использование v[i]является основным фактором, влияющим на время, которое занимает функция - я немного удивлен этим].
Матс Петерссон
1
@MikeBrown Знаете ли вы о реальной std::vectorреализации, которая будет использовать VLA / alloca, или это просто предположение?
Гайд,
3
Вектор действительно использует массив внутри, но, насколько я понимаю, он не может использовать VLA. Я верю, что мой пример показывает, что VLA полезны в некоторых (возможно, даже во многих) случаях, когда объем данных невелик. Даже если вектор использует VLA, это будет после дополнительных усилий внутри vectorреализации.
Матс Петерссон
0

Относительно 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(). Все, что требует хранения в куче (оно возвращается после того, как функция вернется) или a realloc()(размер массива сам по себе) в любом случае будет запрещать VLA.
chrisaycock
@chrisaycock C ++ по некоторым причинам не имеет функции realloc (), предполагая, что память выделяется с помощью new []. Разве это не главная причина, по которой std :: vector должен использовать весы?
@Lundin С ++ масштабирует вектор степенями десяти? У меня только создалось впечатление, что Майк Браун был действительно смущен этим вопросом, учитывая ссылку на связанный список. (Он также сделал более раннее утверждение, что подразумевается, что C99 VLA живут в куче.)
chrisaycock
@hyde Я не понял, о чем ты говоришь. Я думал, что вы имели в виду другие структуры данных на основе кучи. Интересно, что вы добавили это уточнение. Мне не хватает фаната C ++, чтобы сказать вам разницу между ними.
Майкл Браун
0

Причиной использования VLA является прежде всего производительность. Ошибочно пренебрегать примером вики как имеющим только «несущественное» различие. Я легко вижу случаи, когда именно этот код мог иметь огромную разницу, например, если бы эта функция вызывалась в узком цикле, где read_valбыла функция ввода-вывода, которая очень быстро возвращалась в какой-то системе, где скорость была критической.

Фактически, в большинстве мест, где VLA используются таким образом, они не заменяют вызовы кучи, а вместо этого заменяют что-то вроде:

float vals[256]; /* I hope we never get more! */

Суть любой локальной декларации в том, что она очень быстрая. Строка float vals[n]обычно требует только пару инструкций процессора (может быть, только одну). Она просто добавляет значение в nуказатель стека.

С другой стороны, выделение кучи требует обхода структуры данных, чтобы найти свободную область. Время, вероятно, на порядок дольше, даже в самом удачном случае. (Т.е. просто процесс помещения nв стек и вызова malloc- это, вероятно, 5-10 инструкций.) Вероятно, намного хуже, если в куче есть какое-то разумное количество данных. Меня совсем не удивит случай, когда mallocв реальной программе скорость будет в 100-1000 раз медленнее.

Конечно, при сопоставлении вы также оказываете некоторое влияние на производительность free, вероятно, схожее по величине с mallocвызовом.

Кроме того, существует проблема фрагментации памяти. Множество небольших выделений имеют тенденцию фрагментировать кучу. Фрагментированные кучи и тратят впустую память и увеличивают время, необходимое для выделения памяти.

Горт Робот
источник
О примере из Википедии: он может быть частью хорошего примера, но без контекста, больше кода вокруг него, он на самом деле не показывает ни одну из 5 вещей, перечисленных в моем вопросе. В противном случае да, я согласен с вашим объяснением. Хотя следует иметь в виду одну вещь: использование VLA может иметь стоимость доступа к локальным переменным, при этом смещения всех локальных переменных не обязательно известны во время компиляции, поэтому следует позаботиться о том, чтобы не заменять одноразовые затраты на кучу штраф внутреннего цикла за каждую итерацию.
Хайд
Эм ... не знаю, что ты имеешь в виду. Объявления локальных переменных являются одной операцией, и любой слегка оптимизированный компилятор извлекает распределение из внутреннего цикла. Нет особой «стоимости» в доступе к локальным переменным, конечно, нет той, которую увеличит VLA.
Gort the Robot
Конкретный пример:: int vla[n]; if(test()) { struct LargeStruct s; int i; }смещение стека sне будет известно во время компиляции, и также сомнительно, если компилятор переместит хранилище iиз внутренней области в фиксированное смещение стека. Таким образом, требуется дополнительный машинный код из-за косвенного обращения, и это также может поглотить регистры, важные для аппаратного обеспечения ПК. Если вам нужен пример кода с включенным выводом сборки компилятора, задайте отдельный вопрос;)
hyde
Компилятору не нужно размещать в порядке, встречающемся в коде, и не имеет значения, выделено ли пространство и не используется ли оно. Интеллектуальный оптимизатор будет выделять пространство для sи iпри вводе функции, до того, как testбудет вызван или vlaвыделен, так как выделения для sи не iимеют побочных эффектов. (И, фактически, iможет даже быть помещен в регистр, что означает отсутствие «выделения» вообще.) Компилятор не гарантирует порядок размещения в стеке или даже то, что стек используется.
Gort the Robot
(удалил комментарий, который был ошибочным из-за глупой ошибки)
hyde