Производительность qsort vs std::sort?

Question

Производительность qsort vs std::sort?

По словам Скотта Мейерса, в своей книге Effective STL - пункт 46. Он утверждал, что std::sort примерно на 670% быстрее, чем std::qsort из-за факта встраивания. Я проверил себя и увидел, что 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 3-е издание ( 2001)
Глава 7 Программирование с помощью STL
Пункт 46: Рассматривать функциональные объекты вместо функций в качестве параметров алгоритма.

С наилучшими пожеланиями,

80

c++ performance sorting stl

Источник

user398398 16 янв '11 в 21:15

9 ответов

Решение

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

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

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

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

25

Источник

user677004 25 мар '11 в 15:26

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

14

Источник

user501557 16 янв '11 в 21:18

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

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

13

Источник

user13422 16 янв '11 в 21:45

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

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

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

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

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

6

Источник

user320726 16 янв '11 в 21:47

Написание точных тестов сложно, поэтому давайте сделаем так, чтобы 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

и запустив его на моем 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%.

6

Источник

user3645205 01 фев '16 в 22:39

Почему никто не упоминает эту дополнительную выборку памяти в функции сравнения стандартной библиотеки C?

В стандартной библиотеке C void * используется для хранения всех типов данных-членов, что означает, что при фактическом доступе к данным-членам указатель void * должен быть выполнен после дополнительного разыменования.

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

Однако в STL с помощью возможностей генерации кода шаблона данные членов, сохраненные с помощью void * в стандартной библиотеке C, могут быть непосредственно помещены внутри типа, избегая дополнительных разыменований во время доступа.

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

Итак, теоретически std ::sort быстрее, чем qsort.

3

Источник

27 сен '21 в 07:12

Я не уверен, что на 670% быстрее. Должно быть, это был специальный набор данных, предназначенный для демонстрации скорости . В общем, действительно быстрее, чем из-за пары этих вещей:

действует на , что, во-первых, требует разыменования, а во-вторых, требует размера типа данных для выполнения свопов. Следовательно, операция подкачки выполняется для каждого байта. Посмотрите на реализацию и обратите внимание на ее макрос - это цикл. Вот видео Джона Бентли, объясняющее разницу во времени (начиная с 45 м): https://www.youtube.com/watch?v=aMnn0Jq0J-E&amp;t=2700s .
The может немного ускорить его, но это микрооптимизация, а не основной вклад.
на самом деле это гибридный алгоритм под названием Introsort. C — это чистая реализация быстрой сортировки. Учитывая набор данных, который ужасен для быстрой сортировки, вместо этого меняется на пирамидальную сортировку. Поэтому, если вы создадите плохой ввод для , это будет невыносимо медленно.
Приведенного выше кода профилирования недостаточно. Размер ввода должен быть увеличен. 100К вряд ли хватит. Увеличьте его до 1M или 10M, затем повторите сортировку несколько раз, затем возьмите среднее значение или медиану. При необходимости скомпилируйте их в отдельный бинарник и запустите отдельно.

2

Источник

user1290581 10 ноя '21 в 20:37

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

-2

Источник

user4958693 10 окт '15 в 07:17

Другие вопросы по тегам c++ performance sorting stl

user298661 16 янв '11 в 21:22 2011-01-16 21:22 · Accepted Answer · 2011-01-16 21:22

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

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