我已经阅读了维基百科关于Duff's device的文章，但我还是不理解。我非常感兴趣，但我已经多次阅读了那里的解释，仍然不明白Duff's设备如何工作。
更详细的解释会是什么？
11个回答
269
其他地方已经有一些好的解释了，但让我也试试。 （在白板上做起来要容易得多！）下面是维基百科的示例及其注释。
假设你要复制20个字节。 第一次传递程序的流程控制如下：
int count; // Set to 20
{
int n = (count + 7) / 8; // n is now 3. (The "while" is going
// to be run three times.)
switch (count % 8) { // The remainder is 4 (20 modulo 8) so
// jump to the case 4
case 0: // [skipped]
do { // [skipped]
*to = *from++; // [skipped]
case 7: *to = *from++; // [skipped]
case 6: *to = *from++; // [skipped]
case 5: *to = *from++; // [skipped]
case 4: *to = *from++; // Start here. Copy 1 byte (total 1)
case 3: *to = *from++; // Copy 1 byte (total 2)
case 2: *to = *from++; // Copy 1 byte (total 3)
case 1: *to = *from++; // Copy 1 byte (total 4)
} while (--n > 0); // N = 3 Reduce N by 1, then jump up
// to the "do" if it's still
} // greater than 0 (and it is)
}
现在，开始第二遍，我们只运行指定的代码：
int count; //
{
int n = (count + 7) / 8; //
//
switch (count % 8) { //
//
case 0: //
do { // The while jumps to here.
*to = *from++; // Copy 1 byte (total 5)
case 7: *to = *from++; // Copy 1 byte (total 6)
case 6: *to = *from++; // Copy 1 byte (total 7)
case 5: *to = *from++; // Copy 1 byte (total 8)
case 4: *to = *from++; // Copy 1 byte (total 9)
case 3: *to = *from++; // Copy 1 byte (total 10)
case 2: *to = *from++; // Copy 1 byte (total 11)
case 1: *to = *from++; // Copy 1 byte (total 12)
} while (--n > 0); // N = 2 Reduce N by 1, then jump up
// to the "do" if it's still
} // greater than 0 (and it is)
}
现在，开始第三遍：
int count; //
{
int n = (count + 7) / 8; //
//
switch (count % 8) { //
//
case 0: //
do { // The while jumps to here.
*to = *from++; // Copy 1 byte (total 13)
case 7: *to = *from++; // Copy 1 byte (total 14)
case 6: *to = *from++; // Copy 1 byte (total 15)
case 5: *to = *from++; // Copy 1 byte (total 16)
case 4: *to = *from++; // Copy 1 byte (total 17)
case 3: *to = *from++; // Copy 1 byte (total 18)
case 2: *to = *from++; // Copy 1 byte (total 19)
case 1: *to = *from++; // Copy 1 byte (total 20)
} while (--n > 0); // N = 1 Reduce N by 1, then jump up
// to the "do" if it's still
} // greater than 0 (and it's not, so bail)
} // continue here...
现在已经复制了20字节。
注意：上面显示的原始Duff设备将内容复制到一个I/O设备的to地址。因此，不需要递增指针*to。当在两个内存缓冲区之间复制时，需要使用*to++。
- clintp
5
118
《Dr. Dobb's Journal》的解释是我在这个主题上发现的最好的。
这是我的“恍然大悟”时刻：
for (i = 0; i < len; ++i) {
HAL_IO_PORT = *pSource++;
}
变成：
int n = len / 8;
for (i = 0; i < n; ++i) {
HAL_IO_PORT = *pSource++;
HAL_IO_PORT = *pSource++;
HAL_IO_PORT = *pSource++;
HAL_IO_PORT = *pSource++;
HAL_IO_PORT = *pSource++;
HAL_IO_PORT = *pSource++;
HAL_IO_PORT = *pSource++;
HAL_IO_PORT = *pSource++;
}
n = len % 8;
for (i = 0; i < n; ++i) {
HAL_IO_PORT = *pSource++;
}
变成：
int n = (len + 8 - 1) / 8;
switch (len % 8) {
case 0: do { HAL_IO_PORT = *pSource++;
case 7: HAL_IO_PORT = *pSource++;
case 6: HAL_IO_PORT = *pSource++;
case 5: HAL_IO_PORT = *pSource++;
case 4: HAL_IO_PORT = *pSource++;
case 3: HAL_IO_PORT = *pSource++;
case 2: HAL_IO_PORT = *pSource++;
case 1: HAL_IO_PORT = *pSource++;
} while (--n > 0);
}
- Ric Tokyo
6
20这里的关键事实是，由于 C 语言的一个怪异之处，在第一次到达 while 循环后，它会“跳回来并执行所有语句”。因此，即使
len%8 是 4，它也会执行 case 4、case 2、case 2 和 case 1，然后跳回并执行从下一次循环开始的所有 case。这就是需要解释的部分，循环和 switch 语句“交互”的方式。 - ShreevatsaR3《Dr. Dobbs》这篇文章不错，但除了链接外，答案并没有添加任何内容。请看下面的Rob Kennedy的答案，他提供了一个关于先处理剩余转移大小，然后再处理8字节传输块的重要观点。我认为这是理解这段代码的关键。 - Richard Chambers
3我是否遗漏了什么？在第二个代码片段中，
len % 8 字节将不会被复制吗？ - newbie我卡住了，忘记了在case语句列表结尾处不写break语句的话，C（或任何其他语言）将继续执行语句。因此，如果您想知道为什么杜夫设备可以正常工作，这是其中至关重要的一部分。 - goonerify
当我阅读Dr. Dobbs的文章时，Duff's device不过是一种避免后处理清理循环的方法，用于那些大小不是倍数的展开。所以我猜它可以为内存受限的设备节省一些指令。但它似乎不能处理任意的展开大小。你仍然需要编写每个情况。有一个可以说“展开n次”的方法会非常有用。 - Z boson
@新手：确实如此，但我现在已经从文章中粘贴了后处理循环。（我怀疑它被错误地省略了，因为两个循环在文章中被散文分隔开。） - SamB
85
Duff的设备有两个关键点。第一个关键点，我认为比较容易理解，就是循环被展开了。这样做可以通过避免检查循环是否完成以及跳回到循环顶部所涉及的一些开销来换取更快的速度，并且能够使CPU在执行直线代码而不是跳转时运行得更快。
第二个关键点是switch语句。它允许代码在第一次通过时跳转到循环的中间部分。对大多数人来说，令人惊讶的是这种事情是允许的。好吧，它是被允许的。执行从计算出的case标签开始，然后像任何其他switch语句一样穿透到每个后续的赋值语句。在最后一个case标签之后，执行到达循环底部，此时它会跳回到顶部。循环顶部位于switch语句内部，因此switch不会再次被重新评估。
原始循环展开了8次，因此迭代次数被除以8。如果要复制的字节数不是8的倍数，则会有一些剩余字节。大多数每次复制块字节的算法都会在结尾处处理剩余字节，但Duff的设备会在开头处理它们。该函数通过计算count % 8来确定剩余部分是多少字节，并跳转到相应数量的字节的case标签并复制它们。然后循环继续复制8个字节的组。
- Rob Kennedy
2
8这份说明更加易懂了。对我来说理解的关键是先复制剩余部分，然后再按8字节的块复制其余部分。这种方法与通常情况下首先复制8字节块再复制剩余部分的做法不同寻常。首先处理剩余部分是理解该算法的关键。 - Richard Chambers
2+1 提到了 switch / while 循环的疯狂嵌套。这在像 Java 这样的语言中是难以想象的... - Parobay
15
Duffs设备的目的是减少在紧密memcpy实现中所做的比较次数。
假设您想要从b复制'count'字节到a，直接的方法是执行以下操作：
do {
*a = *b++;
} while (--count > 0);
- Johan Dahlin
5
3请注意，Duff设备在switch语句中不仅限于8个复制。 - strager
为什么你不能直接使用 count = count-8 而不是 --count，并使用第二个循环来处理余数？ - hhafez
1Hhafez，你可以使用第二个循环来处理余数。但是现在你需要两倍的代码来完成相同的事情，而且没有速度提升。 - Rob Kennedy
Johan，你搞反了。剩下的4个字节是在循环的第一次迭代中复制的，而不是最后一次。 - Rob Kennedy
不确定这是否是副作用、恶意或无意的。我认为这只是
switch 的工作方式。 - Tim Randall10
第一次阅读时，我自动将其格式化为以下内容
void dsend(char* to, char* from, count) {
int 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);
}
}
我当时并不知道发生了什么。
也许在这个问题被提出的时候还没有，但是现在 Wikipedia上有一个非常好的解释
由于C语言中两个特性，该设备是有效且合法的C代码：
- C语言中switch语句的规范定义相对宽松。在该设备发明时，第一版《C程序设计语言》只要求switch控制的语句是一个合法的（复合）语句，在其中case标签可以出现在任何子语句的前面。结合在缺少break语句的情况下，控制流将从由一个case标签控制的语句流到由下一个case标签控制的语句的事实，这意味着该代码指定了从顺序源地址到内存映射输出端口的连续计数副本。
- C语言中循环中间合法跳转的能力。
- Lazer
7
1：Duffs设备是循环展开的一种特殊实现。如果您在循环中需要执行N次操作，则可以通过执行循环N/n次，然后在循环中内联（展开）循环代码n次来以速度换取程序大小的优化技术。例如，将以下内容替换：
for (int i=0; i<N; i++) {
// [The loop code...]
}
使用
for (int i=0; i<N/n; i++) {
// [The loop code...]
// [The loop code...]
// [The loop code...]
...
// [The loop code...] // n times!
}
如果 N % n == 0，那么这个方法非常完美 - 不需要使用 Duff！但是如果不成立的话，你需要处理余数，这会很麻烦。
2: Duffs 设备与标准循环展开有何不同？
Duffs 设备只是一种聪明地处理当 N % n != 0 时余数循环周期的方法。整个 do / while 循环按照标准循环展开执行 N / n 次（因为情况 0 适用）。在第一次运行循环时，该情况应运而生，我们运行循环代码“余数”次数 - 剩余的循环运行“正常”。
- Ricibob
1
我对Duffs设备产生了兴趣，这是在查看以下问题后引起的：https://dev59.com/v2Qm5IYBdhLWcg3w-i9L，所以我想尝试澄清Duff - 不确定它是否比现有答案更好... - Ricibob
4
虽然我不完全确定您需要什么，但是我会尝试解答...
Duff's 设备解决的问题是循环展开（正如您在发布的维基链接中看到的）。这基本上等同于在运行时效率和内存占用之间进行优化。Duff's 设备处理串行复制，而不仅仅是任何旧问题，但它是减少循环中比较次数的优秀示例。
作为另一个例子，可能更容易理解，想象一下您有一个要循环遍历并每次添加 1 的项目数组...通常，您可能会使用 for 循环，并循环大约 100 次。这似乎相当合理，确实如此...但是，可以通过展开循环来进行优化（显然不能太远...否则您可能就不需要使用循环）。
因此，一个常规的 for 循环：
for(int i = 0; i < 100; i++)
{
myArray[i] += 1;
}
变成
for(int i = 0; i < 100; i+10)
{
myArray[i] += 1;
myArray[i+1] += 1;
myArray[i+2] += 1;
myArray[i+3] += 1;
myArray[i+4] += 1;
myArray[i+5] += 1;
myArray[i+6] += 1;
myArray[i+7] += 1;
myArray[i+8] += 1;
myArray[i+9] += 1;
}
Duff的设备实现了这个想法，用C语言编写，但是（正如您在维基上看到的那样）使用串行复制。您在上面看到的展开示例中，有10次比较，而原始版本中有100次比较 - 这相当于一种轻微但可能显着的优化。
- James Burgess
2
10你漏掉了关键部分。这不仅仅是循环展开的问题。switch语句跳入循环的中间。这就是使设备看起来如此混乱的原因。你上面的循环总是执行10的倍数次拷贝，但是Duff的循环可以执行任何次数。 - Rob Kennedy
4没错，但我试图简化对原帖作者的描述。也许我没有解释清楚！ :) - James B
3
这是我认为Duff设备核心的简要解释：
C语言实际上只是汇编语言的一个很好的外观（具体来说，是PDP-7汇编语言；如果你学过那个，你会发现它们之间有多么相似）。在汇编语言中，并没有真正的循环-只有标签和条件分支指令。因此，循环只是带有标签和分支的整个指令序列的一部分：
在汇编语言中，如何组合这两个控制结构很容易想象。一旦你理解了这个思路，它们在C语言中的组合就不再那么奇怪了。
C语言实际上只是汇编语言的一个很好的外观（具体来说，是PDP-7汇编语言；如果你学过那个，你会发现它们之间有多么相似）。在汇编语言中，并没有真正的循环-只有标签和条件分支指令。因此，循环只是带有标签和分支的整个指令序列的一部分：
instruction
label1: instruction
instruction
instruction
instruction
jump to label1 if some_condition
而 switch 指令则是有点向前跳转的分支指令：
evaluate expression into register r
compare r with first case value
branch to first case label if equal
compare r with second case value
branch to second case label if equal
etc....
first_case_label:
instruction
instruction
second_case_label:
instruction
instruction
etc...
在汇编语言中，如何组合这两个控制结构很容易想象。一旦你理解了这个思路，它们在C语言中的组合就不再那么奇怪了。
- einpoklum
1
这是我在另一个关于达夫设备的问题上发布的答案，在该问题被关闭为重复之前获得了一些赞。我认为它在此处提供了一些有价值的背景，解释了为什么应该避免使用这种结构。
"这就是 达夫设备。它是一种展开循环的方法，避免了添加第二个修正循环来处理循环迭代次数不是展开因子的确切倍数的情况。
由于大多数答案似乎对此持积极态度，我将强调其缺点。
对于这段代码，编译器将难以对循环体应用任何优化。如果您只是将代码编写为简单循环，现代编译器应该能够为您处理展开操作。这样，您可以保持可读性和性能，并希望其他优化应用于循环体。
其他人引用的维基百科文章甚至说，当从Xfree86源代码中删除这个“模式”时，性能实际上有所提高。
这种结果是盲目手动优化任何你认为可能需要的代码的典型。它阻止了编译器正常工作，使你的代码不易读懂、更容易出错，并且通常会减慢代码速度。如果一开始就按照正确的方式进行，即编写简单的代码，然后针对性能瓶颈进行分析和优化，你甚至不会想到使用类似的东西。特别是在现代CPU和编译器下，更不需要使用它。理解它是好的，但我会惊讶地发现你实际上是否会使用它。"
- Pete Fordham
0
只是在做实验，发现另一种不需要交错使用switch语句和do-while循环的变体：
int n = (count + 1) / 8;
switch (count % 8)
{
LOOP:
case 0:
if(n-- == 0)
break;
putchar('.');
case 7:
putchar('.');
case 6:
putchar('.');
case 5:
putchar('.');
case 4:
putchar('.');
case 3:
putchar('.');
case 2:
putchar('.');
case 1:
putchar('.');
default:
goto LOOP;
}
从技术上讲，goto 仍然实现了一个循环，但这种变体可能更易读。
- Aconcagua
3
你的终止条件在哪里？ - user2338150
不要交错使用switch和loop，然后毫不犹豫地说“switch() LOOP: case 0:”。这不是交错使用吗？ - Sjoerd
1@Sjoerd 是指循环的语言结构，即交错使用
switch 和 do {} while，这似乎很奇怪且可能难以理解。诚然，措辞不太精确，因为 goto 结构仍然在技术上实现了一个循环，只是旨在找到更可读的变体。 - Aconcagua网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
do。相反，把switch和while视为旧式的计算后GOTO语句或带有偏移量的汇编jmp语句。switch进行一些数学计算，然后跳转到正确的位置。while进行布尔检查，然后盲目地跳转到与do大约相同的位置。 - Clinton Pierce