1

スイッチとケースの構成が異なるため、duffデバイスはPHPでは機能しないと言われています。私はこのダフがphp.netで逸脱しているのを見つけました、私の質問はこのデバイスの何が問題なのですか？それとも私はダフデバイスを理解していませんでしたか？私のアセンブラーでは、簡単なコマンドでループを展開でき、コンパイルすると展開されたループが表示されます。

<?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's Deviceが回避するように設計されているものです）。

真のDuff'sDeviceには、ロールされていないコードの1つのセクションがあり、最初は。によって部分的にスキップされ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();
}

これの利点はスピードです。条件付き分岐は通常、比較的コストのかかる操作です。展開されたループと比較して、最初のループは条件分岐を4倍頻繁に通過します。

残念ながら、このアプローチには多少問題があります。4で割り切れ$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、これはあなたが得ることができるのと同じくらい良いです（??）。

次に、Duff'sDeviceと入力します。

ダフスデバイス：

効率的な展開ゾーンに入る前にタイトなループを実行する代わりに、別の方法は、展開ゾーンに直接移動することですが、最初はループの途中にジャンプします。これはDuff'sDeviceと呼ばれます。

言語をに切り替え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)（スイッチからの）単一の計算されたジャンプに置き換えられました。

この分析全体は、コードの領域内の条件分岐の数を減らすと常にパフォーマンスが大幅に向上し、コンパイラーが適切な場合にこの種のマイクロ最適化を単独で実行できないという欠陥のある概念に基づいています。最新のコードでは、手動ループ展開とDuff'sDeviceの両方を回避する必要があります。

于 2011-11-12T14:18:50.030 に答える
2

あなたのコードは実際にはDuff'sDeviceではありません。適切なDDには、switchステートメントでインターレースされたwhileまたはdo/whileがあります。

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にジャンプし、しばらくの間、その時点で8ずつ増加して作業を開始することを意味します。

于 2011-11-12T14:21:24.703 に答える