Duff的设备如何工作？

Question

我已经在Duff的设备上阅读了维基百科上的文章,但是我没理解.我真的很感兴趣,但我已经在那里阅读了几次解释,但我仍然不知道Duff的设备是如何工作的.

更详细的解释是什么？

Answer 1

其他地方有一些很好的解释,但让我试一试.(这在白板上要容易得多!)这是带有一些符号的维基百科示例.

假设您正在复制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++.

Answer 2

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

Answer 3

Duff的设备有两个关键的东西.首先,我怀疑是更容易理解的部分,循环是展开的.这通过避免在检查循环是否完成以及跳回到循环顶部所涉及的一些开销来交换更大的代码大小以获得更高的速度.当CPU执行直线代码而不是跳转时,CPU可以更快地运行.

第二个方面是switch语句.它允许代码在第一次跳转到循环的中间.对大多数人来说,令人惊讶的部分是允许这样的事情.嗯,这是允许的.执行从计算的案例标签开始,然后它会落到每个连续的赋值语句中,就像任何其他switch语句一样.在最后一个案例标签之后,执行到达循环的底部,此时它会跳回到顶部.循环的顶部位于switch语句内部,因此不再重新评估开关.

原始循环展开八次,因此迭代次数除以八次.如果要复制的字节数不是8的倍数,则剩下一些字节.大多数一次复制字节块的算法将在最后处理剩余字节,但Duff的设备在开始时处理它们.该函数计算count % 8switch语句以计算余数将是什么,跳转到大量字节的case标签,并复制它们.然后循环继续复制八个字节的组.

Answer 4

duffs设备的目的是减少在紧密的memcpy实现中完成的比较次数.

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

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

您需要多少次比较计数才能看出它是否高于0？'数'次.

现在,duff设备使用开关盒的令人讨厌的无意的副作用,这允许您减少计数/ 8所需的比较次数.

现在假设您想使用duffs设备复制20个字节,您需要进行多少次比较？只有3,因为你一次复制8个字节,除了你复制4 的最后一个字节.

更新:您不必进行8次比较/ case-in-switch语句,但在功能大小和速度之间进行权衡取舍是合理的.

Answer 5

当我第一次阅读它时,我将其自动编码

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语句的情况下,控制流将从由一个案例标签控制的语句转变为由下一个案例标签控制的语句,这意味着代码指定了一系列计数副本.顺序源地址到内存映射输出端口.
• 能够合法地跳入C中的循环中间.

Answer 6

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设备与此标准循环展开有何不同？
当N%n!= 0时,Duffs设备只是一种处理余数循环周期的聪明方法.整个do/while按照标准循环展开执行N/n次数(因为情况0适用).在最后一次循环中('N/n + 1'时间),情况开始并且我们跳到N%n情况并且循环代码运行'余数'次.