How often do you worry about how many if cases will need to be processed?

Question

If you have the following:

$var = 3; // we'll say it's set to 3 for this example
if ($var == 4) {
    // do something
} else if ($var == 5) {
    // do something
} else if ($var == 2) {
    // do something
} else if ($var == 3) {
    // do something
} else {
    // do something
}

If say 80% of the time $var is 3, do you worry about the fact that it's going through 4 if cases before finding the true case?

I'm thinking on a small site it's not a big deal, but what about when that if statement is going to run 1000s of times a second?

I'm working in PHP, but I'm thinking the language doesn't matter.

Answer 1

A classic case of this occurring (with literally 5 options as in your post) was in ffmpeg, in the decode_cabac_residual function. This was rather important, as profiling (very important--don't optimize before profiling!) showed it counted for upwards of 10-15% of the time spent in H.264 video decoding. The if statement controlled a set of statements which was calculated differently for the various types of residuals to be decoded--and, unfortunately, too much speed was lost due to code size if the function was duplicated 5 times for each of the 5 types of residual. So instead, an if chain had to be used.

Profiling was done on many common test streams to order them in terms of likelihood; the top was the most common, the bottom the least. This gave a small speed gain.

Now, in PHP, I suspect that there's a lot less of the low-level style speed gain that you'd get in C, as in the above example.

Answer 2

Well, I believe that almost all the time, the legibility of, say, having numerically ordered values would override any tiny benefits you may gain by reducing the number of comparison instructions.

Having said that, as with all optimisation:

1. Make it work
2. Measure it
3. If it's fast enough, leave it alone
4. If it's too slow, THEN optimise it

Oh, and I'd probably use a switch/case from the get-go! ;-)

Answer 3

If the code has to do additional tests then it will certainly run more slowly. If performance is critical in this section of code then you should put the most common case(s) first.

I normally agree with the "measure, then optimize" method when you're not sure if the performance will be fast enough, but if the code simply needs to run as fast as possible AND the fix is as easy as rearranging the tests, then I would make the code fast now and do some measuring after you go live to insure that your assumption (e.g. that 3 is going to happen 80% of the time) is actually correct.

Answer 4

Here's how we did it when I used to write software for radar systems. (Speed matters in radar. It's one of the few places where "real time" actually means "real" instead of "fast".)

[I'll switch to Python syntax, it's easier for me and I'm sure you can interpret it.]

if var <= 3:
    if var == 2:
        # do something
    elif var == 3:
        # do something
    else: 
        raise Exception
else:
    if var == 4:
        # do something
    elif var == 5:
        # do something
    else:
        raise Exception

Your if-statements form a tree instead of a flat list. As you add conditions to this list, you jiggle around the center of the tree. The flat sequence of n comparisons takes, on average, n/2 steps. The tree leads to a sequence of comparisons that takes log(n) comparisons.

Answer 5

Using a switch/case statement is the definitely the way to go here.

This gives the compiler (interpreter) the chance to utilize a jump table to get to the right branch without having to do N comparisons. Think of it creating an array of addresses indexed as 0, 1, 2, .. then it can just look the correct one up in the array in a single operation.

Plus, since the is less syntatic overhead in a case statement, it reads easier too.

Update: if the comparisons are suitable for a switch statement then this is an area where profile guided optimizations can help. By running a PGO build with realistic test loads the system can generate branch usage information, and then use this to optimize the path taken.

Answer 6

With code where it is purely an equality analysis I would move it to a switch/case, as that provides better performance.

$var = 3; // we'll say it's set to 3 for this example
switch($var)
 {
   case 4:
      //do something
      break;
   case 5:
      //do something
      break;
   case:
      //do something when none of the provided cases match (same as using an else{ after the elseif{
 }

now if your doing more complicated comparisons I would either nest them in the switch, or just use the elseif.

Answer 7

In object-oriented languages, if an option provides massive ifs, then that means you should just move the behavior (e.g., your //do something blocks) to the object containing the value.

Answer 8

Only you can tell if the performance difference of optimizing the order, or rearranging it to in effect be a binary tree, would make a significant difference. But I suspect you'll have to have millions of times per second, not thousands, to even bother thinking about it in PHP (and even more so in some other languages).

Time it. See how many times a second you can run the above if/else if/else statement with no action being taken and $var not being one of the choices.

Answer 9

Rather than answer the PHP question, I'll answer a bit more generally. It doesn't apply directly to PHP as it will go through some kind of interpretation.

Many compilers can convert to and from if-elif-elif-... blocks to switch blocks if needed and the tests in the elif-parts are simple enough (and the rest of the semantics happens to be compatible). For 3-4 tests there is not necessarily anything to gain by using a jump table.

The reason is that the branch-predictor in the CPU is really good at predicting what happens. In effect the only thing that happens is a bit higher pressure on instruction fetching but it is hardly going to be world-shattering.

In your example however, most compilers would recognize that $var is a constant 3 and then replace $var with 3 in the if..elif.. blocks. This in turn makes the expressions constant so they are folded to either true of false. All the false branches is killed by the dead-code eliminator and the test for true is eliminated as well. What is left is the case where $var == 3. You can't rely on PHP being that clever though. In general you can't do the propagation of $var but it might be possible from some call-sites.

Answer 10

You could try having an array of code blocks, which you call into. Then all code blocks have the same overhead.

Perl 6:

our @code_blocks = (
  { 'Code Block 0' },
  { 'Code Block 1' },
  { 'Code Block 2' },
  { 'Code Block 3' },
  { 'Code Block 4' },
  { 'Code Block 5' },
);

if( 0 <= $var < @code_blocks.length ){
  @code_blocks[$var]->();
}