“如果”贵吗？ - 开卷题库

小开

也许分支杀死了 CPU 指令预取？

小开

"Expensive" is a very relative term, especially with relationship to an "if" statement since you also have to take into the account the cost of the condition. That could range anywhere from a few short cpu instructions to testing the result of a function that calls out to a remote database.

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

小开

我能想象到的唯一一件事情可能是，if语句通常会导致一个分支。根据处理器体系结构的具体情况，分支可能导致管道停滞或其他不太理想的情况。

然而，这是非常特定的情况-大多数现代处理器都具有分支预测功能，这些功能试图最小化分支的负面影响。另一个例子是 ARM 架构(可能还有其他架构)如何处理条件逻辑—— ARM 具有指令级条件执行，所以简单的条件逻辑不会导致分支——如果条件不能满足，指令只是作为 NOP 执行。

所有这些都说明——在担心这些事情之前，先把你的逻辑正确化。不正确的代码是最不优化的。

小开

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

小开

在可能的最低级别上，if包括(在计算特定 if的所有特定应用程序的先决条件之后) :

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

与此相关的费用:

一个低级别的比较——通常是一个 CPU 操作，超级便宜
potential jump -- which can be expensive

跳跃之所以昂贵的原因:

你可以跳转到内存中任意位置的任意代码，如果它没有被 CPU 缓存——我们有一个问题，因为我们需要访问主存，这比较慢
现代 CPU 执行分支预处理。他们尝试猜测是否会成功，并在管道中提前执行代码，因此加快了速度。如果预测失败，那么流水线提前完成的所有计算都将失效。这也是一项昂贵的手术

总而言之:

如果可以是昂贵的，如果你真的，真的，真的关心性能。
You should care about it 如果，也只有如果 you are writing real time raytracer or biological simulation or something similar. There is no reason to care about it in most of the real world.

小开

CPU 是深度管道化的。任何分支指令(if/for/while/switch/etc)都意味着 CPU 并不真正知道下一步要加载和运行什么指令。

CPU 要么在等待知道要做什么的时候停止，要么进行猜测。对于较旧的 CPU，或者如果猜测错误，您将不得不在管道运行并加载正确指令时遭遇管道停滞。取决于 CPU，这可以高达10-20指令的失速价值。

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

祝你在课堂上好运。

此外，如果你在现实生活中不得不担心这个问题，你可能正在做操作系统设计，实时图形，科学计算，或类似的 CPU 限制。忧虑之前的侧面。

小开

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

我把它想象成一列长长的货运列车。它可以在一条直线上快速运输大量货物，但是它的转弯很糟糕。

奔腾4(普雷斯科特)有一个著名的长管道31个阶段。

更多关于维基百科的资料

小开

if本身就是没有慢。缓慢总是相对的，我敢打赌，我的生活，你从来没有感觉到一个如果声明的“开销”。如果要编写高性能代码，无论如何都要避免使用分支。使 if变慢的原因是处理器在 if之后根据一些启发式的东西预加载代码。它还将阻止管道在机器代码中的 if分支指令之后直接执行代码，因为处理器还不知道将采用什么路径(在管道处理器中，多个指令交叉执行)。执行的代码可能必须反过来执行(如果采用了另一个分支的话)。它被称为 branch misprediction) ，或 noop的填充在这些地方，这样就不会发生这种情况。

如果 if是邪恶的，那么 switch也是邪恶的，而且 &&，||也是邪恶的。不要担心它。

小开

最佳答案

在最低层次(在硬件上) ，是的，如果是昂贵的。为了理解为什么，你必须理解管道是如何工作的。

要执行的当前指令存储在通常称为 指令指针(IP)或 program counter(PC)的东西中; 这些术语是同义的，但不同的术语用于不同的体系结构。对于大多数指令，下一条指令的 PC 只是当前 PC 加上当前指令的长度。对于大多数 RISC 体系结构来说，指令的长度都是固定的，所以 PC 可以按固定的数量增加。对于像 x86这样的 CISC 架构，指令可以是可变长度的，因此解码指令的逻辑必须计算出当前指令需要多长时间才能找到下一条指令的位置。

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

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语句、各种循环、常规函数调用等等。已计算分支在运行时计算分支的目标。这包括 switch语句(有时)、从函数返回、虚函数调用和函数指针调用。

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

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

