提问



这是一位高级经理提出的面试问题。


哪个更快?


while(1) {
    // Some code
}


要么


while(2) {
    //Some code
}


我说两者都具有相同的执行速度,因为while中的表达式应该最终评估为truefalse。在这种情况下,两者都评估为true并且while条件内没有额外的条件指令。因此,两者都具有相同的执行速度,而我更喜欢(1)。


但采访者自信地说:
检查你的基础。while(1)while(2)快。
(他没有测试我的信心)


这是真的?


另请参阅:for(;;)是否比while(TRUE)快?如果没有,为什么人们会使用它?


最佳参考


两个循环都是无限的,但我们可以看到哪一个循环每次迭代需要更多的指令/资源。


使用gcc,我将以下两个程序编译为不同优化级别的程序集:


int main(void) {
    while(1) {}
    return 0;
}


点击


int main(void) {
    while(2) {}
    return 0;
}


即使没有优化(-O0),生成的程序集对于两个程序都是相同的。因此,两个循环之间没有速度差异。


作为参考,这里是生成的程序集(使用gcc main.c -S -masm=intel和优化标志):


随着-O0:


    .file   "main.c"
    .intel_syntax noprefix
    .def    __main; .scl    2;  .type   32; .endef
    .text
    .globl  main
    .def    main;   .scl    2;  .type   32; .endef
    .seh_proc   main
main:
    push    rbp
    .seh_pushreg    rbp
    mov rbp, rsp
    .seh_setframe   rbp, 0
    sub rsp, 32
    .seh_stackalloc 32
    .seh_endprologue
    call    __main
.L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"


随着-O1:


    .file   "main.c"
    .intel_syntax noprefix
    .def    __main; .scl    2;  .type   32; .endef
    .text
    .globl  main
    .def    main;   .scl    2;  .type   32; .endef
    .seh_proc   main
main:
    sub rsp, 40
    .seh_stackalloc 40
    .seh_endprologue
    call    __main
.L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"


使用-O2-O3(相同输出):


    .file   "main.c"
    .intel_syntax noprefix
    .def    __main; .scl    2;  .type   32; .endef
    .section    .text.startup,"x"
    .p2align 4,,15
    .globl  main
    .def    main;   .scl    2;  .type   32; .endef
    .seh_proc   main
main:
    sub rsp, 40
    .seh_stackalloc 40
    .seh_endprologue
    call    __main
.L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"


事实上,为循环生成的程序集对于每个优化级别都是相同的:


 .L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"


重要的是:


.L2:
    jmp .L2


我不能很好地阅读汇编,但这显然是一个无条件的循环。jmp指令无条件地将程序重置回.L2标签,甚至没有将值与真值进行比较,当然立即所以再一次,直到程序以某种方式结束。这直接对应于C/C ++代码:


L2:
    goto L2;


编辑:


有趣的是,即使没有优化,以下循环都会在汇编中产生完全相同的输出(无条件jmp):


while(42) {}

while(1==1) {}

while(2==2) {}

while(4<7) {}

while(3==3 && 4==4) {}

while(8-9 < 0) {}

while(4.3 * 3e4 >= 2 << 6) {}

while(-0.1 + 02) {}


令我惊讶的是:


#include

while(sqrt(7)) {}

while(hypot(3,4)) {}


用户定义的函数使事情变得更有趣:


int x(void) {
    return 1;
}

while(x()) {}






#include

double x(void) {
    return sqrt(7);
}

while(x()) {}


-O0中,这两个例子实际上调用x并对每次迭代进行比较。


第一个例子(返回1):


.L4:
    call    x
    testl   %eax, %eax
    jne .L4
    movl    $0, %eax
    addq    $32, %rsp
    popq    %rbp
    ret
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"


第二个例子(返回sqrt(7)):


.L4:
    call    x
    xorpd   %xmm1, %xmm1
    ucomisd %xmm1, %xmm0
    jp  .L4
    xorpd   %xmm1, %xmm1
    ucomisd %xmm1, %xmm0
    jne .L4
    movl    $0, %eax
    addq    $32, %rsp
    popq    %rbp
    ret
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"


然而,在-O1及以上,它们都产生与前面例子相同的组件(无条件jmp回到前面的标签)。


TL; DR



在GCC下,不同的循环被编译为相同的程序集。编译器会评估常量值,并且不会执行任何实际比较。


这个故事的寓意是:



  • C ++源代码和CPU指令之间存在一层转换,这一层对性能有重要影响。

  • 因此,仅通过查看源代码无法评估性能。

  • 编译器应该足够智能,以优化这些微不足道的案例。在绝大多数情况下,程序员不应该浪费时间思考它们。


