如何编译Duff的设备代码?
我理解为什么Duff的设备比普通的循环代码更快,可以展开但没有优化。 但我无法理解代码是如何编译的。
我想这是关于切换语法的一个技巧。 但不是了。
如何在切换句中存在句子? 很奇怪。
有没有人可以解释这个?
编辑:另一个问题。 为什么duff使用8? 它可能是16,65536或其他什么。 因为代码大小? 还有其他原因吗? 例如,缓存或流水线操作的好处。
Duff的Device编译原因的简单解释是switch
语句的语法对switch
语句块可能需要采用的forms并不特别具体。 有一些限制,受控语句中允许的一些限制是在switch
外部不允许的( case
和default
标签)。 但除此之外,受控语句只是任何其他语句,可能存在switch
标记的目标。
这是C99的语法:
switch ( expression ) statement
除了语法之外,标准还强加了一些限制:
- 控制表达式必须具有整数类型
- 关于VLA在switch语句中可能出现的位置存在限制
-
case
标签表达式必须是整型常量表达式 - 不能有重复的
case
标签表达式或default
标签
除此之外,应该在受控语句中允许语句块中允许的任何构造(添加case
和default
标签都可以)。 请记住, case
和default
只是交换机根据控制表达式和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
那里。
一旦执行在循环内部,它就会继续循环,直到循环放弃控制。
它实际上非常简单……除非它是最直接的选择,否则不应该使用它。
不要相信任何告诉你它的人会做出任何快速的事情。
我甚至会说要停止听他们说的任何话,即使这是你的老师。
至于编译器,他们将事情分解为通用控制流图,而不关心switch
与if
与while
。 他们都是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。