c++ - library - Rendimiento de qsort vs std:: sort?

sort c++ array

Question

Según Scott Meyers, en su libro Effective STL - artículo 46. Afirmó que std::sort es aproximadamente un 670% más rápido que std::qsort debido al hecho de estar en línea. Me probé a mí mismo y vi que el qsort es más rápido :(! ¿Alguien podría ayudarme a explicar este extraño comportamiento?

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

Este es mi resultado:

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

Actualizar

Effective STL 3rd Edition (2001)
Capítulo 7 Programación con STL
Ítem ​​46: Considere objetos de función en lugar de funciones como parámetros de algoritmo.

Atentamente,

Answer 1

En mi máquina agregué algo de carne (haciendo 10 millones de elementos del conjunto y moviéndolo en la sección de datos) y compilando con

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

Me sale como resultado

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

Tenga también cuidado con las CPU "verdes" modernas que pueden configurarse para funcionar a una velocidad variable dependiendo de la carga del sistema. Cuando la evaluación comparativa de este tipo de comportamiento puede volverte loco (en mi máquina he configurado dos pequeños guiones normal y fast que puedo usar al hacer pruebas de velocidad).

Answer 2

Escribir puntos de referencia precisos es difícil, así que hagamos que Nonius lo haga por nosotros. Probemos qsort , std::sort sin enlínea, y std::sort con inline (por defecto) en un vector de un millón de enteros aleatorios.

// 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;

    });
});

Compilando con Apple Clang 7.3.0,

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

y ejecutarlo en mi Macbook Air i5 de 1,7 GHz, obtenemos

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

Entonces std::sort sin alineación es aproximadamente 1.7x más rápido que qsort (tal vez debido a diferentes algoritmos de clasificación), e incluye baches que son aproximadamente 2.4x más rápidos. Sin duda una aceleración impresionante, pero mucho menos de 670%.

Answer 3

Los dos algoritmos de clasificación, sin optimizaciones habilitadas, deberían tener un rendimiento comparable. La razón por la cual el tipo de C ++ tiende a ganar de manera apreciable qsort es que el compilador puede alinear las comparaciones que se realizan, ya que el compilador tiene información de tipo sobre qué función se está utilizando para realizar la comparación. ¿Ejecutaste estas pruebas con la optimización habilitada? Si no, intente encenderlo y ejecutar esta prueba nuevamente.

Answer 4

Me sorprende que nadie mencione los caches.

En tu código, comienzas tocando ary y * ary_copy * para que residan en el caché en el momento de qsort . Durante qsort , * ary_copy * podría ser desalojado. En el momento de std :: sort , los elementos tendrían que ser recuperados de la memoria o un nivel de caché más grande (leer más lento ). Esto, por supuesto, dependerá de los tamaños de tu caché.

Intenta invertir la prueba, es decir, comienza ejecutando std :: sort .

Como algunas personas han señalado; hacer que la matriz sea más grande hará que la prueba sea más justa. La razón es que una matriz grande tiene menos posibilidades de caber en la memoria caché.

Answer 5

No sé cómo std :: sort se implementó hace años. Pero std :: sort puede ser mucho más rápido, porque std :: sort es quicksort con una especie de reserva de tipo montón. Heapsort es una alghoritm lineal-hítmica, lo que significa que si tienes el doble de datos de clasificación, el tiempo de ordenación se duplica. En realidad, es más que doble porque no es exactamente lineal, pero sin embargo, qsort puede ser cuadrático, por lo que necesita más tiempo exponencial para clasificar el doble de la entrada.

Answer 6

Otra razón por la que qsort puede funcionar mucho mejor de lo esperado es que los compiladores más nuevos pueden alinearse y optimizarse a través del puntero de función.

Si el encabezado C define una implementación en línea de qsort en lugar de implementarlo dentro de una biblioteca y el compilador admite la función indirecta en línea, entonces qsort puede ser tan rápido como std :: sort.

Answer 7

std :: clock () no es un reloj de tiempo viable. Debe usar un temporizador de resolución más alta específico de la plataforma, como el Temporizador de alto rendimiento de Windows. Más que eso, la forma en que llamas clock () es que primero, el texto se envía a la consola, que está incluida en el tiempo. Esto definitivamente invalida la prueba. Además, asegúrese de compilar con todas las optimizaciones.

Finalmente, copié y pegué su código, y obtuve 0.016 para qsort y 0.008 para std :: sort.