与其他类型的循环相比,编译器是否为do-while循环生成更好的代码？

Question

zlib压缩库中有一个注释(在Chromium项目中用于许多其他项目),这意味着C中的do-while循环在大多数编译器上生成"更好"的代码.这是它出现的代码片段.

do {
} while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
         *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
         *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
         *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
         scan < strend);
/* The funny "do {}" generates better code on most compilers */

https://code.google.com/p/chromium/codesearch#chromium/src/third_party/zlib/deflate.c&l=1225

有没有证据表明大多数(或任何)编译器会生成更好(例如更高效)的代码？

更新: 原作者之一Mark Adler在评论中给出了一些背景信息.

Answer 1

首先:

甲do-while环是不一样的一个while-loop或for-loop.

• while和for循环可能根本不运行循环体.
• 一个do-while循环总是在循环体至少一次-它跳过了初始条件检查.

这是合乎逻辑的差异.也就是说,不是每个人都严格遵守这一点.即使在保证它总是至少循环一次的情况下,使用while或for循环也是很常见的.(特别是在带有foreach循环的语言中.)

因此,为了避免比较苹果和橙子,我将继续假设循环将始终至少运行一次.此外,我不再提及for循环,因为它们本质上是while循环,带有一些循环计数器的语法糖.

所以我会回答这个问题:

如果while保证循环至少循环一次,那么使用do-while循环是否有任何性能提升.

A do-while跳过第一个条件检查.因此,有一个较少的分支和一个较少的条件来评估.

如果检查条件很昂贵,并且您知道保证至少循环一次,那么do-while循环可能会更快.

虽然这被认为是最佳的微优化,但它是编译器不能总是这样做的:特别是当编译器无法证明循环将始终至少输入一次时.

换句话说,一个while循环:

while (condition){
    body
}

实际上与此相同:

if (condition){
    do{
        body
    }while (condition);
}

如果你知道你总是至少循环一次,那if语句是无关紧要的.

同样在汇编级别,这大致是不同循环编译的方式:

do-while循环:

start:
    body
    test
    conditional jump to start

while循环:

    test
    conditional jump to end
start:
    body
    test
    conditional jump to start
end:

请注意,条件已重复.另一种方法是:

    unconditional jump to end
start:
    body
end:
    test
    conditional jump to start

...交换掉重复代码以进行额外的跳转.

无论哪种方式,它仍然比正常do-while循环更糟糕.

也就是说,编译器可以做他们想做的事.如果他们能证明循环总是进入一次,那么它就为你完成了工作.

但是对于问题中的特定示例来说,事情有点奇怪,因为它有一个空循环体.由于没有身体,因此while和之间没有逻辑差异do-while.

FWIW,我在Visual Studio 2012中对此进行了测试:

• 对于空体,它确实为while和生成相同的代码do-while.因此,当编译器不那么好时,这部分很可能是旧时代的遗留物.

• 但是由于非空体,VS2012设法避免重复条件代码,但仍会产生额外的条件跳转.

所以具有讽刺意味的是,尽管问题中的示例突出了为什么do-while循环在一般情况下可能更快,但示例本身似乎并没有给现代编译器带来任何好处.

考虑到评论的年龄,我们只能猜测它为何重要.当时的编译器很可能无法识别出身体是空的.(或者如果他们这样做,他们就不会使用这些信息.)

Answer 2

有没有证据表明大多数(或任何)编译器会生成更好(例如更高效)的代码？

除非您在特定平台上查看具有某些特定优化设置的实际特定编译器的实际生成程序集,否则不多.

这可能值得担心几十年前(编写ZLib时),但现在肯定不会,除非您通过实际分析发现这消除了代码中的瓶颈.

Answer 3

简而言之(tl; dr):

我正在解释OPs代码中的注释略有不同,我认为他们声称观察到的"更好的代码"是由于将实际工作转移到循环"条件"中.然而,我完全同意它是非常特定于编译器的,并且它们所做的比较虽然能够产生稍微不同的代码,但是大部分都是毫无意义的并且可能已经过时,如下所示.

细节:

