This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

4-15% speed-up in std::sort special case - is it worth the effort?


Hi all,

I've been experimenting with sorting recently and I have noticed a
possibility to slightly optimize the sorting of std::pair values using
the default < operator. This is, I believe, a common usage case to
retrieve sorting indices (better locality of reference than sorting
via pointers). At least I usually do it that way :)

The idea is simple: we know how the < operator for std::pairs looks
like; basically it's
x.first < y.first || (! (y.first < x.first) && x.second < y.second)

to reduce conditional branching in comparisons, we can delay
evaluating the secondary conditions like this:
1. sort by first components
2. identify identical runs
3. sort each run by second components

The attached source contains a proposed simple sort_pairs
implementation plus a benchmark code.

Using g++ -O3 -march=native, on my Core 2 Duo @ 2.83 GHz, I get for
instance the following results:

hajek@hajek:~/devel/scratch> ./a.out
test int, int:
timings: sort_pairs = 0.47 sec std::sort = 0.51 sec  speed-up = 8.51064%
results identical
test int, int with small range:
timings: sort_pairs = 0.52 sec std::sort = 0.6 sec  speed-up = 15.3846%
results identical
test double, int:
timings: sort_pairs = 0.6 sec std::sort = 0.64 sec  speed-up = 6.66666%
results identical
test double, int with small range:
timings: sort_pairs = 0.68 sec std::sort = 0.71 sec  speed-up = 4.41176%
results identical

and in general the speed-ups vary considerably (it's random data), but
I failed to produce anything below 3%.

The question is whether this slight optimization is worth including in
GCC's C++ library - std::sort could dispatch to sort_pairs
automatically when iterator's ValueType is a std::pair instance using
a trait mechanism (not yet implemented).

best regards and thanks for GCC

-- 
RNDr. Jaroslav Hajek, PhD
computing expert & GNU Octave developer
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz
// Copyright (C) 2010 Jaroslav Hajek
#include <iostream>
#include <ctime>
#include <vector>
#include <algorithm>
#include <iterator>
#include <utility>

namespace std
{
  template <typename _T1, typename _T2>
    struct __less_pair_first
      {
        bool operator ()(const std::pair<_T1, _T2>& __p1,
                         const std::pair<_T1, _T2>& __p2)
          {
            return __p1.first < __p2.first;
          }
      };

  template <typename _T1, typename _T2>
    struct __less_pair_second
      {
        bool operator ()(const std::pair<_T1, _T2>& __p1,
                         const std::pair<_T1, _T2>& __p2)
          {
            return __p1.second < __p2.second;
          }
      };


  template<typename _RandomAccessIterator>
    inline void
    sort_pairs(_RandomAccessIterator __first, _RandomAccessIterator __last)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
	_ValueType;
      typedef typename _ValueType::first_type _FirstType;
      typedef typename _ValueType::second_type _SecondType;

      sort(__first, __last, __less_pair_first<_FirstType, _SecondType>());
      if (__first == __last)
        return;

      for (_RandomAccessIterator __next = __first + 1; 
           __next != __last; __next++)
        {
          if ((*__first).first < (*__next).first)
            {
              if (__first + 1 != __next)
                sort (__first, __next, __less_pair_second<_FirstType, _SecondType>());
              __first = __next;
            }
        }

      if (__first + 1 != __last)
        sort (__first, __last, __less_pair_second<_FirstType, _SecondType>());
    }
}

template<typename T1, typename T2>
struct generator
{
  int i;
  const int range;
  generator (int r) : i (0), range (r) { }
  std::pair<T1, T2> operator () (void) { return std::make_pair (rand () % range, i++); }
};

template<typename T1, typename T2>
void benchmark (int n, int r)
{
  std::vector< std::pair<T1, T2> > v;
  std::generate_n (std::back_inserter (v), n, generator<T1, T2> (r));

  std::vector< std::pair<T1, T2> > w = v;

  std::clock_t st = std::clock ();

  std::sort_pairs (w.begin (), w.end ());

  std::clock_t et = std::clock ();
  float t1 = static_cast<float> (et - st)/CLOCKS_PER_SEC;

  st = std::clock ();

  std::sort (v.begin (), v.end ());

  et = std::clock ();
  float t2 = static_cast<float> (et - st)/CLOCKS_PER_SEC;

  std::cout << "timings: sort_pairs = " << t1 << " sec"
    << " std::sort = " << t2 << " sec" << "  speed-up = " << 100*(t2/t1-1) << "%" << std::endl;

  if (std::equal (v.begin (), v.end (), w.begin ()))
    std::cout << "results identical" << std::endl;
  else
    std::cout << "results differ!" << std::endl;
}

int main ()
{
  srand (time (NULL));

  std::cout << "test int, int:\n";
  benchmark<int, int> (5000000, 20000000);

  std::cout << "test int, int with small range:\n";
  benchmark<int, int> (5000000, 50000);

  std::cout << "test double, int:\n";
  benchmark<double, int> (5000000, 20000000);

  std::cout << "test double, int with small range:\n";
  benchmark<double, int> (5000000, 50000);
}


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]