神奇的Duff's device

C语言编程领域，达夫设备（Duff's device）是一种将循环展开执行，从而提高执行效率的一种技术方法。

汤姆·达夫于1983年11月发明了这种方法，可能是迄今为止利用C语言switch语句特性所作的最巧妙的实现。

通过一个简单的例子，来理解一下什么是Duff's device.

比如，一个循环复制的函数实现(只是例子，不考虑memcpy)：

void send( int * to, int * from, int count) {
    for (int i = 0; i < count; i++) {
        *to++ = *from++;
    }
}

如果count 是10000，那么就需要循环10000次。这么多次数的循环，对CPU利用率并不高。

用Duff's device 方法改写后的代码，展示如下：

void send( int * to, int * 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);
    }  
}

上面的代码中，使用了C语言的一个隐晦的能力，switch case + do while 组合，这个就是达夫设备（Duff's device)。

如果count为10000，那么之前的代码需要循环10000次，而用Duff' device改写后，只需要 1250次循环即可。

实现机理解析：
C语言对switch语句的规范是比较松的，在switch控制语句内，条件标号（case）可以出现在任意子语句之前，充作其前缀。
此外若未加入break语句，则switch语句根据条件判定，跳转到对应的标号，并在开始执行后，控制流会一直执行到switch嵌套语句的末尾。
另一方面，C语言本身也对跳转到循环内部提供了支持，因而此处的switch/case语句便可跳转到循环内部。

C语言的这个能力，是不是非常神奇？

我的微信号是 实力程序员，欢迎大家转发至朋友圈，分享给更多的朋友。