Я портирую код C99, который интенсивно использует массивы переменной длины (VLA), на C ++.
Я заменил VLA (распределение стека) классом массива, который выделяет память в куче. Падение производительности было огромным, замедление в 3,2 раза (см. Тесты ниже). Какую быструю замену VLA я могу использовать в C ++? Моя цель - минимизировать снижение производительности при переписывании кода для C ++.
Одна идея, которая была предложена мне, заключалась в том, чтобы написать класс массива, который содержит хранилище фиксированного размера внутри класса (то есть может быть выделено стеком) и использует его для небольших массивов и автоматически переключается на распределение кучи для больших массивов. Моя реализация этого находится в конце поста. Он работает довольно хорошо, но я все еще не могу достичь производительности исходного кода C99. Чтобы приблизиться к этому, я должен увеличить это хранилище фиксированного размера (MSL ниже) до размеров, которые мне не подходят. Я не хочу выделять слишком большие массивы в стеке даже для множества небольших массивов, которые в этом не нуждаются, потому что я беспокоюсь, что это вызовет переполнение стека. C99 VLA на самом деле менее подвержен этому, потому что он никогда не будет использовать больше памяти, чем необходимо.
Я наткнулся на 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,63x).
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 векторы. Перехожу на heap-allocation выше размера 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]; }
};
GCCвыполняет VLA как расширение и работает на всех этих платформах. - person Galik schedule 03.04.2016alloca(функция, специфичная для платформы, но существует в Linux / Windows / OS X): man7.org/linux/man-pages/man3/alloca.3.html Он динамически выделяет память в стеке. - person tmlen schedule 03.04.2016allocaдля создания класса массива в стеке? Сложность, с которой я сталкиваюсь, заключается в том, что если я вызываюallocaв конструкторе класса, он будет использовать стек конструктора (и указатель не будет действительным после возврата конструктора). - person Szabolcs schedule 04.04.2016Tвсегдаint,charилиboolв этом приложении, но никогда не является плавающей точкой. Это сложный комбинаторный алгоритм. Кроме того, если корень проблемы с производительностью заключается в том, что автоматическая векторизация теряется, то почему оптимизация, которую я пробовал, работает так же хорошо? - person Szabolcs schedule 04.04.2016allocaнужно будет вызвать в функции, стек которой следует использовать. То есть не в конструкторе векторного класса (или в списке инициализации). Класс может принимать указатель в качестве аргумента конструктора, напримерlad_vector vec( (int*)alloca(10 * sizeof(int)), 10 );. Возможно, сделайте для этого макрос (но не встроенную функцию), чтобы получить синтаксис типаlad_vector vec = MAKE_LADVECTOR(10);- person tmlen schedule 04.04.2016