是“IF”昂贵？ [英] Is "IF" expensive?

问题描述

对于我的生活，我不能记得那天我们的老师说了什么，我希望你可能知道。

I can't, for the life of me, remember what exactly did our teacher said that day and I'm hoping you would probably know.

模块是数据结构和算法，他告诉我们一些类似的东西：

The module is "Data Structures and Algorithms" and he told us something along the lines of:

if语句是最昂贵的
[某件事]。 [东西]登记
[某事]。

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

是的，我确实有一段可怕的记忆，我真的很抱歉，但我一直在谷歌搜索几个小时，什么都没有出现。任何想法？

Yes, I do have a horrible memory and I'm really really sorry, but I've been googling for hours and nothing has come up. Any ideas?

推荐答案

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

At the very lowest level (in the hardware), yes, ifs are expensive. In order to understand why, you have to understand how pipelines work.

当前要执行的指令存储在通常称为指令指针（IP）或程序计数器（PC）的内容中;这些术语是同义词，但不同的术语与不同的体系结构一起使用。对于大多数指令，下一条指令的PC只是当前PC加上当前指令的长度。对于大多数RISC架构，指令都是恒定长度，因此PC可以增加一个恒定的量。对于诸如x86之类的CISC架构，指令可以是可变长度的，因此解码指令的逻辑必须确定当前指令找到下一条指令的位置的时间。

The current instruction to be executed is stored in something typically called the instruction pointer (IP) or program counter (PC); these terms are synonymous, but different terms are used with different architectures. For most instructions, the PC of the next instruction is just the current PC plus the length of the current instruction. For most RISC architectures, instructions are all a constant length, so the PC can be incremented by a constant amount. For CISC architectures such as x86, instructions can be variable-length, so the logic that decodes the instruction has to figure out how long the current instruction is to find the location of the next instruction.

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

For branch instructions, however, the next instruction to be executed is not the next location after the current instruction. Branches are gotos - they tell the processor where the next instruction is. Branches can either be conditional or unconditional, and the target location can be either fixed or computed.

条件与无条件很容易理解 - 条件分支只有在某种条件成立（例如一个数字是否等于另一个数字）;如果未采用分支，则控制在正常分支之后进入下一条指令。对于无条件分支，始终采用分支。条件分支显示在，如果语句和的控制测试和，而循环。无条件分支显示在无限循环，函数调用，函数返回， break 和 continue 语句中，臭名昭着的 goto 声明等等（这些列表远非详尽无遗）。

Conditional vs. unconditional is easy to understand - a conditional branch is only taken if a certain condition holds (such as whether one number equals another); if the branch is not taken, control proceeds to the next instruction after the branch like normal. For unconditional branches, the branch is always taken. Conditional branches show up in if statements and the control tests of for and while loops. Unconditional branches show up in infinite loops, function calls, function returns, break and continue statements, the infamous goto statement, and many more (these lists are far from exhaustive).

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

The branch target is another important issue. Most branches have a fixed branch target - they go to a specific location in code that is fixed at compile time. This includes if statements, loops of all sorts, regular function calls, and many more. Computed branches compute the target of the branch at runtime. This includes switch statements (sometimes), returning from a function, virtual function calls, and function pointer calls.

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

So what does this all mean for performance? When the processor sees a branch instruction appear in its pipeline, it needs to figure out how to continue to fill up its pipeline. In order to figure out what instructions come after the branch in the program stream, it needs to know two things: (1) if the branch will be taken and (2) the target of the branch. Figuring this out is called branch prediction, and it's a challenging problem. If the processor guesses correctly, the program continues at full speed. If instead the processor guesses incorrectly, it just spent some time computing the wrong thing. It now has to flush its pipeline and reload it with instructions from the correct execution path. Bottom line: a big performance hit.

因此，if语句昂贵的原因是分支误预测。这只是最低级别。如果您正在编写高级代码，则根本不需要担心这些细节。如果您在C或汇编中编写极其性能关键的代码，那么您应该只关心这一点。如果是这种情况，编写无分支代码通常可以优于分支代码，即使需要更多指令也是如此。你可以用一些很酷的比特技巧来计算诸如 abs（）， min（）之类的东西，和 max（）没有分支。

Thus, the reason why if statements are expensive is due to branch mispredictions. This is only at the lowest level. If you're writing high-level code, you don't need to worry about these details at all. You should only care about this if you're writing extremely performance-critical code in C or assembly. If that is the case, writing branch-free code can often be superior to code that branches, even if several more instructions are needed. There are some cool bit-twiddling tricks you can do to compute things such as abs(), min(), and max() without branching.

这篇关于是“IF”昂贵？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！