How to improve a bunch of else-if conditions that evaluate a variable inside a range among known values?

Question

Is there any way to convert this code below into something more scalable? I've simplified it, but my real one has to check for several different values and it is asking for refactoring.

     if (x < 0) foo1();
else if (x < 3) foo2();
else if (x < 8) foo3();
else            foo4();

I've tried the following:

struct Ptr2foo {
    void (*foo_x)();
}

Ptr2foo ptr2foo_x[4] {
    foo1,
    foo2,
    foo3,
    foo4
}

ptr2foo_x[someMagicWithMy_X_AndMyKnownValues].foo_x();

Those values are known before compiling, and that amount of conditions inside a loop are killing performance.

Is this the best way to approach this issue? Any alternative solution with its explanation is highly appreciated

Answer 1

In the general case that you have some intervals [a1, a2), [a2, a3), ..., [an, infty) and want to find the interval in which x lies, you can do it with worst-case log n comparisons (vs. your if-else-chain that has worst-case n comparisons). You do that by doing binary search on the intervals. So you will check first if x is smaller than a(n/2) and then further check the smaller intervalls in the if-case and the bigger in the else-case. For your example from above, transform

     if (x < 0) foo1();
else if (x < 3) foo2();
else if (x < 8) foo3();
else            foo4();

which has 4 comparisons on it longest path and 1 on its shortest to

if( x < 3 ) {
  if( x < 0 ) foo1();
  else        foo2();
} else {
  if( x < 8 ) foo3();
  else        foo4();
}

This has 2 comparisons on all its paths.

Note that less comparisons in the worst case are not necessarily faster. It is faster if x is roughly equally distributed. If x is negative in 90% of the cases, your first version will be faster since it mostly will only use one comparison, while my version uses always 2.

That is why you should also think about what is the hot-path (i.e. most frequent path) through this code is. If maybe x is at least 8 in most cases, you should definitely check it first and so on.