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

Question

If you have the following:

$var = 3; // we'll say it 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 you say that 80% of the time of $var is 3, are you worried that it goes through 4 cases before finding the true case?

I think this is not a big deal on a small site, but what about when this if statement will run 1000 seconds per second?

I work in PHP, but I think the language does not matter.

Answer 1

This is how we did it when I wrote software for radar systems. (Speed ​​matters in the radar. This is one of the few places where "real time" actually means "real" rather than "fast.")

[I will switch to Python syntax, this is 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. When you add conditions to this list, you move around the center of the tree. A flat sequence of n comparisons takes on average n / 2 steps. The tree leads to a sequence of comparisons that takes into account log (n).

Answer 2

Well, I find that almost all the time, clarity, say, with numerically ordered values ​​overrides any tiny benefits you can get by reducing the number of comparison instructions.

Having said that, as with all optimization:

• Make it work.
• Measure it
• If it's fast enough, leave it alone
• If it is too slow, then optimize it

Oh, and I'll probably use the switch / case from the start !; -)

Answer 3

The classic case of this event (with literally 5 options, as in your post) was in ffmpeg, in the decode_cabac_residual function. This was quite important, since profiling (very important - do not optimize before profiling!) Showed that it was calculated at 10-15% of the time spent decoding H.264 video. The if operator controlled many operators that were calculated differently for different types of residues 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. Therefore, you should use the if chain instead.

Profiling was carried out in many ordinary test threads in order to order them in terms of probability; the upper part was the most common, the lower - the least. This gave a small increase in speed.

Now, in PHP, I suspect that it is much less than the low-level style speed increase you would get in C, as in the example above.

Answer 4

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

This allows the compiler (interpreter) to use the jump table to jump to the correct branch without performing N comparisons. Think about it by creating an array of addresses indexed as 0, 1, 2, .., then it may just look right in the array in one operation.

Plus, since the case description has less syntactic overhead, it is also easier to read.

Update: if comparisons are suitable for the switch statement, then this is the area in which profiles can be optimized. By running the PGO assembly with realistic test loads, the system can generate information about branch usage, and then use it to optimize the distance traveled.

Answer 5

If the code needs to perform additional tests, it will certainly run slower. If performance is important in this section of code, you should first post the most common cases.

I usually agree with the “measurement, then optimization” method, when you are not sure if the performance will be fast enough, but if the code just needs to be executed as quickly as possible And the correction is as simple as reordering the tests, then I would quickly make the code and I’ll take some measurements after you go live to make sure that your assumption (for example, that 3 will happen in 80% of cases) is really correct.

Answer 6

Instead of answering a PHP question, I will answer a bit in general. It does not 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 necessary, and the tests in the elif parts are quite simple (and the rest of the semantics are compatible). For 3-4 tests, it is not necessary to get anything using the conversion table.

The reason is that the predictor branch in the CPU is really good at predicting what is going on. In fact, the only thing that happens is a little higher pressure on the choice of a team, but it is unlikely to be destroying the world.

In your example, however, most compilers recognize that $ var is a constant of 3, and then replaces $ var with 3 in if..elif blocks ... This, in turn, makes the expressions constant, so they add up either to true, either false. All false branches kill the dead code ejector, and the truth test is also eliminated. The case remains when $ var == 3. You cannot rely on PHP, albeit smart. In general, you cannot distribute $ var, but this is possible on some sites.

Answer 7

You can try to have an array of code blocks that you are accessing. 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]->(); } 

Answer 8

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

 $var = 3; // we'll say it 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 you make more complex comparisons, I would either nest them in the switch, or just use elseif.

Answer 9

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

Answer 10

Only you can determine if the performance difference will optimize the order or rebuild it on the actual binary tree. But I suspect that you will have to have millions of times per second, not thousands, even think about it in PHP (and even more so in some other languages).

Time. See how many times per second you can run the above if / else if / else statement without any action, and $ var is not one option.