Написание точных тестов сложно, поэтому давайте заставим 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;
});
});
Компиляция с помощью Apple Clang 7.3.0,
$ clang++ -std=c++14 -stdlib=libc++ -O3 -march=native sort.cpp -o sort
$ ./sort
и запустив его на моем i5 Macbook Air с частотой 1,7 ГГц, мы получаем
qsort 211 ms +/- 6 ms
std::sort noinline 127 ms +/- 5 ms
std::sort inline 87 ms +/- 4 ms
Так что std::sort без встраивания примерно в 1,7 раза быстрее, чем qsort (возможноразличные алгоритмы сортировки) и врезки ударов, которые примерно в 2,4 раза быстрее.Конечно, впечатляющее ускорение, но намного меньше, чем 670%.