1

有人告诉我 duff 设备不适用于 PHP，因为 switch 和 case 构造的工作方式不同。我在 php.net 上找到了这个 duff devive，我的问题是这个设备有什么问题？还是我不了解 duff 设备？在我的汇编器中，我可以用一个简单的命令展开一个循环，当它编译时，我得到一个展开的循环。

<?php
$n = $ITERATIONS % 8;
while ($n--) $val++;
$n = (int)($ITERATIONS / 8);
while ($n--) {
   $val++;
   $val++;
   $val++;
   $val++;
   $val++;
   $val++;
   $val++;
   $val++;
}
?>
4

2 回答 2

6

那不是达夫装置。它使用特殊的预循环对齐步骤（这正是 Duff 的设备旨在避免的）。

在真正的 Duff 设备中，有一段展开的代码最初被switch. 这个技巧减少了所需的代码量（仅限于循环）并减少了代码中条件跳转的数量。

您提供的代码只是一个手动展开的循环。

循环展开：

循环展开是一种优化技术，其中一次处理循环的多个迭代。所以而不是：

$number_of_iterations = 128;
for ($n = 0; $n !== $number_of_iterations; ++$n) {
    do_something();
}

你用：

$number_of_iterations = 128;
for ($n = 0; $n !== (int)($number_of_iterations / 4); ++$n) {
    //Repeat do_something() four times.
    //Four is the "unrolling factor".
    do_something();
    do_something();
    do_something();
    do_something();
}

这样做的好处是速度。条件分支通常是相对昂贵的操作。与展开的循环相比，第一个循环将通过条件分支的频率高出四倍。

不幸的是，这种方法有些问题。假设$number_of_iterations不能被四整除——将劳动分工成更大的块将不再有效。对此的传统解决方案是有另一个循环，它以较小的块执行工作，直到剩余的工作量可以由展开的循环执行：

$number_of_iterations = 130;
//Reduce the required number of iterations
//down to a value that is divisible by 4
while ($number_of_iterations % 4 !== 0) {
    do_something();
    --$number_of_iterations
}
//Now perform the rest of the iterations in an optimised (unrolled) loop.
for ($n = 0; $n !== (int)($number_of_iterations / 4); ++$n) {
    do_something();
    do_something();
    do_something();
    do_something();
}

这更好，但初始循环仍然不必要地低效。它再次在每次迭代中分支 - 这是一个昂贵的提议。在php中，这是你能得到的最好的（??）。

现在进入达夫的设备。

达夫装置：

不是在进入有效展开区域之前执行紧密循环，另一种选择是直接进入展开区域，但最初跳转到循环的一部分。这被称为达夫装置。

我现在将语言切换为C，但代码的结构将保持非常相似：

//Note that number_of_iterations
//must be greater than 0 for the following code to work
int number_of_iterations = 130;
//Integer division truncates fractional parts
//counter will have the value which corresponds to the
//number of times that the body of the `do-while`
//will be entered.
int counter = (number_of_iterations + 3) / 4;
switch (number_of_iterations % 4) {
    case 0: do { do_something();
    case 3:      do_something();
    case 2:      do_something();
    case 1:      do_something();
            while (--counter > 0)
}

from 前面的所有条件分支while ($number_of_iterations % 4 !== 0)都已被单个计算跳转（来自 switch）替换。

整个分析基于有缺陷的概念，即减少代码区域中的条件分支的数量总是会显着提高性能，并且编译器将无法在适当的情况下自行执行这些类型的微优化。在现代代码中应该避免手动循环展开和 Duff 的设备。

于 2011-11-12T14:18:50.030 回答
2

您的代码实际上不是 Duff 的设备。一个适当的 DD 会有一个 while 或 do/while交错在 switch 语句中。

DD 的重点是删除这段代码：

$n = $ITERATIONS % 8;
while ($n--) $val++;

Duff Device 的第一步像 GOTO 一样处理到代码中：

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

Saycount % 8结果是 5。这意味着switch跳转到案例 5，然后一直下降到 while 结束，此时它开始以 8 为增量执行工作。

于 2011-11-12T14:21:24.703 回答