小开

The most expensive in terms of ALU usage? It uses up CPU registers to store the values to be compared and takes up time to fetch and compare the values each time the if statement is run.

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

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

小开

我曾经和一个朋友吵过一次架。他使用了一个非常天真的圆算法，但声称他的算法比我的算法快(那种只能算出圆的八分之一) ，因为我的算法使用了 if。最后，if 语句被 sqrt 替换，不知怎么的，它变得更快了。也许是因为 FPU 内置了 sqrt？

小开

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

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

在绝大多数情况下，程序应该首先为清晰度编写，其次为性能优化。在许多问题领域中，性能是最重要的，但是一个简单的事实是，大多数开发人员并没有编写深入到渲染引擎核心的模块，也没有编写连续运行数周的高性能流体动力学模拟。当最重要的事情是你的解决方案“只是工作”的时候，你最不应该考虑的事情应该是你是否可以节省代码中一个 If判断语句的开销。

小开

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

也就是说，有很多条件分支不存在于 if 语句中，你不可能总是知道编译器会得出什么结果，担心基本语句会花多长时间实际上总是错误的。(如果你知道编译器会可靠地生成什么，你可能不会有一个好的编译器最佳化。)

小开

Also note that inside a loop is 没有 necessarily very expensive.

现代 CPU 在第一次访问 if 语句时假定将采用“ if-body”(或者换一种说法: 它还假定将多次采用循环 body)(*)。经过第二次和进一步的访问，它(CPU)也许可以查看 分支历史表，看看上一次的情况如何(是真的吗？是假的吗?).如果上次为 false，那么 Speculative_execution 将继续执行 If 的“ else”，或者超出循环。

(*)规则实际上是“ 前面的树枝没拿走，后面的树枝拿走了”。在 if 语句中，如果条件的计算结果为 false (请记住: CPU 无论如何都假定不采用分支/跳转) ，那么只有有一个[正向]跳转(到 在 if-body 之后点) ，但是在循环中，可能有一个前向分支到循环后的位置(不采用) ，并且在重复时有一个后向分支(采用)。

这也是为什么对虚函数或函数指针的调用没有许多假设(http://phresnel.org/blog/)那么糟糕的原因之一

小开

一些 CPU (如 X86)为编程级别提供分支预测，以避免这种分支预测延迟。

Some compiler exposes(like GCC) these as a extension to higher level programming languages(like C/C++).

请参阅 Linux 内核中可能的()/不可能的()宏——它们是如何工作的? 它们的好处是什么？。

小开

以最清晰、最简单、最干净的方式编写程序，而且效率不会明显下降。这样才能最好地利用最昂贵的资源。无论是编写程序还是稍后调试(需要理解)程序。如果性能不够好，那么量度就是瓶颈所在，看看如何减轻它们。只有在极其罕见的情况下，您才需要在这样做时担心单个(源)指令。性能就是在第一行选择正确的算法和数据结构，仔细编程，获得足够快的机器。使用一个好的编译器，当你看到现代编译器所做的那种代码重构时，你会感到惊讶。为了性能而重新构造代码是一种最后的手段，代码变得更复杂(因此更麻烦) ，更难修改，因此全面更昂贵。

小开

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

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

int apple = 1;

如果(apple = = 1) ，那么这是可预测的，可能的代码。

这也是优化的代码，因为你已经使它容易为编译器和 CPU; 他们不必预测任何事情，因此没有错误预测或分支错误预测，这是昂贵的。

所以你试着写一个程序，这样每一行都是一个自我实现的预言。你有三种筹码: 真实，虚假和未知。你试图建立一个只有真相芯片的程序。

Towards that end:

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

“Simple integer operations such as addition, subtraction, comparison, bit operations and shift operations (and increment operators) take only one clock cycle on most microprocessors.”

Incremental operators: i++ is better than ++I;

Boolean operands:

在 & & 语句中最有可能是真的放在最后
最有可能是真的。

因此，为了回答你的问题，如果条件为真或者可能为真，if 语句的开销并不大，否则它就会陷入分支错误预测。

小开

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

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