Performances de qsort vs std :: sort?

Question

Selon Scott Meyers, dans sa Effective STL livre - l'article 46. Il a affirmé qu' std::sort est d'environ 670% plus rapide que l' std::qsort en raison du fait de la ligne. Je l'ai testé moi-même, et j'ai vu que qsort est plus rapide :( ! Quelqu'un pourrait-il m'aider à expliquer ce comportement étrange?

#include <iostream>
#include <vector>
#include <algorithm>

#include <cstdlib>
#include <ctime>
#include <cstdio>

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<double>( 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<double>( clock() - start ) / CLOCKS_PER_SEC << "\n";
}

C'est mon résultat:

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

Mise à jour

Efficace STL 3e Édition ( 2001 )
Chapitre 7 la Programmation avec le TSL
Article 46: Considérons la fonction des objets à la place des fonctions des paramètres de l'algorithme.

Meilleures salutations,

Answer 1

std :: clock () n'est pas une horloge de temps viable. Vous devez utiliser un minuteur de résolution supérieure spécifique à la plate-forme, tel que le minuteur haute performance de Windows. Plus que cela, la façon dont vous appelez clock () est la suivante: le texte est envoyé à la console, qui est incluse dans l'heure. Cela invalide définitivement le test. De plus, assurez-vous d'avoir compilé toutes les optimisations.

Enfin, j'ai copié et collé votre code, et obtenu 0.016 pour qsort et 0.008 pour std :: sort.

Answer 2

Je suis surpris que personne ne parle de caches.

Dans votre code, vous commencez par toucher ary et *ary_copy* afin qu'ils résident dans le cache au moment de qsort. Au cours de qsort, *ary_copy* on peut obtenir des expulsés. Au moment de std::sort, les éléments doivent être récupérées à partir de la mémoire ou un plus grand (lire plus lent) niveau de cache. Cela dépendra de votre taille de cache.

Essayez d'inverser le test, c'est à dire, commencer par exécuter std::sort.

Comme certaines personnes l'ont souligné; rendre le tableau plus permettra de rendre le test plus juste. La raison en est qu'un grand tableau est moins susceptible de place dans le cache.

Answer 3

Les deux algorithmes de tri, sans optimisation activée, devraient avoir des performances comparables. La raison pour laquelle le C ++ sort tend à battre sensiblement qsort est que le compilateur peut intégrer les comparaisons en cours, car il dispose d'informations de type sur la fonction utilisée pour effectuer la comparaison. . Avez-vous exécuté ces tests avec optimisation activée? Sinon, essayez de l'activer et de relancer ce test.

Answer 4

Une autre raison pour laquelle qsort peut fonctionner beaucoup mieux que prévu est que les nouveaux compilateurs peuvent s'inscrire en ligne et optimiser via le pointeur de la fonction.

Si l'en-tête C définit une implémentation inline de qsort au lieu de l'implémenter à l'intérieur d'une bibliothèque et que le compilateur prend en charge l'inline line, alors qsort peut être aussi rapide que std :: sort.

Answer 5

std::clock n'est pas assez précise pour l'analyse comparative. Vous devez utiliser la haute résolution de la performance des minuteries disponible pour votre plate-forme (QueryPerformanceCounter sur Windows, vous ne savez pas POSIX) afin d'obtenir des résultats significatifs ici.

L'autre problème, std::clock,, c'est que même si c'était fiable à 100%, si le processus n'est plus actif sur la machine (c'est à dire il y a eu un changement de contexte), qui n'est pas comptabilisé dans les tests.

Scott Meyers mesures ne sont valables que pour la mise en oeuvre de la il a testé sur qui a effectué que mal. Il dit qu'il a testé sur plusieurs implémentations, et c'est tout à fait possible de faire la différence pour votre mise en œuvre est à moins de 600 pour cent.

Enfin, comme @templatetypedef a déclaré, significative de référence peuvent être effectuées uniquement avec la version (optimisations) construit.

EDIT: en Utilisant le code suivant:

#define _SCL_SECURE 0
#include <stdlib.h>
#include <ctime>
#include <algorithm>
#include <vector>
#include <iostream>
#include <windows.h>

//Shamelessly using Windows specific stuff here because we're benchmarking.

static const unsigned __int64 numInts = 100000000ull;

int qCmp(const void * a, const void * b)
{
    return *static_cast<const int *>(a) - *static_cast<const int *>(b);
}

int main()
{
    LARGE_INTEGER start, afterSort;
    std::vector<int> arrayToSort(numInts);
    std::srand(static_cast<unsigned int>(std::time(0)));
    std::generate_n(arrayToSort.begin(), numInts, std::rand);
    std::vector<int> arrayToQSort(arrayToSort);
    QueryPerformanceCounter(&start);
    std::qsort(&arrayToQSort[0], numInts, sizeof(int), qCmp);
    QueryPerformanceCounter(&afterSort);
    std::cout << "Qsort took     " << afterSort.QuadPart - 
        start.QuadPart << " ticks." << std::endl;
    QueryPerformanceCounter(&start);
    std::sort(arrayToSort.begin(), arrayToSort.end());
    QueryPerformanceCounter(&afterSort);
    std::cout << "std::sort took " << afterSort.QuadPart -
        start.QuadPart << " ticks." << std::endl;
}

Je reçois (sur un AMD Athlon II "Regor" overclocké à 3.5 GHZ Windows 7 Ultimate):

c:\Users\Billy\Documents\Visual Studio 2010\Projects\Test\x64\Release>Test.exe
Qsort a pris 28849379 les tiques.
std::sort a eu 21859763 les tiques.

une victoire pour std::sort, mais nulle part près de l'stipulé de 600 pour cent.

C'est bien sûr sans même discuter les autres avantages de l' std::sort sur qsort, comme la capacité de manière fiable de tri non POD types, la sélection automatique d'un définis par l'utilisateur operator< de surcharge, et le type de sécurité.

EDIT2: En réponse à @DeadMG:

int qCmp2(const void * a, const void * b)
{
    //This is what you'd have to do if you wanted to do it in terms of `operator<` --
    //qsort is almost half as fast as `std::sort` with this comparison function.
    int ac = *static_cast<const int *>(a);
    int bc = *static_cast<const int *>(b);
    if (ac < bc)
    {
        return -1;
    }
    else if (bc < ac)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}