Sorting array of doubles extremely slow, and slower

Question

I am trying to sort an array of doubles. It is extremely slow:

double price[1000];

    void sortArrayOfDoubles(double price[ ], int length)    
    {   
        qsort(price, length, sizeof (double), compareDoubles);
    }

I am using this as the compare method, which is very slow. Call it Method A:

int compareDoubles_SlowMethod(const void* elem1, const void* elem2)
{
    if(*(const double*)elem1 < *(const double*)elem2)
        return -1;
    return *(const double*)elem1 > *(const double*)elem2;
}

So then I tried this one, Method B, which is more than 3x slower than the other one.

int compareDoubles_EvenSlowerMethod(const void *x, const void *y)
{
  double xx = *(double*)x, yy = *(double*)y;
  if (xx < yy) return -1;
  if (xx > yy) return  1;
  return 0;
}

Is there anything faster?

Answer 1

I would write it as:

static int compareDoubles(const void *px, const void *py)
{
  const double x = *(double *) px, y = *(double *) py;

  if(x < y)
    return -1;
  return x > y;
}

This is essentially a mix of your two suggestions. Note that doing a callback just to compare a single value will never be optimally efficient. This is a drawback of how C's qsort() works; it would be best to inline the comparison inside the sort, but that's not possible in C.

Unless, of course, you implement the sorting algorithm yourself and tailor it for double values.

Answer 2

It is possible that getting the branch out of the function would improve its runtime. For example:

int compareDoubles_noBranch(const void *x, const void *y) {
    return -1 * (*(const double*)x < *(const double*)y)
         +  1 * (*(const double*)x > *(const double*)y);
}

Probably it is not a good idea to do something like const double x = *(const double*)x, ... because of the memory/copy overhead if this is not optimized away by the compiler. I'm not certain but I think that the inlined casts add no overhead, they just affect what CPU instructions are called on the memory x and y point to when the inequality operators are invoked.