boost::spreadsort for std::pair

Question

Boost 1.58 has new library spreadsort, so I tried it out. I wrote simple sample for sorting vector of pairs of int:

#include <chrono>
#include <iomanip>

#include <boost/sort/sort.hpp>

// based on http://www.boost.org/doc/libs/develop/libs/sort/doc/html/sort/sort_hpp/string_sort.html

struct lessthan
{
  inline bool operator()(const std::pair<int, int> &x, const std::pair<int, int> &y) const
  {
    return x < y;
  }
};

struct bracket
{
  inline unsigned char operator()(const std::pair<int, int> &x, size_t offset) const
  {
    if (offset < sizeof(int))
      return get_char(x.first, offset);

    return get_char(x.second, offset - sizeof(int));
  }

private:
  inline unsigned char get_char(int x, size_t offset) const
  {
    static const boost::uint64_t base_mask = 0xff;

    const int bit_shift = 8 * (sizeof(int) - offset - 1);
    unsigned char result = (x & (base_mask << bit_shift)) >> bit_shift;
    if (offset == 0)
      return result ^ 128;

    return result;
  }
};


struct getsize
{
  inline size_t operator()(const std::pair<int, int> &) const
  {
    return 2 * sizeof(int);
  }
};

bool verify_sorted(const std::vector<std::pair<int, int>> & a)
{
  lessthan ls;
  for (size_t i = 0; i + 1 < a.size(); i++)
  {
    if (ls(a[i + 1], a[i]))
      return false;
  }

  return true;
}

int main()
{
  std::vector<std::pair<int, int>> r;

  srand(12345);
  for (size_t i = 0; i < 10000000; i++)
    r.push_back(std::make_pair(rand(), rand()));

  {
    std::vector<std::pair<int, int>> a = r;

    auto t_start = std::chrono::high_resolution_clock::now();
    std::sort(a.begin(), a.end());
    auto t_end = std::chrono::high_resolution_clock::now();

    std::cout << std::fixed << std::setprecision(2) << "CPU time used (std::sort): "
      << std::chrono::duration<double, std::milli>(t_end - t_start).count()
      << " ms\n";

    std::cout << (verify_sorted(a) ? "OK." : "FAIL!") << std::endl;
  }

  {
    std::vector<std::pair<int, int>> a = r;

    auto t_start = std::chrono::high_resolution_clock::now();
    boost::sort::spreadsort::string_sort(a.begin(), a.end(), bracket(), getsize(), lessthan());
    auto t_end = std::chrono::high_resolution_clock::now();

    std::cout << std::fixed << std::setprecision(2) << "CPU time used (boost::sort::spreadsort::string_sort): "
      << std::chrono::duration<double, std::milli>(t_end - t_start).count()
      << " ms\n";

    std::cout << (verify_sorted(a) ? "OK." : "FAIL!") << std::endl;
  }
}

It's faster then std::sort, but it's seems to me this implementation is to heavyweight and ugly for such a simple task. Can anyone propose better one?

Answer 1

You spend a lot of lines of code trying to get the expressions lessthan(), getsize(), and bracket() to behave like plain old functions. Consider just using plain old functions, instead. For example:

static uint8_t get_char(int x, size_t offset)
{
    const int bit_shift = 8 * (sizeof(int) - offset - 1);
    uint8_t result = (x >> bit_shift) & 0xFF;
    if (offset == 0) result ^= 128;
    return result;
}

static uint8_t bracket(const std::pair<int,int>& x, size_t offset)
{
    if (offset < sizeof(int))
      return get_char(x.first, offset);
    return get_char(x.second, offset - sizeof(int));
}

...
string_sort(a.begin(), a.end(), bracket, getsize(), lessthan());

You could also productively replace the expression getsize() with

auto getsize = [](auto){ return 2*sizeof(int); };

...
string_sort(a.begin(), a.end(), bracket, getsize, lessthan());

Finally, lessthan is equivalent to std::less<std::pair<int,int>>, so you can just write

string_sort(a.begin(), a.end(), bracket, getsize, std::less<>());

That's the kind of shortening you were looking for, right? :)