qsort与std::sort的性能比较？

Question

根据斯科特·迈耶斯的说法，在他的有效STL书中-项目46。他声称，由于内联的事实，std::sort比std::qsort快大约670%。我测试了自己，我发现qsort更快:(！有人能帮我解释一下这种奇怪的行为吗？

#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 quick-sort time elapsed: 0.061
C++ quick-sort time elapsed: 0.086
Press any key to continue . . .

更新

有效STL第三版( 2001 )

第7章使用STL进行编程

第46项:考虑函数对象而不是函数作为算法参数。

Answer 1

clock ()不是可行的计时时钟。您应该使用特定于平台的较高分辨率计时器，如Windows高性能计时器。更重要的是，调用clock()的方法是首先将文本输出到控制台，该控制台包含在时间中。这肯定会使测试无效。此外，请确保使用所有优化进行编译。

最后，我复制并粘贴了您的代码，qsort获得了0.016，std::sort获得了0.008。

Answer 2

我很惊讶，竟然没有人提到缓存。

在您的代码中，首先要接触ary和*ary_copy*，以便它们在qsort时驻留在缓存中。在qsort期间，*ary_copy*可能会被逐出。在执行std::sort时，必须从内存或更大(读取速度较慢)的缓存级获取元素。当然，这取决于您的缓存大小。

尝试反向测试，即通过运行std::sort开始。

正如一些人所指出的那样，使数组变得更大将使测试更加公平。原因是大型数组不太可能放入缓存中。

Answer 3

在没有启用优化的情况下，这两种排序算法应该具有相当的性能。C++ sort明显优于qsort的原因是，编译器可以内联正在进行的比较，因为编译器具有关于正在使用什么函数执行比较的类型信息。您是否在启用优化的情况下运行这些测试？如果没有，请尝试将其打开并再次运行此测试。