“IF”语句是否昂贵？

Question

“IF”语句是否昂贵？

if-statementlanguage-agnosticbranch-prediction

126

我实在是想不起来我们老师当时具体讲了什么，希望你可能知道。

这个模块是“数据结构和算法”，他告诉我们的大致是：

if语句是最昂贵的 [某些东西]。[某些东西]寄存器 [某些东西]。

是的，我的记忆力真的很糟糕，非常非常抱歉，但我已经搜索了几个小时，没有任何结果。有任何想法吗？

- pek

37

问问你的老师是一个选择吗？ - Michael Myers

8

为什么不给你的老师发电子邮件呢？除非他们当时在场（或者你的老师本人阅读SO），否则SO上的任何人都不太可能知道你的老师说了什么。 - Bill Karwin

16

当然，这里是必不可少的铁路答案链接。 - bobobobo

一个好的编译器有时需要一点推动，以便它使用条件指令而不是愚蠢地使用条件跳转，通过重新组织代码和可能在表达式或？：表达式中使用巧妙的算术。除非你真正了解汇编语言并阅读过例如Agner Fog的优化指南，否则不要尝试这样做。无论使用if语句还是？：表达式，编译器有时都能正确处理。 - Cecil Ward

我目前主要使用 Elixir 进行编程。其中一个非正式的“规则”是优先选择基于函数元数和参数的模式匹配，而不是 if 语句。我最初学习 Elixir 的人建议，写 if 语句是重构代码的好理由。 - user483040

显示剩余2条评论

18个回答

25

"昂贵"这个词是一个非常相对的术语，特别是与"if"语句相关时，因为您还必须考虑条件的成本。它可能涉及从几个简短的CPU指令到测试调用远程数据库的函数的结果。

我不会担心这个问题。除非您正在进行嵌入式编程，否则您可能根本不应该关注"if"的成本。对于大多数程序员来说，它将永远不会成为应用程序性能的决定性因素。

- Joel Coehoorn

2

绝对相对来说，cmp/cond jmp 在许多处理器上仍然比乘法更快。 - Brian Knoblauch

4

是的，我同意我不应该担心它。我并不试图去优化任何东西。我只是想找到答案并学习。 ;) - pek

17

分支指令，特别是在RISC体系结构的微处理器上，是最昂贵的指令之一。这是因为在许多架构中，编译器预测将最可能采取哪个执行路径，并将那些指令放在可执行文件中的下一个位置，这样当分支发生时它们就已经在CPU缓存中了。如果分支发生了其他方向，它就必须回到主存储器中获取新的指令，这是相当昂贵的。在许多RISC体系结构中，除了分支指令（通常需要2个周期），所有指令都只需要1个周期。这里谈论的成本不是很大，所以不用担心。另外，编译器99%的时间会比您做得更好:) EPIC体系结构（例如Itanium）的一项真正棒的功能是，它会缓存（并开始处理）来自分支两侧的指令，然后在分支结果确定后丢弃不需要的指令集。这样，在沿着不可预测的路径分支时，就可以节省典型架构中的额外内存访问。

- rmeador

13

请查看Cell Performance上的一篇文章“通过分支消除获得更好性能”。另一个有趣的是Real Time Collision Detection Blog上关于无分支选项的这篇文章。

除了已经发布的优秀答案，我想提醒大家的是，尽管“if”语句被认为是昂贵的低级操作，但在高级环境中（例如脚本语言或业务逻辑层，无论使用哪种语言），尝试利用无分支编程技术可能是荒谬的不合适。

绝大多数情况下，程序应该首先为清晰易懂而编写，然后再进行性能优化。虽然在许多问题域中，性能至关重要，但简单的事实是，大多数开发人员并不是为了在渲染引擎的核心深处或运行数周的高性能流体动力学模拟中使用模块而编写代码。当您的解决方案的最高优先级是“只需工作”，您最后需要考虑的是是否可以在代码中节省条件语句的开销。

- Parappa

确实！还可以补充一点，当使用鼓励调用的语言进行编码时（基本上是除了汇编语言或没有stdlib的C之外的任何语言），来自正常编程技术的管道干扰将压倒有关条件分支的任何问题。 - Ross Patterson

9

if语句本身并不慢，慢指的是相对的。我敢打赌你从未感受过if语句的“开销”。如果你要编写高性能代码，最好避免使用分支语句。if语句变慢的原因是处理器会基于某些启发式和其他因素预加载if后面的代码。此外，处理器还会停止执行if分支指令后直接执行代码的流水线进程，因为处理器尚不知道将采取哪条路径（在流水线处理器中，多个指令交错执行）。如果执行的代码需要反向执行（如果执行了另一个分支，则称为分支错误预测），则必须在这些位置填充noop，以防止出现这种情况。

如果说if语句是有害的，那么switch语句、&&、||也同样有害。不用担心。

- litb

1

嗯，我不知道该如何评价那个答案。当编写运行10天的模拟并能在单个if语句上节省20％时，这就是2天的节省。 - Julian Bechtold

7

在最低级别上，if由以下组成（在计算特定if的所有应用程序特定先决条件之后）：

一些测试指令
如果测试成功，则跳转到代码中的某个位置，否则继续向前进行。

与此相关的成本：

低级别比较--通常为1个CPU操作，非常便宜
潜在的跳转--可能很昂贵

跳转昂贵的原因：

您可以跳转到存储在内存中任何位置的任意代码，如果发现该代码未被CPU缓存，则会出现问题，因为我们需要访问较慢的主内存
现代CPU进行分支预测。他们尝试猜测是否会成功并执行管道中的代码以加快速度。如果预测失败，则必须使管道前面执行的所有计算无效。那也是一个昂贵的操作

因此，总结一下：

