Замена C++ для C99 VLA (цель: сохранить производительность)

Question

Замена C++ для C99 VLA (цель: сохранить производительность)

Я портирую код C99, который интенсивно использует массивы переменной длины (VLA), на C++.

Я заменил VLA (выделение стека) классом массива, который выделяет память в куче. Падение производительности было огромным, снижение в 3,2 раза (см. Тесты ниже). Какую быструю замену VLA я могу использовать в C++? Моя цель - минимизировать снижение производительности при переписывании кода для C++.

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

Я наткнулся std::dynarray, но я понимаю, что это не было принято в стандарт (пока?).

Я знаю, что clang и gcc поддерживают VLA в C++, но мне нужно, чтобы он работал и с MSVC. Фактически, лучшая переносимость является одной из основных целей переписывания на C++ (другая цель - превратить программу, которая изначально была инструментом командной строки, в библиотеку многократного использования).

эталонный тест

MSL относится к размеру массива, выше которого я переключаюсь на выделение кучи. Я использую разные значения для 1D и 2D массивов.

Оригинальный код C99: 115 секунд.
MSL = 0 (то есть выделение кучи): 367 секунд (3,2x).
1D-MSL = 50, 2D-MSL = 1000: 187 секунд (1,63х).
1D-MSL = 200, 2D-MSL = 4000: 143 секунды (1,24x).
1D-MSL = 1000, 2D-MSL = 20000: 131 (1,14x).

Увеличение MSL еще больше повышает производительность, но в итоге программа начнет возвращать неправильные результаты (я полагаю, из-за переполнения стека).

Эти тесты соответствуют clang 3.7 на OS X, но gcc 5 показывает очень похожие результаты.

Код

Это текущая реализация "smallvector", которую я использую. Мне нужны 1D и 2D векторы. Я переключаюсь на кучу-выделение выше размера MSL,

template<typename T, size_t MSL=50>
class lad_vector {
    const size_t len;
    T sdata[MSL];
    T *data;
public:
    explicit lad_vector(size_t len_) : len(len_) {
        if (len <= MSL)
            data = &sdata[0];
        else
            data = new T[len];
    }

    ~lad_vector() {
        if (len > MSL)
            delete [] data;
    }

    const T &operator [] (size_t i) const { return data[i]; }
    T &operator [] (size_t i) { return data[i]; }

    operator T * () { return data; }
};


template<typename T, size_t MSL=1000>
class lad_matrix {
    const size_t rows, cols;
    T sdata[MSL];
    T *data;

public:
    explicit lad_matrix(size_t rows_, size_t cols_) : rows(rows_), cols(cols_) {
        if (rows*cols <= MSL)
            data = &sdata[0];
        else
            data = new T[rows*cols];
    }

    ~lad_matrix() {
        if (rows*cols > MSL)
            delete [] data;
    }

    T const * operator[] (size_t i) const { return &data[cols*i]; }
    T * operator[] (size_t i) { return &data[cols*i]; }
};

36

c++ arrays performance variable-length-array stack-allocation

Источник

user695132 03 апр '16 в 20:01

3 ответа

Решение

Я думаю, что вы уже перечислили большинство вариантов в вашем вопросе и комментариях.

