# 探討 Duff's device 和 loop unrolling
###### tags: `Duff's device`

:::info
[Duff's device - Wiki](https://en.wikipedia.org/wiki/Duff%27s_device)
:::

## 破題

Duff's device 可以改善 loop 循環效率的 coding 技巧，基本概念就是：**減少 loop 循環==測試的執行次數==**
> Loop unrolling attempts to reduce the overhead of conditional branching needed to check whether a loop is done

也就是說，如果一個 loop 循環內的動作執行若足夠快（e.g. assign value），那麼測試 conditional branch 將佔用很大部分時間。應該進行 [loop unrolling](https://en.wikipedia.org/wiki/Loop_unrolling)，如此原 loop 內執行操作一次完成多個且減少測試 conditional branch。

for (int x = 0; x < 10000; x++) { // loop 得經過 10000 次的 x < 10000 測試
v = x; // 若此操作執行夠快
}

另外透過 C 語言 switch 特性將要進行的連續循環操作進行預判（根據 case 語句的位置）接著依次執行，而不必每次都進行測試 conditional branch。

根據 Wiki 的範例程式碼：

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

## Reference
- [A Reusable Duff Device](https://www.drdobbs.com/a-reusable-duff-device/184406208)