Rendimiento de qsort vs std :: sort?

Question

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

#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 . . . 

actualización

Efectivo STL 3rd Edition (2001)
Capítulo 7 Programación con STL
Artículo 46: Considere los objetos de función en lugar de funciones como algori thm parámetros.

Saludos,

Answer 1

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.

Answer 2

Los dos algoritmos de ordenación, sin optimizaciones habilitado, debería tener un rendimiento comparable. La razón por la que C++ sort tiende a ganar sensiblemente 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 3

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 4

En mi máquina añadiendo un poco de carne (haciendo que la matriz 10 millones de elementos y moviéndolo en la sección de datos) y compilar con

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

consigo como resultado

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

Prestad atención a 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 volverse loco (en mi máquina he configurado dos pequeños guiones, normal y fast, que puedo usar cuando realizo pruebas de velocidad).

Answer 5

Me sorprende que nadie mencione los caches.

En su código, se empieza tocando ary y ary_copy * * por lo que son residentes en la memoria 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 de un nivel de caché más grande (leer más lento). Esto, por supuesto, dependerá de los tamaños de tu caché.

Intente invertir la prueba, es decir, comience ejecutando std :: sort.

Como han señalado algunas personas; 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 6

No sé cómo se implementó std :: sort hace años. Pero std :: sort puede ser mucho más rápido, porque std :: sort es quicksort con una alternativa de tipo de 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 7

Escribir puntos de referencia exactos es difícil, así que vamos a obtener Nonius para hacerlo por nosotros! Vamos a probar qsort, std::sort sin alineación, y std::sort con la alineación (el valor predeterminado) 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; 

    }); 
}); 

Compilar con Apple Clang 7.3.0,

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

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

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

Así std::sort sin procesos en línea es de aproximadamente 1,7 x más rápido que qsort (tal vez debido a diferentes algoritmos de clasificación), y la creación de baches que hasta aproximadamente 2.4x más rápido. Sin duda una aceleración impresionante, pero mucho menos de 670%.