if-statement - "IF"贵吗？

Question

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

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

The if statement is the most expensive [something]. [something] registers [something].

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

Answer 1

在最低级别(在硬件中)，是的，如果很昂贵。为了了解原因，您必须了解如何pipelines工作。

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

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

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

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

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

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