On Friday, 9 June 2017 at 23:10:28 UTC, Ali Çehreli wrote:
You would get the exact performance if you implemented e.g.
with pointers. Your test has been very valuable for exposing an
embarrassing performance issue. :)
I can confirm that, after changing implementation to the
following, performance is on par. It is not immediatetly clear to
me how
r[r[0 .. i].getTransitionIndex!Less(r[i]) .. i + 1]
would look like if written idiomatically.
size_t getTransitionIndex(alias test, Range, V)(Range r, V v)
if (isRandomAccessRange!Range && hasLength!Range)
{
size_t first = 0;
size_t count = r.length;
while (count > 0)
{
immutable step = count / 2;
immutable it = first + step;
if (!test(v, r[it]))
{
first = it + 1;
count -= step + 1;
}
else
{
count = step;
}
}
return first;
}
void rotateRight(Range)(Range r)
if (hasLength!Range && isRandomAccessRange!Range &&
hasSlicing!Range)
{
auto t = r[$ - 1];
foreach_reverse (i; 0 .. r.length - 1)
{
r[i + 1] = r[i];
}
r[0] = t;
}
void insertionSort(alias Less, Range)(Range r)
if (hasLength!Range && isRandomAccessRange!Range &&
hasSlicing!Range)
{
foreach (i; 1 .. r.length)
{
rotateRight(r[r[0 .. i].getTransitionIndex!Less(r[i]) .. i
+ 1]);
}
}