Re: Is D slow?

[Honey via Digitalmars-d-learn]

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]);
   }
}