C语言冷知识：Duff's Device(达夫设备) - 哈喽比特

538次阅读 | 发布于2年以前

相信大家主要都是写业务逻辑的if else程序员，面向if、else、for、while、switch编程。但是你见过switch嵌套do..while吗？


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 );
        }  
}

这个就是达夫设备（Duff's Device)。咋一看，这玩意能编译通过？别说，还真能。

这是语言律师在炫技吗？不是，这东西在当时确实也有一些实用价值（不过大家不要学，在公司写代码写这个，估计会被老大打死）。

1983年，在卢卡斯影业（没错，就是星球大战那个卢卡斯）上班的程序员Tom Duff，为了加速一个实时动画程序发明了这一写法。

Tom Duff

应用的是C语言里面case 标签的Fallthrough特性（其实就是没有break继续执行）。

简单讲下背景。最早他是想实现从一个数组复制数据到一个寄存器。

duff 写的第一版（大众版）

第一次是这样写的(略有修改，补了返回值声明）：

void send(to, from, count)
register short *to, *from;
register int count;
{
    do {                          /* count > 0 assumed */
        *to++ = *from++;
    } while (--count > 0);
}

开头一坨，你可能没加过，但是其实C语言课本里应该都有讲过，这种“古早”的函数定义方式：把参数和参数类型分离。其实等价于：


void send(register short* to, register short* from, register int count)
{
    do {                          /* count > 0 assumed */
        *to++ = *from++;
    } while (--count > 0);
}

先忽略register可能更清晰一点（暂时忽略越界、覆盖这种事）：


void send(short* to, short* from, int count)
{
    do {                          /* count > 0 assumed */
        *to++ = *from++;
    } while (--count > 0);
}

一般人应该都是这么写的。但是他的使用场景下，count永远是8的倍数，然后他就写了第二版（我直接去掉了古早的语法）。

duff 写的第二版（特化版）


void send2(short* to, short* from, int count)
{
    int n = count / 8;
    do {
        *to++ = *from++;
        *to++ = *from++;
        *to++ = *from++;
        *to++ = *from++;
        *to++ = *from++;
        *to++ = *from++;
        *to++ = *from++;
        *to++ = *from++;
    } while (--n > 0);
}

你可能觉得这代码太丑了，有啥意义。也无非就是减少了，比较次数。其实在汇编层面讲 do... while(--count > 0) 这个代码（不算里面的逻辑）是6条指令（不同编译器可能不同）。大家可以用godbolt.org/ 测一下。

如果原始count是256，但就这一部分指令减少（256-256/8）*6=（256-32）*6=1344。当然这个并不准确，因为写法2 引入了额外的除法操作（int n = count/8)，对应6条指令：

实际减少的指令约为1344-6*32=1152条。当然这个数字也不一定准，可能我还有遗漏。大家不要较真啦。大概就是确实会减少指令数。

这样就够了吗。达夫又写了第三版！也就是最终的达夫设备。

duff写的第三版（Duff's Device)


void send3(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的倍数了！而第二版存在这个限制。

然而时至今日，达夫设备到底还能否提高性能是存疑的，因为编译器也早已今非昔比。在代码里显式地用这种Trick的方式进行优化，可能反而阻碍了编译器潜在的优化。