Is there a way to code a qsort comparison function for unsigned integers without using lots of branching statements?

Question

I wrote a (qsort-compatible) comparison function for a struct that has some unsigned fields in it:

typedef struct {
   int      a;
   unsigned b;
} T;

int cmp(T t1, T t2)
{
   // Decreasing order in "a"
   if (t1.a < t2.a) return +1;
   if (t1.a > t2.a) return -1;
   // Increasing order in "b"
   if (t1.b < t2.b) return -1;
   if (t1.b > t2.b) return +1;
   return 0;
}

Is there a way to write this function without needing two comparisons per field? I can't use the t1.b - t2.b trick because subtraction for unsigned integer wraps around.

I'm willing to accept answers using GCC extensions.

Answer 1

Use wider math.

Given int and unsigned fields, a given platform very likely supports a wider integer type such as long long that accommodates putting these 2 together.

int cmp(T t1, T t2)
{
   // An optimized compilation will not do any multiplication nor addition,
   // Just simply load `n1` high/low halves with `t1.a`, `t1.b`.
   long long n1 = t1.a * (UINT_MAX + 1LL) + t1.b;
   long long n2 = t2.a * (UINT_MAX + 1LL) + t2.b;
   return (n1 > n2) - (n1 < n2);  
}

If this approach is faster - profiling will answer that for select platforms.

Although this uses fewer compares, the compares use wider math - possible a zero sum gain.

When a 2x integer width is available as in How to determine integer types that are twice the width as `int` and `unsigned`?. This works. For high portability, stick with OP's original approach.

The (var1 > var2) - (var1 < var2) is considered by some to be branch-less. Of course OP's original code could end with:

return (t1.b > t2.b) - (t1.b < t2.b);

Answer 2

Any relational comparison between two values can only yield one of two results. You need three distinct results for a qsort comparison function, so a single comparison can't do the job. (Perl has a <=> operator that does exactly what you want, but it's not available in C.)

You'll need to evaluate 1 or 2 comparisons to compare the a values, plus 1 or 2 comparisons to compare the b values, for a total of up to 4 comparisons. You can write code that performs them more tersely, but it's going to be essentially equivalent to what you've already written.

Here's one possible slightly tricky solution:

int cmp(T t1, T t2) {
    return ((t2.a > t1.a) - (t2.a < t1.a)) || ((t2.b > t1.b) - (t2.b < t1.b));
}

I'd split it up like this:

int cmp(T t1, T t2) {
    return ((t2.a > t1.a) - (t2.a < t1.a))
           ||
           ((t2.b > t1.b) - (t2.b < t1.b));
}

The first half of the expression yields 0 if t1.a and t2.a are equal, -1 if t1.a < t2.a, and +1 if t1.a > t2.a. It depends on the fact that the relational operators always return either 0 or 1.

If the first half is either -1 or +1, the || short-circuits, and we're done; otherwise it goes on to compare the t1.b vs. t2.b.

This might actually be slightly less efficient than the code in your question since it always evaluates both t2.a > t1.a and t2.a < t1.a.

Incidentally, that's not a valid qsort comparison function. Such a function must take two const void* arguments. It can be written like this:

int cmp(const void *arg1, const void *arg2) {
    const T *t1 = arg1;
    const T *t2 = arg2;
    return ((t2->a > t1->a) - (t2->a < t1->a))
           ||
           ((t2->b > t1->b) - (t2->b < t1->b));
}

Answer 3

Assuming a restricted range of input values, a in range INT_MIN/2 .. INT_MAX/2, b in range 0 .. UINT_MAX/2, and assuming 2nd complement integer arithmetics, you can implement the compare function with one branch only:

int cmp(T t1, T t2)
{
   // Decreasing order in "a"
   int d = t2.a - t1.a;
   if (d) return d;

   // Increasing order in "b"
   return (int)(t1.b - t2.b);
}

Visual Studio 2013 disassembly:

  int d = t2.a - t1.a;
00FC1000  mov         eax,dword ptr [esp+0Ch]  
00FC1004  sub         eax,dword ptr [esp+4]  
  if (d) return d;
00FC1008  jne         cmp+12h (0FC1012h)  

  // Increasing order in "b"
  return (int)(t1.b - t2.b);
00FC100A  mov         eax,dword ptr [esp+8]  
00FC100E  sub         eax,dword ptr [esp+10h]  
}
00FC1012  ret  

Answer 4

When you may ignore this answer: all reasoning about branching is useless if compiler will generate branchless code both for Keit's answer and even for original OP's code (Keit's one is treated as condition ? ~0 : 0 and OP's one will generate CMOV).

Of course you may target a CPU without SETcc and CMOVcc instructions. In this case yes, I'd avoid branches (if possible) using subtraction (doing a small performance test to determine what is faster between long long and double). If you other preconditions and range limitation isn't an issue you may even go with plain integer math.

---

When you shouldn't ignore this answer: if your target CPU has not CMOVcc and/or SETcc (or equivalent) instructions.

You don't need to return exactly +1 and -1, any positive or negative value works well (assuming you want to optimize this function to reduce jumps, math operations are relatively cheap). If we can make assumptions about platform specific signed integers implementation (2's complement) and unsigned/signed conversion then first step to remove branches (introducing cheap subtractions) is:

int cmp(T t1, T t2) {
    if (t2.a != t1.a)
        return t2.a - t1.a;

    if (t1.b < t2.b)
        return -1;

    return (int)(t1.b - t2.b);
}

