Оптимизация C ++ 2-D массивов

Question

Мне нужен способ представления двумерного массива (плотной матрицы) двойных чисел в C ++ с абсолютным минимумом доступа к накладным расходам.

Я провел некоторое время на разных машинах linux / unix и версиях gcc. Вектор STL векторов, объявленный как:

vector<vector<double> > matrix(n,vector<double>(n));

и доступ через matrix[i][j] происходит на 5-100% медленнее, чем для массива, объявленного как:

double *matrix = new double[n*n];

доступ через встроенную индексную функцию matrix[index(i,j)], где index(i,j) оценивается как i + n * j. Другие способы размещения двумерного массива без STL - массив из n указателей на начало каждой строки или определение всего элемента в стеке как постоянного размера matrix[n][n] - работают почти с той же скоростью, что и индекс Функциональный метод.

Недавние версии GCC (> 4.0), по-видимому, способны компилировать вектор-векторы STL почти с той же эффективностью, что и код без STL, когда оптимизация включена, но это в некоторой степени зависит от машины.

Я бы хотел использовать STL, если это возможно, но мне придется выбрать самое быстрое решение. У кого-нибудь есть опыт оптимизации STL с GCC?

Answer 1

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

-fipa-matrix-reorg

Выполнить матричное выравнивание и транспонирование. Матрица сплющивания пытается заменить m-мерную матрицу его эквивалентная n-мерная матрица, где n <м. Это снижает уровень косвенное обращение, необходимое для доступа к элементы матрицы. Второй оптимизация - это транспонирование матрицы который пытается изменить порядок размеры матрицы для того, чтобы улучшить локальность кэша. И то и другое Оптимизация требует FWhole-программы флаг. Транспонирование включено только если информация профилирования доступна. </p>

Обратите внимание, что эта опция не включена -O2 или -O3. Вы должны пройти его самостоятельно.

Answer 2

Я полагаю, что для матрицы быстрее всего будет использовать массив 1D STL и переопределить оператор (), чтобы использовать его в качестве 2D-матрицы.

Однако STL также определяет тип специально для числовых массивов без возможности изменения размера: valarray. У вас также есть различные оптимизации для операций на месте.

valarray принимает в качестве аргумента числовой тип:

valarray<double> a;

Затем вы можете использовать слайсы, косвенные массивы и ... и, конечно, вы можете наследовать valarray и определить свой собственный оператор () (int i, int j) для 2D массивов ...

Answer 3

Скорее всего, это проблема месторасположения. vector использует new для выделения своего внутреннего массива, поэтому каждая строка будет хотя бы немного разнесена в памяти из-за заголовка каждого блока; это может быть на большом расстоянии друг от друга, если память уже фрагментирована, когда вы выделяете их. Разные строки массива могут, по крайней мере, вызвать ошибку строки кэша и могут вызвать ошибку страницы; если вам действительно не повезло, две соседние строки могут быть в строках памяти, которые совместно используют слот TLB, и доступ к одной из них вытеснит другую.

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

vector предназначен для изменяемых размеров массивов. Если вам не нужно изменять размер массивов, используйте обычный массив C ++. Операции STL обычно могут работать с массивами C ++.

Обязательно перемещайте массив в правильном направлении, то есть поперек (последовательные адреса памяти), а не вниз. Это уменьшит ошибки кеша.

Answer 4

Рекомендую использовать Boost.UBLAS, который обеспечивает быстрые классы матрицы / вектора.

Answer 5

Вы можете посмотреть библиотеку шаблонов Eigen C ++ по адресу http://eigen.tuxfamily.org/. Он генерирует код AltiVec или sse2 для оптимизации вычислений вектора / матрицы.

Answer 6

Вы можете так же легко сделать vector (n * m);

Answer 7

Чтобы быть справедливым, зависит от алгоритмов, которые вы используете на матрице.

Формат двойного имени [n * m] очень быстр, когда вы обращаетесь к данным по строкам, потому что он почти не имеет служебных данных, кроме умножения и сложения, и потому что ваши строки представляют собой упакованные данные, которые будут согласованы в кэше.

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

Попытайтесь провести какое-то исследование, направленное на тип использования и алгоритмы, которые вы используете. Это особенно важно, если матрица очень велика, поскольку ошибки в кеше могут снизить производительность, а не 1 или 2 дополнительные математические операции для доступа к каждому адресу.

Answer 8

Я сделал это некоторое время назад для необработанных изображений, объявив свои собственные 2-мерные классы массивов.

В обычном 2D-массиве вы получаете доступ к таким элементам, как:

Массив [2] [3]. Теперь, чтобы получить этот эффект, у вас будет массив классов с перегруженным [] Массив доступа. Но это по существу вернет другой массив, тем самым давая Вы второе измерение.

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

То, как я это сделал, было использовать перегрузку стиля ().

Так что вместо массив [2] [3], изменить, я сделал это сделать этот массив стилей (2,3).

Эта функция () была очень маленькой, и я позаботился о том, чтобы она была встроенной.

См. Эту ссылку для общей концепции этого: http://www.learncpp.com/cpp-tutorial/99-overloading-the-parenthesis-operator/

При необходимости вы можете создать шаблон типа.
Разница у меня была в том, что мой массив был динамическим. У меня был блок памяти чар, который я бы объявил. И я использовал кеш столбцов, поэтому я знал, где в моей последовательности байтов начинается следующий ряд. Доступ был оптимизирован для доступа к соседним значениям, потому что я использовал его для обработки изображений.

Трудно объяснить без кода, но по сути результат был таким же быстрым, как C, и намного проще для понимания и использования.

Answer 9

Другая связанная библиотека - Blitz ++: http://www.oonumerics.org/blitz/docs/blitz.html

Blitz ++ предназначен для оптимизации работы с массивами.

Answer 10

В Boost есть реализация uBLAS. Это стоит посмотреть.

http://www.boost.org/doc/libs/1_36_0/libs/numeric/ublas/doc/matrix.htm