ダフの装置

Cプログラミング言語におけるダフの手法は、 C の 2 つの構文構造 ( do - whileループとswitch ステートメント)をインターリーブすることで、ループ展開を手動で実装する方法です。この手法は、1983 年 11 月にトム ダフがルーカスフィルムで働いていたときに、リアルタイム アニメーション プログラムを高速化するために使用して発見されました。

ループアンローリングは、ループが完了したかどうかを確認するために必要な条件分岐のオーバーヘッドを削減するために、反復ごとにループ本体のバッチを実行します。反復回数がアンロールされたループの増分で割り切れない場合に対処するために、アセンブリ言語プログラマーの間でよく使われる手法は、アンロールされたループ本体の途中に直接ジャンプして、残りの部分を処理することです。^[1] Duff は、C のcase ラベルのフォールスルー機能を使用してアンロールされた本体にジャンプすることで、この手法を C で実装しました。^[2]

ダフの問題は、16ビットの符号なし整数（ほとんどのC実装では「short」）を配列からメモリマップ出力レジスタ（Cではポインタで示される）にコピーすることだった。彼の元のCコードは次のようだった：^{[3] [4]}

send ( to , from , count )レジスタshort * to 、* from ;レジスタcount ; { do { /* count > 0 と想定 */ * to = * from ++ ; } while ( -- count > 0 ); }  
   
 

                               
          
        

このコードでは、初期カウント > 0であると想定しています。出力場所はメモリマップされたレジスタであるため、メモリ間のコピーに必要な ポインタは増加しません。

count が常に 8 で割り切れる 場合、このループを 8 回展開すると次のようになります。

send ( to 、from 、count )レジスタshort * to 、* from ;レジスタcount ; {レジスタn = count / 8 ; do { * to = * from ++ ; * to = * from ++ ; * to = * from ++ ; * to = * from ++ ; * to = * from ++ ; * to = * from ++ ; * to = * from ++ ; * to = * from ++ ; * to = * from ++ ; * to = * from ++ ; } while ( -- n > 0 ); }  
   
 

         
     
          
          
          
          
          
          
          
          
        

ダフは、 countが8で割り切れない場合を処理するために、ループ本体にジャンプするというアセンブリプログラマのテクニックを、switch文とループの構造を織り交ぜ、ループ本体のcount/8の余りに対応するポイントにswitchのcaseラベルを配置することで実装できることに気付きました。^[1]

send ( to 、from 、count )レジスタshort * to 、* from ;レジスタ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 ); } }  
   
 

           
        
          
             
             
             
             
             
             
             
                
    

Duff のデバイスは、上記の例のように 8 だけではなく、展開されたループの他の任意のサイズにも同様に適用できます。

アセンブリ言語でコーディングするプログラマーがコピー中のテストと分岐の数を最小限に抑えるために広く使用しているアルゴリズムに基づいているDuff のデバイスは、C で実装すると場違いに見えます。このデバイスは、C の 2 つの属性のおかげで C として有効です。

1. 言語の定義におけるswitchステートメントの仕様が緩和されました。デバイスの発明当時、これはC プログラミング言語の最初の版であり、 switchの本体が構文的に有効な (複合) ステートメントであることのみを要求していました。このステートメント内では、サブステートメントの前にcaseラベルを記述できます。break ステートメントがない場合、制御フローは、 1 つのcaseラベルによって制御されるステートメントから次の case ラベルによって制御されるステートメントへとフォールスルーするという事実と合わせて、これは、コードが連続するソース アドレスからメモリ マップされた出力ポートへのcountコピーの連続を指定することを意味します。
2. C でループの途中にジャンプする機能。

これは、 Jargon File が「C におけるフォールスルーのこれまでで最も劇的な使用法」と呼ぶものにつながります。 ^[5] C の case ステートメントにおけるデフォルトのフォールスルーは、長い間最も物議を醸す機能の 1 つでした。Duff 自身は、「このコードはその議論の中で何らかの議論を形成しますが、賛成か反対かはわかりません」と述べています。^[5]

Duff のデバイスは C では有効ですが、 MISRA ガイドラインなどの一般的な C ガイドラインに反しています。一部のコンパイラ ( CompCertなど) はそのようなガイドラインに制限されているため、特に指示がない限り Duff のデバイスを拒否します。

