Re: D's rotateTail [was: C++'s std::rotate]

[Fool via Digitalmars-d]

On Saturday, 23 August 2014 at 18:07:43 UTC, Fool wrote:
[2] http://dpaste.dzfl.pl/514a1ef77d0a

The 'three reverses' algorihm could be actually improved. Updated 
code (along with additional unit tests and a strengthened 
assertion) is available at [3].

I compared this implementation to an iterator based C++ 
translation and std::rotate [4]. Considering C++ std::vector and 
D dynamic array, here are the results:

 compiler | algorithm                | execution time
----------+--------------------------+----------------
 clang++  | std::rotate              | 1.62s
 clang++  | my_rotate / std::reverse | 1.45s
 clang++  | my_rotate / my_reverse   | 0.58s
 ldc2     | rotateTail               | 1.64s
 g++      | std::rotate              | 0.57s
 g++      | my_rotate / std::reverse | 1.43s
 g++      | my_rotate / my_reverse   | 0.36s
 gdc      | rotateTail               | 0.38s

Here, my_reverse is an adaption of D's reverse for 
RandomAccessRange.

These results make me think that the implementation proposed for 
RandomAccessRange is not too bad. It needs to be investigated 
why, in this particular situation, ldc2 produces significantly 
slower code than gdc and clang.

System: GNU/Linux x86_64

Compiler versions:

clang version 3.4.2
LDC - the LLVM D compiler (0.14.0): based on DMD v2.065 and LLVM 
3.4.2
g++ (GCC) 4.9.1
gdc (GCC) 4.9.1

Compiler flags:

clang++ -std=c++11 -O3 -march=native
ldc2 -O3 -mcpu=native -release -disable-boundscheck
g++ -std=c++11 -O3 -march=native
gdc -O3 -march=native -frelease -fno-bounds-check


[3] http://dpaste.dzfl.pl/b8e47941a007

[4] C++ translation of rotateTail for RandomAccessRange:

template <typename TIterator>
void my_reverse
(
   TIterator b,
   TIterator e
)
{
   auto steps = std::distance(b, e) / 2;

   if (steps)
   {
      auto l = b;
      auto r = std::prev(e);
      do
      {
         std::iter_swap(l, r);
         ++l;
         --r;
      } while (--steps);
   }
}

template <typename TIterator>
TIterator my_rotate
(
   TIterator b,
   TIterator m,
   TIterator e
)
{
   if (m == e) return b;
   if (b == m) return e;

//   my_reverse(b, m);
   std::reverse(b, m);

   auto s = std::next(b, std::distance(m, e));

//   my_reverse(b, e);
   std::reverse(b, e);
//   my_reverse(s, e);
   std::reverse(s, e);

   return s;
}