Pourquoi le Quicksort parallèle GNU est-il si lent par rapport à Mergesort?

Question

J'ai testé la praticité des algorithmes de tri parallèle OpenMP GNU dans la bibliothèque standard C++ et j'ai trouvé que l'algorithme Quicksort parallèle était significativement plus lent que l'algorithme Mergesort. Sur mon PC, Mergesort prendrait 52 secondes pour trier un vecteur de 8 milliards d'entiers, tandis que Quicksort prendrait juste un peu moins de 8 minutes. L'inspection non scientifique de son utilisation de CPU a montré que le quicksort a fait un usage complet du parallélisme pendant environ 20 secondes et que le reste de son exécution a juste utilisé 2 threads (ou% 200 CPU). J'ai vérifié le code source de l'algorithme et, bien que je ne comprenais pas tout. Si ce n'est pas la raison, quelqu'un pourrait peut-être m'expliquer pourquoi l'algorithme est si lent par rapport au mergesort? J'avais pensé à contacter l'auteur original de l'algorithme, mais je l'ai considéré comme un moyen de tenter ici d'abord.

Voici un code qui, espérons-le, montre le problème, vous pouvez spécifier sur la ligne de commande le nombre d'éléments à trier si vous n'avez pas des quantités démesurées de ressources requises pour mon exécution. J'utilise GCC 4.9:

#include <vector> 
#include <parallel/algorithm> 
#include <boost/date_time.hpp> 
#include <stdlib.h> 
#include <iostream> 
#include <omp.h> 
#include <sstream> 

const size_t DEFAULT_NUMBER = 8000000000; 
int main(int argc, char **argv) 
{ 
    size_t number_of_elements = DEFAULT_NUMBER; 
    if(argc > 1 && argv[1] != 0) 
    { 
     number_of_elements = atoi(argv[1]); 
    } 
    std::vector<int> elements(number_of_elements); 
    srandom(10); 
    for(size_t i = 0; i < elements.size(); i++) 
    { 
     elements[i] = random(); 
    } 

    boost::posix_time::ptime time = boost::posix_time::second_clock::local_time(); 
    __gnu_parallel::sort(elements.begin(), elements.end(), __gnu_parallel::multiway_mergesort_tag()); 
    std::cout << "Mergesort took: " << boost::posix_time::to_simple_string(boost::posix_time::second_clock::local_time() - time) << std::endl; 

    //Repopulate vector with random elements 
    srandom(10); 
    for(size_t i = 0; i < elements.size(); i++) 
    { 
     elements[i] = random(); 
    } 
    time = boost::posix_time::second_clock::local_time(); 
    __gnu_parallel::sort(elements.begin(), elements.end(), __gnu_parallel::quicksort_tag()); 
    std::cout << "Quicksort took: " << boost::posix_time::to_simple_string(boost::posix_time::second_clock::local_time() - time) << std::endl; 
} 

Answer 1

S'il vous plaît lire this. Je Options:

CFLAGS += -fopenmp -Ofast -march=native 

Ils accélèrent votre test, mais désolé de dire que je n'ai pas assez de carottes pour reproduire vos résultats. Quoi qu'il en soit, autoriser les opérations natives du processeur devrait affecter la sérialisation de l'accès aux données.