14

考虑:

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标签的顺序以提高效率吗?我是不是该?在我的代码中,为了代码的可读性,我一直按字母顺序排列案例标签,而没有真正考虑过。这是微优化吗?

4

9 回答 9

33

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

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

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

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

所以问题不在于您的跳跃是否更有可能被采用,而是它们是否可以很好地预测,至少对于您打算在其上运行代码的硬件而言。这根本不是一个简单的问题。但是,如果您有取决于随机(或伪随机)条件的分支,则可以尝试将其重新表述为无分支语句(如果可能)。

于 2009-12-01T17:01:54.043 回答
7

您关于 if 语句的结论在我熟悉的大多数硬件上都不会成立。问题不在于你在跳跃,而在于你在分支。根据比较的结果,代码可以采用两种不同的方式。这可能会使大多数现代 CPU 上的流水线停止。分支预测很常见,并且大部分时间都可以解决问题,但与您的示例无关。预测器同样可以很好地预测比较是假的,因为它可以是真的。

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

于 2009-12-01T16:49:25.593 回答
6

这取决于。编译器将使用一堆内部实现相关的标准来决定是switch作为 if 类测试序列还是作为跳转表来实现。例如,这可能取决于您的case标签集有多“紧凑”。如果您的case标签值形成“密集”集,则编译器可能更可能使用跳转表,在这种情况下,case标签的顺序无关紧要。如果它决定使用类似于 if-else 测试的序列,那么顺序可能很重要。

但请记住,主体switch是一个大型语句,case标签提供了该语句的多个入口点。因此,编译器(以及您的)case在该语句中重新排列“子块”的能力可能会受到限制。

于 2009-12-01T16:46:23.303 回答
3

案例标签应以最有效的方式排序以提高可读性。

重新排序案例标签以提高效率是一种过早优化的情况,除非分析器明确告诉您这是一个问题。

于 2009-12-01T16:45:26.240 回答
3

我认为即使是您最初的前提 - 您可以if通过重新排列条件来优化语句也可能是错误的。在未优化的构建中,您可能会发现做您正在谈论的事情有一些价值 - 也许。在一般情况下,无论哪种情况,您都必须至少跳一次,因此(通常)安排条件没有任何优势。但那是针对未优化的构建,那么谁在乎优化呢?

在优化的构建中,我认为您可能会对编译器有时为 if 语句生成的内容感到惊讶。编译器可能会将一种或另一种(或两种)情况移到不符合要求的地方。我认为你试图天真地通过使用“首先出现”的条件来优化这一点不一定会做你想做的事。充其量只能在检查编译器生成的内容之后执行此操作。而且,当然,这将成为一个代价高昂的过程,因为即使您对语句所做的最轻微的更改也会改变编译器决定生成输出代码的方式。

现在,就 switch 语句而言,我总是使用 a switchwhen 它使代码更具可读性。编译器对switch等价于语句的语句所做的最糟糕的事情if是生成相同的代码。不止少数情况,switch语句一般会编译成跳转表。但话又说回来,一组if将单个变量与一组值进行比较的测试很可能会被编译器识别,这样它就会做同样的事情。但是,我猜想使用开关将使编译器更容易识别这种情况。

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

于 2009-12-01T19:02:36.013 回答
2

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

于 2009-12-01T16:56:45.770 回答
1

我假设您知道只有当这是一个热点时才重要。判断它是否是热点的最好方法是运行代码,对程序计数器进行采样,然后查看它是否存在超过 10% 的时间。if如果它是热点,请查看执行or花费了多少时间switch。通常它可以忽略不计,除非你Block 1和/或Block 2几乎什么都不做。您可以为此使用分析器。我只是反复暂停。

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

于 2009-12-01T20:06:40.283 回答
0

As others have said, it depends on lots of things, including how many cases there are, how optimization is done, and the architecture you're running on. For an interesting overview, see http://ols.fedoraproject.org/GCC/Reprints-2008/sayle-reprint.pdf

于 2009-12-02T04:04:37.657 回答
-2

如果将最常发生的情况放在首位,这将稍微优化代码,并且由于 switch 语句的工作方式,情况也是如此。当程序进入 switch 并找到一个为 true 的 case 时,它​​将执行它并点击 break,这将退出循环。你的想法是正确的。

但是,我确实认为这种优化非常小,如果这样做会减慢您的开发时间,那可能不值得。此外,如果您必须大幅修改程序流程以适应这种情况,那可能不值得。您最多只能节省几个周期,并且可能永远不会看到改进。

于 2009-12-01T16:46:41.513 回答