Pourquoi la multiplication matricielle augmente-t-elle plus lentement que la mienne?

Question

J'ai mis en œuvre une multiplication de matrice avec boost::numeric::ublas::matrix (voir mon plein, travail code boost)

Result result = read ();

boost::numeric::ublas::matrix<int> C;
C = boost::numeric::ublas::prod(result.A, result.B);

et une autre avec l'algorithme standard (voir texte intégral de la norme de code):

vector< vector<int> > ijkalgorithm(vector< vector<int> > A, 
                                    vector< vector<int> > B) {
    int n = A.size();

    // initialise C with 0s
    vector<int> tmp(n, 0);
    vector< vector<int> > C(n, tmp);

    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            for (int j = 0; j < n; j++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return C;
}

C'est comment j'ai tester la vitesse:

time boostImplementation.out > boostResult.txt
diff boostResult.txt correctResult.txt

time simpleImplementation.out > simpleResult.txt
diff simpleResult.txt correctResult.txt

Les deux programmes de lecture codée en dur fichier texte qui contient deux 2000 x 2000 matrices. Les deux programmes ont été compilé avec les options suivantes:

g++ -std=c++98 -Wall -O3 -g $(PROBLEM).cpp -o $(PROBLEM).out -pedantic

J'ai eu 15 secondes pour ma mise en œuvre et de plus de 4 minutes pour le coup de pouce de la mise en œuvre!

edit: Après compilation avec

g++ -std=c++98 -Wall -pedantic -O3 -D NDEBUG -DBOOST_UBLAS_NDEBUG library-boost.cpp -o library-boost.out

J'ai eu 28.19 secondes pour le ikj-algorithme et 60.99 secondes pour Boost. Donc Boost est toujours beaucoup plus lent.

Pourquoi est-boost de manière beaucoup plus lente que ma mise en œuvre?

Answer 1

Le ralentissement des performances de l'uBLAS version peut être en partie expliqué par des fonctionnalités de débogage de ce dernier comme l'a souligné TJD.

Voici le temps pris par les uBLAS version de débogage sur:

real    0m19.966s
user    0m19.809s
sys     0m0.112s

Voici le temps pris par les uBLAS version de débogage off (-DNDEBUG -DBOOST_UBLAS_NDEBUG drapeaux du compilateur ajouté):

real    0m7.061s
user    0m6.936s
sys     0m0.096s

Donc, avec le débogage off, uBLAS version est presque 3 fois plus vite.

Restant différence de performance peut être expliqué, en citant l'article de uBLAS FAQ "Pourquoi est-uBLAS beaucoup plus lent que (atlas-)BLAS":

Un important objectif de la conception de ublas est d'être le plus général possible.

Cette généralité presque toujours un coût. En particulier, l' prod modèle de fonction peut gérer différents types de matrices, comme la creuse ou triangulaires. Heureusement uBLAS offre des alternatives optimisé pour les dense de multiplication de matrice, en particulier, axpy_prod et block_prod. Voici les résultats de la comparaison de différentes méthodes:

ijkalgorithm   prod   axpy_prod  block_prod
   1.335       7.061    1.330       1.278

Comme vous pouvez le voir les deux axpy_prod et block_prod sont un peu plus vite que votre mise en œuvre. Mesurant à peine le temps de calcul sans I/O, la suppression copie inutile et le choix de la taille de bloc pour block_prod (j'ai utilisé 64) peut faire la différence plus profonde.

Voir aussi uBLAS FAQ et Efficace uBlas générale et d'optimisation de code.

Answer 2

Je crois, votre compilateur n'optimisent pas assez. uBLAS code fait un usage intensif des modèles et des modèles nécessitent l'utilisation intensive des optimisations. J'ai couru votre code par MS VC 7.1 compilateur en mode release pour 1000x1000 matrices, il me donne

10.064s pour uBLAS

7.851s pour vecteur

La différence est toujours là, mais pas écrasante. uBLAS du concept de base est l'évaluation différée, alors prod(A, B) évalue les résultats uniquement lorsque cela est nécessaire, par exemple, prod(A, B)(10,100) exécutera en un rien de temps, puisque seulement qu'un élément sera effectivement calculé. En tant que tel il n'y a effectivement pas d'algorithme dédié pour l'ensemble de la matrice de multiplication qui pourrait être optimisée (voir ci-dessous). Mais vous pouvez aider à la bibliothèque un peu, déclarant

matrix<int, column_major> B;

permettra de réduire le temps d'exécution d' 4.426s qui bat votre fonction avec une main liée. Cette déclaration rend l'accès à la mémoire séquentielle lors de la multiplication des matrices, l'optimisation de l'utilisation du cache.

P. S. après Avoir lu uBLAS de la documentation à la fin ;), vous devriez avoir découvert qu'il y a en fait une fonction dédiée à multiplier l'ensemble des matrices à la fois. 2 fonctions - axpy_prod et opb_prod. Donc

opb_prod(A, B, C, true);

même sur unoptimized row_major B de la matrice exécute, en 8.091 s et est sur le pair avec votre vecteur de l'algorithme

P. P. S. Il n'y a même plus d'optimisations:

C = block_prod<matrix<int>, 1024>(A, B);

s'exécute en 4.4s, peu importe si B est column_ ou row_ majeur. D'examiner la description: "La fonction block_prod est conçu pour les grandes dense matrices." Choisir des outils spécifiques pour des tâches spécifiques!