是“IF”吗？ 昂贵的？

Question

我一辈子都记不起老师那天到底说了什么，我希望你能知道。

该模块是“数据结构和算法”，他告诉我们以下内容：

if 语句是最昂贵的 [某物]。 [某事] 注册 [某事]。

是的，我的记忆力确实很糟糕，我真的很抱歉，但我已经在谷歌上搜索了几个小时，但什么也没找到。 有任何想法吗？

Answer 1

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

话虽这么说，有很多条件分支并不存在于 if 语句中，您无法总是知道编译器会产生什么结果，并且担心基本语句将花费多长时间实际上总是错误的事情去做。 （如果你能知道编译器将可靠地生成什么，那么你可能没有一个好的优化编译器。）

Answer 2

我唯一能想象到的可能是 if 语句通常可以产生分支。 根据处理器架构的具体情况，分支可能会导致管道停顿或其他不太理想的情况。

然而，这是极其具体的情况 - 大多数现代处理器都具有分支预测功能，试图最大限度地减少分支的负面影响。 另一个例子是 ARM 架构（可能还有其他架构）如何处理条件逻辑 - ARM 具有指令级条件执行，因此简单的条件逻辑不会导致分支 - 如果条件不满足，指令将简单地作为 NOP 执行。

综上所述，在担心这些事情之前先确保你的逻辑正确。 不正确的代码是尽可能未优化的。

Answer 3

CPU 是深度流水线的。 任何分支指令（if/for/while/switch/etc）都意味着CPU并不真正知道接下来要加载和运行什么指令。

CPU 要么在等待知道要做什么时停止，要么进行猜测。 对于较旧的 CPU，或者如果猜测错误，您将不得不在它加载正确的指令时遭遇管道停顿。 根据 CPU 的不同，这可能会导致高达 10-20 条指令的停顿。

现代 CPU 试图通过良好的分支预测、同时执行多个路径并仅保留实际路径来避免这种情况。 这有很大帮助，但也只能到此为止。

祝你在课堂上好运。

另外，如果您在现实生活中不得不担心这个问题，您可能正在做操作系统设计、实时图形、科学计算或类似的 CPU 限制的事情。 担心之前的简介。

Answer 4

以最清晰、最简单、最干净的方式编写程序，而且效率不会明显低下。 这充分利用了最昂贵的资源，即您。 无论是编写程序还是稍后调试（需要理解）程序。 如果性能不够，请测量瓶颈所在，并了解如何缓解它们。 只有在极少数情况下，您在执行此操作时才需要担心个别（源）说明。 性能是指在第一行选择正确的算法和数据结构，仔细编程，获得足够快的机器。 使用好的编译器，当您看到现代编译器所做的代码重组时，您会感到惊讶。 重组代码以提高性能是一种最后的手段，代码会变得更加复杂（因此有更多错误），更难以修改，因此总体上更加昂贵。

Answer 5

一些CPU（如X86）提供编程级别的分支预测以避免这种分支预测延迟。

一些编译器（如 GCC）将它们公开为高级编程语言（如 C/C++）的扩展。

请参阅 Linux 内核中的 likely()/unlikely() 宏 - 它们如何工作？ 他们有什么好处？。

Answer 6

就 ALU 使用而言最昂贵的是？ 它会占用 CPU 寄存器来存储要比较的值，并且每次运行 if 语句时都会占用时间来获取和比较值。

因此，对此的优化是在运行循环之前进行一次比较并将结果存储为变量。

只是想解释一下你漏掉的单词。

Answer 7

我曾经和一个朋友因为这个问题发生过争执。 他使用的是一种非常幼稚的圆算法，但声称他的比我的更快（只计算圆的1/8的那种），因为我使用了if。 最后，if 语句被 sqrt 替换，不知何故速度更快。 也许是因为 FPU 内置了 sqrt？

Answer 8

你的代码应该是可预测的和可能的。

如果你的整个程序是这样的：

int apple = 1;

if (apple == 1) then 这是可预测且可能的代码。

它也是优化的代码，因为您已经使编译器和 CPU 变得容易； 他们不需要预测任何事情，因此不存在代价高昂的错误预测，即分支错误预测。

所以你尝试编写一个程序，使每一行都是一个自我实现的预言。
你有 3 种筹码：真相、虚假和未知。
您正在尝试仅使用真相芯片构建一个程序。

为此：

If else: if should be more likely and if there is a return that should be in else.

