Skip to content
My Docs

duff deviceという技法

C言語で配列のコピーを高速化するとき、例えば8バイトずつコピーする場合は余った分が問題となるが、switch の落下を利用して端数の問題を解決するTom Duffが考案した技法のことをいう。

void
copy(short *to, short *from, int count)
{
  int 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);
  }
}

上記のコードでは、まず最初だけ count%8 で端数を求めて switch の落下を利用したコピーを行う。2ループ目以降は case 句に関係なく switch の内側にある do … while でループするため、1ループ8バイトのコピーを count/8 (端数切り上げ)の回数だけ実行する。

具体的には、count が13の場合、count%8 が5となるので最初は5バイトのコピーが行われる。その後 do … while の条件を確認すると --n > 0 は真となって do … while により8バイトコピーが行われる。最後に、もう一度 --n > 0 を検査するが、今度は n が0となってループの繰り返しから抜ける。結果として $5+8=13$ バイトのコピーが実現できる。

しかしまあ古い技法ではある。