是“IF"吗?昂贵的? [英] Is "IF" expensive?

问题描述

我这辈子都记不住老师那天说的话，我希望你可能知道.

I can't, for the life of me, remember what exactly 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?

推荐答案

在最底层(在硬件中)，是的，ifs 很昂贵.为了理解原因，您必须了解管道是如何工作的.

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指令，下一条要执行的指令不是当前指令之后的下一个位置.分支是 goto - 它们告诉处理器下一条指令在哪里.分支可以是有条件的也可以是无条件的，目标位置可以是固定的也可以是计算出来的.

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.

条件 vs. 无条件很容易理解——条件分支只有在某个条件成立时才会被采用(例如一个数字是否等于另一个)；如果没有采用分支，则控制像往常一样进行分支后的下一条指令.对于无条件分支，总是采用分支.条件分支出现在if 语句和for 和while 循环的控制测试中.无条件分支出现在无限循环、函数调用、函数返回、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屋！