использование std::vector, Это наиболее очевидное, наиболее беспроблемное, но, возможно, и самое медленное решение.
Используйте специфичные для платформы расширения на тех платформах, которые их предоставляют. Например, GCC поддерживает массивы переменной длины в C++ в качестве расширения. POSIX указывает alloca который широко поддерживается для выделения памяти в стеке. Даже Microsoft Windows предоставляет _malloca, как сказал быстрый поиск в Интернете.
Чтобы избежать ночных кошмаров по обслуживанию, вы действительно захотите инкапсулировать эти зависимости платформы в абстрактный интерфейс, который автоматически и прозрачно выбирает подходящий механизм для текущей платформы. Реализация этого для всех платформ будет небольшим трудом, но если эта единственная функция учитывает 3-кратную разницу в скорости, как вы сообщаете, это может стоить того. Как запасной вариант для неизвестных платформ, я бы сохранил std::vector в заповеднике в крайнем случае. Лучше бегать медленно, но правильно, чем вести себя неуверенно или вообще не бегать.
Создайте свой собственный тип массива переменного размера, который реализует оптимизацию "малого массива", встроенную в качестве буфера в сам объект, как вы показали в своем вопросе. Я просто отмечу, что я бы предпочел использовать union из std::array и std::vector вместо того, чтобы катить мой собственный контейнер.
Когда у вас есть собственный тип, вы можете сделать интересное профилирование, например, поддерживать глобальную хеш-таблицу всех вхождений этого типа (по расположению исходного кода) и записывать каждый размер выделения во время стресс-теста вашей программы. Затем вы можете сбросить хеш-таблицу при выходе из программы и построить распределение в размерах распределения для отдельных массивов. Это может помочь вам точно настроить объем памяти, который нужно зарезервировать для каждого массива в стеке.
Использовать std::vector с пользовательским распределителем. При запуске программы выделите несколько мегабайт памяти и отдайте ее простому распределителю стека. Для распределителя стека распределение просто сравнивает и добавляет два целых числа, а освобождение - просто вычитание. Я сомневаюсь, что сгенерированное компилятором выделение стека может быть намного быстрее. Тогда ваш "стек массивов" будет пульсировать в соответствии с вашим "стеком программ". Такое проектирование также будет иметь преимущество в том, что случайное переполнение буфера - при этом все еще вызывая неопределенное поведение, удаление случайных данных и все такое плохое - не будет так легко повредить стек программы (адреса возврата), как это было бы с нативными VLA.
Пользовательские распределители в C++ - это довольно грязный бизнес, но некоторые люди сообщают, что используют их успешно. (У меня нет большого опыта их использования.) Вы можете начать изучать cppreference. Элисдейр Мередит, которая является одним из тех, кто продвигает использование пользовательских распределителей, выступила на CppCon'14 с двойной сессией под названием "Как заставить распределители работать" ( часть 1, часть 2), что также может показаться вам интересным. Если std::allocator Интерфейс это слишком неудобно для использования, реализация собственной переменной (в отличие от динамически) класса массива размера с вашим собственным распределителем также должно быть выполнимо.

17

Источник

user1392132 03 апр '16 в 20:48

Что касается поддержки MSVC:

MSVC имеет _alloca который выделяет пространство стека. Он также имеет _malloca который выделяет пространство стека, если имеется достаточно свободного места в стеке, в противном случае возвращается к динамическому распределению.

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

Вам может понадобиться использовать макрос, который имеет разные определения в зависимости от платформы. Например, вызвать _alloca или же _malloca на MSVC и на g++ или других компиляторах, либо вызывает alloca (если они поддерживают это), или делает VLA и указатель.

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

9

Источник

user1505939 03 апр '16 в 23:49

Другие вопросы по тегам c++ arrays performance variable-length-array stack-allocation

user1774667 03 апр '16 в 21:01 2016-04-03 21:01 · Accepted Answer · 2016-04-03 21:01

Создайте большой буфер (MB+) в локальном потоке. (Фактическая память на куче, управление в TLS).

Разрешить клиентам запрашивать у него память в формате FILO (в виде стека). (это имитирует, как это работает в C VLA; и это эффективно, поскольку каждый запрос / возврат является просто целочисленным сложением / вычитанием).

Получите ваше хранилище VLA от этого.

Оберните это красиво, так что вы можете сказать stack_array<T> x(1024);и есть это stack_array иметь дело со строительством / разрушением (обратите внимание, что ->~T() где T является int является законным noop, и конструкция может быть аналогичным noop), или сделать stack_array<T> завернуть std::vector<T, TLS_stack_allocator>,

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

SBO stack_array<T> может быть реализован с помощью распределителя и вектора std, объединенного с массивом std, или с уникальным ptr и пользовательским разрушителем, или множеством других способов. Вероятно, вы можете дооснастить свое решение, заменив новый /malloc/free/delete звонками в вышеуказанное хранилище TLS.

Я говорю о переходе на TLS, поскольку это устраняет необходимость в накладных расходах на синхронизацию и позволяет использовать многопоточность, а также отражает тот факт, что сам стек является неявно TLS.

Распределитель STL на основе стекового буфера? SO & Q с ответами, по крайней мере, с двумя "стековыми" распределителями. Им потребуется некоторая адаптация, чтобы автоматически получать свой буфер от TLS.

Обратите внимание, что TLS, являющийся одним большим буфером, в некотором смысле является деталью реализации. Вы можете сделать большие выделения, а когда у вас закончится свободное место, сделайте еще одно большое выделение. Вам просто нужно отслеживать текущую емкость каждой "страницы стека" и список страниц стека, поэтому, когда вы опустошите одну, вы сможете перейти на более раннюю. Это позволяет вам быть немного более консервативным в начальном распределении TLS, не беспокоясь о запуске OOM; важная часть заключается в том, что вы являетесь FILO и выделяете его редко, а не то, что весь буфер FILO является одним непрерывным.