如果您真的非常关心性能，if可能会很昂贵。
您应该关注它仅当且仅当您正在编写实时光线跟踪器、生物模拟或类似的东西时。在大多数现实世界中，没有理由关心它。

- Marcin

把它提升到下一个级别：嵌套和/或复合if语句怎么办？如果有人写了很多这样的if语句，开销很快就会变得非常明显。由于对大多数开发人员来说，if语句似乎是如此基本的操作，因此避免复杂的条件分支通常被归为风格上的问题。风格上的问题仍然很重要，但在紧要关头，它们往往是被忽视的第一个问题。 - user483040

7

现代处理器有着很长的执行流水线，这意味着多个指令在不同阶段同时执行。当下一条指令开始运行时，处理器可能并不总是知道上一条指令的结果。当它们遇到条件跳转（if）时，有时必须等待流水线清空后才能知道指令指针应该走哪个方向。

我认为这就像一列长长的货车。它可以快速地直线行驶，但转弯时表现不佳。

Pentium 4 (Prescott) 有着著名的31级流水线。

更多信息请参见维基百科。

- Guge

6

也许分支会影响CPU指令预取吗？

- divideandconquer.se

在我的“研究”中，我了解到了关于跳转表和分支用于switch语句的内容，但是对于if语句却一无所知。您能详细说明一下吗？ - pek

据我所知，CPU通常会沿着单一的可能执行路径预取指令，但是一个导致从预测执行路径分支的“if”语句将使预取指令失效，预取将不得不重新开始。 - activout.se

任何像样的处理器都应该具备分支预测能力，它会尝试猜测一个分支是否会被执行，并根据这个预测来预取指令（通常效果相当不错）。GCC甚至提供了C扩展，允许程序员为分支预测器提供提示。 - mipadi

3

此外，中央处理器通常会提前查看并开始执行即将到来的指令（而不仅是预取指令），编译器也试图重新排序指令，但跨越分支时这就变得危险了，所以过多的分支会真正影响指令调度，从而影响性能。 - jalf

6

还要注意，循环内部不一定非常昂贵。现代CPU在第一次访问if语句时会假设“if-body”需要被执行（或者说，它也会假设循环体需要被执行多次）(*)。在第二次及更多次访问时，它（CPU）可以查看分支历史表，看看上次条件是什么（是真还是假？）。如果上次是假的，那么就会进行推测执行，进入if的“else”或超出循环。

(*) 规则实际上是“前向分支不被取，后向分支被取”。在if语句中，只有当条件为false时（记住：CPU总是假设不会跳转/分支），才会有[前向]跳转（到if-body之后的位置），但在循环中，可能会有一个前向分支到达循环后的位置（不被取），以及重复时的后向分支（被取）。

这也是为什么调用虚函数或函数指针调用并不像许多人认为的那样糟糕的原因之一。 (http://phresnel.org/blog/)

- phresnel

5

正如许多人指出的那样，条件分支在现代计算机上可能非常缓慢。

尽管如此，还有许多条件分支不在 if 语句中，您并不能总是确定编译器会生成什么代码，并且担心基本语句执行的时间几乎总是错误的。（如果您可以可靠地确定编译器将生成什么代码，则可能没有一个好的优化编译器。）

- David Thornley

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Adam Rosenfield · Accepted Answer

在最底层（硬件层面），是的，如果语句比较耗费资源。要理解为什么，您必须了解流水线的工作原理。

当前要执行的指令存储在通常称为指令指针（IP）或程序计数器（PC）的位置；这些术语是同义词，但不同的体系结构使用不同的术语。对于大多数指令，下一条指令的PC就是当前PC加上当前指令的长度。对于大多数RISC体系结构，指令都具有恒定的长度，因此PC可以增加一个恒定量。对于像x86这样的CISC结构，指令可以是可变长度的，因此解码指令的逻辑需要查找当前指令的长度以找到下一条指令的位置。

然而，对于分支指令，要执行的下一条指令不是当前指令后面的位置。分支是跳转 - 它们告诉处理器下一条指令的位置。分支可以是条件的或无条件的，并且目标位置可以是固定的或计算的。

条件与无条件很容易理解 - 条件分支仅在某些条件成立时（例如一个数字是否等于另一个数字）才会执行；如果不执行分支，则控制会像正常那样继续执行下一条指令。无条件分支始终执行。条件分支出现在if语句和for和while循环的控制测试中。无条件分支出现在无限循环，函数调用，函数返回，break和continue语句，臭名昭著的goto语句等许多情况中（这些列表远非详尽无遗）。

分支目标是另一个重要问题。大多数分支具有固定的分支目标 - 它们转到编译时固定的代码位置。这包括if语句，各种循环，常规函数调用等等。计算分支在运行时计算分支目标。这包括switch语句（有时），从函数返回，虚函数调用和函数指针调用。

那么这对性能意味着什么？当处理器在其流水线中看到分支指令出现时，它需要找出如何继续填充其流水线。为了弄清楚程序流中分支后面的指令，它需要知道两件事：（1）分支是否被采取和（2）分支的目标。找出这一点称为分支预测，这是一个具有挑战性的问题。如果处理器猜测正确，则程序以全速继续。如果处理器猜测不正确，那么它刚刚花费了一些时间计算错误的内容。现在它必须清空其流水线并重新加载来自正确执行路径的指令。最终结果：严重影响性能。

因此，if语句昂贵的原因是由于分支预测错误。这仅限于最低级别。如果您编写高级代码，则根本不需要担心这些细节。只有在编写C或汇编中极其性能关键的代码时，您才应该关注此内容。如果是这种情况，编写无分支代码通常比具有分支的代码更优，即使需要更多指令也是如此。有一些很酷的位操作技巧可以用来计算abs()、min()和max()等内容而不使用分支。