массивы — замена 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

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

Решение

Другие решения

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

использование 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

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

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

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

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

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

8

Источник

Accepted Answer

Создайте большой буфер (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 является одним непрерывным.

38