6

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

切换语句中存在while语句怎么办？很奇怪。 有谁能解释一下吗？

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

4

5 回答 5

11

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

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 标签没有什么不同。

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

于 2011-04-06T16:19:52.733 回答
6

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

这是来自 C99 的语法：

switch ( expression ) statement

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

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

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

另外，我认为今天您可能会从 Duff 的设备中受益的情况非常罕见（我认为即使在 1980 年代也很少见）。不要忘记汤姆·达夫本人在他的描述中说过以下内容：

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

与最初描述时相比，Duff 的设备应该被视为一种好奇心而不是使用的工具。

于 2011-04-06T19:44:02.520 回答
4

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

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

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

不要相信任何告诉你它使任何事情都快的人。

我什至会说不要再听他们说的任何话，即使是你的老师。

至于编译器，他们将事情分解为通用控制流图，而不关心switchvs. ifvs. while。它们都if ( … ) goto …; else goto …;交给编译器。

于 2011-04-06T16:30:34.520 回答
2

虽然 Duff 的设备在最初的用途上已经过时了，但它对于特殊用途仍然有用，例如状态机通常会在状态中反复循环N，但有时需要返回给调用者，然后在它停止的状态下恢复. 将switch语句放在循环外，将case标签放在循环内（我认为这是“Duff 设备”的定义）就很有意义了。

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

于 2011-04-06T18:30:50.717 回答
2

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

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/循环...whileifgoto

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 范围没有引入任何局部变量的这种用法中 - do-while 实际上没有什么比跳回绕过开关的 case 0 更重要的了，因此需要评估 count % 8 （在事物方案中，% 是一个非常昂贵的操作）。

希望能帮助它点击，但可能不会......？:-)

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

只是一个收益递减的例子。在每 8 个数据副本之后进行--n > 0检查和跳转并不是很大的开销，但是代码的大小（源代码和缓存中的编译代码）仍然非常紧凑。也许是 90% 或 95% 的工作与间接费用，这显然已经足够了。此外，为了说明和与其他人分享这个概念，Tom Duff 可能更喜欢它是一个典型的 80x25 终端的代码价值，而不是一页或 10 页。

于 2011-04-07T02:23:56.627 回答