Duff's device - yohhoyの日記

プログラミング言語Cにおいて、たまに「メモリ転送処理の最適化実装」もしくは「swtich文の難解な使い方」として紹介されるアルゴリズムの名前。

ループ展開(loop unwinding, loop unrolling)最適化の一種。オリジナルコードでは転送先to＝メモリマップドレジスタを想定しており*1、memcpy関数のようなメモリ転送処理は意図していない。

“メモリ転送処理” に変更された実装例を示す。通常はC標準ライブラリのmemcpyを用いるべき。

// ナイーブな実装
void copy(char *to, char *from, int count)
{
  do {
    *to++ = *from++;
  } while (--count > 0);
}

// "最適化"された実装
void copy(char *to, char *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);
  }
}