是“IF”吗? 昂贵的?
我一辈子都记不起老师那天到底说了什么,我希望你能知道。
该模块是“数据结构和算法”,他告诉我们以下内容:
if
语句是最昂贵的 [某物]。 [某事] 注册 [某事]。
是的,我的记忆力确实很糟糕,我真的很抱歉,但我已经在谷歌上搜索了几个小时,但什么也没找到。 有任何想法吗?
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:
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?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
发布评论
评论(18)
CPU 是深度流水线的。 任何分支指令(if/for/while/switch/etc)都意味着CPU并不真正知道接下来要加载和运行什么指令。
CPU 要么在等待知道要做什么时停止,要么进行猜测。 对于较旧的 CPU,或者如果猜测错误,您将不得不在它加载正确的指令时遭遇管道停顿。 根据 CPU 的不同,这可能会导致高达 10-20 条指令的停顿。
现代 CPU 试图通过良好的分支预测、同时执行多个路径并仅保留实际路径来避免这种情况。 这有很大帮助,但也只能到此为止。
祝你在课堂上好运。
另外,如果您在现实生活中不得不担心这个问题,您可能正在做操作系统设计、实时图形、科学计算或类似的 CPU 限制的事情。 担心之前的简介。
一些CPU(如X86)提供编程级别的分支预测以避免这种分支预测延迟。
一些编译器(如 GCC)将它们公开为高级编程语言(如 C/C++)的扩展。
请参阅 Linux 内核中的 likely()/unlikely() 宏 - 它们如何工作? 他们有什么好处?。
你的代码应该是可预测的和可能的。
如果你的整个程序是这样的:
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;
布尔操作数:
- In && 将最有可能为真的陈述放在最后
- In || 把最有可能为真的放在第一位。
因此,为了回答您的问题,如果条件为真或可能为真,则 if 语句并不那么昂贵,否则它会陷入分支错误预测。
在许多较旧的处理器上,人们可以识别“如果”的情况会很昂贵以及不会的情况,但是现代高性能处理器包括用于预测将采用和不会采用哪些分支的电路,并且只有在以下情况下分支才会昂贵这样的电路猜测错误。 不幸的是,这通常使得确定编写一段代码的最佳方式变得非常困难,因为处理器完全有可能在处理人为的测试数据时正确预测分支结果,但在处理现实世界时却猜测其中许多结果是错误的数据,反之亦然。
除非人们试图优化其分支时序很好理解的特定目标的性能,否则最好的方法通常是假设分支时序不太可能成为整体性能的重要因素,除非或直到人们能够证明这一点。 分支时序可能会受到输入数据中细微差异的影响,并且通常没有实际的方法来确保测试数据包括可能影响性能的所有变化。
在最低级别(在硬件中),是的,如果是昂贵的。 为了理解其中的原因,您必须了解管道的工作原理。
当前要执行的指令通常存储在指令指针 (IP) 或程序计数器 (PC) 中; 这些术语是同义词,但不同的术语用于不同的架构。 对于大多数指令,下一条指令的PC只是当前PC加上当前指令的长度。 对于大多数RISC架构,指令都是恒定长度,因此PC可以按恒定量递增。 对于x86等CISC架构,指令可以是可变长度的,因此解码指令的逻辑必须弄清楚当前指令有多长才能找到下一条指令的位置。
然而,对于分支指令,要执行的下一条指令不是当前指令之后的下一个位置。 分支是 goto - 它们告诉处理器下一条指令在哪里。 分支可以是有条件的或无条件的,目标位置可以是固定的或计算的。
有条件与无条件很容易理解 - 仅当某个条件成立时才会采用条件分支(例如一个数字是否等于另一个数字); 如果未采用分支,则控制将像平常一样继续执行分支后的下一条指令。 对于无条件分支,总是采用该分支。 条件分支出现在 if
语句以及 for
和 while
循环的控制测试中。 无条件分支出现在无限循环、函数调用、函数返回、break 和 continue 语句、臭名昭著的 goto 语句等等(这些列表远非详尽)。
分支目标是另一个重要问题。 大多数分支都有固定的分支目标 - 它们转到在编译时固定的代码中的特定位置。 这包括 if 语句、各种循环、常规函数调用等等。 计算分支在运行时计算分支的目标。 这包括 switch 语句(有时)、从函数返回、虚函数调用和函数指针调用。
那么这对性能意味着什么呢? 当处理器看到其管道中出现分支指令时,它需要弄清楚如何继续填充其管道。 为了弄清楚程序流中分支之后有哪些指令,它需要知道两件事:(1)是否将采用分支以及(2)分支的目标。 弄清楚这一点被称为分支预测,这是一个具有挑战性的问题。 如果处理器猜测正确,程序就会全速继续运行。 相反,如果处理器猜测不正确,它只是花了一些时间计算错误的东西。 现在它必须刷新其管道并使用来自正确执行路径的指令重新加载它。 底线:性能受到巨大影响。
因此,if 语句昂贵的原因是由于分支错误预测。 这只是最低级别的。 如果您正在编写高级代码,则根本不需要担心这些细节。 仅当您用 C 或汇编编写对性能极其关键的代码时,您才应该关心这一点。 如果是这种情况,编写无分支代码通常优于分支代码,即使需要更多指令。 您可以使用一些很酷的小技巧来计算诸如 abs()
、min()
和 max()
之类的东西,而无需分枝。
分支,特别是在 RISC 架构微处理器上,是最昂贵的指令之一。 这是因为在许多体系结构上,编译器会预测最有可能采用哪条执行路径,并将这些指令放在可执行文件中的下一个位置,因此当分支发生时它们已经位于 CPU 缓存中。 如果分支走另一条路,它必须返回主内存并获取新指令——这是相当昂贵的。 在许多 RISC 架构上,除了分支(通常是 2 个周期)之外,所有指令都是一个周期。 我们这里讨论的不是主要成本,所以不用担心。 此外,编译器在 99% 的情况下都会比您优化得更好:) EPIC 架构(Itanium 就是一个例子)真正令人敬畏的事情之一是它缓存(并开始处理)来自分支两侧的指令,然后一旦知道分支的结果就丢弃不需要的集合。 如果典型架构沿着不可预测的路径分支,这可以节省额外的内存访问。
请查看有关单元性能的文章通过分支消除提高性能。 另一篇有趣的文章是实时碰撞检测博客上的这篇关于无分支选择的文章。
除了针对这个问题已经发布的优秀答案之外,我想提醒一下,尽管“if”语句被认为是昂贵的低级操作,但尝试在更高级别的环境中利用无分支编程技术,例如脚本语言或业务逻辑层(无论语言如何),可能是非常不合适的。
绝大多数情况下,编写程序时应首先考虑清晰度,其次考虑性能优化。 在许多问题领域中,性能至关重要,但简单的事实是,大多数开发人员编写的模块并不是用于渲染引擎的核心或连续运行数周的高性能流体动力学模拟。 当您的解决方案的首要任务是“正常工作”时,您最不需要考虑的事情应该是是否可以节省代码中条件语句的开销。
if
本身不慢。 缓慢总是相对的,我敢打赌,你从来没有感受到 if 语句的“开销”。 如果您要编写高性能代码,无论如何您可能都希望避免分支。 使 if
变慢的原因是处理器根据一些启发式方法从 if
之后预加载代码。 它还会阻止管道直接在机器代码中的 if
分支指令之后执行代码,因为处理器还不知道将采取什么路径(在管道处理器中,多个指令是交错的,并且执行)。 执行的代码可能必须反向执行(如果采用了另一个分支。这称为分支错误预测),或者在这些地方填充了 noop,这样就不会发生这种情况。不会发生。
如果 if
是邪恶的,那么 switch
也是邪恶的,&&
、||
也是邪恶的。 别担心。
在最低可能级别 if
包含(在计算特定 if
的所有特定于应用程序的先决条件之后):
- 如果测试成功,则某些测试指令
- 跳转到代码中的某个位置,否则继续前进。
与此相关的成本:
- 低级比较——通常是 1 个 cpu 操作,超级便宜的
- 潜在跳转——这可能很昂贵
思考为什么跳转很昂贵:
- 你可以跳转到内存中任何地方的任意代码,如果事实证明它是这样的不被CPU缓存——我们有一个问题,因为我们需要访问主内存,而
- 现代CPU执行分支预测的速度较慢。 他们尝试猜测是否会成功,并在管道中提前执行代码,从而加快速度。 如果预测失败,则管道之前完成的所有计算都必须失效。 这也是一项昂贵的操作
所以总结一下:
- 如果您真的非常关心性能,那么这可能会很昂贵。
- 当且仅当您正在编写实时光线追踪器或生物模拟或类似的东西时,您才应该关心它。 在现实世界的大多数情况下,没有理由关心它。
另请注意,循环内部不一定非常昂贵。
现代 CPU 假定在第一次访问 if 语句时,将采用“if-body”(或者换句话说:它还假定循环体将被多次采用)(*)。 在第二次和进一步访问时,它(CPU)也许可以查看分支历史表,并查看上次的情况如何(是真的吗?是假的吗?)。 如果上次为 false,则推测执行将继续到 if 的“else”,或超出循环。
(*) 该规则实际上是“不采用前向分支,采用后向分支”。 在 if 语句中,如果条件计算结果为 false,则仅有一个[向前]跳转(到 if 主体之后的点)(记住:CPU 无论如何假设不进行分支/跳转),但在循环中,可能有一个到循环后位置的前向分支(不进行),以及重复时的向后分支(要进行)。
这也是为什么对虚函数或函数指针调用并不像许多人想象的那么糟糕的原因之一(http://phresnel.org/blog/)
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
正如许多人指出的那样,条件分支在现代计算机上可能非常慢。
话虽这么说,有很多条件分支并不存在于 if 语句中,您无法总是知道编译器会产生什么结果,并且担心基本语句将花费多长时间实际上总是错误的事情去做。 (如果你能知道编译器将可靠地生成什么,那么你可能没有一个好的优化编译器。)
As pointed out by many, conditional branches can be very slow on a modern computer.
That being said, there are a whole lot of conditional branches that don't live in if statements, you can't always tell what the compiler will come up with, and worrying about how long basic statements will take is virtually always the wrong thing to do. (If you can tell what the compiler will generate reliably, you may not have a good optimizing compiler.)