Выполнение qsort vs std:: sort?

Ответ 1

std:: clock() не является жизнеспособным синхронизирующим таймером. Вы должны использовать таймер с более высоким разрешением для платформы, например, высокопроизводительный таймер Windows. Более того, способ, которым вы называете clock(), заключается в том, что сначала текст выводится на консоль, которая включена во время. Это определенно делает недействительным тест. Кроме того, убедитесь, что вы скомпилированы со всеми оптимизациями.

Наконец, я скопировал и вставил ваш код и получил 0,016 для qsort и 0.008 для std:: sort.

Ответ 2

Я удивлен, что никто не упоминает тайники.

В вашем коде вы начинаете с касания ary и * ary_copy *, чтобы они находились в кэше во время qsort. Во время qsort * ary_copy * может быть выселен. Во время std:: sort элементы должны были быть извлечены из памяти или большего (более медленного) уровня кэша. Это, конечно же, будет зависеть от размеров вашего кеша.

Попробуйте изменить тест, т.е. начать с запуска std:: sort.

Как указывали некоторые люди; что делает массив более крупным, сделает тест более справедливым. Причина в том, что большой массив с меньшей вероятностью подходит для кеша.

Ответ 3

Два алгоритма сортировки без включенной оптимизации должны иметь сопоставимую производительность. Причина, по которой С++ sort имеет тенденцию заметно бить qsort, заключается в том, что компилятор может встроить сравнения, поскольку компилятор имеет информацию о типе о том, какая функция используется для выполнения сравнения. Проводили ли вы эти тесты с включенной оптимизацией? Если нет, попробуйте включить его и снова запустить этот тест.

Ответ 4

Другая причина, по которой qsort может работать намного лучше, чем ожидалось, заключается в том, что новые компиляторы могут встроить и оптимизировать с помощью указателя функции.

Если заголовок C определяет встроенную реализацию qsort вместо ее реализации внутри библиотеки, а компилятор поддерживает непрямую функцию, то qsort может быть столь же быстрым, как и std:: sort.

Ответ 5

На моей машине добавлено немного мяса (создание массива 10 миллионов элементов и перемещение его в разделе данных) и компиляция с помощью

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

Я получаю результат

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

Будьте также осторожны с современными "зелеными" ЦП, которые могут быть сконфигурированы для работы с переменной скоростью в зависимости от нагрузки системы. Когда бенчмаркинг такого поведения может свести вас с ума (на моей машине я установил два небольших script normal и fast, которые можно использовать при выполнении тестов скорости).

Ответ 6

Написание точных тестов сложно, поэтому давайте Nonius сделать это для нас! Пусть test 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 ГГц i5 Macbook Air, мы получаем

qsort                211 ms +/- 6 ms
std::sort noinline   127 ms +/- 5 ms
std::sort inline      87 ms +/- 4 ms

So std::sort без инкрустации примерно на 1,7 раза быстрее, чем qsort (возможно, из-за разных алгоритмов сортировки), и наложение ударов, что примерно до 2.4x быстрее. Конечно, впечатляющее ускорение, но гораздо меньше 670%.

Ответ 7

Не знаю, как std:: sort был реализован много лет назад. Но std:: sort может быть намного быстрее, потому что std:: sort quicksort с резервным копированием кучи. Heapsort - это линейный алгоритмический альгоритм, то есть если у вас есть дважды данные сортировки, время сортировки удваивается. На самом деле он более чем удваивается, потому что он не является точно линейным, но, тем не менее, qsort может быть квадратичным, поэтому требуется экспоненциальное больше времени для сортировки в два раза ввода.