Duff's device是什么

2020-4-14
今天，我在知乎上面看到一个很有意思的回答，在这里附上链接
哪段代码最能代表程序员的暴力美学
其中，一个回答是关于 Duff's device的

什么是Duff's device?

Duff's device 是当时在卢卡斯影业就职的程序员汤姆.达夫发明的一种对循环进行展开优化，提高执行效率的技巧。
循环体在程序的执行过程中是一个开销比较大的操作

for(int i=0; i<N; i++) {
    do_something();
}

这种循环其实并不需要进行什么特别的优化，但是如果说循环体内部的 do_something单次操作很快，那么循环结束后的判断语句i < N对整体的性能就会有很大的影响。
Duff's device的优化方法就是减少循环迭代的次数，既然i < N判断的频繁检查会影响程序的效率，那么就将循环体展开从而限制循环迭代的次数,在代码中，Duff使用了swich中case的穿透特性和do...while代码块结合起来加速了算法的效率，这里面就不上C的代码了，2001年Jeff Greenberg将Duff's device移植到了JavaScript中，我们直接看JS代码：

var iterations = Math.floor(items.length/8),
      startAt = items.length % 8,
      i = 0;
      do {
        switch(startAt) {
          case 0: process(items[i++]);
          case 7: process(items[i++]);
          case 6: process(items[i++]);
          case 5: process(items[i++]);
          case 4: process(items[i++]);
          case 3: process(items[i++]);
          case 2: process(items[i++]);
          case 1: process(items[i++]);
        }
        startAt = 0;
      }while(--iterations);

本段代码和文字来自铁拐李FE的文章javascript性能提升——Duff's Device
Duff's device中每次循环最多可以调用8次process。循环迭代次数为元素总数除以8。因为总数不一定能整除8，所以startAt变量存放余数，指出第一次循环中应当执行多少次process。比方说现在有12个元素，因为switch...case语句的穿透特性,那么第一次循环将直接调用process 4次，第二次循环调用process 8次，用2次循环代替了12次循环。

关于Duff's device 具体的性能测试我没有做过，本着学而不精的思想，我认为只要涉猎广泛，有所了解即可。大家加油