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 if
s.
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
.
cmp
function definition on one line. Of course you shouldn't, but I don't think putting it on one line is really your goal. I suggest updating your title to reflect what you're actually asking. – Stactea
andb
values, or are they using whole possible range of their types? – YeorgiJcc
, in my case it generatedCMOV
and full function is branchless. – Panelqsort()
. It should beint cmp(T *t1, T *t2);
2 pointers, not two structures copied by value. – Satanic