如何编译Duff的设备代码?

我理解为什么Duff的设备比普通的循环代码更快,可以展开但没有优化。 但我无法理解代码是如何编译的。
我想这是关于切换语法的一个技巧。 但不是了。

如何在切换句中存在句子? 很奇怪。
有没有人可以解释这个?

编辑:另一个问题。 为什么duff使用8? 它可能是16,65536或其他什么。 因为代码大小? 还有其他原因吗? 例如,缓存或流水线操作的好处。

Duff的Device编译原因的简单解释是switch语句的语法对switch语句块可能需要采用的forms并不特别具体。 有一些限制,受控语句中允许的一些限制是在switch外部不允许的( casedefault标签)。 但除此之外,受控语句只是任何其他语句,可能存在switch标记的目标。

这是C99的语法:

 switch ( expression ) statement 

除了语法之外,标准还强加了一些限制:

  • 控制表达式必须具有整数类型
  • 关于VLA在switch语句中可能出现的位置存在限制
  • case标签表达式必须是整型常量表达式
  • 不能有重复的case标签表达式或default标签

除此之外,应该在受控语句中允许语句块中允许的任何构造(添加casedefault标签都可以)。 请记住, casedefault只是交换机根据控制表达式和case标签表达式跳转到的标签。 正如Potatoswatter所说 , switch只是一个计算goto 。 所以就像goto可以跳到循环的中间一样,所以可以switch

此外,我认为你可能会看到Duff设备的好处的情况今天非常罕见(我认为它们甚至在20世纪80年代也很少见)。 不要忘记Tom Duff自己在他的描述中说了以下内容:

  • “恶心,不是吗?”
  • “在这一发现中,我感到自豪和反感的结合。”

甚至比最初描述时更多,Duff的设备应该被认为是一种好奇而不是使用的工具。

“它的工作原理”很简单。

C和C ++都是编译语言,通常编译为平台机器代码。 机器代码没有块结构的概念 – 所有块结构必须转换为使用(实际上)无条件和条件gotos的某种混合的forms。

C语法规则允许switch语句和循环以不是真正的分层块结构的方式组合,但是纠缠控制流。 只要编译器可以处理这个问题(任何好的编译器都应该),底层机器代码就没有问题。 结果将是“spaghetti”,但生成的机器代码通过优化器总是意大利面 – 它不是人类可读的,所以它不是问题。 这里的问题是源代码也是spaghetti,即使gotos已被“隐藏”。

注意 – 虽然任何好的编译器都应该应对Duffs设备,正如其他人已经评论过的那样,但这并不意味着它能够很好地应对以正确地优化它 – 只能很好地生成正确的可执行代码。 这是曾经有目的的一些古老奇怪的习语,但现在更有可能混淆你的编译器并破坏它生成有效代码的能力。

编辑

以下是与Duffs设备有关,可能有助于说明基本思路……

 switch (count & 1) { case 0 : goto lbl0; case 1 : goto lbl1; } lbl0: while (count != 0) { handle_one (); count--; lbl1: handle_one (); count--; } 

在循环中包含case子句在概念上与在循环中具有goto-target标签没有什么不同,如上所述。

警告 – 这纯粹是为了说明一个想法,不应该复制到现实代码中。

switch只是一个计算过的goto 。 因此,循环内部有几个标签,循环外部有一个switch语句。 switch决定在循环内goto哪个标签,然后goto那里。

一旦执行在循环内部,它就会继续循环,直到循环放弃控制。

它实际上非常简单……除非它是最直接的选择,否则不应该使用它。

不要相信任何告诉你它的人会做出任何快速的事情。

我甚至会说要停止听他们说的任何话,即使这是你的老师。

至于编译器,他们将事情分解为通用控制流图,而不关心switchifwhile 。 他们都是if ( … ) goto …; else goto …; if ( … ) goto …; else goto …; 到编译器。

虽然Duff的设备因其原始目的而过时,但它仍然可用于特殊用途,例如通常在N个状态中重复循环的状态机,但有时需要返回到调用者,然后在它离开的状态下恢复关闭。 把switch语句放在循环之外, case标签放在循环中(我会把它作为“Duff的设备”的定义)然后很有意义。

话虽如此,不要使用Duff的设备“手动优化”。 将所有有效“goto标签”放在一起的地方将无助于编译器优化。

如果我们从维基百科文章中获取实现链接…

 send(to, from, count) register short *to, *from; register count; { register n=(count+7)/8; switch(count%8){ case 0: do{ *to = *from++; case 7: *to = *from++; case 6: *to = *from++; case 5: *to = *from++; case 4: *to = *from++; case 3: *to = *from++; case 2: *to = *from++; case 1: *to = *from++; }while(--n>0); } } 

…并使用汇编级if / goto替换“高级” do / while循环,编译器确实将其缩减为…

 send(to, from, count) register short *to, *from; register count; { register n=(count+7)/8; switch(count%8){ case 0: do_label: *to = *from++; case 7: *to = *from++; case 6: *to = *from++; case 5: *to = *from++; case 4: *to = *from++; case 3: *to = *from++; case 2: *to = *from++; case 1: *to = *from++; if (--n>0) goto do_label; } } 

…它可能会帮助你认识到 – 在这种使用中,do / while范围没有引入任何局部变量 – 实际上没有什么比跳回到案例0绕过开关并因此需要评估计数%8(%是一个非常昂贵的操作方案)。

希望能帮助它点击,但可能不会……? 🙂

为什么duff使用8? 它可能是16,65536或其他什么。 因为代码大小? 还有其他原因吗? 例如,缓存或流水线操作的好处。

只是一个收益递减的案例。 必须在每8个数据副本之后执行--n > 0检查和跳转不是一个很大的百分比开销,但代码的大小(源代码和缓存中的编译代码)仍然非常紧张。 也许这是90%或95%的工作与间接费用,这显然已经足够好了。 此外,为了说明和与其他人分享这个概念,Tom Duff可能更喜欢它是关于一个典型的80×25终端的代码而不是一个页面或10。