4

So, I am using qsort in my C program from C library. It works as expected so I decided to play around with comparators.

Comparator 1 (I use this):

 int compare (const void * a, const void * b)
{
  if (*(double*)a > *(double*)b) return 1;
  else if (*(double*)a < *(double*)b) return -1;
  else return 0;  
}

Comparator 2:

int comp (const void *a, const void *b)
{
    const double *ia = (const double *)a; // casting pointer types 
    const double *ib = (const double *)b;
    return *ia  - *ib; 
}

The first one works as I want to. The second one is supposed to do the same the first one. I would like to use the second because the program runs a bit faster, but the thing it that it doesn't really sort anything!

I am pretty sure that I have used comparator #2 on smaller arrays and it worked. Unless I am missing something there.

Baum mit Augen
  • 49,044
  • 25
  • 144
  • 182
Mpr. Moe
  • 83
  • 4
  • I find it difficult to believe that the tricky, 'optimized' comparator is measurably faster even when corrected to actually work, except maybe in the most specific of situations. Keep in mind that the `qsort()` function calls the comparator through a pointer. The overhead of that will likely dominate the performance of this simple function. – Michael Burr Mar 18 '17 at 23:03
  • Try replacing `return *ia - *ib;` with `double diff = *ia - *ib; return *(int*)((char*)&diff+4);` and see what performance it gives. This is very implementation specific, not complete and not recommended, but should work on little-endian with sizeof(int) = 4. It just returns the most significant 32-bit word of `diff`, it should have the sign bit set. Also assumes that the bit content of that word is not zero for positive diff. – nnn Mar 18 '17 at 23:58

1 Answers1

7

The second one is supposed to do the same the first one.

At the first glance it should, but upon closer examination it turns out that it shouldn't.

Consider, for example, comparing 5.3 and 4.9. It's clear that the first number is greater than the second one; however, subtracting one from the other produces 0.4, which rounds down to zero on conversion to int, telling qsort that 5.3 and 4.9 are equal to each other.

What you want is to apply signum function to the difference of the two arguments. Unfortunately, C standard does not define one; see this Q&A for several good work-arounds.

Community
  • 1
  • 1
Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • @Mpr.Moe That's right, you can't return a `double` in place of an `int`, because `qsort` has been compiled with the assumption that the function pointer you give it would return an `int`. Breaking this assumption will produce undefined behavior. The trick from the linked Q&A will work, though. – Sergey Kalinichenko Mar 18 '17 at 22:56
  • 1
    I read it. Is there going to be any performance gains anyway? I wanted to avoid comparisons and now we are back to it. Missing something here? – Mpr. Moe Mar 18 '17 at 23:00
  • @Mpr.Moe Comparison is not as bad as conditional execution. You first code snippet uses ternary `? :` operator, which has conditional execution. Comparison and subtraction do not use conditional execution, resulting in slightly better performance. All this is theory, though, because in practice you would hardly see any difference. – Sergey Kalinichenko Mar 18 '17 at 23:04
  • Oh my god, I don't believe that they didn't implement this correctly. The signum way is in fact slightly slower than 1st comparator (like 5% slower). Now, If I use the 2nd comparator as in my OP the gains are insane. From 11sec down to 3sec! Too bad it doesn't work. – Mpr. Moe Mar 18 '17 at 23:28