很难说他的评论是关于这个do {} while产生更好的代码的原始作者的意思,但我想在另一个方向推测而不是在这里提出的 - 我们认为do {} while和while {}循环之间的差异非常小(少一个分支作为神秘说道,但是在这段代码中有一些甚至"更有趣"的东西,它将所有的工作都置于这种疯狂的状态,并将内部部分保持为空(do {}).

我在gcc 4.8.1(-O3)上尝试了以下代码,它给出了一个有趣的区别 -

#include "stdio.h" 
int main (){
    char buf[10];
    char *str = "hello";
    char *src = str, *dst = buf;

    char res;
    do {                            // loop 1
        res = (*dst++ = *src++);
    } while (res);
    printf ("%s\n", buf);

    src = str;
    dst = buf;
    do {                            // loop 2
    } while (*dst++ = *src++);
    printf ("%s\n", buf);

    return 0; 
}

编译后 -

00000000004003f0 <main>:
  ... 
; loop 1  
  400400:       48 89 ce                mov    %rcx,%rsi
  400403:       48 83 c0 01             add    $0x1,%rax
  400407:       0f b6 50 ff             movzbl 0xffffffffffffffff(%rax),%edx
  40040b:       48 8d 4e 01             lea    0x1(%rsi),%rcx
  40040f:       84 d2                   test   %dl,%dl
  400411:       88 16                   mov    %dl,(%rsi)
  400413:       75 eb                   jne    400400 <main+0x10>
  ...
;loop 2
  400430:       48 83 c0 01             add    $0x1,%rax
  400434:       0f b6 48 ff             movzbl 0xffffffffffffffff(%rax),%ecx
  400438:       48 83 c2 01             add    $0x1,%rdx
  40043c:       84 c9                   test   %cl,%cl
  40043e:       88 4a ff                mov    %cl,0xffffffffffffffff(%rdx)
  400441:       75 ed                   jne    400430 <main+0x40>
  ...

因此,第一个循环执行7个指令,而第二个循环执行6个指令,即使它们应该执行相同的工作.现在,我无法确定这背后是否有一些编译器智能,可能不是,这只是巧合,但我还没有检查它是如何与该项目可能使用的其他编译器选项交互的.

另一方面,在clang 3.3(-O3)上,两个循环都生成这5个指令代码:

  400520:       8a 88 a0 06 40 00       mov    0x4006a0(%rax),%cl
  400526:       88 4c 04 10             mov    %cl,0x10(%rsp,%rax,1)
  40052a:       48 ff c0                inc    %rax
  40052d:       48 83 f8 05             cmp    $0x5,%rax
  400531:       75 ed                   jne    400520 <main+0x20>

这只是表明编译器是完全不同的,并且推进速度远远超过一些程序员几年前所预期的速度.这也意味着这个评论毫无意义,可能就是因为没有人检查过它是否仍然有意义.

底线 - 如果你想优化到最好的代码(你知道它应该是什么样子),直接在汇编中做,并从等式中剪切"中间人"(编译器),但考虑到更新编译器和更新的HW可能会使此优化过时.在大多数情况下,让编译器为您完成这一级别的工作要好得多,并专注于优化大型工作.

应该做的另一点 - 指令计数(假设这是原始OP代码所用的),对于代码效率来说绝不是一个好的衡量标准.并非所有指令都是相同的,其中一些(例如简单的reg-to-reg移动)非常便宜,因为它们被CPU优化.其他优化实际上可能会损害CPU内部优化,因此最终只有适当的基准测试计数.

Answer 4

甲while环通常编译为一个do-while循环具有初始分支的条件,即

    bra $1    ; unconditional branch to the condition
$2:
    ; loop body
$1:
    tst <condition> ; the condition
    brt $2    ; branch if condition true

而do-while没有初始分支的循环编译是相同的.你可以从中看出,初始分支的成本固有地降低了效率,但是只支付了一次.[比较天真的实现方式,while()每次迭代都需要条件分支和无条件分支.]

话虽如此,它们并不是真正可比的替代方案.将while,循环转换为while循环是很痛苦的,反之亦然.他们做不同的事情.在这种情况下的几个方法调用将完全主宰一切的编译器做do-while对抗while

Answer 5

这句话不是关于控制语句的选择(do vs. while),而是关于循环展开!

正如您所看到的,这是一个字符串比较函数(字符串元素可能长度为2个字节),可以使用单个比较而不是快捷方式和表达式中的四个来编写.

后一种实现肯定更快,因为它在每四个元素比较之后对字符串结束条件进行单次检查,而标准编码将涉及每次比较一次检查.换句话说,每4个元素进行5次测试,每4个元素进行8次测试.

无论如何,它只有在字符串长度是4的倍数或者有一个sentinel元素时才会起作用(这样两个字符串保证在strend边界之外不同).风险很大!