To remove 2nd branch we can rely on a well-defined behavior of unsigned (not signed) integers math: t1.b - t2.b will wrap (when t1.b is smaller than t2.b) then (int)(t1.b - t2.b) will be a negative number and 2nd if may be omitted. With that assumption code can be:

int cmp(T t1, T t2) {
    if (t2.a != t1.a)
        return t2.a - t1.a;

    return (int)(t1.b - t2.b);
}

Note 1: 2nd optimization works just in your case because you're ordering descending for T.b then it's not a general rule.

Note 2: here you're working with copied structures. Compiler may optimize your code to remove T copies but it's not required to do it then IMO you should check generated code or use pointers T* for cmp arguments (if possible). Expansive copies will vanish any other micro-optimization we may do here.

Explanation

I see some explanation is needed, if we're trying to reduce (to avoid AFAIK is impossible) branches then we have to consider both visible and invisible ones (otherwise no reason to even start this possibly micro-optimization).

Branches
Every condition (like t2->b > t1->b) is compiled with branches. Let me pick nice peace of code from Keith's answer:

((t2.a > t1.a) - (t2.a < t1.a))
||
((t2.b > t1.b) - (t2.b < t1.b))

For t2.a > t1.a compiler will produce this:

008413FE  mov  eax,dword ptr [t2]     ; Load t2.a in EAX
00841401  cmp  eax,dword ptr [t1]     ; Compare EAX with t1.a
00841404  jle  cmp+32h (0841412h)     ; Go to set result to not true
00841406  mov  dword ptr [ebp-0C4h],1 ; Result for t2.a > t1.a is 1 (true)
00841410  jmp  cmp+3Ch (084141Ch)     ; Go to perform t2.a < t1.a
00841412  mov  dword ptr [ebp-0C4h],0 ; Result for t2.a > t1.a is 0 (false)

Similar code is produced for 2nd part t2.a < t1.a. Same code is then repeated for right side of || ((t2.b > t1.b) - (t2.b < t1.b)). Let's count branches: fastest code path has five branches (jle, jmp in first part, jge, jmp in second part) for each sub-expression plus an extra jump for short-circuit of || (for a total of six branches). Slowest one has even few more. It's worse than original implementation with many ifs.

For comparison let's see what is generate for comparison with subtraction:

; if (t2.a != t1.a)
00F313FE  mov  eax,dword ptr [t2] ; Load t2.a
00F31401  cmp  eax,dword ptr [t1] ; Compare with t1.a
00F31404  je   cmp+2Eh (0F3140Eh) ; If they are equal then go work with T.b

; return t2.a - t1.a;
00F31406  mov  eax,dword ptr [t2]  ; Load t2.a
00F31409  sub  eax,dword ptr [t1]  ; Subtract t1.a
00F3140C  jmp  cmp+34h (0F31414h)  ; Finished

This is our best code path, just two branches. Let's see 2nd part:

; return (int)(t1.b - t2.b);
00F3140E  mov  eax,dword ptr [ebp+0Ch] ; Load t1.b
00F31411  sub  eax,dword ptr [ebp+14h] ; Subtract t2.b

No more branches here. Our fastest and slowest code paths always have same number of branches.

Subtractions
Why subtractions work? Let's see with simple values and some edge cases Suma picked in comments. Let's say:

t1.a = 1;
t2.a = 10;

t1.b = 10;
t2.b = 1;

Then we have:

t2.a - t1.a == 10 - 1 == 9. Positive number as required in original code (if (t1.a < t2.a) return +1;). Opposite case is trivial. Here we're assuming signed integer math will wrap.

(int)(t1.b - t2.b) == 10 - 1 == 9. Positive number as required (inverse ordering for T.a and T.b). This needs more explanation because of edge cases. Imagine t1.b is UINT_MAX and t2.b is 0. t1.b - t2.b is still UINT_MAX and it has to be casted to int, it's bit pattern is 0xFFFFFFFF, exactly bit pattern of -1 for a signed int. Result is again correct. Note that here we're assuming two important things: signed numbers are represented in 2's complement and unsigned to signed conversion simply reinterpret raw memory value with new given type (no explicit calculation is done).

As noted by Suma problems arise when numbers are big, if you want full int and unsigned int range then you may simply cast them to double:

int cmp(T t1, T t2) {
    if (t2.a != t1.a)
        return (int)((double)t2.a - t1.a);

    return (int)((double)t1.b - t2.b);
}

Extract of generated assembly code:

; return (double)t2.a - (double)t1.a;
01361926  cvtsi2sd  xmm0,dword ptr [t2]  ; Load t2.a
0136192B  cvtsi2sd  xmm1,dword ptr [t1]  ; Load t1.a
01361930  subsd     xmm0,xmm1            ; Subtract t1.a to t2.a
01361934  cvttsd2si eax,xmm0             ; Convert back
01361938  jmp       cmp+88h (01361988h)

In this way the only tuple you can't use is INT_MIN for t1.a together with INT_MAX for t2.a.

Answer 5

This does not reduce the number of conditions compiled, however it does reduce the number of conditions executed:

if(t1.a != t2.a)
    return t1.a < t2.a ? -1 : 1;
if(t1.b != t2.b)
    return t1.b < t2.b ? -1 : 1;
return 0;

If the two a members are equal, no more comparision is done on them. For N-field sorting you would do maximum N+1 comparisions, compared to 2N comparisions for original code.