达夫的装置是怎么工作的？

我读过 关于 Duff 设备的维基百科文章，但我不明白。我真的很感兴趣，但是我已经读了好几遍那里的解释，我还是不明白 Duff 的设备是如何工作的。

更详细的解释是什么？

38427 次浏览
小开

Dobb 医生的日记里的解释是我在这个话题上发现的最好的。

这就是我的 AHA 时刻:

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

Duff 设备的目的是减少在严格的 memcpy 实现中进行的比较次数。

假设您想要将“ count”字节从 b复制到 a，直接的方法是执行以下操作:

  do {
*a = *b++;
} while (--count > 0);

你需要比较计数多少次才能知道它是否高于0? ‘ count’次数。

现在，Duff 设备使用了一个令人讨厌的开关盒意外的副作用，它可以让你减少计数/8所需的比较次数。

现在假设您想使用 Duffs 设备复制20个字节，那么需要多少比较？只有3个字节，因为您一次复制8个字节，除了第一个 最后，您只复制4个字节。

更新: 您不必进行8个比较/case-in-switch 语句，但是在函数大小和速度之间进行权衡是合理的。

小开

虽然我不是百分百确定你想要什么，但是..。

Duff 的设备地址是一个循环展开的问题(你肯定在你发布的 Wiki 链接中看到过)。这基本上等同于优化运行时效率，超过内存占用。Duff 的设备处理的是串行复制，而不仅仅是任何老问题，但它是一个经典的例子，说明了如何通过减少循环比较的次数来进行优化。

作为一个可选的例子，这可能更容易理解，假设您有一个希望循环遍历的项数组，并且每次向它们添加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 语言实现这个想法，但是(正如你在 Wiki 上看到的)使用串行副本。你在上面看到的，通过展开的例子，是10个比较，而原始的100个-这相当于一个小的，但可能是重要的，优化。

小开

达夫的设备有两个关键点。首先，我想这是最容易理解的部分，循环被打开了。通过避免检查循环是否完成和跳回循环顶部所涉及的一些开销，这样可以以更大的代码大小换取更快的速度。当 CPU 执行直线代码而不是跳转时，它可以运行得更快。

第二个方面是 switch 语句。它允许代码在第一次通过时跳入循环的 中间。令大多数人惊讶的是，这样的事情是被允许的。这是允许的。执行从计算的 case 标签开始，然后对每个连续的赋值语句执行 失败了，就像任何其他 switch 语句一样。在最后一个 case 标签之后，执行到达循环的底部，然后跳回到顶部。循环的顶部是开关语句 在里面，因此不再重新计算开关。

原始循环被展开8次，因此迭代次数除以8。如果要复制的字节数不是8的倍数，那么就会有一些字节剩余。大多数一次复制字节块的算法将在末尾处理剩余的字节，但是 Duff 的设备在开始处理它们。该函数计算 switch 语句的 count % 8，以确定余数是什么，跳转到 case 标签，并复制这些字节。然后循环继续复制8个字节的组。

小开
最佳答案

其他地方有一些很好的解释，但让我试一试。(这在白板上就容易多了!)下面是维基百科的例子和一些注释。

假设您要复制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 设备(如上所示)复制到位于 to地址的 I/O 设备。因此，没有必要增加指针 *to。在两个内存缓冲区之间复制时，需要使用 *to++。

小开

当我第一次读它的时候，我把它自动格式化成了这个

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

我完全不知道发生了什么。

也许不是在问这个问题的时候，但是现在 维基百科有很好的解释

根据 C 中的两个属性，该设备是有效的、合法的 C:

  • 在语言的定义中放宽了 switch 语句的规范。在设备发明的时候，这是第一版的 C 语言编程语言，它只要求开关的控制语句是一个语法上有效的(复合)语句，其中大小写标签可以出现在任何子语句的前面。在没有 break 语句的情况下，控制流将从一个 case 标签控制的语句落到下一个 case 标签控制的语句，这意味着代码指定了从顺序源地址到内存映射输出端口的一连串计数副本。
  • 在 C 语言中合法地跳入循环中间的能力。
小开

达夫斯装置是一种特殊的循环展开装置。循环展开是一种优化技术，适用于在循环中执行 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! 如果这不是真的，那么你必须处理剩余的部分——这是一种痛苦。

达夫斯设备与这个标准循环展开有什么不同？
Duffs 设备只是处理 N% n 时剩余循环周期的一种聪明的方法！= 0.整个 do/while 在每个标准循环展开时执行 N/n 次(因为应用了大小写0)。在 最后中，首先运行循环，然后我们运行循环代码的“余数”次数——剩余的次数通过循环“正常”运行。

小开

下面是一个不详细的解释，我认为这是达夫设备的关键:

