6

Duffのデバイスが、展開できるが最適化されていない通常のループコードよりも高速である理由を理解しました。しかし、コードをどのようにコンパイルできるかはまだわかりません。
私はそれがスイッチ構文についてのトリックだと思います。もうそうじゃない。

センテンスがスイッチセンテンスに存在する間、どうすればよいですか？とても奇妙です。 これを説明できる人はいますか？

編集： 別の質問。なぜダフは8を使用したのですか？16、65536などになります。コードサイズのため？別の理由はありますか？たとえば、キャッシュやパイプラインのメリット。

4

5 に答える 5

11

「仕組み」は簡単です。

CとC++はどちらもコンパイルされた言語であり、通常はプラットフォームのマシンコードにコンパイルされます。マシンコードにはブロック構造の概念がありません。すべてのブロック構造は、無条件と条件付きのgotoを（事実上）組み合わせて使用​​する形式に変換する必要があります。

C構文規則により、switchステートメントとループを、真の階層ブロック構造ではないが、制御フローを絡める方法で組み合わせることができます。コンパイラがこれに対処できる限り（優れたコンパイラならどれでも）、基礎となるマシンコードに問題はありません。結果は「スパゲッティ」になりますが、オプティマイザーを介して生成されたマシンコードは常にスパゲッティです。人間が読める形式ではないため、問題にはなりません。ここでの問題は、gotoが「隠されている」にもかかわらず、ソースコードもスパゲッティであるということです。

注-他の人がすでにコメントしているように、優れたコンパイラはDuffsデバイスに対応する必要がありますが、それは適切に最適化するのに十分に対応できるという意味ではありません-正しい実行可能コードを生成するのに十分なだけです。これは、かつては目的を持っていたこれらの古い奇妙なイディオムの1つですが、コンパイラを混乱させ、効率的なコードを生成する機能を妨害する可能性が高くなっています。

編集

以下はDuffsデバイスに関連しており、基本的な考え方を説明するのに役立つ場合があります...

switch (count & 1)
{
  case 0 : goto lbl0;
  case 1 : goto lbl1;
}

lbl0:

while (count != 0)
{
  handle_one ();
  count--;
lbl1:
  handle_one ();
  count--;
}

ループ内にcase句を含めることは、上記のように、ループ内にgoto-targetラベルを含めることと概念的に同じです。

警告-これは純粋にアイデアを説明するためのものであり、実際のコードにコピーしないでください。

于 2011-04-06T16:19:52.733 に答える
6

Duff's Deviceがコンパイルされる理由の簡単な説明は、ステートメントの構文が、ステートメントブロックがとる必要switchのある形式について特に具体的ではないということです。switchいくつかの制限があり、制御されたステートメントで許可されているもののうち、switch（caseおよびdefaultラベル）の外部では許可されていないものがいくつかあります。ただし、それ以外は、制御されたステートメントは他のステートメントであり、switchターゲットとするラベルがある可能性があります。

C99の構文は次のとおりです。

switch ( expression ) statement

構文以外にも、標準にはいくつかの制約があります。

  • 制御式は整数型である必要があります
  • switchステートメントでVLAが発生する可能性のある場所には制限があります
  • caseラベル式は整数定数式でなければなりません
  • case重複するラベル式またはdefaultラベルは存在できません

それ以外は、ステートメントブロックで許可されている構成は、制御されたステートメントで許可されている必要があります（さらにcase、defaultラベルはOKです）。とは、制御式とラベル式に基づいてスイッチがジャンプする単なるラベルであることcaseを忘れないでください。 Potatoswatterが言うように、は単なる計算です。つまり、ループの途中にジャンプできるのと同じように、できます。defaultcaseswitchgotogotoswitch

また、Duff's Deviceの恩恵を受ける可能性のあるケースは、今日ではかなりまれだと思います（1980年代でもまれだったと思います）。トム・ダフ自身が彼の説明で次のように言ったことを忘れないでください：

  • 「うんざりだよね？」
  • 「この発見には、誇りと嫌悪感の組み合わせを感じます。」

Duff's Deviceは、最初に説明されたときよりも、使用するツールというよりも好奇心を持っていると見なす必要があります。

于 2011-04-06T19:44:02.520 に答える
4

switchは計算されただけgotoです。したがって、ループ内にはいくつかのラベルがあり、ループswitch外にはステートメントがあります。は、ループ内のどのswitchラベルに移動するかを決定します。goto

実行がループ内に入ると、ループが制御を放棄するまでループを続けます。

それは実際には非常に簡単です…そしてそれが最も簡単な代替手段でない限り使用されるべきではありません。

それが何かを速くするとあなたに言う人を信じてはいけません。

たとえそれがあなたの先生であったとしても、私は彼らが言うことを全く聞くのをやめるとさえ言うでしょう。

switchコンパイラーに関しては、それらは物事を一般的な制御フローグラフに分解し、 vs。vs .を気にしませifんwhile。それらはすべてif ( … ) goto …; else goto …;コンパイラーにあります。

于 2011-04-06T16:30:34.520 に答える
2

Duff's Deviceは元の目的では古くなっていることは事実ですが、通常は状態を繰り返し循環するステートマシンなど、特別な目的には役立ちますNが、呼び出し元に戻って、中断した状態で再開する必要がある場合があります。 。switchステートメントをループの外側に置き、ラベルをループの内側に置くことcase（これを「ダフのデバイス」の定義と見なします）は、非常に理にかなっています。

そうは言っても、「手作業で最適化」するためにDuffのデバイスを使用しないでください。効果的に「gotoラベル」であるものをあちこちに配置しても、コンパイラーの最適化には役立ちません。

于 2011-04-06T18:30:50.717 に答える
2

リンクしているウィキペディアの記事から実装を取得する場合...

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

...そして「高レベル」do/whileループをアセンブリレベルif/に置き換えます。gotoこれはコンパイラが実際にそれを...に減らします。

send(to, from, count)
register short *to, *from;
register count;
{
        register n=(count+7)/8;
        switch(count%8){
        case 0:     do_label: *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++;
                if (--n>0) goto do_label;
        }
}

... do / whileスコープがローカル変数を導入しなかったこの使用法では、スイッチをバイパスするケース0に戻って、 count％8を評価する必要があります（％は物事のスキームではかなり高価な操作です）。

それがクリックするのに役立つことを願っていますが、そうではないかもしれません...？:-)

なぜダフは8を使用したのですか？16、65536などになります。コードサイズのため？別の理由はありますか？たとえば、キャッシュやパイプラインのメリット。

収穫逓減の場合。8つのデータコピーごとにチェックとジャンプを実行する--n > 0必要があることは、大きな割合のオーバーヘッドではありませんが、コードのサイズ（ソースとキャッシュ内のコンパイル済みコードの両方）は依然としてかなりタイトです。多分それはオーバーヘッドに対して90または95％の作業になるでしょう、それは明らかに十分に良かったです。さらに、概念を説明して他の人と共有するために、トム・ダフは、1ページまたは10ページではなく、典型的な80x25端末のコードに相当するものにすることを好んだかもしれません。

于 2011-04-07T02:23:56.627 に答える