"IF"价格昂贵吗？

Question

在我的生活中,我不能记住那天老师说的话,我希望你可能知道.

该模块是"数据结构和算法",他告诉我们的一些事情:

该if声明是最昂贵的[东西.[东西]注册[东西].

是的,我确实有一个可怕的记忆,我真的很抱歉,但我一直在谷歌搜索几个小时,没有任何事情发生.有任何想法吗？

Answer 1

在最低级别(在硬件中),是的,如果 s很贵.为了理解原因,您必须了解管道的工作原理.

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

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

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

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

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

因此,if语句昂贵的原因是分支错误预测.这只是最低级别.如果您正在编写高级代码,则根本不需要担心这些细节.如果您在C或汇编中编写极其性能关键的代码,那么您应该只关心这一点.如果是这种情况,编写无分支代码通常优于分支代码,即使需要更多指令也是如此.有一些很酷位变换花样,你可以做计算的东西,如abs(),min()和max()没有分支.

Answer 2

"昂贵"是一个非常相对的术语,特别是与" if"声明的关系,因为您还必须考虑条件的成本.这可以是从几个简短的cpu指令到测试调用远程数据库的函数的结果.

我不担心.除非您正在进行嵌入式编程,否则您可能根本不应该关注" if" 的成本.对于大多数程序员而言,它不会成为应用程序性能的驱动因素.

Answer 3

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

Answer 4

查看文章通过分支消除细胞性能的更好性能.另一个有趣的是关于实时碰撞检测博客上的无分支选择的帖子.

除了针对这个问题已经发布的优秀答案之外,我还想提醒一下,虽然"if"语句被认为是昂贵的低级操作,但试图在更高级别的环境中使用无分支编程技术,例如脚本语言或业务逻辑层(不管语言),可能是荒谬的不合适.

绝大多数情况下,程序应首先为清晰度编写,然后针对性能进行优化.有许多问题领域,其中性能至关重要,但简单的事实是,大多数开发人员不是在渲染引擎的核心深处编写模块,也不是在几周内运行的高性能流体动力学模拟.当你的解决方案"正常工作"的首要任务时,最后一件事就是你是否可以节省代码中条件语句的开销.

Answer 5

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

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

与此相关的成本:

• 低级别比较 - 通常是1个cpu操作,超级便宜
• 潜在的跳跃 - 这可能很昂贵

Reson为什么跳跃很贵:

• 你可以跳转到存在于内存中的任何地方的arbirary代码,如果事实证明它没有被cpu缓存 - 我们有一个问题,因为我们需要访问主内存,这是较慢的
• 现代CPU做分支预备.他们试图猜测是否会成功并在管道中提前执行代码,从而加快速度.如果预测失败,则必须使管道提前完成的所有计算无效.这也是一项昂贵的操作

总结一下:

• 如果真的,真的,非常关心性能,那么可能会有所体现.
• 当且仅当您正在编写实时光线跟踪器或生物模拟或类似的东西时,您应该关心它.在大多数现实世界中没有理由关心它.

Answer 6

if本身并不慢.慢慢总是相对的,我打赌我的生活,你从来没有感受到if语句的"开销".如果你打算制作一个高性能的代码,那么你无论如何都要避免分支.是什么让if慢的是,处理器从后预压代码if基于一些启发和诸如此类的东西.它还将阻止管道直接在if机器代码中的分支指令之后执行代码,因为处理器还不知道将采用什么路径(在流水线处理器中,多个指令被交错并执行).执行的代码可能必须反向执行(如果另一个分支被执行.它被调用branch misprediction),或者noop在那些地方被填充,这样就不会发生这种情况.

如果if是邪恶,那么switch也是邪恶的&&,||也是.别担心.

Answer 7

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

Answer 8

现代处理器具有长的执行流水线,这意味着几个指令同时在各个阶段执行.当下一个指令开始运行时,它们可能并不总是知道一条指令的结果.当它们遇到条件跳转(if)时,它们有时必须等到管道为空才能知道指针指针应该走哪条路.

我认为这是一个长途货运列车.它可以在一条直线上快速运载大量货物,但它的角落很严重.

奔腾4(普雷斯科特)拥有31个阶段的着名长管道.

更多关于维基百科

Answer 9

还要注意，在循环中是不是一定是非常昂贵的。

现代 CPU 假设在第一次访问 if 语句时，将采用“if-body”（或者换句话说：它也假设循环主体将被多次采用）（*）。在第二次和进一步访问时，它（CPU）可能会查看分支历史记录表，并查看上次条件如何（是否为真？是否为假？）。如果上次为 false，则推测执行将继续执行 if 的“else”，或超出循环。

(*) 规则实际上是“不采用前向分支，采用后向分支”。在 if 语句中，如果条件计算结果为 false ，则只有[forward] 跳转（到if-body 之后的点）（请记住：CPU 无论如何假定不进行分支/跳转），但在循环中, 可能有一个前向分支到循环后的位置（不采取），以及重复时的后向分支（采取）。

这也是为什么调用虚函数或函数指针调用并不像许多人认为的那么糟糕的原因之一 ( http://phresnel.org/blog/ )

Answer 10

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

话虽这么说，有很多条件分支并不存在于 if 语句中，你不能总是知道编译器会想出什么，担心基本语句需要多长时间实际上总是错误的去做。（如果你能确定编译器将可靠地生成什么，你可能没有一个好的优化编译器。）