For and While should be replace by: do while -> except if there is a continue.

That continue should then become an: if do while -> in that order.

If it absolutely necessary to test at beginning use: if do while

If there is less than 5 cases switch to if else from most likely to least likely

Cases should be of relative likelihood, otherwise should be expressed as if else before switch.

Bitwise operators and better logical operators

“简单的整数运算，例如加法、减法、比较、位运算和移位运算（以及增量运算符）在大多数微处理器上只需要一个时钟周期。”

增量运算符：i++ 优于 ++I；

布尔操作数：

1. In && 将最有可能为真的陈述放在最后
2. In || 把最有可能为真的放在第一位。

因此，为了回答您的问题，如果条件为真或可能为真，则 if 语句并不那么昂贵，否则它会陷入分支错误预测。

Answer 9

在许多较旧的处理器上，人们可以识别“如果”的情况会很昂贵以及不会的情况，但是现代高性能处理器包括用于预测将采用和不会采用哪些分支的电路，并且只有在以下情况下分支才会昂贵这样的电路猜测错误。 不幸的是，这通常使得确定编写一段代码的最佳方式变得非常困难，因为处理器完全有可能在处理人为的测试数据时正确预测分支结果，但在处理现实世界时却猜测其中许多结果是错误的数据，反之亦然。

除非人们试图优化其分支时序很好理解的特定目标的性能，否则最好的方法通常是假设分支时序不太可能成为整体性能的重要因素，除非或直到人们能够证明这一点。 分支时序可能会受到输入数据中细微差异的影响，并且通常没有实际的方法来确保测试数据包括可能影响性能的所有变化。

Answer 10

在最低级别（在硬件中），是的，如果是昂贵的。 为了理解其中的原因，您必须了解管道的工作原理。

当前要执行的指令通常存储在指令指针 (IP) 或程序计数器 (PC) 中； 这些术语是同义词，但不同的术语用于不同的架构。 对于大多数指令，下一条指令的PC只是当前PC加上当前指令的长度。 对于大多数RISC架构，指令都是恒定长度，因此PC可以按恒定量递增。 对于x86等CISC架构，指令可以是可变长度的，因此解码指令的逻辑必须弄清楚当前指令有多长才能找到下一条指令的位置。

然而，对于分支指令，要执行的下一条指令不是当前指令之后的下一个位置。 分支是 goto - 它们告诉处理器下一条指令在哪里。 分支可以是有条件的或无条件的，目标位置可以是固定的或计算的。

有条件与无条件很容易理解 - 仅当某个条件成立时才会采用条件分支（例如一个数字是否等于另一个数字）； 如果未采用分支，则控制将像平常一样继续执行分支后的下一条指令。 对于无条件分支，总是采用该分支。 条件分支出现在 if 语句以及 for 和 while 循环的控制测试中。 无条件分支出现在无限循环、函数调用、函数返回、break 和 continue 语句、臭名昭著的 goto 语句等等（这些列表远非详尽）。

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

那么这对性能意味着什么呢？ 当处理器看到其管道中出现分支指令时，它需要弄清楚如何继续填充其管道。 为了弄清楚程序流中分支之后有哪些指令，它需要知道两件事：（1）是否将采用分支以及（2）分支的目标。 弄清楚这一点被称为分支预测，这是一个具有挑战性的问题。 如果处理器猜测正确，程序就会全速继续运行。 相反，如果处理器猜测不正确，它只是花了一些时间计算错误的东西。 现在它必须刷新其管道并使用来自正确执行路径的指令重新加载它。 底线：性能受到巨大影响。

因此，if 语句昂贵的原因是由于分支错误预测。 这只是最低级别的。 如果您正在编写高级代码，则根本不需要担心这些细节。 仅当您用 C 或汇编编写对性能极其关键的代码时，您才应该关心这一点。 如果是这种情况，编写无分支代码通常优于分支代码，即使需要更多指令。 您可以使用一些很酷的小技巧来计算诸如 abs()、min() 和 max() 之类的东西，而无需分枝。

Answer 11

“昂贵”是一个非常相对的术语，特别是与“if”语句的关系，因为您还必须考虑条件的成本。 其范围可以从一些简短的 CPU 指令到测试调用远程数据库的函数的结果。

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

Answer 12

