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

Question

根据Scott Meyers在他的《Effective 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 . . .

更新

Effective STL第三版（2001）
第7章 使用STL编程
条款46：考虑使用函数对象而不是函数作为算法参数。

- roxrook

---

你是否让编译器进行优化了？调试/未优化的版本无法充分利用例如内联等功能。 - Edward Strange

理解快速排序的工作原理，将有助于您更好地测试它。简而言之：1.使用一个更大的数组，例如大小为10^6，然后按降序填充数组999999...4,3,2,1——这将导致排序变为O(n^2)，这样做将有效地证明为什么在这个特定算法中内联比较器会产生如此大的差异。 - Matthieu N.

几乎没有 qsort 或 sort 的实现会使用在逆排序输入时会出错的快速排序实现。最常见的STLsort实现使用 introsort，它会检查快速排序例程以确保它永远不会退化到 O(n lg n) 更差的情况，我相当有信心 C 的 qsort例程使用类似的东西（或至少使用介于三数中位数之间的启发式）来防止这种情况。 - templatetypedef

根据Artima SM网站2006年的一篇文章：“我要开始说一个让你们中许多人难以接受的自白：我已经20年没有编写过生产软件了，而且我从未用过C++编写过生产软件。”他称自己为C++语言的考古学家/人类学家。 - Matthieu N.

@Chan: Bentley 和 McIlroy 的论文可以在这里找到：http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol23/issue11/spe862jb.pdf - Matthieu N.

Answer 1

std::clock() 不是一种可行的计时钟。你应该使用一个特定于平台的高分辨率计时器，比如 Windows 高性能计时器。此外，调用 clock() 的方式是先将文本输出到控制台，这会包含在计时中，从而导致测试无效。另外，请确保编译时打开了所有优化选项。

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

- Puppy

---

@DeadMG：谢谢！我改成了发布模式，得到了类似的结果。我真的很喜欢Scott Meyers，也相信他的话 ;) - roxrook

@Oo Tiib：输出的文本并不意味着它不会同时输出。如果缓冲区比第一个大但比第二个小怎么办？现在必须在第二次调用之前刷新-但在第一次调用中没有这样做。哦，亲爱的。虽然我已经解决了以上所有问题，qsort现在快多了，但我还是不太高兴。:( - Puppy

@DeadMG: std::qsort 要求“此函数的返回值应表示 elem1 是否被认为小于、等于或大于 elem2，分别通过返回负值、零或正值来实现。” operator< 不符合该要求（具体而言，它仅返回 0 或 1）。请确保在测试中 std::sort 和 std::qsort 产生相同的结果 :) （仅将“-”更改为“<”会导致 qsort 返回错误的答案） - Billy ONeal

@Billy：啊，有趣。我没意识到它不像std::sort那样接受二元谓词。这就解释了。 - Puppy

@Andrew Janke：他使用模运算来限制尺寸。 - Puppy

Answer 2

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

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

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

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

- rasmus

---

我很惊讶没有人提到任何度量代码实际有效性的策略。你可以编写一个小程序来对几百个元素进行排序，将所有内容加载到L1缓存中，并在记录时间内快速完成，但这绝不会反映出你的实际程序在运行时会面临的情况——系统中有其他几百个活动进程，在计算受限且调度器不给力的情况下进行上下文切换，同时对新泽西州大小的数据集进行排序。让你的基准测试看起来更像真实应用程序。 - Wexxor

Answer 3

没有启用优化的两个排序算法应该有相当的性能。C++sort比qsort表现更好的原因是，编译器可以内联比较操作，因为编译器具有关于所使用的函数类型信息。你是否启用优化来运行这些测试？如果没有，请尝试开启优化并再次运行此测试。

- templatetypedef

---

谢谢！我正在使用Visual Studio，但我真的不知道如何打开优化。 - roxrook

@Chan：切换到使用“发布”版本。同时确保你不要在Visual Studio内运行程序进行基准测试--像调试器这样的工具会改变程序的时间特性。 - Billy ONeal

@Billy ONeal：我切换到了Release模式，得到了预期的结果。开心 ^_^！ - roxrook

