案例标签的顺序对switch语句的效率有多大影响？

Question

考虑:

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

如果我知道这condition1将是true大部分时间,那么我应该将逻辑编写为编写,而不是:

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

因为我将避免对jump第二个代码块的惩罚(注意:我对汇编语言的了解有限).这个想法是否继续switch发表声明和case标签？

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

    case Case2:
        // Code block 2
        break;

    // etc.
}

如果我知道其中一个案例会更频繁发生,我可以重新排列case标签的顺序,以便更有效吗？我是不是该？在我的代码中,我一直在按字母顺序排列案例标签以获得代码可读性,而没有真正考虑它.这是微优化吗？

Answer 1

现代硬件如x86或x86_64的一些事实:

• 除了解码之外,无条件采用的分支几乎没有额外的成本.如果你想要一个数字,它大概是四分之一个时钟周期.
• 正确预测的条件分支几乎没有额外成本.
• 没有正确预测的条件分支的惩罚等于处理器流水线的长度,这大约是12-20个时钟,具体取决于硬件.
• 预测机制非常复杂.迭代次数较少的循环(在Core 2上,例如最多64次)可以完美预测.如果它们不太长(Core2上的IIRC 6),可以预测像"采取采取未采取"这样的小重复模式.

您可以在Agner Fogs优秀手册中阅读有关分支预测的更多信息.

Switch语句通常由编译器的跳转表替换.在大多数情况下,案件的顺序根本不会产生任何影响.间接跳跃也有预测机制.

所以问题不在于你是否更有可能进行跳转,如果它们是可以预测的,至少对于你打算运行代码的硬件来说是这样.这根本不是一个简单的问题.但是如果你有一个取决于随机(或伪随机)条件的分支,你可以尝试将其重新表述为无分支语句.

Answer 2

关于if语句的结论在我熟悉的大多数硬件上都不会出现.问题不在于你在跳跃,而在于你正在分支.代码可以采用两种不同的方式,具体取决于比较结果.这可能会阻止大多数现代CPU上的管道.分支预测很常见,并且在大多数情况下修复了问题,但与您的示例无关.预测器同样可以预测比较将是错误的,因为它可能是真的.

像往常一样,请参阅维基百科:分支预测器

Answer 3

这取决于.编译器将使用一组依赖于内部实现的标准来决定是将其实现switch为if-like测试序列还是跳转表.例如,这可能取决于您的case标签组的"紧凑" 程度.如果您的case标签值形成"密集"集,则编译器可能更有可能使用跳转表,在这种情况下,case标签的排序无关紧要.如果它决定使用类似于if-else测试的序列,则顺序可能很重要.

但请记住,主体switch是一个大型语句,case标签为该语句提供了多个入口点.出于这个原因,编译器case在该语句中重新排列"子块"的能力(以及你的能力)可能是有限的.