ループアンローリングの基本的な考え方は、ループテストの数を減らすことでループ内で実行される命令の数を減らし、ループに費やされる時間を減らすことができるというものです。たとえば、ブロックコードに命令が 1 つしかないループの場合、ループテストは通常​​、ループの各反復、つまり命令が実行されるたびに実行されます。代わりに、同じ命令の 8 つのコピーがループ内に配置されていれば、テストは 8 回の反復ごとにのみ実行され、7 回のテストを回避することで時間を節約できます。ただし、これは 8 回の反復の倍数しか処理しないため、残りの反復を処理するには別のものが必要です。^[1]

ダフのデバイスは、最初に残りの反復を実行し、続いて同様の命令を8の倍数だけ必要な回数繰り返すという解決策を提供します。残りの反復回数を決定するために、コードは最初に8を法とする反復の合計回数を計算します。この余りに応じて、プログラム実行は必要な反復回数だけ続くステートメントにジャンプします。これが完了すると、すべては簡単です。コードは8つの命令のグループの反復を実行して続行します。これは、残りの反復回数が8の倍数であるため可能になりました。^[1]case

Duff の手法では、ループの内側と外側の両方でcase キーワードを使用することで、コンパクトなループ展開が実現されます。これは珍しいことです。case 文の内容は、従来は case 文の中にネストされたコード ブロックであると考えられており、読者は通常、次の case 文の前に終了すると想定するからです。C 言語の仕様では、これは必要ありません。実際、case 文はswitchコード ブロック内のどこにでも、どの深さでも出現できます。プログラム実行は、次の文がどこにあっても、その文にジャンプするだけです。

多くのコンパイラは、アセンブリ実装の場合と同様に、 スイッチを分岐テーブルに最適化します。

単純で単純なループと比較した場合の速度の主な向上は、ループのアンワインドによって実現されます。ループのアンワインドにより、命令パイプラインをフラッシュして停止させる必要があるため、計算コストが高くなる分岐の実行回数が減ります。 ステートメントswitchは、アンロールされた操作の数で割り切れない残りのデータを処理するために使用されます (この例では、8 つのショート ムーブがアンロールされるため、 はswitch自動的に 1 ～ 7 個の追加のショート ムーブを処理します)。

この残りの部分の自動処理は、すべてのシステムおよびコンパイラにとって最善の解決策ではない可能性があります。場合によっては、2 つのループの方が実際に高速になることがあります (1 つのループは展開されてメイン コピーを実行し、2 つ目のループは残りの部分を処理します)。この問題は、デバイスを正しく最適化するコンパイラの能力に帰着するようです。一部のアーキテクチャでは、パイプライン処理や分岐予測にも影響する可能性があります。 ^[6] Duff のデバイスの多数のインスタンスがバージョン 4.0 のXFree86サーバーから削除されたとき、パフォーマンスが向上し、実行可能ファイルのサイズが著しく減少しました。^[7]したがって、このコードをプログラムの最適化と見なす場合、いくつかのベンチマークを実行して、ターゲット アーキテクチャ、ターゲット最適化レベル、ターゲット コンパイラで実際に最速のコードであることを確認するとともに、最適化されたコードが後で異なるプラットフォームで使用され、そこでは最速のコードではないというリスクを考慮する価値があります。

メモリ間のコピー（これは前述のようにダフのデバイスの本来の用途ではない）のために、標準Cライブラリは関数を提供しているmemcpy。^[8]このコードのメモリ間コピーバージョンよりもパフォーマンスが劣ることはなく、アーキテクチャ固有の最適化により大幅に高速化される可能性がある。^{[9] [10]}

• 計算された GOTO
• コルーチン – Duff のデバイスは、C/C++ でコルーチンを実装するために使用できます (Tatham の外部リンクを参照)
• ジェンセンの装置

• カーニハン、ブライアン、リッチー、デニス(1988 年 3 月)。プログラミング言語 C (第 2 版)。ニュージャージー州エングルウッド クリフス: プレンティス ホール。ISBN 0-13-110362-8。

• LysatorのDuffによる説明と元のメール
• Simon TathamのC言語のコルーチンは同じswitch/caseトリックを利用している
• Adam Dunkels の Protothreads - C の軽量スタックレス スレッドでも、ネストされた switch/case ステートメントが使用されています (最も軽量なスレッド、Protothreads も参照)
• ピジョンのデバイスは関連する技術です。スイッチ/ケースとif/else文が絡み合っています。