Duff's Device（ループ展開の妙技）

何のコードか（背景と何が有名か）

Duff's Device（ダフのデバイス）は、C言語で書かれた驚愕のループ展開イディオムです。何が驚愕かというと、switch 文の case ラベルを、do-while ループの本体の途中に割り込ませて書いている点にあります。制御構造どうしが構文上「重なって」いて、初見では文法エラーにしか見えません。しかしこれは完全に正しいCコードで、ループのオーバーヘッド（各反復での回数判定と分岐）を減らす目的で機能します。

有名になった理由は3つあります。第一に、見た目のインパクト。2つの独立した制御構造を絡み合わせるという発想が、多くのプログラマの常識を破壊しました。第二に、それが実用目的で書かれた本物の最適化だったこと。単なるパズルではありません。第三に、C言語という言語の「緩さ」——switch の飛び先とループ本体が構文的に直交しているという仕様の隙間——を象徴する事例として、長く語り継がれてきたことです。

コードと仕組みの解説

横にスクロール

Tom Duff 本人が書いた原型は、配列ではなく1つの固定アドレス（メモリマップドI/Oレジスタ）へ連続で値を書き込むものでした。まずその形を示します。

send(to, from, count)
register short *to, *from;
register count;
{
    register n = (count + 7) / 8;   /* 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);
    }
}

注目すべきは *to = *from++; で、to は増えません。これは to がハードウェアレジスタのアドレスで、そこへ count 個の値を次々に送り込む用途だからです。通常のバッファ間コピーなら *to++ = *from++; となり、これも同じ骨格で機能します。

動作の鍵はCの2つの仕様です。1つは switch が「ラベルへのジャンプ」でしかなく、飛び込んだ後は break に当たるまで下のcaseへ流れ落ちるフォールスルー。もう1つは、C言語では switch の飛び先ラベルを、その内側にあるループなど別の制御構造の途中に置いてよいという直交性です。

具体的に count が 11 の場合を追います。n = (11 + 7) / 8 = 2、count % 8 = 3 なので、実行はまず case 3: へジャンプします。そこから case 3, 2, 1 の3文が実行され（端数3個を処理）、while (--n > 0) に到達。n は 2 から 1 になり真なので、ループ先頭 do の直後へ戻り、今度は case 0 相当の位置から8文すべてを実行します（残り8個）。再び while で n が 0 になり終了。合計 3 + 8 = 11 個、ちょうど処理し切りました。

一般化すると、剰余 count % 8 が最初の（短い）反復で処理される端数になり、以降は毎回きっちり8個ずつ。剰余処理のためだけの独立したループを書かずに済むのが、この技法の眼目です。素朴に書けば「8個ずつのループ」と「端数用のループ」の2本が必要なところを、フォールスルーで1本にまとめています。

逸話と経緯

考案者は Tom Duff。1983年11月、彼が Lucasfilm（ジョージ・ルーカスのスタジオ内でのちに Pixar につながるコンピュータ部門）に在籍していたときの産物です。当時 DEC の VAX 上でリアルタイムアニメーションのコードを書いており、ある実時間処理のループを速くする必要がありました。処理内容は前述のとおり、データをひとつの出力レジスタへ次々に送り出すもので、ループ制御のオーバーヘッドが無視できなかったのです。

Duff はこの発見を Usenet に投稿し、そこから広まりました。名称の「device」は「装置」ではなく「うまい手・工夫」の意で、Duff 自身が皮肉と誇りを込めて名付けたものです。彼は投稿で、この構造を認めるC言語について「これがCへの賛辞なのか非難なのか判断がつかないが、とにかく認めざるを得ない」という趣旨の、両義的なコメントを残しています。技巧の凄みと、それを許してしまう言語の緩さへの当惑が同居した名言として知られます。

なお、この技法にまつわる俗説には注意が必要です。「memcpy を高速化する典型例」としてよく紹介されますが、Duff の原型はメモリ間コピーではなく、固定アドレスへの連続書き込みでした。バッファ間コピーへの一般化は後年の応用であり、Duff 自身の動機とは区別すべきです。また「C標準はこんな書き方を想定していなかった」と言われがちですが、switch の飛び先が内側のブロックのラベルでよいことは仕様上明確に許されており、未定義動作ではありません。あくまで仕様の範囲内の離れ業です。

遺産と教訓

Duff's Device が現役の高速化テクニックだった時代は、もう過ぎています。理由は明快で、現代のコンパイラは最適化としてループ展開を自動で行い、さらに SIMD 命令によるベクトル化まで施すからです。素直に while ループや標準の memcpy を書けば、コンパイラや標準ライブラリが CPU・データ量に応じた最適なコードを生成します。手で展開した Duff's Device は、むしろ分岐予測やキャッシュ、命令パイプラインとの相性で通常の memcpy に負けることさえあるのが実情です。事実、ある有名OSS（XFree86）ではこの技法を撤去したところ性能が向上した、という報告も残っています。手動の巧妙さが、ハードウェアとコンパイラの進歩に追い抜かれた典型例です。

では今なぜ学ぶ価値があるのか。第一に、ループ展開という最適化の原理を、これほど鮮烈に体得できる教材は他にありません。剰余をどう捌くか、オーバーヘッドがどこに潜むかが、コード1つで腑に落ちます。第二に、これは「言語仕様の隙間」を突く発想の記念碑です。switch は本質的にラベルへのジャンプでしかなく、ループ本体とは直交する——この制御構造の分解された理解があって初めて、2つを重ねる発想が生まれます。仕様を額面どおりでなく構造として捉える力は、あらゆる言語で通用します。

最大の教訓は、性能の常識には賞味期限があるということです。1983年に理にかなっていた最適化が、コンパイラとCPUの進化で不要になりました。だからこそ、手で凝ったトリックに走る前にまず素直に書き、プロファイルで測り、必要なときだけ武器を抜く——この順序が普遍の原則です。Duff's Device は、C言語の緩さと switch の本質を映す鏡として、また「言語仕様の隙間には妙技が眠る」という発想の教材として、これからも語り継がれるでしょう。

C言語や制御構造の原理をより深く知るにはプログラミングを、メモリマップドI/Oやハードウェアに近い最適化の文脈はOSを参照してください。