Answer 4

qsort之所以比预期性能更好的另一个原因是新的编译器可以内联和优化函数指针。

如果C头文件定义了qsort的内联实现而不是在库中实现，并且编译器支持间接函数内联，则qsort可以像std::sort一样快。

- Zan Lynx

Answer 5

编写准确的基准测试很困难，所以让我们通过Nonius来为我们完成！ 让我们在一个包含一百万个随机整数的向量上测试 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;

    });
});

使用苹果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倍（可能是由于不同的排序算法），而内联可以将速度提高到大约2.4倍。这确实是一个令人印象深刻的加速，但远远少于670％。

- Mr Bingley

---

CPU缓存是否可能储存值，因此对它们的连续访问速度更快，因此，例如，在运行qsort之前运行std :: sort测试，会显示qsort更快？ - Soup Endless

Answer 6

在我的电脑上，添加一些元素（将数组扩展到1000万个元素并将其移动到数据段中），然后使用以下编译器进行编译：

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

我得到的结果

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

同时还要注意现代的“绿色”CPU，这些CPU可能根据系统负载配置为可变速度运行。在进行基准测试时，这种行为可能会让你发疯（在我的机器上，我有一个小脚本来修复CPU时钟，在进行速度测试时使用）。

- 6502

---

如果您正在使用性能计数器（应该这样做才能获得有意义的基准测试结果），那么“绿色”CPU并不重要。 - Billy ONeal

性能计数器非常好用，但如果你不想测量小东西，那么时钟也不错。此外，clock()是每个进程的，而性能计数器是全局的。 - 6502

@6502：你搞反了。性能计数器是针对每个进程的，时钟是全局的。 - Billy ONeal

@Billy ONeal：我以为你指的是RDTSC，那个很好但是全局的。而且不，clock()是一个每个进程的计数器。请参见http://www.cs.utah.edu/dept/old/texinfo/glibc-manual-0.02/library_19.html。 - 6502

@6502：glibc != 标准C。通常我相信这些东西是用“rdtsc”实现的，但是操作系统会在执行上下文切换时跟踪时间戳，并在将上下文返回给正在被测量的进程时恢复这些值。 - Billy ONeal

@Billy ONeal: 很高兴知道…我总是直接使用RDTSC，因此系统负载是一个问题。关于时钟，如果我没记错的话，POSIX要求每个进程都可以使用clock()函数，但确实不足为奇地发现Windows不遵守这一点（显然可移植性不是他们的主要关注点…根据msdn VS6.0所述，时钟是每个进程的，而8.0则是墙上时钟-请参见http://msdn.microsoft.com/en-us/library/4e2ess30(VS.80).aspx和http://msdn.microsoft.com/en-us/library/aa272059(VS.60).aspx） - 6502

Answer 7

为什么没有人提到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更快。

- Jinliang Zheng

Answer 8

我不确定 670% 更快是什么意思。这可能是针对展示 std::sort 速度的特定数据集。通常情况下，std::sort 的确比 qsort 快，因为有几个原因：

1. qsort 操作的是 void*，首先需要解引用，其次需要知道数据类型的大小以执行交换。因此，qsort 的交换操作是每个字节都进行的。查看 qsort 的实现并注意其 SWAP 宏是一个循环。这是 Jon Bentley 解释时间差异的视频（从 45 分钟开始）：https://www.youtube.com/watch?v=aMnn0Jq0J-E&t=2700s

2. inline 可能会使它稍微加速一点，但那只是微小的优化，不是主要贡献者。

3. std::sort 实际上是一种混合算法，称为 Introsort。C qsort 是一个纯快速排序实现。如果给定的数据集对于快速排序来说很糟糕，std::sort 将改为使用堆排序。因此，如果你创建了一个对于 qsort 来说很糟糕的输入，它将变得无法忍受地慢。

4. 上面的分析代码不足够。输入大小应该增加。100K 远远不够。将其增加到 1M 或 10M，然后多次重复排序，取平均值或中位数。如果有必要，将它们编译成单独的二进制文件并分别运行。

- garbagecollector