How to optimize a statement of the form "if (A == B) { ...} else if (A < B) {...} else { ....}"

Question

I have a piece of code that's like

if (A == B)
{
    ...
}
else if (A < B)
{
    ... 
}
else // (A > B)
{
    ...
}

I realize there is a redundancy problem because there will be some of the same bit comparisons going into the computation of == and <. How can I optimize my code to make it fancier and faster?

Branch prediction is going to influence how fast this will run much more than minimizing one comparison. — amit, May 28 '14 at 17:42
Other than that - this is really a premature optimization, if you have a logic with 3 different behaviors for `<,>,==` you should use the 3 conditions as you described, makes it readable. — amit, May 28 '14 at 17:43
I think you should change your user name. [Donald Knuth](https://de.wikipedia.org/wiki/Donald_Knuth) would know the solution :-) — Bergi, May 28 '14 at 17:56
Some languages might offer a [three way comparison](https://en.wikipedia.org/wiki/Three-way_comparison). — Bergi, May 28 '14 at 18:46

phuclv · Answer 1 · 2018-07-29T12:17:55.260

You're not specifying the language but depending on language this could be rewritten in many ways

Ruby way (using the spaceship operator):

case A <=> B
    when -1 then... # A < B
    when  0 then... # A = B
    when  1 then... # A > B
end

Perl, PHP7 and Groovy also have the same operator. Many other languages have similar operators or functions for the same combined comparison purpose like cmp in Python 2, compare in OCaml and compareTo in Kotlin. C# doesn't have that operator but it has the IComparable interface with CompareTo method.

VB way:

Select Case A
    Case Is < B
        ...
    Case Is = B
        ...
    Case Is > B
        ...
End Select

In C, C++ and many C-like languages without CompareTo method you can use this way

int cmp = (A > B) - (A < B);
switch (cmp)
{
    case -1: ...
    case  0: ...
    case  1; ...
}

Many languages like Java don't allow you to directly use the comparison results as a numeric value. In that case you can use the signum function

switch(Integer.signum(A - B))

You can implement signum function easily in C and C++ like this

Those are for the high-level languages. At the assembly level things are simpler. In x86 assembly only a single comparison is needed, then depending on the result we'll jump to the corresponding block, so it's not 3 comparisons and the compiler is smart enough to optimize this simple case. For example:

    cmp eax, ebx
    je EQUAL_TO      ; jump if =
    ja GREATER_THAN  ; jump if >

    ; less than case's code
    jmp END_CMP

EQUAL_TO:
    ; equal case's code
    jmp END_CMP

GREATER_THAN:
    ; larger than case's code

END_CMP:

The same to other architectures with comparison flags like ARM or 68k... For architectures without a flag like MIPS you may need one more comparison but never 3 comparisons

MIPS example:

    beq $t0, $t1, EQUAL_TO       # $t0 = A, $t1 = B; if ($t0 == $t1) equal();
    slt $t0, $t1, $t2            # $t2 = is_less_than = ($t0 < $t1);
    beq $t2, $zero, GREATER_THAN # if (!is_less_than) larger();

    # "less than" code here
    # ...
    j END_CMP

EQUAL_TO:
    # "equal" code
    # ...
    j END_CMP

GREATER_THAN:
    # "larger" code
    # ...

END_CMP:

For architectures with conditional instructions like ARM or Itanium and with simple enough body in the if-else blocks you may not even need a jump

Good answer for assembly though after having tested for equal and above/greater all that remains is below/less which therefore does not need a test of its own - as per the OP's example. This is what gcc and other compilers would do. In for-debugging generated code you would probably have the two tests performed explicitly, comparison and all. The OP's code might be (somewhat) optimized by testing for the most common/time critical case first and then moving on to less and less common/time critical variants. — Olof Forshell, Dec 20 '14 at 11:18

score 0 · Accepted Answer · edited May 29 '14 at 08:50

For C# you could use a generic function that takes in the 2 values, and then a lambda action for each case.

void CompareAndAct<T>(T a, T b, Action fnEqualTo, Action fnLessThan, Action fnGreaterThan)  {

   var comparison = System.Collections.Generic.Comparer<T>.Default.Compare(a, b);
   if (comparison == 0) {
      fnEqualTo();
   }
   else if (comparison < 0) {
      fnLessThan();
   }
   else {  //A > B
      fnGreaterThan();
   }
}

Then you can re-use it as much as you wanted like so:

CompareAndAct(a,b, () => Console.Writeline("Equal"),() => Console.WriteLine("Less Than", () => Console.WriteLine("Greater Than"));

I can't say I'd recommend doing this, but it'd work. It's no faster (prob slower), but I suppose one could say that it's "fancier."

How to optimize a statement of the form "if (A == B) { ...} else if (A < B) {...} else { ....}"

2 Answers2