Leistung von qsort vs std :: sort?

Laut Scott Meyers in seinem Buch Effective STL - Punkt 46. Er behauptete, dass dies std::sortetwa 670% schneller ist als std::qsortaufgrund der Tatsache der Inline. Ich habe mich selbst getestet und festgestellt, dass qsort schneller ist :(! Könnte mir jemand helfen, dieses seltsame Verhalten zu erklären?

#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";
}

Das ist mein Ergebnis:

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

Aktualisieren

Effektive STL 3rd Edition (2001)
Kapitel 7 Programmieren mit STL
Punkt 46: Betrachten Sie Funktionsobjekte anstelle von Funktionen als Algorithmusparameter.

Freundliche Grüße,

std :: clock () ist keine brauchbare Zeitschaltuhr. Sie sollten einen plattformspezifischen Timer mit höherer Auflösung verwenden, z. B. den Windows-Hochleistungstimer. Darüber hinaus wird beim Aufrufen von clock () zunächst Text an die Konsole ausgegeben, die in der Uhrzeit enthalten ist. Dies macht den Test definitiv ungültig. Stellen Sie außerdem sicher, dass Sie mit allen Optimierungen kompiliert haben.

Schließlich habe ich Ihren Code kopiert und eingefügt und 0,016 für qsort und 0,008 für std :: sort erhalten.

Ich bin überrascht, dass niemand Caches erwähnt.

In Ihrem Code berühren Sie zunächst ary und * ary_copy *, damit sie sich zum Zeitpunkt von qsort im Cache befinden . Während qsort wird * ary_copy * möglicherweise entfernt. Zum Zeitpunkt von std :: sort müssten die Elemente aus dem Speicher oder einer größeren ( langsamer gelesenen ) Cache-Ebene abgerufen werden. Dies hängt natürlich von Ihrer Cache-Größe ab.

Versuchen Sie, den Test umzukehren, indem Sie zunächst std :: sort ausführen .

Wie einige Leute betont haben; Wenn Sie das Array vergrößern, wird der Test fairer. Der Grund ist, dass ein großes Array weniger wahrscheinlich in den Cache passt.

Die beiden Sortieralgorithmen sollten ohne aktivierte Optimierungen eine vergleichbare Leistung aufweisen. Der Grund, warum C ++ sortdazu neigt, merklich zu schlagen, qsortist, dass der Compiler die durchgeführten Vergleiche einbinden kann, da der Compiler Typinformationen darüber hat, welche Funktion zum Durchführen des Vergleichs verwendet wird. Haben Sie diese Tests mit aktivierter Optimierung durchgeführt? Wenn nicht, schalten Sie es ein und führen Sie diesen Test erneut aus.

Ein weiterer Grund dafür, dass qsort möglicherweise eine viel bessere Leistung als erwartet erbringt, besteht darin, dass neuere Compiler über den Funktionszeiger inline und optimiert werden können.

Wenn der C-Header eine Inline-Implementierung von qsort definiert, anstatt sie in einer Bibliothek zu implementieren, und der Compiler das Inlining indirekter Funktionen unterstützt, kann qsort genauso schnell sein wie std :: sort.

Auf meiner Maschine etwas Fleisch hinzufügen (das Array 10 Millionen Elemente machen und es im Datenbereich verschieben) und mit kompilieren

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

Ich bekomme als Ergebnis

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

Seien Sie auch vorsichtig mit modernen "grünen" CPUs, die je nach Auslastung des Systems so konfiguriert werden können, dass sie mit variabler Geschwindigkeit laufen. Beim Benchmarking kann diese Art von Verhalten Sie verrückt machen (auf meinem Computer habe ich ein kleines Skript, das die CPU-Uhr korrigiert, die ich bei Geschwindigkeitstests verwende).

Es ist schwierig, genaue Benchmarks zu schreiben. Lassen Sie uns Nonius dazu bringen, dies für uns zu tun! Lassen Sie uns Test qsort, std::sortohne inlining und std::sortmit inlining (Standardeinstellung) auf einen Vektor von einer Million Zufallszahlen.

// sort.cpp
#define NONIUS_RUNNER
#include <nonius.h++>
#include <random>
#include <algorithm>

// qsort
int comp(const void* a, const void* b) {
    const int arg1 = *static_cast<const int*>(a);
    const int arg2 = *static_cast<const int*>(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<int> gen_random_vector(const size_t size) {

    std::random_device seed;
    std::default_random_engine engine{seed()};
    std::uniform_int_distribution<int> dist{std::numeric_limits<int>::min(), std::numeric_limits<int>::max()};

    std::vector<int> 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<int> 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<size_t>(meter.runs());
    std::vector<std::vector<int>> vectors{runs};
    std::fill(vectors.begin(), vectors.end(), rand_vec);

    meter.measure([&](const size_t run) {

        std::vector<int>& 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<size_t>(meter.runs());
    std::vector<std::vector<int>> vectors{runs};
    std::fill(vectors.begin(), vectors.end(), rand_vec);

    meter.measure([&](const size_t run) {

        std::vector<int>& 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<size_t>(meter.runs());
    std::vector<std::vector<int>> vectors{runs};
    std::fill(vectors.begin(), vectors.end(), rand_vec);

    meter.measure([&](const size_t run) {

        std::vector<int>& current_vec = vectors[run];

        std::sort(current_vec.begin(), current_vec.end(), compare{});

        return current_vec;

    });
});

Kompilieren mit Apple Clang 7.3.0,

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

und wenn wir es auf meinem 1,7 GHz i5 Macbook Air laufen lassen, bekommen wir

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

Also std::sortohne inlining ist etwa 1,7x schneller als qsort(vielleicht aufgrund unterschiedlicher Sortieralgorithmen) und inlining Beulen , dass bis zu etwa 2,4 - fach schneller. Sicherlich eine beeindruckende Beschleunigung, aber viel weniger als 670%.