Duff的设备代码如何编译？

Question

我明白为什么 Duff 的设备 比可以展开但未优化的普通循环代码更快。但我还不明白如何编译代码。
我猜这是关于 switch 语法的一个技巧。但现在不再了。

do while 语句怎么能存在于 switch 语句中呢？很奇怪。
有谁可以解释一下吗？

编辑： 另一个问题。 达夫为什么用8？它可以是 16、65536 或其他。因为代码大小？难道还有别的原因吗？例如，缓存或流水线的好处。

Answer 1

“它是如何工作的”很简单。

C 和 C++ 都是编译语言，通常编译为平台机器代码。机器代码没有块结构的概念 - 所有块结构都必须转换为（实际上）使用无条件和条件 goto 的某种组合的形式。

C 语法规则允许 switch 语句和循环以某种方式组合，这种方式不是真正的分层块结构，而是混乱控制流。只要编译器能够处理这个问题（任何好的编译器都应该这样做），底层机器代码就不会有问题。结果将是“意大利面条”，但通过优化器生成的机器代码始终是意大利面条 - 它并不意味着人类可读，所以这不是问题。这里的问题是源代码也是意大利面条，即使 goto 已被“隐藏”。

注意 - 尽管任何好的编译器都应该能够处理 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 标签没有什么不同，如上所述。

警告 - 这纯粹是为了说明一个想法，不应在现实生活中的代码中复制。

Answer 2

Duff's Device 编译原因的一个简单解释是，switch 语句的语法对于 switch 语句块可能需要采用的形式并不特别具体。有一些限制，以及受控语句中允许的一些事情在 switch 之外是不允许的（case 和 default标签）。但除此之外，受控语句只是任何其他语句，可能有 switch 目标的标签。

以下是 C99 的语法：

switch ( expression ) statement

除了语法之外，该标准还施加了一些约束：

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

除此之外，语句块中允许的任何构造都应该在受控语句中允许（此外，< code>case 和 default 标签都可以）。请记住，case 和 default 只是开关根据控制表达式和 case 标签表达式跳转到的标签。 正如 Potatoswatter 所说，切换 只是一个计算的goto。就像goto可以跳到循环中间一样，switch也可以。

另外，我认为今天您可能会看到 Duff 设备带来的好处的情况非常罕见（我认为即使在 1980 年代，这种情况也很少见）。不要忘记 Tom Duff 本人在他的描述中说过以下内容：

• “恶心，不是吗？”
• “对于这一发现，我既感到自豪又感到厌恶。”

与最初描述时相比，达夫的装置更应该被视为一种好奇心，而不是一种使用工具。

Answer 3

switch 只是一个计算出的goto。因此，循环内有多个标签，循环外有一个 switch 语句。 switch 决定要转到哪个标签，并在循环内goto 那里。

一旦执行进入循环，它就会继续循环，直到循环放弃控制。

它实际上非常简单……除非它是最简单的替代方案，否则不应使用。

不要相信任何人告诉你它可以使任何事情变得更快。

我什至会说完全停止听他们说的任何话，即使是你的老师。

至于编译器，它们将事物分解为通用控制流图，并且不关心 switch 与 if 与 while。它们都是if ( … ) goto …； else goto ...; 到编译器。

Answer 4

虽然 Duff 的设备确实已经过时了，但它对于特殊用途仍然有用，例如状态机通常会反复循环 N 状态，但有时需要返回给调用者，然后再返回给调用者。恢复到上次中断的状态。将 switch 语句放在循环外部，将 case 标签放在循环内部（我将其视为“Duff 设备”的定义）就很有意义。

话虽如此，不要使用达夫的设备来“手动优化”。将有效的“转到标签”放在各处将无助于编译器优化。

Answer 5

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

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);
        }
}

...并将“高级”do / while 循环替换为程序集级别 if / goto 编译器确实将其简化为...

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 范围没有引入任何本地变量 - 实际上，除了跳回到 case 0 绕过开关之外，do-while 没有什么其他的了，因此需要评估 count % 8 （% 在方案中是一个相当昂贵的操作）。

希望这有助于点击，但可能不会......？ :-)

达夫为什么用8？它可以是 16、65536 或其他。因为代码大小？难道还有别的原因吗？例如，缓存或流水线的好处。

只是收益递减的情况。必须执行 --n >每 8 个数据副本后进行 0 检查和跳转并不是很大的开销，但代码的大小（无论是源代码还是缓存中的编译代码）仍然相当紧张。也许这将是 90% 或 95% 的工作与管理费用，这显然已经足够好了。此外，为了说明并与其他人分享这个概念，Tom Duff 可能更喜欢使用典型 80x25 终端的代码，而不是一页或 10 页。