其它参考1


是的,while(1)远远快于while(2),让人类阅读!如果我在一个不熟悉的代码库中看到while(1),我立即知道作者的意图,我的眼球可以继续下一行。


如果我看到while(2),我可能会停下来试图找出作者为什么不写while(1)。作者的手指是否在键盘上滑动?这个代码库的维护者是否使用while(n)作为一种模糊的评论机制来使循环看起来不同?这是一个在一些破碎的静态分析工具中虚假警告的粗略解决方法吗?或者这是我在阅读生成代码的线索吗?这是一个由于不明智的查找和替换全部,或者糟糕的合并或宇宙射线导致的错误?也许这行代码应该做一些截然不同的事情。也许应该阅读while(w)while(x2)。我最好在文件的历史中找到作者并给他们发送一个WTF电子邮件......现在我已经打破了我的心理背景。while(2)可能会耗费几分钟的时间,而[[while(1)只需要几分之一秒!


我夸张,但只是一点点。代码可读性非常重要。这在采访中值得一提!

其它参考2


显示特定编译器为具有特定选项集的特定目标生成的代码的现有答案不能完全回答问题 - 除非在该特定上下文中询问了问题(使用gcc 4.7.2 for x86_64更快使用默认选项?,例如)。


就语言定义而言,在抽象机器中 while (1)计算整数常量1while (2)计算整数常量2 ;在两种情况下,将结果与等式进行比较。语言标准对两种结构的相对性能完全没有任何说明。


我可以想象一个非常天真的编译器可能会为这两种形式生成不同的机器代码,至少在编译时没有请求优化。


另一方面,C编译器绝对必须在编译时评估某些常量表达式,当它们出现在需要常量表达式的上下文中时。例如,这个:


int n = 4;
switch (n) {
    case 2+2: break;
    case 4:   break;
}


需要诊断;懒惰的编译器没有选择将2+2推迟到执行时间。由于编译器必须能够在编译时评估常量表达式,因此即使不需要,也没有充分的理由不利用该功能。


C标准(N1570 6.8.5p4)说[97]



??迭代语句会导致一个名为循环体的语句
??重复执行,直到控制表达式等于
??0。



所以相关的常数表达式是1 == 02 == 0,两者都评估int0。 (这些比较隐含在while循环的语义中;它们不作为实际的C表达式存在。)


一个反常天真的编译器可以为这两个结构生成不同的代码。例如,对于第一个,它可以生成无条件无限循环(将1视为特殊情况),对于第二个,它可以生成等效于2 != 0的显式运行时比较。但我从未遇到过实际上会以这种方式运行的C编译器,我严重怀疑这样的编译器是否存在。


大多数编译器(我很想说所有生产质量编译器)都可以选择进行额外的优化。在这种选择下,任何编译器都不太可能为这两种形式生成不同的代码。


如果编译器为这两个构造生成不同的代码,请首先检查不同的代码序列是否实际上具有不同的性能。如果是,请尝试使用优化选项再次编译(如果可用)。如果它们仍然不同,请向编译器供应商提交错误报告。它不是(必然)在不符合C标准的意义上的错误,但它几乎肯定是一个应该纠正的问题。


底线:while (1)while(2) 几乎肯定具有相同的性能。它们具有完全相同的语义,并且任何编译器都没有充分的理由不生成相同的代码。


虽然编译器为while(1)生成比while(2)更快的代码是完全合法的,但编译器为while(1)生成更快的代码比对另一次生成更快是合法的的while(1)在同一个程序中。


(你问的那个问题隐含着另一个问题:你如何处理一个坚持不正确的技术要点的面试官。这可能是Workplace网站的一个好问题。)[98]

其它参考3


等一下。面试官,他看起来像这个家伙?


[99]


面试官本人失败这次采访真是太糟糕了,
如果这家公司的其他程序员通过这项测试怎么办?


不。评估语句1 == 02 == 0 应该同样快。我们可以想象糟糕的编译器实现,其中一个可能比另一个更快。但是,为什么一个人应该比另一个更快,没有好的理由。


即使在声明属实时存在一些模糊的情况,也不应该根据晦涩(在这种情况下,令人毛骨悚然)的琐事知识来评估程序员。不要担心这次采访,这里最好的举动就是走路远。


免责声明:这不是原创的Dilbert漫画。这只是一个混搭。 [100]

其它参考4


你的解释是正确的。除了技术知识之外,这似乎是一个测试你自信心的问题。


顺便说一句,如果你回答



??这两段代码同样快,因为两者都需要无限的时间才能完成



面试官会说



??但while (1)每秒可以做更多的迭代;你能解释一下原因吗? (这是废话;再次测试你的信心)



因此,通过像你一样回答,你节省了一些时间,否则你会浪费在讨论这个糟糕的问题上。





以下是我的系统(MS Visual Studio 2012)上的编译器生成的示例代码,关闭了优化:


yyy:
    xor eax, eax
    cmp eax, 1     (or 2, depending on your code)
    je xxx
    jmp yyy
xxx:
    ...


启用优化后:


xxx:
    jmp xxx


所以生成的代码完全相同,至少使用优化编译器。

其它参考5


这个问题最可能的解释是,面试官认为处理器一个接一个地检查数字的各个位,直到它达到非零值:


1 = 00000001
2 = 00000010


如果为零?算法从数字的右侧开始,并且必须检查每个位直到它达到非零位,while(1) { }循环必须检查每次迭代的两倍于while(2) { }循环。


这需要一个非常错误的计算机工作方式的心智模型,但它确实有自己的内部逻辑。一种检查方法是询问while(-1) { }while(3) { }是否同样快,或者while(32) { } 甚至更慢。

其它参考6


当然,我不知道这位经理的真实意图,但我提出了一个完全不同的观点:当一个新成员加入一个团队时,了解他如何应对冲突局势是有用的。


他们让你陷入冲突。如果这是真的,他们很聪明,问题很好。对于某些行业,例如银行业务,将您的问题发布到Stack?溢出可能是拒绝的原因。


但我当然不知道,我只提出一个选择。

其它参考7


我认为线索可以在高级经理问中找到。这个人在成为经理时显然已停止编程,然后他/她花了几年时间成为高级经理。从未对编程失去兴趣,但从那时起就从未写过一条线。所以他的参考文献不是任何体面的编译器,正如一些答案所提到的那样,而是这个人在20 - 30年前工作的编译器。


那时,由于中央小型机的CPU时间非常有价值,程序员花费了相当大的时间来尝试各种方法来使代码更快更有效。正如编写编译器的人一样。我猜测他的公司当时可用的独一无二的编译器是根据经常遇到的可以优化的语句进行优化的,并在遇到一段时间时采取了一些捷径(1)并评估了所有内容否则,包括一段时间(2)。有过这样的经历可以解释他的立场和对它的信心。


让你受雇的最佳方法可能就是让高级经理在你强势顺利带领他走向下一步之前,在编程的美好时光上讲课2-3分钟。面试主题。 (好的时机在这里很重要 - 太快了,你打扰了故事 - 太慢了,你被贴上了一个焦点不够的人)。在面试结束时告诉他你有兴趣了解更多关于这个话题。

其它参考8


你应该问他是如何得出这个结论的。在任何体面的编译器下,两个编译为相同的asm指令。所以,他应该告诉你编译器也要开始。即使这样,你也必须非常了解编译器和平台,甚至做出理论上有根据的猜测。最后,它在实践中并不重要,因为还有其他外部因素,如内存碎片或系统负载,这将影响循环而不是这个细节。

其它参考9


为了这个问题,我应该补充一点,我记得来自C委员会的Doug Gwyn写道,一些没有优化器传递的早期C编译器会在while(1)的汇编中生成一个测试(与[[??for(;;)相比较]]不会有它。


我会通过给出这个历史记录来回答访问者,然后说即使我对任何编译器都这样做感到非常惊讶,编译器也可以:



  • 没有优化器传递编译器为while(1)while(2)
  • 生成测试
  • 使用优化器传递编译器被指示优化(使用无条件跳转)所有while(1)因为它们被认为是惯用的。这会使while(2)留下一个测试,因此在两者之间产生性能差异。



我当然会向访调员添加不考虑while(1)while(2)的相同构造是低质量优化的标志,因为这些是等效构造。

其它参考10


对这个问题的另一个看法是看你是否有勇气告诉你的经理他/她错了!你可以多么轻柔地沟通它。


我的第一直觉是生成程序集输出以向管理员显示任何体面的编译器应该处理它,如果它没有这样做,你将为它提交下一个补丁:)

其它参考11


要看到这么多人深入研究这个问题,请确切地说明为什么这很可能是一个测试,看看你想要多快微优化的东西。


我的回答是;这并不重要,我更关注我们正在解决的业务问题。毕竟,这就是我将要付出的代价。


此外,我会选择while(1) {},因为它更常见,其他队友不需要花时间弄清楚为什么有人会选择高于1的数字。


现在去写一些代码。 ;-)

其它参考12


当这种废话可能产生影响时,我曾经编程C和汇编代码。当它确实有所作为时,我们在大会上写了它。


如果我被问到这个问题,我会重复唐纳德克努特1974年关于过早优化的着名言论,如果采访者不笑又继续前进,那就走了。

其它参考13


在我看来,这是一个被掩盖为技术问题的行为面试问题。有些公司这样做 - 他们会问一个技术问题,任何有能力的程序员都应该很容易回答,但当受访者给出正确答案时,面试官会告诉他们他们错了。


该公司希望了解您将如何应对这种情况。你是否静静地坐在那里并且不要因为自我怀疑或害怕面试官而害怕你的答案是正确的?或者你是否愿意挑战一个你知道错误的权威人士?他们想看看是否你愿意坚持自己的信念,如果你能够以机智和尊重的方式做到这一点。

其它参考14


如果你担心优化,你应该使用


for (;;)


因为没有测试。 (愤世嫉俗的模式)

其它参考15


这是一个问题:如果你实际编写一个程序并测量它的速度,两个循环的速度可能会有所不同!对于一些合理的比较:


unsigned long i = 0;
while (1) { if (++i == 1000000000) break; }

unsigned long i = 0;
while (2) { if (++i == 1000000000) break; }


添加一些代码打印时间,一些随机效果,如循环在一个或两个缓存行中的位置可能会产生影响。一个循环可能完全在一个缓存行内,或者在缓存行的开头,或者它可能跨越两个缓存行。因此,无论采访者声称最快,实际上可能是最快的 - 巧合。


最糟糕的情况:优化编译器不会弄清楚循环的作用,但要确定执行第二个循环时产生的值与第一个循环产生的值相同。并为第一个循环生成完整代码,但不是第二个。

其它参考16


它们都是平等的 - 相同。


根据规范,任何不为0的东西都被认为是真的,所以即使没有任何优化,一个好的编译器也不会产生任何代码
for while(1)或while(2)。编译器将生成!= 0的简单检查。

其它参考17


从人们花费大量时间和精力来测试,证明和回答这个非常直截了当的问题,Id说,通过提出问题,两者都变得非常缓慢。


所以要花更多的时间在上面......


而(2)是荒谬的,因为,


while(1)和while(true)在历史上用于创建一个无限循环,该循环期望在循环内的某个阶段基于肯定会发生的条件调用break。


1只是总是评估为真,因此,说while(2)与说while(1 + 1 == 2)一样愚蠢,这也将评估为真。


如果你想完全愚蠢,只需使用: -


while (1 + 5 - 2 - (1 * 3) == 0.5 - 4 + ((9 * 2) / 4)) {
    if (succeed())
        break;
}


我想你的编码器做了一个错字,但没有影响代码的运行,但如果他故意使用2只是为了变得奇怪,那么在他把你的代码变得很奇怪之前把它解雇之前很难阅读和使用。

其它参考18


也许面试官故意提出这样一个愚蠢的问题,并希望你提出3分:



  1. 基本推理。两个循环都是无限的,很难谈论性能。

  2. 有关优化级别的知识。如果您让编译器为您进行任何优化,他想听听您的意见,它会优化条件,尤其是在块不为空的情况下。

  3. 关于微处理器架构的知识。大多数架构都有一个特殊的CPU指令用于与0进行比较(但不一定更快)。


其它参考19


这取决于编译器。


如果它优化代码,或者如果使用相同数量的指令对特定指令集求值1和2为真,则执行速度将相同。


在实际情况下,它总是同样快,但是可以想象一个特定的编译器和一个特定的系统,当这将被不同地评估。


我的意思是:这不是一个与语言(C)相关的问题。

其它参考20


由于想要回答这个问题的人想要最快的循环,我会回答说两者同样编译成相同的汇编代码,如其他答案中所述。不过你可以使用循环展开向面试官建议; a {while while循环而不是while循环。


谨慎:您需要确保循环至少始终运行一次


循环内部应该有一个中断条件。


同样对于那种循环,我个人更喜欢使用do {} while(42),因为除了0之外的任何整数都可以完成这项工作。

其它参考21


我能想到while(2)为什么会变慢的唯一原因是:



  1. 代码优化循环


    cmp eax, 2

  2. 当减法发生时,你基本上减去


    一个。 00000000 - 00000010 cmp eax, 2


    代替


    00000000 - 00000001 cmp eax, 1



cmp仅设置标志而不设置结果。因此,在最不重要的位上,我们知道是否需要借用 b 来借用。而使用 a 则必须执行two在借入之前扣除。