PHP中的Duff设备不可能吗？

Question

我被告知duff设备不适用于PHP,因为交换机和案例结构的工作方式不同.我在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++;
}
?>

Answer 1

那不是达夫的装置.它使用一个特殊的预循环对齐步骤(这正是Duff的设备旨在避免的).

在一个真正的Duff设备中,有一部分展开的代码,最初被a部分跳过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不能被4整除 - 将劳动分工成更大的块将不再有效.对此的传统解决方案是使用另一个循环以较小的块执行工作,直到可以通过展开的循环执行剩余的工作量:

$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,这是你能得到的(??).

现在进入Duff的设备.

达夫设备:

在进入有效的展开区域之前,不是执行紧密循环,而是直接进入展开区域,但最初跳转到循环的一部分.这叫做Duff的设备.

我现在将语言切换为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)
}

while ($number_of_iterations % 4 !== 0)早期的所有条件分支都被单个计算跳转(来自开关)取代.

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