D's rotateTail [was: C++'s std::rotate]
Fool via Digitalmars-d
digitalmars-d at puremagic.com
Sun Aug 24 02:20:58 PDT 2014
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;
}
More information about the Digitalmars-d
mailing list