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

Question

考虑以下代码：

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

如果我知道condition1大部分时候都会是true，那么我应该按照原本的逻辑编码，而不是：

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

由于我将避免跳转到第二个代码块的惩罚（注意：我对汇编语言的知识有限），所以这个想法是否适用于switch语句和case标签呢？

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

    case Case2:
        // Code block 2
        break;

    // etc.
}

如果我知道其中一种情况更常见，是否可以重新排列case标签的顺序以使效率更高？我应该这样做吗？在我的代码中，我按字母顺序对case标签进行排序，以提高代码的可读性，但没有真正考虑过这个问题。这算是微观优化吗？

- Jon Seigel

---

这是一种微小的优化。 - Michael Burr

@Andy E: 但我的真正观点是，人们似乎假定在SO上问问题的人不懂基本知识，比如花很多时间优化不需要快速运行的代码是一个错误。然后他们抓住这一点而不是回答更难的问题。 - PeterAllenWebb

OP要求进行优化。虽然一般认为过早地进行优化是不好的，但这并不一定使任何微观优化都是坏的。为什么不假设OP已经完成了所有宏观优化，现在想要做更多优化呢？确实，这种情况可能非常罕见，但@Andy E：仅因为您似乎不知道任何性能不重要的应用程序，就错误地假设它们不存在。如果执行速度差异是可察觉的，则取决于观察者。 - Gunther Piez

无论是微优化还是不是，我都觉得这个问题很有趣。 - Nemanja Trifunovic

在特定的上下文之外，不存在所谓的“过早优化”。当有人提出一个抽象的无上下文关联的优化问题时，比如本例中的OP，用“过早优化”的言论攻击发帖人是最毫无意义的事情之一。如果发帖人想知道他们的优化是否“过早”，发帖人会具体询问并提供适当的上下文。在那之前，请不要将毫无根据的“过早优化”评论引入讨论。 - AnT stands with Russia

Answer 1

针对现代硬件，如 x86 或 x86_64，有以下几点需要注意：

• 无条件跳转除了解码之外几乎没有额外的开销。如果你需要一个数字，大约是四分之一个时钟周期。
• 已正确预测的条件跳转几乎没有额外开销。
• 未正确预测的条件跳转会产生惩罚，惩罚的长度等于处理器流水线的长度，这约为 12-20 个时钟周期，具体取决于硬件。
• 预测机制非常复杂。低迭代次数的循环（例如 Core 2 上最多可达 64 次）可以完美预测。像 "taken-taken-nottaken-taken" 这样的小重复模式也可以预测，但如果它们太长（Core2 上为 6），就无法预测。

您可以在 Agner Fog 的优秀手册中了解更多关于分支预测的知识：manual.

编译器通常会使用跳转表替换 switch 语句。在大多数情况下，case 的顺序不会有任何影响。对于间接跳转，也有预测机制。

因此，问题并不是你的跳转更可能被执行，而是它们是否可以被很好地预测，至少对于你计划在其上运行代码的硬件而言。这并不是一个容易回答的问题。但是如果您的分支依赖于随机（或伪随机）条件，如果可能，您可以尝试将其重新表述为无分支语句。

- Gunther Piez

---

到目前为止，这是最好的答案。除了微控制器外，不要假设您的C代码在伪机器代码中有1:1的翻译。在现代处理器中，有许多参数对于您的C代码是不可见的，但可能会对性能产生影响：缓存局部性、TLB、寄存器溢出、页面故障、分支预测、高速缓存的关联性等等......所有这些都可能对您的优化工作产生意想不到的影响。 - Patrick Schlüter

你假设处理器不会同时评估分支的两侧（直到表达式被评估）。当我回到大学时（20年前），他们已经在这方面做了一些事情。我没有跟上这个领域，但我认为现在它会更普遍。 - Martin York

你所谈论的是预测，例如在Itanium中存在预测，其中条件的两侧都被评估，然后保留“正确”的一侧而丢弃“错误”的一侧。这避免了流水线停顿，但代价是大量能源消耗（处理器执行了不必要的工作）。我认为更好的做法是拥有更好的分支预测器。 - Patrick Schlüter

“分支预测”的概念仅适用于具有硬编码目标的跳转，这使得switch语句的情况更加复杂。跳转表方法在某些情况下理论上更快，但在实践中可能会因缺乏分支预测而受到影响。很难（如果可能的话）确定哪种方法在每种特定情况下效果更好。 - AnT stands with Russia

实际上，一些处理器对于间接跳转（跳转表）已经有了工作分支预测。例如，在Core2上可以完美地预测最多36个不同目标的间接跳转。请查看http://www.agner.org/optimize/microarchitecture.pdf。 - Gunther Piez

Answer 2

我对你关于if语句的结论在我熟悉的大多数硬件上都不成立持保留意见。 问题不在于跳转，而在于分支。代码会根据比较结果走两种不同的方式。这可能会阻塞大多数现代CPU的流水线。分支预测很常见，并且大多数情况下可以解决问题，但与你的示例无关。预测器一样可以预测一个比较结果为false，也可以预测它为true。

通常请参考维基百科: Branch Predictor。

- PeterAllenWebb

---

我认为汇编清单并不能清楚地说明发生了什么。您需要逐步查看特定CPU的模拟，在if语句上循环多次。 - PeterAllenWebb

编译器可以轻松地反转条件。试图猜测编译器如何将if语句转换为代码是毫无意义的，如果编译器正在进行优化，则更是如此。 - deft_code

Answer 3