分支，特别是在 RISC 架构微处理器上，是最昂贵的指令之一。 这是因为在许多体系结构上，编译器会预测最有可能采用哪条执行路径，并将这些指令放在可执行文件中的下一个位置，因此当分支发生时它们已经位于 CPU 缓存中。 如果分支走另一条路，它必须返回主内存并获取新指令——这是相当昂贵的。 在许多 RISC 架构上，除了分支（通常是 2 个周期）之外，所有指令都是一个周期。 我们这里讨论的不是主要成本，所以不用担心。 此外，编译器在 99% 的情况下都会比您优化得更好:) EPIC 架构（Itanium 就是一个例子）真正令人敬畏的事情之一是它缓存（并开始处理）来自分支两侧的指令，然后一旦知道分支的结果就丢弃不需要的集合。 如果典型架构沿着不可预测的路径分支，这可以节省额外的内存访问。

Answer 13

请查看有关单元性能的文章通过分支消除提高性能。 另一篇有趣的文章是实时碰撞检测博客上的这篇关于无分支选择的文章。

除了针对这个问题已经发布的优秀答案之外，我想提醒一下，尽管“if”语句被认为是昂贵的低级操作，但尝试在更高级别的环境中利用无分支编程技术，例如脚本语言或业务逻辑层（无论语言如何），可能是非常不合适的。

绝大多数情况下，编写程序时应首先考虑清晰度，其次考虑性能优化。 在许多问题领域中，性能至关重要，但简单的事实是，大多数开发人员编写的模块并不是用于渲染引擎的核心或连续运行数周的高性能流体动力学模拟。 当您的解决方案的首要任务是“正常工作”时，您最不需要考虑的事情应该是是否可以节省代码中条件语句的开销。

Answer 14

if 本身不慢。 缓慢总是相对的，我敢打赌，你从来没有感受到 if 语句的“开销”。 如果您要编写高性能代码，无论如何您可能都希望避免分支。 使 if 变慢的原因是处理器根据一些启发式方法从 if 之后预加载代码。 它还会阻止管道直接在机器代码中的 if 分支指令之后执行代码，因为处理器还不知道将采取什么路径（在管道处理器中，多个指令是交错的，并且执行）。 执行的代码可能必须反向执行（如果采用了另一个分支。这称为分支错误预测），或者在这些地方填充了 noop，这样就不会发生这种情况。不会发生。

如果 if 是邪恶的，那么 switch 也是邪恶的，&&、|| 也是邪恶的。 别担心。

Answer 15

在最低可能级别 if 包含（在计算特定 if 的所有特定于应用程序的先决条件之后）：

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

与此相关的成本：

• 低级比较——通常是 1 个 cpu 操作，超级便宜的
• 潜在跳转——这可能很昂贵

思考为什么跳转很昂贵：

• 你可以跳转到内存中任何地方的任意代码，如果事实证明它是这样的不被CPU缓存——我们有一个问题，因为我们需要访问主内存，而
• 现代CPU执行分支预测的速度较慢。 他们尝试猜测是否会成功，并在管道中提前执行代码，从而加快速度。 如果预测失败，则管道之前完成的所有计算都必须失效。 这也是一项昂贵的操作

所以总结一下：

• 如果您真的非常关心性能，那么这可能会很昂贵。
• 当且仅当您正在编写实时光线追踪器或生物模拟或类似的东西时，您才应该关心它。 在现实世界的大多数情况下，没有理由关心它。

Answer 16

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

我认为它是一列长货运列车。 它可以在直线上快速运载大量货物，但转弯性能很差。

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

更多关于维基百科

Answer 17

也许分支会终止 CPU 指令预取？

Answer 18

另请注意，循环内部不一定非常昂贵。

现代 CPU 假定在第一次访问 if 语句时，将采用“if-body”（或者换句话说：它还假定循环体将被多次采用）(*)。 在第二次和进一步访问时，它（CPU）也许可以查看分支历史表，并查看上次的情况如何（是真的吗？是假的吗？）。 如果上次为 false，则推测执行将继续到 if 的“else”，或超出循环。

(*) 该规则实际上是“不采用前向分支，采用后向分支”。 在 if 语句中，如果条件计算结果为 false，则仅有一个[向前]跳转（到 if 主体之后的点）（记住：CPU 无论如何假设不进行分支/跳转），但在循环中，可能有一个到循环后位置的前向分支（不进行），以及重复时的向后分支（要进行）。

这也是为什么对虚函数或函数指针调用并不像许多人想象的那么糟糕的原因之一（http://phresnel.org/blog/）