3
\$\begingroup\$

I'm comparing performance of two sorting algorithms applied to sort integers using google benchmark.

I'm quite surprised by the results so wanted to ask if you see some mistakes in the way I measure the performance. I would expect performance of my naive radix sort to be much worse that std::sort because it is supposed to be bandwidth bound.

#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-axis is number of elements in the array, Y-axis is time spend on computations in average for all the times I run the code within for loop. It is in kMicrosecond.

enter image description here

\$\endgroup\$
4
  • \$\begingroup\$ I added text regarding axis labels. \$\endgroup\$ – Kirill Lykov Feb 9 at 17:21
  • 3
    \$\begingroup\$ Thanks for that. Is kMicrosecond a new word for millisecond? \$\endgroup\$ – Toby Speight Feb 9 at 17:21
  • \$\begingroup\$ I didn't look too close at the code, but don't you just pick all elements in range [0,n) and randomly shuffle them? How would std::sort be more efficient at sorting such a range compared to a radix sort? These are the perfect conditions ever for radix sorting. If your numbers were random arbitrary values then things would be different - also if they were a bizarre set of floating points - then radix sort would perform quite bad. \$\endgroup\$ – ALX23z Feb 12 at 2:52
  • \$\begingroup\$ Probably you are right regarding choosing numbers. \$\endgroup\$ – Kirill Lykov Feb 12 at 9:26
0
\$\begingroup\$

I'm not too surprised to see the radix sort being faster in this use case, 32 bits is very short for a key. You may want to look at this comparison as well as at the last paragraph of this History section.

About the bench method, I would:

  • Try with values already sorted.
  • Try with values sorted in reverse.
  • Try with multiple sets of random values, each set identified by its seed (so no random seed).
  • Try with the same as above but with the first half filled with random values and the second half being a copy of the first half.

I would also test the end result, of course.

\$\endgroup\$
2
  • \$\begingroup\$ I think I will make a separate repo for benchmarking sorting algorithms. It might be interesting for a broad audience for educational purposes as well as to make provide a guidance which sorting algorithm to choose depending on the data. \$\endgroup\$ – Kirill Lykov Feb 12 at 9:28
  • \$\begingroup\$ I've added this repo, comments are welcomed. See github.com/KirillLykov/int-sort-bmk \$\endgroup\$ – Kirill Lykov 15 hours ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.