Desempenho do qsort vs std :: sort?

Segundo Scott Meyers, em seu livro Effective STL – item 46. Ele afirmou que std::sort é cerca de 670% mais rápido que std::qsort devido ao fato de inline. Eu testei a mim mesmo, e eu vi qsort é mais rápido :(! Alguém poderia me ajudar a explicar esse comportamento estranho?

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

Este é o meu resultado:

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

Atualizar

Efetivo STL 3ª Edição (2001)
Capítulo 7 Programando com STL
Item 46: Considere objects de function em vez de funções como parâmetros de algoritmo.

Cumprimentos,

std :: clock () não é um relógio de tempo viável. Você deve usar um timer de resolução maior específico da plataforma, como o Timer de alto desempenho do Windows. Mais do que isso, a maneira como você chama clock () é a primeira, o texto é enviado para o console, que é incluído no tempo. Isso definitivamente invalida o teste. Além disso, certifique-se de ter compilado todas as otimizações.

Por fim, copiei e colei seu código e obtive 0,016 para qsort e 0,008 para std :: sort.

Estou surpreso que ninguém mencione caches.

Em seu código, você começa tocando ary e * ary_copy * para que eles sejam residentes no cache no momento do qsort . Durante o qsort , * ary_copy * pode ser despejado. No momento de std :: sort , os elementos teriam que ser buscados da memory ou um nível de cache maior (ler mais lento ). Isto dependerá, obviamente, dos seus tamanhos de cache.

Tente inverter o teste, isto é, comece executando std :: sort .

Como algumas pessoas apontaram; tornar o array maior tornará o teste mais justo. A razão é que é menos provável que uma matriz grande se ajuste ao cache.

Os dois algoritmos de sorting, sem otimizações ativadas, devem ter desempenho comparável. A razão pela qual o sort C ++ tende a agredir bastante o qsort é que o compilador pode alinhar as comparações feitas, já que o compilador possui informações de tipo sobre qual function está sendo usada para realizar a comparação. Você executou esses testes com a otimização ativada? Caso contrário, tente ativá-lo e executar esse teste novamente.

Outra razão pela qual o qsort pode ter um desempenho muito melhor que o esperado é que os compiladores mais novos podem inline e otimizar através do ponteiro de function.

Se o header C define uma implementação inline do qsort em vez de implementá-lo dentro de uma biblioteca e o compilador suporta inlining de function indireta, então qsort pode ser tão rápido quanto std :: sort.

Na minha máquina adicionando um pouco de carne (fazendo a matriz de 10 milhões de elementos e movendo-a na seção de dados) e compilando com

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

Fico como resultado

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

Tenha também cuidado com CPUs modernas “verdes” que podem ser configuradas para rodar a uma velocidade variável, dependendo da carga do sistema. Quando o benchmarking desse tipo de comportamento pode deixá-lo louco (na minha máquina eu configurei dois scripts pequenos, normal e fast que eu posso usar ao fazer testes de velocidade).

Escrever benchmarks precisos é difícil, então vamos fazer a Nonius fazer isso por nós! Vamos testar qsort , std::sort sem inlining e std::sort com inlining (o padrão) em um vetor de um milhão de inteiros randoms.

 // 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_distribution 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; }); }); 

Compilando com o Apple Clang 7.3.0,

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

e executá-lo no meu 1.7 GHz i5 Macbook Air, obtemos

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

Portanto std::sort sem inline é cerca de 1.7x mais rápido que o qsort (talvez devido a diferentes algoritmos de ordenação), e inlining bump que é até cerca de 2.4x mais rápido. Certamente uma aceleração impressionante, mas muito menos que 670%.

Não sei como o std :: sort foi implementado anos atrás. Mas std :: sort pode ser muito mais rápido, porque std :: sort é quicksort com um fallback de tipo de heap. Heapsort é um algoritmo linear hitmico, significando que se você tiver o dobro dos dados de ordenação, o tempo de ordenação será duplicado. Na verdade, mais do que dobra, porque não é exatamente linear, mas, no entanto, o qsort pode ser quadrático, precisando assim de mais tempo para ordenar o dobro da input.