сравнительные алгоритмы сортировки: std :: sort против моего наивного основания

Я сравниваю производительность двух алгоритмов сортировки, применяемых для сортировки целых чисел, с помощью теста Google.

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

#include <benchmark/benchmark.h>

#include <random>
#include <vector> 
#include <array> 
#include <algorithm>

#define TEST_SIZE DenseRange(50000, 1000000, 50000)

class SortingBmk : public benchmark::Fixture
{
public:
    using T = int32_t;
    std::vector<T> m_vals;

    void SetUp(const ::benchmark::State& state)
    {
        const auto n = state.range(0);
        m_vals.resize(n);
        std::iota(m_vals.begin(), m_vals.end(), 0);

        std::random_device rd;
        std::mt19937 g(rd());
        std::shuffle(m_vals.begin(), m_vals.end(), g);
    }

    void TearDown(const ::benchmark::State& state) {}
};

BENCHMARK_DEFINE_F(SortingBmk, StdSort)(benchmark::State& state)
{
    const auto n = state.range(0);

    std::vector<T> values(m_vals.size());
    for (auto _ : state)
    {
        std::copy(m_vals.begin(), m_vals.end(), values.begin());

        std::sort(values.begin(), values.end());
        benchmark::DoNotOptimize(values);
        benchmark::ClobberMemory();
    }
}
BENCHMARK_REGISTER_F(SortingBmk, StdSort)->Unit(benchmark::kMicrosecond)->TEST_SIZE;

inline int getBits(SortingBmk::T v, SortingBmk::T i) { return (v >> i)&0b11; }
void radixSort_count(std::vector<SortingBmk::T>& data, std::vector<SortingBmk::T>& buf) {
    const int n = data.size();
    std::array<int, 8> psum = {0};
    constexpr auto sz = sizeof(SortingBmk::T) * 8 - 2;
    for (SortingBmk::T i = 0; i < sz; i += 2) {
        //count sort
        for (int v : data) {
            auto bits = getBits(v, i);
            ++psum[bits];
        }
        for (int i = 1; i < 8; ++i)
            psum[i] += psum[i-1];
        for (int j = n - 1; j>= 0; --j) {
            auto bits = getBits(data[j], i);
            --psum[bits];
            assert(psum[bits] < buf.size());
            buf[ psum[bits] ] = data[j];
        }
        swap(buf, data);
        psum = {0};
    }
}

BENCHMARK_DEFINE_F(SortingBmk, NaiveRadixSort)(benchmark::State& state)
{
    const auto n = state.range(0);

    std::vector<T> values(m_vals.size());
    std::vector<T> buffer(m_vals.size());
    for (auto _ : state)
    {
        std::copy(m_vals.begin(), m_vals.end(), values.begin());

        radixSort_count(values, buffer);
        for (int i = 1; i < values.size(); ++i)
            assert(values[i-1] < values[i]);
        benchmark::DoNotOptimize(values);
        benchmark::ClobberMemory();
    }
}
BENCHMARK_REGISTER_F(SortingBmk, NaiveRadixSort)->Unit(benchmark::kMicrosecond)->TEST_SIZE;

BENCHMARK_MAIN();

UPD: ось X — это количество элементов в массиве, ось Y — время, затрачиваемое на вычисления в среднем за все время, когда я запускаю код в for петля. Это в килограммах микросекунды.

Я не слишком удивлен, увидев, что сортировка по основанию в этом случае использования выполняется быстрее, 32 бита — это очень мало для ключа. Вы можете посмотреть на это сравнение а также в последнем абзаце этого История раздел.

Что касается стендового метода, я бы:

• Попробуйте использовать уже отсортированные значения.
• Попробуйте отсортировать значения в обратном порядке.
• Попробуйте использовать несколько наборов случайных значений, каждый из которых идентифицируется своим начальным числом (так что случайных начальных значений нет).
• Попробуйте сделать то же, что и выше, но с первой половиной, заполненной случайными значениями, а вторая половина будет копией первой половины.

Конечно, я бы тоже проверил конечный результат.