qsort 与 std::sort 的性能？

Question

根据 Scott Meyers 的说法，在他的 Effective STL book - item 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 第 3 版（2001 年）

第 7 章 STL 编程

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

原文由 roxrook 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

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

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

原文由 Puppy 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

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

在您的代码中，您首先触摸 ary 和 ary_copy 因此它们在 qsort 时驻留在缓存中。在 qsort 期间， ary_copy 可能会被驱逐。在 std::sort 时，必须从内存或更大（读取 _速度较慢_）的缓存级别中获取元素。这当然取决于您的缓存大小。

尝试反转测试，即首先运行 std::sort 。

正如一些人指出的那样；使数组更大将使测试更公平。原因是大数组不太可能适合缓存。

原文由 rasmus 发布，翻译遵循 CC BY-SA 4.0 许可协议