Почему Eigen в 5 раз медленнее, чем ublas на следующем примере?

В версии Eigen я использую «настоящие» матрицы и векторы фиксированного размера, лучший алгоритм (LDLT по сравнению с LU в uBlas), он использует внутри SIMD-инструкции. Итак, почему он медленнее, чем uBlas на следующем примере?

Я уверен, что делаю что-то не так - Eigen ДОЛЖЕН быть быстрее или, по крайней мере, сопоставимым.

#include <boost/numeric/ublas/matrix.hpp>
#include <boost/numeric/ublas/vector.hpp>
#include <boost/numeric/ublas/lu.hpp>
#include <boost/numeric/ublas/symmetric.hpp>
#include <boost/progress.hpp>
#include <Eigen/Dense>
#include <iostream>

using namespace boost;
using namespace std;
const int n=9;
const int total=100000;

void test_ublas()
{
    using namespace boost::numeric::ublas;
    cout << "Boost.ublas ";
    double r=1.0;
    {
        boost::progress_timer t;
        for(int j=0;j!=total;++j)
        {
            //symmetric_matrix< double,lower,row_major,bounded_array<double,(1+n)*n/2> > A(n,n);
            matrix<double,row_major,bounded_array<double,n*n> > A(n,n);
            permutation_matrix< unsigned char,bounded_array<unsigned char,n> > P(n);
            bounded_vector<double,n> v;
            for(int i=0;i!=n;++i)
                for(int k=0;k!=n;++k)
                    A(i,k)=0.0;
            for(int i=0;i!=n;++i)
            {
                A(i,i)=1.0+i;
                v[i]=i;
            }
            lu_factorize(A,P);
            lu_substitute(A,P,v);
            r+=inner_prod(v,v);
        }
    }
    cout << r << endl;
}

void test_eigen()
{
    using namespace Eigen;
    cout << "Eigen ";
    double r=1.0;
    {
        boost::progress_timer t;
        for(int j=0;j!=total;++j)
        {
            Matrix<double,n,n> A;
            Matrix<double,n,1> b;
            for(int i=0;i!=n;++i)
            {
                A(i,i)=1.0+i;
                b[i]=i;
            }
            Matrix<double,n,1> x=A.ldlt().solve(b);
            r+=x.dot(x);
        }
    }
    cout << r << endl;
}

int main()
{
    test_ublas();
    test_eigen();
}

Выход:

Boost.ublas 0.50 s

488184
Eigen 2.66 s

488184

(Выпуск Visual Studio 2010 x64)


ИЗМЕНИТЬ:

Для

const int n=4;
const int total=1000000;

Выход:

Boost.ublas 0.67 s

1.25695e+006
Eigen 0.40 s

5.4e+007

Я предполагаю, что такое поведение связано с тем, что версия uBlas вычисляет факторизацию на месте, а версия Eigen создает COPY матрицы (LDLT) - поэтому она хуже подходит для кеша.

Есть ли способ выполнить вычисления на месте в Eigen? Или, может быть, есть другие способы улучшить его?


ИЗМЕНИТЬ:

Следуя совету Февеза и используя LLT вместо LDLT, я получаю:

Eigen 0.16 s

488184

Это хорошо, но все еще делает ненужное выделение стека матриц:

sizeof(A.llt()) == 656

Я предпочитаю избегать этого - это должно быть еще быстрее.


ИЗМЕНИТЬ:

Я удалил выделение, создав подкласс из LDLT (его внутренняя матрица защищена) и заполнив его напрямую. Теперь результат для LDLT:

Eigen 0.26 s
488209

Это работает, но это обходной путь - не настоящее решение...

Наследование от LLT тоже работает, но не дает такого большого эффекта.


person qble    schedule 14.11.2012    source источник


Ответы (2)


Ваш бенчмарк не справедлив, потому что версия ublas решается на месте, а версию Eigen можно легко настроить для этого:

b=A.ldlt().solve(b);
r+=b.dot(b);

При компиляции с помощью g++-4.6 -O2 -DNDEBUG я получаю (на процессоре 2,3 ГГц):

Boost.ublas 0.15 s
488184

Eigen 0.08 s
488184

Также убедитесь, что вы скомпилировали с включенной оптимизацией и включенным SSE2, если вы используете 32-битную систему или (32-битную цепочку компиляции).

РЕДАКТИРОВАТЬ: я также пытался избежать копирования матрицы, но это вообще приводит к нулевому усилению.

Также, увеличивая n, увеличиваем разницу скоростей (здесь n=90):