这取决于编译器。编译器将使用一系列内部实现依赖的标准来决定是否将 switch 实现为一系列类似 if 的测试，还是作为跳转表。例如，这可能取决于你的 case 标签集合的“紧凑程度”。如果你的 case 标签值形成了一个“密集”的集合，则编译器可能更可能使用跳转表，这种情况下，case 标签的顺序就不重要了。如果决定采用类似 if-else 测试的方式，那么顺序可能很重要。

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

- AnT stands with Russia

Answer 4

为了提高可读性，案例标签应按最有效的方式排序。

除非使用分析器明确告知这是问题，否则重新排列案例标签以提高效率是过早优化的一种情况。

- JaredPar

---

不回答问题，这就像是所有与表现相关的问题都可以使用的基本复制粘贴答案。 - Ramónster

我同意Ramonster的观点。这个回答太简单了，最多只应该作为一条评论。 - Richard Simões

@Ramónster，确实，这是一个复制/粘贴的答案，因为它本质上是相同的问题。这并不会使答案变得不正确，将其变成评论也肯定不会改变其正确性。这是过早优化。 - JaredPar

你猜测他的代码不在热点位置。一个好的回答应该解释如何通过重新排列switch/case语句来进行性能优化，并且顺带提到如果代码不是热点，则这样做是浪费的。请注意，翻译时必须保持原意，但需要使内容更加通俗易懂。 - Ramónster

@Ramónster，说什么东西是一个热点而没有配置文件只是一种猜测，不过如此而已。我花费了更多的时间来撤销人们的猜测所带来的坏优化，而不是实际实现性能修复。没有配置文件的任何优化都只是一种猜测，不会有更多的作用。你很可能会使事情变得更慢、更难读。 - JaredPar

Answer 5

我认为你的初衷——通过重新排列条件语句来优化代码——可能是错误的。在未经过优化的版本中，你可能会发现这样做有一定的价值，但在一般情况下，无论如何你都必须跳转至少一次，因此没有优势。但这只适用于未经过优化的版本，所以谁在乎这种优化呢？

在经过优化的版本中，编译器有时会将其中一个或两个条件移到某个位置。我认为你试图通过简单地改变条件的顺序来进行优化是不可取的。最好在检查编译器生成的代码后再进行操作。当然，这是一个昂贵的过程，因为即使你在语句周围进行微小的更改，也可能会改变编译器决定生成输出代码的方式。

现在就 switch 语句而言，当它可以使代码更易读时，我总是会使用 switch。如果一个 switch 语句等同于一个 if 语句，编译器最糟糕的情况是生成相同的代码。对于超过几个案例，switch 语句通常会被编译为跳转表。但是，一组将单个变量与一组值进行比较的 if 测试很可能也会被编译器识别并执行相同的操作。然而，我想使用 switch 将使编译器更容易地识别这种情况。

如果您真的有兴趣从条件语句中获得最佳性能，您可以考虑使用类似 MSVC's Profile Guided Optimization（PGO 或“pogo”）的东西，它使用分析运行的结果来优化条件语句的生成方式。我不知道 GCC 是否具有类似的功能。

- Michael Burr

---

这个回答比所有关于处理器架构的讨论都要好，求点赞。 - deft_code

@Caspin：处理器特定讨论突出的一件事情是，即使你查看生成的汇编代码，也很难猜测像这样的构造的性能会是什么样子。因为即使在汇编代码后面，也有很多事情发生，你真的需要测量才能知道发生了什么。仅从 C 级别来看这个问题，就好像试图从飞机上指挥城市十字路口的交通一样。 - Michael Burr

Answer 6

我不确定C#编译器是否支持，但是我知道在汇编语言中，switch语句可以实际上被编程为跳转到特定的行，而不像if语句一样评估表达式。由于在select语句中您有所有常量，因此它将case视为行号，并且您可以直接跳转到传递的行号（case值），而无需进行任何评估。这使得case语句的顺序实际上并不重要。

- Seth Moore

Answer 7

我假设你已经意识到只有在这是一个热点时才会有影响。判断它是否是热点的最好方法是运行代码，采样程序计数器，并查看它是否超过了10％的时间。如果是热点，请查看执行if或switch所花费的时间。通常情况下，除非Block 1和/或Block 2几乎什么都不做，否则可以忽略不计。您可以使用分析器来进行此操作。我只是反复暂停它。

如果您不熟悉汇编语言，我建议您学习一下，至少要了解编译器生成的内容。它很有趣，也不难。

- Mike Dunlavey

Answer 8

正如其他人所说，这取决于很多因素，包括有多少个案例、优化是如何进行的以及你运行的架构。如果想了解更多信息，请参阅http://ols.fedoraproject.org/GCC/Reprints-2008/sayle-reprint.pdf。

- Ken Rose

Answer 9

如果您首先处理最常发生的情况，这将稍微优化代码，并且由于switch语句的工作方式是相同的。当程序进入switch并找到一个为真的情况时，它将执行它并命中break，这将退出循环。您的思路是正确的。

然而，我认为这种优化非常小，如果它减慢了您的开发时间，那么它可能不值得。此外，如果您必须彻底修改程序流以适应此内容，那么它可能不值得。您只会节省几个周期，最多可能看不到任何改进。

- Jeremy Morgan

---

不能保证按字典顺序进行排序。编译器可以自由地以任何方式重新排列案例。它很可能比程序员更好地完成这项工作。因此，最好按最容易理解或最能传达意图的顺序编写它们。如果顺序偏差很重要，请使用级联条件语句（if-else if-else）。否则，将优化留给编译器。 - seh

只有在每个“case”“段”末尾有无条件的“break”语句（或等效语句），并且编译器足够聪明以识别它们（当然，现代编译器都是如此）时，编译器才能自由地这样做。如果没有这样的“break”语句，则这些段是不可重新排列的，因为整个“switch”的主体是一个具有预定内部排序的大复合语句。 - AnT stands with Russia