Performances de qsort vs std :: sort?

Selon Scott Meyers, dans son livre intitulé Effective STL – item 46. Il a affirmé que std::sort est environ 670% plus rapide que std::qsort raison du fait de l’inline. Je me suis testé, et j’ai vu que qsort est plus rapide :(! Quelqu’un pourrait-il m’aider à expliquer ce comportement étrange?

 #include  #include  #include  #include  #include  #include  const size_t LARGE_SIZE = 100000; struct rnd { int operator()() { return rand() % LARGE_SIZE; } }; int comp( const void* a, const void* b ) { return ( *( int* )a - *( int* )b ); } int main() { int ary[LARGE_SIZE]; int ary_copy[LARGE_SIZE]; // generate random data std::generate( ary, ary + LARGE_SIZE, rnd() ); std::copy( ary, ary + LARGE_SIZE, ary_copy ); // get time std::time_t start = std::clock(); // perform quick sort C using function pointer std::qsort( ary, LARGE_SIZE, sizeof( int ), comp ); std::cout << "C quick-sort time elapsed: " << static_cast( clock() - start ) / CLOCKS_PER_SEC << "\n"; // get time again start = std::clock(); // perform quick sort C++ using function object std::sort( ary_copy, ary_copy + LARGE_SIZE ); std::cout << "C++ quick-sort time elapsed: " << static_cast( clock() - start ) / CLOCKS_PER_SEC << "\n"; } 

Ceci est mon résultat:

 C quick-sort time elapsed: 0.061 C++ quick-sort time elapsed: 0.086 Press any key to continue . . . 

Mettre à jour

3e édition effective du STL (2001)
Chapitre 7 Programmation avec STL
Rubrique 46: Considérons les objects de fonction au lieu de fonctions comme parameters d’algorithme.

Meilleures salutations,

std :: clock () n’est pas une horloge de synchronisation viable. Vous devez utiliser une horloge haute résolution spécifique à la plate-forme, comme le minuteur haute performance Windows. De plus, la façon dont vous appelez clock () est que le texte est d’abord envoyé à la console, qui est inclus dans le temps. Cela invalide définitivement le test. De plus, assurez-vous d’avoir compilé avec toutes les optimisations.

Enfin, j’ai copié et collé votre code et obtenu 0,016 pour qsort et 0,008 pour std :: sort.

Je suis surpris que personne ne mentionne les caches.

Dans votre code, vous commencez par toucher ary et * ary_copy * pour qu’ils résident dans le cache au moment de qsort . Au cours de qsort , * ary_copy * peut être expulsé. Au moment de std :: sort , les éléments devraient être récupérés de la mémoire ou d’un niveau de cache plus grand (lecture plus lente ). Cela dépendra bien sûr de la taille de votre cache.

Essayez d’inverser le test, c.-à-d., Commencez par exécuter std :: sort .

Comme certaines personnes l’ont fait remarquer; agrandir le tableau rendra le test plus équitable. La raison en est qu’un grand tableau est moins susceptible de tenir dans le cache.

Les deux algorithmes de sorting, sans optimisations activées, devraient avoir des performances comparables. La raison pour laquelle le sort C ++ a tendance à battre de manière appréciable qsort est que le compilateur peut aligner les comparaisons en cours, car le compilateur dispose d’informations de type sur la fonction utilisée pour effectuer la comparaison. Avez-vous exécuté ces tests avec l’optimisation activée? Sinon, essayez de l’allumer et relancez ce test.

Une autre raison pour laquelle qsort peut être plus performant que prévu est que les compilateurs les plus récents peuvent être intégrés et optimisés via le pointeur de fonction.

Si l’en-tête C définit une implémentation en ligne de qsort au lieu de l’implémenter dans une bibliothèque et que le compilateur prend en charge l’inlining de fonctions indirectes, alors qsort peut être aussi rapide que std :: sort.

Sur ma machine en ajoutant de la viande (en faisant le tableau 10 millions d’éléments et en la déplaçant dans la section des données) et en compilant avec

 g++ -Wall -O2 -osortspeed sortspeed.cpp 

Je reçois comme résultat

 C quick-sort time elapsed: 3.48 C++ quick-sort time elapsed: 1.26 

Faites également attention aux CPU “verts” modernes qui peuvent être configurés pour fonctionner à une vitesse variable en fonction de la charge du système. Lors de l’parsing comparative, ce type de comportement peut vous rendre fou (sur ma machine, j’ai configuré deux petits scripts normal et fast que je peux utiliser pour faire des tests de vitesse).

Ecrire des repères précis est difficile, alors allons-y avec Nonius ! Testons qsort , std::sort sans inlining et std::sort avec inlining (valeur par défaut) sur un vecteur de millions d’entiers aléatoires.

 // sort.cpp #define NONIUS_RUNNER #include  #include  #include  // qsort int comp(const void* a, const void* b) { const int arg1 = *static_cast(a); const int arg2 = *static_cast(b); // we can't simply return a - b, because that might under/overflow return (arg1 > arg2) - (arg1 < arg2); } // std::sort with no inlining struct compare_noinline { __attribute__((noinline)) bool operator()(const int a, const int b) { return a < b; } }; // std::sort with inlining struct compare { // the compiler will automatically inline this bool operator()(const int a, const int b) { return a < b; } }; std::vector gen_random_vector(const size_t size) { std::random_device seed; std::default_random_engine engine{seed()}; std::uniform_int_dissortingbution dist{std::numeric_limits::min(), std::numeric_limits::max()}; std::vector vec; for (size_t i = 0; i < size; i += 1) { const int rand_int = dist(engine); vec.push_back(rand_int); } return vec; } // generate a vector of a million random integers constexpr size_t size = 1'000'000; static const std::vector rand_vec = gen_random_vector(size); NONIUS_BENCHMARK("qsort", [](nonius::chronometer meter) { // Nonius does multiple runs of the benchmark, and each one needs a new // copy of the original vector, otherwise we'd just be sorting the same // one over and over const size_t runs = static_cast(meter.runs()); std::vector> vectors{runs}; std::fill(vectors.begin(), vectors.end(), rand_vec); meter.measure([&](const size_t run) { std::vector& current_vec = vectors[run]; std::qsort(current_vec.data(), current_vec.size(), sizeof(int), comp); return current_vec; }); }); NONIUS_BENCHMARK("std::sort noinline", [](nonius::chronometer meter) { const size_t runs = static_cast(meter.runs()); std::vector> vectors{runs}; std::fill(vectors.begin(), vectors.end(), rand_vec); meter.measure([&](const size_t run) { std::vector& current_vec = vectors[run]; std::sort(current_vec.begin(), current_vec.end(), compare_noinline{}); return current_vec; }); }); NONIUS_BENCHMARK("std::sort inline", [](nonius::chronometer meter) { const size_t runs = static_cast(meter.runs()); std::vector> vectors{runs}; std::fill(vectors.begin(), vectors.end(), rand_vec); meter.measure([&](const size_t run) { std::vector& current_vec = vectors[run]; std::sort(current_vec.begin(), current_vec.end(), compare{}); return current_vec; }); }); 

Comstackr avec Apple Clang 7.3.0,

 $ clang++ -std=c++14 -stdlib=libc++ -O3 -march=native sort.cpp -o sort $ ./sort 

et le faire fonctionner sur mon Macbook Air i5 1,7 GHz, nous obtenons

 qsort 211 ms +/- 6 ms std::sort noinline 127 ms +/- 5 ms std::sort inline 87 ms +/- 4 ms 

Ainsi, std::sort sans incrustation est environ 1,7 fois plus rapide que qsort (peut-être en raison d’algorithmes de sorting différents) et l’inclusion de bosses jusqu’à environ 2,4 fois plus rapide. Certainement une accélération impressionnante, mais beaucoup moins que 670%.

Je ne sais pas comment std :: sort a été mis en œuvre il y a des années. Mais std :: sort peut être beaucoup plus rapide, car std :: sort est quicksort avec un repli de sorting de tas. Heapsort est un algorithme linéaire, ce qui signifie que si vous avez deux fois les données de sorting, le temps de sorting double. En fait, cela fait plus que doubler car ce n’est pas exactement linéaire, mais cependant, qsort peut être quadratique, nécessitant donc plus de temps exponentiel pour sortinger deux fois plus l’entrée.