Оптимизация двумерных массивов C++
Мне нужен способ представить двумерный массив (плотную матрицу) двойников в 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?
Ответы 10
Я предполагаю, что самым быстрым для матрицы будет использование одномерного массива STL и переопределение оператора (), чтобы использовать его как двухмерную матрицу.
Однако STL также определяет тип специально для числовых массивов без изменения размера: valarray. У вас также есть различные оптимизации для операций на месте.
valarray принимает в качестве аргумента числовой тип:
valarray<double> a;
Затем вы можете использовать срезы, косвенные массивы ... и, конечно же, вы можете унаследовать valarray и определить свой собственный operator () (int i, int j) для 2D-массивов ...
Осторожное наследование от std :: valarray; он не предназначен для наследования, как большая часть «STL».
Вы можете наследовать любой класс STL до тех пор, пока вы не добавляете в них данные, поскольку конструктор не будет вызываться. Однако нет никаких методов добавления pb.
Вы можете наследовать классы «не предназначенные для наследования», если вы используете наследование частный, если я правильно понимаю. например, матрица классов: private std :: valarray <double> или подобное. По сути, вы не полагаетесь ни на какое виртуальное поведение.
Однако публичное или защищенное наследование классов, не предназначенных для наследования, недопустимо.
Я не согласен с последним утверждением. Проблема с классами, не предназначенными для наследования, заключается в том, что деструктор не является виртуальным => производный деструктор может не вызываться. Таким образом, никакая переменная, выделенная в производном классе, не будет освобождена => вы не должны добавлять никаких переменных.
Обратите внимание, что даже если вы не добавляете данные члена, удаление производного объекта с помощью указателя на базовый тип является неопределенным поведением, если деструктор невиртуален.
Однако, если вы наследуете поведение, а не указание / апкастинг, это не будет проблемой. Однако для таких целей композиция работает лучше (за исключением необходимости повторно декларировать весь интерфейс класса).
@Iraimbilanja - Откуда ты это взял? Очевидно, что, поскольку деструктор листового класса не будет вызываться, там ничего делать не должно. Это означает: ни виртуальных методов, ни членов. Иначе не вижу проблемы.
Я бы рекомендовал использовать Boost.UBLAS, который предоставляет быстрые классы матриц / векторов.
Я должен был пояснить, что пока я имею дело с матрицами, выполняемые мной операции не являются типичной линейной алгеброй. UBLAS выглядит очень хорошо для линейной алгебры, но, возможно, излишний, если я использую его только как хранилище 2D-массивов.
Я пробовал различные библиотеки линейной алгебры для использования в качестве 2-мерных данных (карт), но они неудобны для использования в целях нелинейной алгебры и не быстрее, чем вектор векторов. UBLAS (и другие) быстр только для умножения и других «типичных» матриц, а не для доступа.
Скорее всего, это проблема местонахождения справки. vector использует new для выделения своего внутреннего массива, поэтому каждая строка будет хотя бы немного обособлена в памяти из-за заголовка каждого блока; они могут быть на большом расстоянии друг от друга, если память уже фрагментирована, когда вы их распределяете. Различные строки массива, вероятно, по крайней мере вызовут сбой строки кэша и могут вызвать сбой страницы; если вам действительно не повезло, две соседние строки могут быть на линиях памяти, которые разделяют слот TLB, и доступ к одной приведет к вытеснению другой.
Напротив, ваши другие решения гарантируют, что все данные смежны. Это может улучшить вашу производительность, если вы выровняете структуру, чтобы она пересекала как можно меньше строк кеша.
vector предназначен для массивов изменяемый размер. Если вам не нужно изменять размер массивов, используйте обычный массив C++. Операции STL обычно могут работать с массивами C++.
Обязательно перемещайтесь по массиву в правильном направлении, то есть через (последовательные адреса памяти), а не вниз. Это уменьшит количество ошибок кеша.
Я не думал о заголовках блоков в векторном решении. Я знал о потенциальном замедлении ходьбы из-за неправильной ходьбы: мои тесты скорости показывают, что неправильная ходьба может быть в четыре раза медленнее, чем правильная!
Если вы используете GCC, компилятор может анализировать доступ к вашей матрице и в некоторых случаях изменять порядок в памяти. Флаг компилятора magic определяется как:
-fipa-matrix-reorg
Perform matrix flattening and transposing. Matrix flattening tries to replace a m-dimensional matrix with its equivalent n-dimensional matrix, where n < m. This reduces the level of indirection needed for accessing the elements of the matrix. The second optimization is matrix transposing that attemps to change the order of the matrix's dimensions in order to improve cache locality. Both optimizations need fwhole-program flag. Transposing is enabled only if profiling information is avaliable.
Обратите внимание, что эта опция не включена -O2 или -O3. Вы должны пройти это сами.
Было бы действительно удивительно и страшно.
Честно говоря, это зависит от алгоритмов, которые вы используете для матрицы.
Формат двойного имени [n * m] очень быстр, когда вы обращаетесь к данным по строкам, потому что почти не имеет накладных расходов, кроме умножения и сложения, и потому, что ваши строки представляют собой упакованные данные, которые будут согласованы в кеше.
Если ваши алгоритмы обращаются к данным, упорядоченным по столбцам, то другие макеты могут иметь гораздо лучшую согласованность кеша. Если ваш алгоритм обращается к данным в квадрантах матрицы, даже другие макеты могут быть лучше.
Попробуйте провести небольшое исследование, направленное на тип использования и алгоритмы, которые вы используете. Это особенно важно, если матрица очень большая, поскольку промахи в кеше могут повредить вашей производительности больше, чем необходимость 1 или 2 дополнительных математических операций для доступа к каждому адресу.
Вы могли бы так же легко сделать vector <double> (n * m);
В Boost есть реализация uBLAS. Стоит посмотреть.
http://www.boost.org/doc/libs/1_36_0/libs/numeric/ublas/doc/matrix.htm
Вы можете посмотреть библиотеку шаблонов Eigen C++ по адресу http://eigen.tuxfamily.org/. Он генерирует код AltiVec или sse2 для оптимизации векторных / матричных вычислений.
Другая связанная библиотека - Blitz ++: http://www.oonumerics.org/blitz/docs/blitz.html
Blitz ++ разработан для оптимизации работы с массивами.
Некоторое время назад я сделал это для необработанных изображений, объявив свои собственные классы двумерных массивов.
В обычном 2D-массиве вы получаете доступ к таким элементам, как:
массив [2] [3]. Теперь, чтобы получить этот эффект, у вас будет массив классов с перегруженным [] метод доступа к массиву. Но это, по сути, вернет другой массив, тем самым давая вы второе измерение.
Проблема с этим подходом состоит в том, что у него накладные расходы на двойной вызов функции.
Я использовал перегрузку стиля ().
Так что вместо array [2] [3], изменить я сделал это в стиле array (2,3).
Эта функция () была очень маленькой, и я убедился, что она встроена.
См. Эту ссылку для получения общей концепции этого: http://www.learncpp.com/cpp-tutorial/99-overloading-the-parenthesis-operator/
При необходимости вы можете создать шаблон типа. Разница была в том, что мой массив был динамическим. Я объявил, что у меня был блок символьной памяти. И я использовал кеш столбцов, поэтому я знал, где в моей последовательности байтов начинается следующая строка. Доступ был оптимизирован для доступа к соседним значениям, потому что я использовал его для обработки изображений.
Трудно объяснить без кода, но, по сути, результат был таким же быстрым, как и C, и его было намного проще понять и использовать.
Мое голосование за valarray, не обязательно для создания пользовательского типа матрицы. Ну, настраиваемый тип матрицы может работать, но все равно должен основываться на valarray вместо вектора (valarray поддерживает нарезку, что делает получение столбца таким же простым, как получение строки).