Qsort 与 std: : sort 的性能如何？

根据 Scott Meyers 在他的有效 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 编程
项目46: 将函数对象而不是函数视为算法参数。

68882 次浏览
小开

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

小开
最佳答案

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

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

小开

另一个原因是，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 时钟的小脚本，我在进行速度测试时使用它)。

小开

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

在代码中，首先触摸 ary和 ary_copy，使它们在 qsort时驻留在缓存中。在 qsort期间，ary_copy可能被驱逐。在 std::sort时，必须从内存或更大的(读取 慢一点)缓存级别获取元素。这当然取决于您的缓存大小。

尝试反向测试，例如，从运行 std::sort开始。

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

小开

编写准确的基准测试是很困难的，所以让我们让 诺尼斯为我们做到这一点！让我们在一个百万个随机整数的向量上测试 qsort、不带内联的 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倍(可能是由于不同的排序算法) ，而内联颠簸的速度比 qsort快2.4倍。的确是令人印象深刻的加速，但远低于670% 。

小开

为什么没有人在 C 标准库的比较函数中提到额外的内存获取呢？

在 C 标准库中，void * 用于保存所有类型的成员数据，这意味着当实际访问成员数据时，必须执行 void * 指针。

struct list {
void *p_data; // deference this pointer when access real data
struct list *prev;
struct list *next;
};

然而，在 STL 中，借助于模板的代码生成功能，在 C 标准库中使用 void * 保存的成员数据可以直接放置在类型中，避免在访问期间出现额外的解引用。

template <typename T>
class list {
public:
T data; // access data directly
list *prev;
list *next;
};

所以理论上 std: : sort 比 qsort 快。

小开

我不确定670% 更快。它必须是一个特定的数据集，以显示 std::sort的速度。一般来说，std::sort 是确实比 qsort快，这是因为以下几点:

  1. qsort在 void*上运行，void*首先需要解引用，其次需要数据类型的大小来执行交换。因此，qsort的交换操作是每个字节执行的。看看 qsort的实现，注意它的 SWAP宏是一个循环。下面是乔恩 · 本特利(Jon Bentley)解释时间差异的视频(从45m 开始) : < a href = “ https://www.youtube.com/watch? v = aMnn0Jq0J-E & amp。 t = 2700s”rel = “ nofollow noReferrer”> https://www.youtube.com/watch?v=amnn0jq0j-e&t=2700s

  2. inline可能会加快一点速度，但这只是微观优化，不是主要因素。

  3. std::sort实际上是一种称为 内向的混合算法。Cqsort是一个纯粹的快速排序实现。给定一个对快速排序很糟糕的数据集，std::sort改为堆排序。因此，如果您为 qsort创建了一个错误的输入，那么它将慢得令人难以忍受。

  4. 上面的分析代码是不够的。输入量应该增加。十万根本不够。增加到1M 或10M，然后重复排序多次，然后采取平均或中位数。如果有必要，将它们编译成一个单独的二进制文件并单独运行它们。


提交答案