我读过article on Wikipedia on the Duff's device,但我不明白。我真的很感兴趣,但我已经读了几次那里的解释,我仍然不明白达夫的设备是如何工作的。
更详细的解释是什么?
发布于 2009-02-05 02:25:55
其他地方也有一些很好的解释,但让我试一试。(在白板上这要容易得多!)以下是带有一些注释的维基百科示例。
假设你正在复制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++
。
发布于 2009-02-05 01:15:31
explanation in Dr. Dobb's Journal是我在这个主题上找到的最好的。
这是我的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);
}
发布于 2009-02-05 01:19:41
虽然我不能百分之百确定你想要的是什么。
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上看到的)使用串行拷贝。在上面的展开示例中,您看到的是与原始示例中的100个比较相比的10个比较-这相当于一个次要的,但可能是重要的优化。
https://stackoverflow.com/questions/514118
复制相似问题