代码之家 › 专栏 › 技术社区 › Jon Seigel

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

conditional-statements performance c c++ c#

Jon Seigel · 技术社区 · 15 年前

考虑:

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.
}

如果我知道其中一种情况会更频繁发生,我可以重新排列 案例 贴标签以便更有效?我应该吗?在我的代码中,为了代码的可读性,我一直按字母顺序排列大小写标签,而没有真正考虑它。这是微观优化吗?

9 回复 | 直到 15 年前

Gunther Piez 15 年前

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

无条件执行的分支除了解码之外几乎没有额外的成本。如果你想要一个数字,大约是四分之一时钟周期。
一个有条件的分支机构,经过正确的预测,几乎没有额外的成本。
没有正确预测的条件分支的惩罚等于处理器管道的长度,这大约是12-20个时钟,具体取决于硬件。
预测机制非常复杂。迭代次数较少的循环(例如核心2上多达64次)可以完全预测。如果时间不太长,可以预测像“taketakenottaken”这样的小重复模式(核心2上的IIRC 6)。

您可以阅读更多关于Agner Fogs中分支预测的内容优秀 manual.

switch语句通常由编译器用跳转表替换。在大多数情况下,案件的顺序根本不会有什么不同。也有间接跳跃的预测机制。

所以问题不在于你的跳跃是否更有可能被执行,而是它们是否可以很好地预测,至少对于你打算运行代码的硬件来说。这个问题一点也不简单。但是,如果您有依赖于随机(或伪随机)条件的分支,您可以尝试在可能的情况下将其重新表述为无分支语句。

PeterAllenWebb 15 年前

您关于if语句的结论在我熟悉的大多数硬件上都不正确。问题不是你在跳,而是你在分支。根据比较的结果,代码可以有两种不同的方式。这会使大多数现代CPU上的管道停止运行。分支预测是常见的,并且大多数时候都会解决问题,但与您的示例无关。预测者同样能很好地预测一个比较是错误的,就像它能预测是正确的一样。

和往常一样,见维基百科: Branch Predictor

AnT stands with Russia 15 年前

这要看情况而定。编译器将使用一系列与实现相关的内部标准来决定是否实现 switch 作为if-like测试的序列,或作为跳转表。例如,这可能取决于您的 case 标签是。如果你的 案例 标签值形成一个“密集”集合,编译器可能更倾向于使用跳转表,在这种情况下 案例 标签无关紧要。如果它决定采用类似于if-else序列的测试,那么顺序可能很重要。

不过,请记住, 转换 是一个大声明,带有 案例 为该语句提供多个入口点的标签。因此,编译器(以及您的)可以重新排列 案例 该语句中的“子块”可能受到限制。

JaredPar 15 年前

为了可读性,应以最有效的方式订购箱标签。

为了提高效率而重新排序案例标签是一种过早的优化,除非一个探查器明确告诉您这是一个问题。

Michael Burr 15 年前

我认为即使是你最初的前提-你可以优化 if 重新排列条件的陈述很可能是错误的。在一个非优化的构建中,你可能会发现做你所说的有一些价值——也许。在一般情况下,对于任何一种情况,您都必须至少跳一次,因此(一般情况下)无论如何安排条件都没有好处。但这是针对未优化的构建的,那么谁关心优化呢?

在优化的构建中,我想您可能会惊讶于编译器有时为if语句生成什么。编译器可能会将一个或另一个(或两个)案例移动到某个不一致的地方。我认为,你试图通过玩“先到”的条件来幼稚地优化这一点,不一定会做你想做的。最好只有在检查编译器正在生成什么之后才能这样做。当然,这会成为一个昂贵的过程,因为即使在语句周围做一点点的更改,也会改变编译器决定生成输出代码的方式。

现在,就switch语句而言,我总是使用 switch 当它使代码更具可读性时。编译器应该对 转换 等价于 如果 语句将生成相同的代码。对于多个情况,switch语句通常被编译为跳转表。但又有一套 如果 将单个变量与一组值进行比较的测试可能会被编译器很好地识别出来,以便它也能做到这一点。不过,我想使用开关可以使编译器更容易地识别这种情况。

如果您真的对充分利用该条件的性能感兴趣,可以考虑使用 MSVC's Profile Guided Optimization (pgo或“pogo”),它使用分析运行的结果来优化如何生成条件。我不知道GCC是否有类似的能力。

Seth Moore 15 年前

我不确定C编译器,但我知道在汇编中,switch语句实际上可以被编程为跳转到特定行,而不是像if语句那样计算表达式。因为在select中,您拥有所有的常量,所以它只将case视为行号,而直接跳转到传入的行号(case值),而不进行任何计算。这使得案例陈述的顺序根本不重要。

Mike Dunlavey 15 年前

我假设你知道,只有当这是一个热点时,这才有关系。判断它是否是一个热点的最佳方法是运行代码,对程序计数器进行采样,并查看它是否在那里超过10%的时间。如果它是一个热点,请查看在执行 if 或 switch . 通常可以忽略不计,除非 Block 1 和/或 Block 2 做几乎 没有什么 . 您可以为此使用分析器。我只是反复停顿。

如果您不熟悉汇编语言,我建议您学习它,足够了解编译器生成的内容。这很有趣,也不难。

Ken Rose 15 年前

正如其他人所说,这取决于很多事情,包括有多少情况,如何进行优化,以及您正在运行的体系结构。有关有趣的概述,请参见 http://ols.fedoraproject.org/GCC/Reprints-2008/sayle-reprint.pdf

-2

Jeremy Morgan 15 年前

如果您将最常见的情况放在第一位,这将稍微优化代码,并且由于开关语句的工作方式,这也是正确的。当程序进入switch并发现一个正确的情况时,它将执行并点击break,这将退出循环。你的想法是正确的。

但是,我确实认为这种优化是非常小的,如果它减慢了开发时间,那么它可能不值得。另外,如果您必须彻底修改您的程序流以适应这一点,那么它可能不值得。你最多只能节省几个周期,而且可能永远也看不到改善。