case 标签的顺序对 switch 语句的效率有多大影响? [英] How much does the order of case labels affect the efficiency of switch statements?

问题描述

Consider:

if (condition1)
{
    // Code block 1
}
else
{
    // Code block 2
}

If I know that condition1 will be true the majority of the time, then I should code the logic as written, instead of:

if (!condition1)
{
    // Code block 2
}
else
{
    // Code block 1
}

since I will avoid the penalty of the jump to the second code block (note: I have limited knowledge of assembly language). Does this idea carry forward to switch statements and case labels?

switch (myCaseValue)
{
    case Case1:
        // Code block 1
        break;

    case Case2:
        // Code block 2
        break;

    // etc.
}

If I know that one of the cases will happen more often, can I rearrange the order of the case labels so that it's more efficient? Should I? In my code I've been ordering the case labels alphabetically for code readability without really thinking about it. Is this micro-optimization?

解决方案

Some facts for modern hardware like x86 or x86_64:

• A unconditionally taken branch has almost no additional costs, besides the decoding. If you want a number, it's about a quarter clock cycle.
• A conditional branch, which was correctly predicted, has almost no additional costs.
• A conditional branch, which was not correctly predicted, has a penalty equal to the length of the processor pipelines, this is about 12-20 clocks, depending on the hardware.
• The prediction mechanisms are very sophisticated. Loops with a low number of iterations (on Core 2 for example up to 64) can be perfectly predicted. Small repeating patterns like "taken-taken-nottaken-taken" can be predicted, if they are not too long (IIRC 6 on Core2).

You can read more about branch prediction in Agner Fogs excellent manual.

Switch statements are usually replaced by a jump table by the compiler. In most cases the order of cases won't make a difference at all. There are prediction mechanisms for indirect jumps as well.

So the question isn't if your jumps are more likely to be taken, it is if they are well predictable, at least for the hardware you intend to run your code on. This isn't an easy question at all. But if you have branches depending on a random (or pseudo random) condition, you could try to reformulate it as a branchless statement if possible.

这篇关于case 标签的顺序对 switch 语句的效率有多大影响?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！