Duff's Device（ダフスデバイス）とは、C言語での可変長の連続的コピーをループ展開により最適化実装するときに直面する端数の問題を解決するための手法である。
C言語のswitch-case文が持つフォールスルーを利用して、アセンブリ言語で行われる技巧をC言語で実現している。1983年11月、ルーカスフィルムで働いていたトム・ダフが発見した。
背景問題
ループ展開は、ループのための分岐回数を減らす技法である。指定されるループ回数が不明な場合、ループ展開すると回数が合わない場合が出てくるので、ループの途中にジャンプすることで調整する。例えば、8回ぶんのループを展開した場合、指定されたループ回数が8で割り切れないなら、その回数を8で割った剰余のぶんだけ処理を実行する位置にジャンプさせる。
ダフはそのような最適化を検討していてCでの技法を発見した。
本来のバージョン
連続コピーを普通にコーディングすると以下のようになる。
ダフの本来の意図はメモリマップされた周辺機器の出力レジスタへのコピーだったため、to がインクリメントされていない。
これを最適化するにあたり、ダフは、switch 文と do ループを組み合わせた構造によってループ展開ができると気づいた。
Duff's device は、8に限らずどのようなサイズのループ展開にも応用可能である。
なぜ機能するのか
このアルゴリズム自体はアセンブリ言語でコピーの際に比較と分岐を最小限にする手法として以前から使われていたが、Duff's Device はこれを C言語で実現した。このコーディングは次に挙げる2つのCの性質から、完全に有効で正当なCのコーディングである。
C言語におけるswitch文の定義が緩やかである点。Duff's device…
まちカドおるみん御嬢様
All hisso.li content and data are available under the Creative Commons Attribution 3.0 license.