问题是，C 基本上是汇编语言的一个很好的外观(具体来说，是 PDP-7汇编; 如果你研究过这个，你会发现它们的相似之处是多么惊人)。而且，在汇编语言中，实际上并没有循环——只有标签和条件分支指令。所以循环只是整个指令序列的一部分，它有一个标签和一个分支:

        instruction
label1: instruction
instruction
instruction
instruction
jump to label1 if some_condition

开关指令在某种程度上向前分支/跳跃:

        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 语言中的组合就不再那么奇怪了。

小开

在实验中，我发现了另一个不用交错 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仍然实现了一个循环，但是这个变体可能更具可读性。

小开

这是我在另一个关于 Duff 设备的问题上发布的答案，在问题作为副本结束之前得到了一些赞成票。我认为它提供了一些有价值的上下文，告诉我们为什么应该避免这种结构。

”这里是 达夫的装置。这是一种展开循环的方法，当循环迭代的次数不知道是展开因子的精确倍数时，这种方法可以避免添加二次修复循环。

由于这里的大多数答案似乎总体上是积极的，我将强调它的不利方面。

使用这段代码，编译器将很难对循环体应用任何优化。如果你只是把代码写成一个简单的循环，一个现代的编译器应该能够为你处理展开。通过这种方式，您可以保持可读性和性能，并且有希望将其他优化应用到循环体中。

其他人引用的 Wikipedia 文章甚至说，当这种“模式”从 Xfree86源代码中删除时，性能实际上得到了改善。

这种结果是典型的盲目手工优化您认为可能需要的任何代码。它阻止编译器正确地完成它的工作，使代码更不易读，更容易出错，并且通常会降低它的速度。如果你一开始就用正确的方式做事情，比如编写简单的代码，然后分析瓶颈，然后优化，你甚至不会想到使用这样的东西。至少现代的 CPU 和编译器不会。

理解它没问题，但如果你真的用过它，我会很惊讶。”

小开

下面是一个使用 Duff 设备的64位 memcpy 的工作示例:

#include <iostream>
#include <memory>


inline void __memcpy(void* to, const void* from, size_t count)
{
size_t numIter = (count  + 56) / 64;  // gives the number of iterations;  bit shift actually, not division
size_t rest = count & 63; // % 64
size_t rest7 = rest&7;
rest -= rest7;


// Duff's device with zero case handled:
switch (rest)
{
case 0:  if (count < 8)
break;
do { *(((unsigned long long*&)to)++) = *(((unsigned long long*&)from)++);
case 56:      *(((unsigned long long*&)to)++) = *(((unsigned long long*&)from)++);
case 48:      *(((unsigned long long*&)to)++) = *(((unsigned long long*&)from)++);
case 40:      *(((unsigned long long*&)to)++) = *(((unsigned long long*&)from)++);
case 32:      *(((unsigned long long*&)to)++) = *(((unsigned long long*&)from)++);
case 24:      *(((unsigned long long*&)to)++) = *(((unsigned long long*&)from)++);
case 16:      *(((unsigned long long*&)to)++) = *(((unsigned long long*&)from)++);
case 8:      *(((unsigned long long*&)to)++) = *(((unsigned long long*&)from)++);
} while (--numIter > 0);
}


switch (rest7)
{
case 7: *(((unsigned char*)to)+6) = *(((unsigned char*)from)+6);
case 6: *(((unsigned short*)to)+2) = *(((unsigned short*)from)+2); goto case4;
case 5: *(((unsigned char*)to)+4) = *(((unsigned char*)from)+4);
case 4: case4: *((unsigned long*)to) = *((unsigned long*)from); break;
case 3: *(((unsigned char*)to)+2) = *(((unsigned char*)from)+2);
case 2: *((unsigned short*)to) = *((unsigned short*)from); break;
case 1: *((unsigned char*)to) = *((unsigned char*)from);
}
}


void main()
{
static const size_t NUM = 1024;


std::unique_ptr<char[]> str1(new char[NUM+1]);
std::unique_ptr<char[]> str2(new char[NUM+1]);


for (size_t i = 0 ; i < NUM ; ++ i)
{
size_t idx = (i % 62);
if (idx < 26)
str1[i] = 'a' + idx;
else
if (idx < 52)
str1[i] = 'A' + idx - 26;
else
str1[i] = '0' + idx - 52;
}


for (size_t i = 0 ; i < NUM ; ++ i)
{
memset(str2.get(), ' ', NUM);
__memcpy(str2.get(), str1.get(), i);
if (memcmp(str1.get(), str2.get(), i) || str2[i] != ' ')
{
std::cout << "Test failed for i=" << i;
}


}


return;
}

它处理长度为零的情况(在原始的 Duff’s Device 中，假设 num > 0)。 函数 main ()包含 _ _ memcpy 的简单测试用例。


提交答案