性能的QSORT VS STD ::sorting？
根据斯科特·迈耶斯（Scott Meyers）在其有效的STL书籍 – 第46项。他声称std::sort比std::qsort速度快670％，这是由于内联的缘故。 我testing了自己，我看到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：考虑函数对象而不是函数作为algorithm参数。
最好的祝福，
std :: clock（）不是一个可行的时钟。 您应该使用特定于平台的高分辨率计时器，如Windows高性能计时器。 更重要的是，你调用clock（）的方式是，首先将文本输出到控制台，这是包括在内的。 这绝对无效的testing。 另外，请确保您使用所有优化进行编译。
最后，我复制并粘贴了你的代码，得到了0.016的qsort和0.008的std :: sort。
我很惊讶，没有人提到caching。
在你的代码中，你首先触摸ary和* ary_copy *，这样它们在qsort时就驻留在caching中。 在qsort期间，* ary_copy *可能会被驱逐。 在std :: sort时 ，元素必须从内存中读取，或者从较大（读取较慢 ）的caching级别获取。 这当然取决于你的caching大小。
尝试颠倒testing，即开始运行std :: sort 。
正如有人指出的那样， 使arrays变大会使testing更公平。 原因是大数组不太可能适合caching。
没有启用优化的两种sortingalgorithm应具有可比较的性能。 因为编译器具有关于正在使用什么函数来执行比较的types信息，所以C ++ sort的原因是编译器可以内联进行比较。 您是否启用了启用优化的这些testing？ 如果不是，请尝试将其打开并再次运行此testing。
qsort可能比预期好得多的另一个原因是，较新的编译器可以通过函数指针内联和优化。
如果C头文件定义了一个qsort的内联实现，而不是在库内部实现它，而且编译器支持间接函数内联，那么qsort可以和std :: sort一样快。
在我的机器上添加一些肉（使数组1000万个元素并在数据部分中移动）并编译
g++ -Wall -O2 -osortspeed sortspeed.cpp
我得到的结果
C quick-sort time elapsed: 3.48 C++ quick-sort time elapsed: 1.26
请注意现代的“绿色”CPU，这些CPU可能configuration为根据系统的负载以可变的速度运行。 当对这种行为进行基准testing可能会使你疯狂（在我的机器上，我已经设置了两个normal和fast小脚本，可以在进行速度testing时使用）。
编写准确的基准是困难的，所以让我们让Nonius为我们做！ 让我们来testingqsort ， std::sort没有内联，而std::sort的内联（默认）在一百万个随机整数的向量上。
// 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; }); });
用Apple Clang 7.3.0编译，
$ clang++ -std=c++14 -stdlib=libc++ -O3 -march=native sort.cpp -o sort $ ./sort
并在我的1.7 GHz i5 Macbook Air上运行它，我们得到了
qsort 211 ms +/- 6 ms std::sort noinline 127 ms +/- 5 ms std::sort inline 87 ms +/- 4 ms
所以std::sort没有内联的速度比qsort快1.7倍（可能是由于不同的sortingalgorithm），并且内联速度快了2.4倍。 当然是一个令人印象深刻的加速，但远低于670％。
不知道几年前std :: sort是如何实现的。 但是std :: sort可以更快，因为std :: sort是一个堆sorting回退的快速sorting。 Heapsort是一个linearhitmic alghoritm，意思是如果你有两倍的sorting数据，sorting时间加倍。 实际上它不是双线，因为它不完全线性，但是qsort可以是二次的，所以需要指数多的时间来对input进行两次sorting。
