A Benchmark for Phobos Sort Algorithm

[Craig Black]

On my computer, the custom sort algorithm performs almost 40 percent better 
than the Phobos one.  I provided this in case anyone wanted to improve the 
phobos algorithm.  I only benchmarked this with DMD.  I would be curious to 
know how it performs with GDC.

-Craig

import std.stdio;
import std.random;
import std.algorithm;

static bool less(T)(T a, T b) { return a < b; }

void insertionSort(A, alias L)(A a, int low, int high)
{
  for(int i = low; i <= high; i++)
  {
    int min = i;
    for(int j = i + 1; j <= high; j++)
      if(L(a[j], a[min])) min = j;
    swap(a[i], a[min]);
  }
}

void quickSort(A, alias L)(A a, int p, int r)
{
  if (p >= r) return;
  if(p + 7 > r) return insertionSort!(A, L)(a, p, r);
  auto x = a[r];
 int j = p - 1;
 for (int i = p; i < r; i++)
 {
  if (L(x, a[i])) continue;
  swap(a[i], a[++j]);
 }
 a[r] = a[j + 1];
 a[j + 1] = x;
 quickSort!(A, L)(a, p, j);
 quickSort!(A, L)(a, j + 2, r);
}

void customSort(T)(T[] a)
{
  quickSort!(T[], less!T)(a, 0, a.length-1);
}

ulong getCycle() { asm { rdtsc; } }

ulong bench1(double[] vals)
{
  ulong startTime = getCycle();
  double[] v;
  v.length = vals.length;
  for(int i = 0; i < 100; i++)
  {
    for(int j = 0; j < v.length; j++) v[j] = vals[j];
    sort(v);
  }
  return getCycle() - startTime;
}

ulong bench2(double[] vals)
{
  ulong startTime = getCycle();
  double[] v;
  v.length = vals.length;
  for(int i = 0; i < 100; i++)
  {
    for(int j = 0; j < v.length; j++) v[j] = vals[j];
    customSort(v);
  }
  return getCycle() - startTime;
}

void main()
{
  Mt19937 gen;
  double[] vals;
  vals.length = 1000;
  for(int i = 0; i < vals.length; i++) vals[i] = uniform(0.0,1000.0);

  ulong time1, time2;
  for(int i = 0; i < 100; i++)
  {
    time1 += bench1(vals);
    time2 += bench2(vals);
  }
  writeln("Sorting with phobos sort: ", time1/1e5);
  writeln("Sorting with custom quickSort: ", time2/1e5);
  writeln(100.0 * (time1-time2) / time1, " percent faster");
}