Boost.ublas 0.47 s
Eigen 0.13 s
person ggael    schedule 15.11.2012
comment
версию можно легко настроить для этого - есть лучшая альтернатива этому -solveInPlace. Но все дело в векторах в уравнениях, а не в Матрице, так что это вообще не влияет. Также убедитесь, что вы скомпилировали с включенной оптимизацией - да, я проверил это: 1) Я использую x64 - sse включен по умолчанию, 2) Я пытался даже явно включить sse - тот же результат. Компиляция с помощью g++ - вопрос был о MSVC 2010. - person qble; 15.11.2012
comment
Я также пытался избежать матричного копирования, но это приводит к нулевому усилению. - как именно ты это сделал? По подклассам? Также, увеличивая n, увеличивайте разницу в скорости (здесь n=90): - такое увеличение бессмысленно в контексте данного вопроса. Когда вы увеличиваете N до таких довольно высоких чисел, сложность самого решения начинает доминировать O (N ^ 3). В то время как при N = 9 - я достигаю некоторых границ кеша в случае Eigen, и это влияет на производительность. - person qble; 15.11.2012
comment
Что ж, 2,66 с с MSVC и 0,08 с с GCC для одного и того же кода означает, что проблема в компиляторе, а не в коде Eigen. Как правило, такие накладные расходы вызваны плохим встраиванием. Огромное ускорение, которое вы получили при создании подклассов LDLT, показывает, что ваши модификации помогли MSVC создать лучший код. Если бы вы могли прислать мне ASM, сгенерированный для исходного кода, мы могли бы определить точную проблему и устранить ее выше по течению. Ваши модификации тоже могут быть интересны - person ggael; 15.11.2012
comment
Что ж, 2,66 с с MSVC и 0,08 с с GCC для одного и того же кода означает, что проблема в компиляторе, а не в коде Eigen — некоторые компиляторы могут оптимизировать более агрессивно, чем другие. Однако в данном конкретном случае в библиотеке есть все средства, чтобы избежать лишнего копирования, не полагаясь на мощный оптимизатор. Нужна только операция факторизации, позволяющая модифицировать исходную матрицу - вот и все, Boost.uBlas делает именно это, мои модификации тоже делают то же самое. Пока Эйген копирует матрицу: m_matrix = a; - вот в чем проблема, ее можно определить без проверки ASM. - person qble; 15.11.2012
comment
Извините за настойчивость, но нет, эта копия не является источником падения производительности: 1) я вижу, что эта копия не оптимизирована GCC, и с gcc нет замедления; 2) решатель LLT тоже выполняет копирование, но вы не заметили подтормаживаний в случае с LLT; 3) вы утверждаете, что дополнительная операция O (n ^ 2) может объяснить 10-кратное замедление операции O (n ^ 3), что не имеет смысла; 4) Матрицы 9x9, размещенные в стеке, слишком малы, чтобы уличать промахи в кэше. - person ggael; 15.11.2012
comment
1) некоторые другие вещи могут быть оптимизированы, он может использовать лучшую компоновку стека и т. д. 2) LLT использует меньше данных - просто копия матрицы, но LDLT использует дополнительные данные и размер больше, просто проверьте источник. Когда модифицирую llt struct, добавляя дополнительные данные - тоже тормозит. 3) Я не утверждаю, что сама операция копирования является проблемой, я говорю, что проблема заключается в размещении памяти, а не в самом копировании (когда я увеличил размер структуры LLT - не было никакой операции копирования, просто изменение размера необработанных данных). 4) мое изменение LDLT, которое делает его намного быстрее, касалось выполнения вычислений на месте, т.е. удалить один аллок - person qble; 15.11.2012

Я последовал вашей подсказке о вычислении на месте:

Используя точно такой же код и используя функции A.llt().solveInPlace(b); и A.ldlt().solveInPlace(b); (которые заменяют b на x), я получил это

There were  100000  Eigen standard LDLT linear solvers applied in  12.658  seconds 
There were  100000  Eigen standard LLT linear solvers applied in  4.652  seconds 

There were  100000  Eigen in place LDLT linear solvers applied in  12.7  seconds 
There were  100000  Eigen in place LLT linear solvers applied in  4.396  seconds 

Возможно, решатель LLT просто больше подходит для такого рода задач, чем решатель LDLT? (Я вижу, что вы имеете дело со своими матрицами размера 9)

(Кстати, я немного ответил на предыдущий вопрос, который у вас был о вашем линейном решателе в измерении 9, и мне очень грустно видеть, что реализация Eigen LDLT имеет много накладных расходов...)

person B. Decoster    schedule 14.11.2012
comment
solveInPlace просто использует вектор на месте, а не матрицу на месте. Матрица все еще выделена. - person qble; 14.11.2012
comment
Да, но я хотел сказать вам, что я последовал вашему совету о решении на месте. Конечно, я был разочарован, прочитав, что он просто заменил b вместо того, чтобы делать какие-то действия с матрицей на месте, но я все же попытался. И я наткнулся на другой результат, а именно, что LLT кажется лучше, чем LDLT для этой конкретной проблемы =) - person B. Decoster; 14.11.2012
comment
Мне очень грустно видеть, что реализация LDLT в Eigen имеет много накладных расходов - мне также грустно это видеть, я рекомендовал Eigen многим людям. - person qble; 14.11.2012
comment
Я обхожу распределение стека, и теперь делаю LDLT на месте - теперь Eigen в 2 раза быстрее, чем uBlas, проверьте редактирование внизу вопроса. - person qble; 14.11.2012