Duff's device

出典: フリー百科事典『ウィキペディア（Wikipedia）』

Duff's Device（ダフズデバイス）とは、連続的コピーの最適化実装の１つで、アセンブリ言語ではループ展開として一般的に用いられている手法のC言語版。1983年11月、ルーカスフィルムで働いていた Tom Duff が発見した。C言語の case ラベルの fall-through 特性を見事に生かした手法と言える。Duff は単に C言語での独得な手法を見つけたのであり、ループ展開のコンセプトを発見したのではない。

目次

[編集] 本来のバージョン

連続コピーを普通にコーディングすると以下のようになる。

 do {                          /* count > 0 と仮定 */
   *to = *from++;              /* to はインクリメントされていない */
 } while (--count > 0);

Duff の本来の意図はメモリマップされた周辺機器の出力レジスタへのコピーだったため、to がインクリメントされていない。

これを最適化するにあたり、Duff は switch 文と do ループを組み合わせた構造によってループ展開ができると気づいた。

 switch (count % 8)  /* count > 0 とする */
 {
   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 ((count -= 8) > 0);
 }

このアルゴリズム自体はアセンブリ言語でコピーの際に比較と分岐を最小限にする手法として以前から使われていたが、Duff's Device はこれを C言語で実現した。このコーディングは完全に有効で正当なCのコーディングであり、アセンブリ言語での実装と同じように多くのコンパイラで正しくコンパイルされる。C言語の case ラベルでの fall-through 特性は長年に渡って議論となってきた。Duff は「このコードはその議論に何らかの影響を与えるだろう。しかし、それがどちらの立場になるのかはわからない」と述べている。

単純なループよりこのコードが高速である主要因はループ展開によるものである。ループ展開によりループの終了条件の比較回数が減少する。switch/case 文はコピーすべき文字数の残りが展開されたコピー回数と必ずしも一致しないときの調整のために存在する（この例では、8バイトぶんのコピーが展開されている。したがって switch/case 文 は残りバイト数が 1 から 7 の時に自動的に調整する）。また分岐回数が減っていることもパイプライン処理を行うプロセッサにおいては、パイプラインストールを起こす機会を少なくし高速化に貢献する。

このような剰余の自動処理は全てのシステムやコンパイラで最良な手段となるわけではない。場合によってはループを2つに分けた方が高速である（1つのループは展開されていて大部分のコピーを行い、2つめのループで残りのコピーを行う）。コンパイラがこのコードを正しく最適化するかどうかも問題であるが、一部のマイクロプロセッサではパイプラインや分岐予測がうまく働かないという指摘もある。したがって、このコードを使う前にいくつかベンチマークを行って、対象アーキテクチャの対象コンパイラの対象最適化レベルで最も性能の良いコードを選ぶ方がよいだろう。

[編集] ストロヴストルップのバージョン

本来のコードはレジスタへのコピーであった。メモリからメモリへのコピーをするには to ポインタを以下のようにインクリメントしなければならない。

 *to++ = *from++;

この修正版のコードはビャーネ・ストロヴストルップの著書 The C++ Programming Language で「このコードは何をしている？」という練習問題として登場している。これは初心者がメモリマップされた出力レジスタを知らない可能性があると判断したためだろう。しかし、このバージョンのコードはそれほど有用ではない。というのも標準Cライブラリには十分に最適化されたメモリコピー関数が用意されているからである。

この記述は GNU Free Documentation License のもとに公開されているコンピュータ用語辞典『 Free On-line Dictionary of Computing (FOLDOC) 』に基づいています。

[編集] 関連書籍

[編集] 外部リンク

"http://ja.wikipedia.org/wiki/Duff%27s_device" より作成