这是一位高级经理提出的面试问题 .
哪个更快?
while(1) {
// Some code
}
要么
while(2) {
//Some code
}
我说两者都具有相同的执行速度,因为 while
中的表达式最终应该评估为 true
或 false
. 在这种情况下,两者都评估为 true
并且 while
条件中没有额外的条件指令 . 因此,两者都具有相同的执行速度,而我更喜欢(1) .
但是采访者自信地说:“检查你的基础知识. while(1)
比 while(2)
更快 . ” (他没有测试我的信心)
这是真的?
22 回答
对这个问题的另一个看法是看你是否有勇气告诉你的经理他/她错了!你可以多么轻柔地沟通它 .
我的第一直觉是生成程序集输出以向管理员显示任何体面的编译器应该处理它,如果它没有这样做,你将为它提交下一个补丁:)
由于想要回答这个问题的人想要最快的循环,我会回答说两者同样编译成相同的汇编代码,如其他答案中所述 . 不过你可以使用 'loop unrolling'; a do {} while loop 而不是while循环向面试官建议 .
谨慎: You need to ensure that the loop would at least always run once .
循环内部应该有一个中断条件 .
同样对于那种循环,我个人更喜欢使用do {} while(42),因为除了0之外的任何整数都可以完成这项工作 .
这是一个问题:如果您实际编写程序并测量其速度,则两个循环的速度可能会有所不同!对于一些合理的比较:
添加一些代码打印时间,一些随机效果,如循环在一个或两个缓存行中的位置可能会产生影响 . 一个循环可能完全在一个缓存行内,或者在缓存行的开头,或者它可能跨越两个缓存行 . 因此,无论采访者声称最快,实际上可能是最快的 - 巧合 .
最糟糕的情况:优化编译器不会弄清楚循环的作用,但是会发现第二个循环执行时产生的值与第一个循环产生的值相同 . 并为第一个循环生成完整代码,但不为第二个循环生成完整代码 .
从人们花费大量时间和精力来测试,证明和回答这个非常直截了当的问题,Id说,通过提出问题,两者都变得非常缓慢 .
所以要花更多的时间在上面......
“而(2)”是荒谬的,因为,
“while(1)”和“while(true)”在历史上用于创建一个无限循环,该循环期望在循环内的某个阶段基于肯定会发生的条件调用“break” .
“1”只是总是评估为真,因此,说“while(2)”与说“while(1 1 == 2)”一样愚蠢,这也将评估为真 .
如果你想完全愚蠢,只需使用: -
我想你的编码器做了一个错字,但没有影响代码的运行,但如果他故意使用“2”只是为了变得奇怪,那么在他把你的代码变得很奇怪之前把它解雇之前很难阅读和使用 .
为了这个问题,我应该补充一下,我记得来自C委员会的Doug Gwyn写道,一些没有优化器传递的早期C编译器会在
while(1)
的汇编中生成一个测试(与没有它的for(;;)
相比) .我会通过给出这个历史记录来回答访问者,然后说即使我对任何编译器都这样做感到非常惊讶,编译器也可以:
没有优化器传递编译器生成
while(1)
和while(2)
的测试使用优化器传递编译器被指示优化(使用无条件跳转)所有
while(1)
因为它们被认为是惯用的 . 这将使while(2)
进行测试,从而在两者之间产生性能差异 .我当然会向面试官添加不考虑
while(1)
和while(2)
的相同构造是低质量优化的标志,因为这些是等效构造 .当然,我不知道这位经理的真实意图,但我提出了一个完全不同的观点:当一个新成员加入一个团队时,了解他如何应对冲突局势是有用的 .
他们让你陷入冲突 . 如果这是真的,他们很聪明,问题很好 . 对于某些行业,例如银行业务,将您的问题发布到Stack Overflow可能是拒绝的原因 .
但我当然不知道,我只提出一个选择 .
这个问题最可能的解释是,面试官认为处理器一个接一个地检查数字的各个位,直到它达到非零值:
如果"is zero?"算法从数字的右侧开始,并且必须检查每个位直到它达到非零位,
while(1) { }
循环必须检查每次迭代的两倍于while(2) { }
循环 .这需要一个非常错误的计算机工作方式的心智模型,但它确实有自己的内部逻辑 . 一种检查方法是询问
while(-1) { }
或while(3) { }
是否同样快,或者while(32) { }
是否会更慢 .等一下 . 面试官,他看起来像这个家伙?
面试官本人在这次采访中失败了,如果这家公司的其他程序员有这样的测试怎么办呢?
否 . 评估陈述
1 == 0
和2 == 0
应该同样快 . 我们可以想象糟糕的编译器实现,其中一个可能比另一个更快 . 但是没有充分的理由说为什么一个人应该比另一个人更快 .即使在声明为真的情况下存在一些模糊的情况,也不应该根据对模糊(在这种情况下,令人毛骨悚然)的琐事的知识来评估程序员 . 不要担心这次采访,这里最好的举动就是走开 .
Disclaimer: 这不是原始的Dilbert卡通片 . 这只是一个mashup .
是的,
while(1)
比while(2)
快得多,供人阅读!如果我在一个不熟悉的代码库中看到while(1)
,我立即知道作者的意图,我的眼球可以继续下一行 .如果我看到
while(2)
,我'll probably halt in my tracks and try to figure out why the author didn' t写while(1)
. 作者的手指在键盘上滑动了吗?这个代码库的维护者是否使用while(n)
作为一个模糊的注释机制来使循环看起来不同?对于某些破碎的静态分析工具中的虚假警告,这是一个粗略的解决方法吗?或者这是我正在阅读生成代码的线索吗?这是一个由于不明智的查找和替换全部,或者糟糕的合并或宇宙射线导致的错误?也许这行代码应该做一些截然不同的事情 . 也许应该读while(w)
或while(x2)
. 我'd better find the author in the file'的历史并给他们发了一封"WTF"电子邮件......现在我已经破坏了我的心理背景 .while(2)
可能会耗费几分钟的时间,而while(1)
只需要几分之一秒!我夸张了,但只是一点点 . 代码可读性非常重要 . 这在接受采访时值得一提!
显示特定编译器为具有特定选项集的特定目标生成的代码的现有答案不能完全回答问题 - 除非在该特定上下文中询问了问题(“使用gcc 4.7.2 for x86_64更快”使用默认选项?“,例如) .
就语言定义而言,在抽象机器中
while (1)
计算整数常量1
,while (2)
计算整数常量2
;在两种情况下,将结果与等式进行比较 . 语言标准对两种结构的相对性能完全没有任何说明 .我可以想象一个非常天真的编译器可能会为这两种形式生成不同的机器代码,至少在编译时没有请求优化 .
另一方面,C编译器绝对必须在编译时评估一些常量表达式,当它们出现在需要常量表达式的上下文中时 . 例如,这个:
需要诊断;惰性编译器没有选择将
2+2
的延迟推迟到执行时间 . 由于编译器必须能够在编译时计算常量表达式,因此不需要's no good reason for it not to take advantage of that capability even when it' .C标准(N1570 6.8.5p4)说明了这一点
所以相关的常量表达式是
1 == 0
和2 == 0
,两者都计算为int
值0
. (这些比较隐含在while
循环的语义中;它们不作为实际的C表达式存在 . )一个反常天真的编译器可以为这两个结构生成不同的代码 . 例如,对于第一个,它可以生成无条件无限循环(将
1
视为特殊情况),对于第二个,它可以生成等效于2 != 0
的显式运行时比较 . 但我从未遇到过实际上会以这种方式运行的C编译器,我严重怀疑这样的编译器是否存在 .大多数编译器(我很想说所有 生产环境 质量编译器)都可以选择进行额外的优化 . 在这样的选项下,任何编译器都不太可能为这两种形式生成不同的代码 .
如果编译器为这两个构造生成不同的代码,请首先检查不同的代码序列是否实际上具有不同的性能 . 如果是,请尝试使用优化选项再次编译(如果可用) . 如果他们仍然不同,请提交错误报告编译厂商 . 它(不一定)是一个不符合C标准的错误,但它几乎肯定是一个应该纠正的问题 .
底线:
while (1)
和while(2)
几乎肯定具有相同的性能 . 它们具有完全相同的语义,并且没有充分的理由让任何编译器不生成相同的代码 .虽然编译器为
while(1)
生成比while(2)
更快的代码是完全合法的,但编译器为while(1)
生成比在同一程序中出现的另一个while(1)
更快的代码同样合法 .(你问的那个问题隐含着另一个问题:你如何处理一个坚持不正确的技术要点的面试官 . 这可能是一个很好的问题the Workplace site) .
要看到这么多人深入研究这个问题,请说明为什么这很可能是一个测试,看看你想要多快的事情 .
我的回答是;这并不重要,我更关注我们正在解决的业务问题 . 毕竟,这就是我要付出的代价 .
此外,我会选择
while(1) {}
,因为它更常见,其他队友也不需要花时间弄清楚为什么有人会选择高于1的数字 .现在去写一些代码 . ;-)
在我看来,这是一个被掩盖为技术问题的行为面试问题 . 有些公司这样做 - 他们会问一个技术问题,任何有能力的程序员都应该很容易回答,但当受访者给出正确答案时,面试官会告诉他们他们错了 .
该公司希望了解您将如何应对这种情况 . 你是否安静地坐在那里,不要因为自我怀疑或害怕面试官而害怕你的答案是正确的?或者你是否愿意挑战一个你知道错误的权威人士?他们想看看你是否愿意坚持自己的信念,如果你能以一种机智和尊重的方式做到这一点 .
我能想到
while(2)
为什么会变慢的唯一原因是:cmp eax, 2
一个 .
00000000 - 00000010 cmp eax, 2
代替
湾
00000000 - 00000001 cmp eax, 1
cmp
仅设置标志,不设置结果 . 因此,在最不重要的位上,我们知道是否需要借用 b . 而使用 a ,您必须在借入之前执行两次减法 .你的解释是正确的 . 除了技术知识之外,这似乎是一个测试你自信心的问题 .
顺便说一句,如果你回答
面试官会说
因此,通过像你一样回答,你节省了一些时间,否则你会浪费在讨论这个糟糕的问题上 .
以下是我的系统(MS Visual Studio 2012)上的编译器生成的示例代码,关闭了优化:
启用优化后:
所以生成的代码完全相同,至少使用优化编译器 .
两个循环都是无限的,但是我们可以看到哪一个循环每次迭代需要更多的指令/资源 .
使用gcc,我将以下两个程序编译为不同优化级别的程序集:
即使没有优化(
-O0
), the generated assembly was identical for both programs. 因此,两个循环之间没有速度差异 .作为参考,这里是生成的程序集(使用带有优化标志的
gcc main.c -S -masm=intel
):使用
-O0
:使用
-O1
:使用
-O2
和-O3
(相同输出):事实上,为循环生成的程序集对于每个优化级别都是相同的:
重要的是:
我不能很好地阅读汇编,但这显然是一个无条件的循环 .
jmp
指令无条件地将程序重置回.L2
标签,甚至没有将值与true进行比较,当然会立即再次执行,直到程序以某种方式结束 . 这直接对应于C / C代码:编辑:
有趣的是,即使没有优化,以下循环都会在汇编中产生完全相同的输出(无条件
jmp
):令我惊讶的是:
用户定义的函数使事情变得更有趣:
在
-O0
,这两个示例实际上调用x
并对每次迭代执行比较 .第一个例子(返回1):
第二个例子(返回
sqrt(7)
):但是,在
-O1
及以上,它们都生成与前面示例相同的程序集(无条件jmp
返回前一个标签) .TL; DR
在GCC下,不同的循环被编译为相同的程序集 . 编译器会评估常量值,并且不会执行任何实际比较 .
这个故事的寓意是:
C源代码和CPU指令之间存在一层转换,该层对性能有重要影响 .
因此,仅通过查看源代码无法评估性能 .
编译器 should be 足够聪明,可以优化这些琐碎的案例 . 程序员 should not 在绝大多数情况下浪费时间思考它们 .
这取决于编译器 .
如果它优化代码,或者如果使用相同数量的指令对特定指令集计算1和2为真,则执行速度将相同 .
在实际情况下,它总是同样快,但是可以想象一个特定的编译器和一个特定的系统,当这将被不同地评估 .
我的意思是:这不是一个与语言(C)相关的问题 .
当这种废话可能产生影响时,我曾经编程C和汇编代码 . 当它确实有所作为时,我们在大会上写了它 .
如果我被问到这个问题,我会重复唐纳德·克努特(Donald Knuth)1974年关于过早优化的着名言论,如果采访者不笑并继续前进,那就走了 .
你应该问他是如何得出这个结论的 . 在任何体面的编译器下,两个编译为相同的asm指令 . 所以,他应该告诉你编译器也要开始 . 即使这样,你也必须非常了解编译器和平台,甚至做出理论上有根据的猜测 . 最后,它在实践中并不重要,因为还有其他外部因素,如内存碎片或系统负载,这将影响循环而不是这个细节 .
我认为线索可以在“高级经理问”中找到 . 这个人在成为经理时显然已停止编程,然后他/她花了几年时间成为高级经理 . 从未对编程失去兴趣,但从那时起就从未写过一条线 . 所以他的参考文献不是“任何体面的编译器”,正如一些答案所提到的那样,而是“这个人在20 - 30年前工作的编译器” .
那时,程序员花费了相当大的时间来尝试各种方法来使代码更快更高效,因为“中央小型机”的CPU时间非常有 Value . 正如编写编译器的人一样 . 我猜他的公司当时提供的唯一编译器是根据“经常遇到的可以优化的语句”进行优化的,并在遇到一段时间(1)并评估所有内容时采取了一些快捷方式否则,包括一段时间(2) . 有过这样的经历可以解释他的立场和对此的信心 .
让你受雇的最佳方法可能就是让高级经理在你接受下一次面试之前,在"the good old days of programming"上讲课2-3分钟 . (好的时机在这里很重要 - 太快了,你很有兴趣了解这个话题的更多信息 .
它们都是平等的 - 相同 .
根据规范,任何非0的都被认为是真的,所以即使没有任何优化,良好的编译器也不会为while(1)或while(2)生成任何代码 . 编译器将生成
!= 0
的简单检查 .也许面试官故意提出这样一个愚蠢的问题,并希望你提出3分:
Basic reasoning. 两个循环都是无限的,很难谈论性能 .
Knowledge about optimisation levels. 他想听听你是否让编译器为你做任何优化,它会优化条件,特别是如果块不为空 .
Knowledge about microprocessor architecture. 大多数体系结构都有一个特殊的CPU指令用于与0进行比较(但不一定更快) .
如果你担心优化,你应该使用
因为没有测试 . (愤世嫉俗的模式)