第40章 达夫装置

达夫装置(Duff’s Device)是一种综合了多种控制语句的循环展开技术,可大幅度地减少代码的分支总数。这种循环展开技术巧妙地利用了swtich语句的滑梯(fallthrough)效应。

本章对Tom Duff的原始程序进行了轻度简化。

现在假设我们要编写一个清除一块连续内存的函数。当然,我们可以使用循环语句、逐个字节的复写数据。但是现代的计算机内存总线都很宽,以字节为单位地清除效率会非常低。若以4字节或8字节为操作单位进行io操作,那么操作效率会高一些。由于本例演示的是64位应用程序,所以我们就以8字节为单位进行操作。不过,我们又当如何应对那些不足8字节的内存空间?毕竟我们的函数也可能清除容量不足8字节的内存空间。

因此,合理的算法应当是:

简单的循环语句即可完成第二步的任务。然而我们更希望把这个循环分解、展开:

#include <stdint.h>
#include <stdio.h>

void bzero(uint8_t* dst, size_t count)
{
         int i;

         if (count&(~7))
                  // work out 8-byte blocks
                  for (i=0; i<count>>3; i++)
                  {
                           *(uint64_t*)dst=0;
                           dst=dst+8;
                  };

         // work out the tail
         switch(count & 7)
         {
         case 7: *dst++ = 0;
         case 6: *dst++ = 0;
         case 5: *dst++ = 0;
         case 4: *dst++ = 0;
         case 3: *dst++ = 0;
         case 2: *dst++ = 0;
         case 1: *dst++ = 0;
         case 0: // do nothing
                  break;
         }
}

我们来看看这个计算是如何完成的。待处理内存区域的大小是64位数据,它分为如下两个部分。

7 6 5 4 3 2 1 0
B B B B B S S S

备注:B代表大小为8字节的内存块;S代表大小不足8字节的尾部内存块。

当我们将输入的内存块的大小除以8,其实就是将该值右移3位。然而不足8字节的内存块总数,即这步除法计算的余数,恰恰是刚刚位移出去的那最后的三位。可见,把目标空间大小/即变量count右移3位,可求得它含有多少个8字节的内存块;令变量counter与数字7进行逻辑与运算可求得它有多少字节的尾部内存块。

当然,我们也得首先看看这块目标空间是否足够进行一次8字节的清除操作。因此首先就要检查变量count是否大于7。为此,我们就要将变量count的最低三位清零,并将结果和零比较。如果该数大于零,则表示这个数量count大于7,我们就可以进行8字节的块操作。当然我们不需要知道它到底比7大多少,只需知道它是否比7大,即count的高位是否为零。

当然之所以能这样做,主要是因为8是2的3次方,而且“某数除以2的n次方”通过位移计算即可实现,其他类型的数字就不能通过位移运算进行判断了。

很难说这些技术是不是值得采用,毕竟这种技巧会明显降低源程序的可读性。然而这已经属于常见技术了。凡是资深的编程人员,不论他愿否使用达夫装置,他都应当能够理解使用了这种技巧的程序。

第一部分其实很简单,用64位的零填充所有8字节内存块。

第二部分的难点在于其循环展开技术。达夫装置利用的是switch()函数的滑梯效应。用人类的语言来讲,这段代码的功能就是将变量count与数字7进行逻辑与运算,得到尾数,然后把它们逐个清零。如果尾数为0,那么直接跳转至函数尾声,不做任何操作。如果尾数是1的话,跳转到switch()语句中清除单字节的那条语句。如果尾数是2的话,跳转到swith()语句中相应的位置执行清零操作;由于滑梯效应的存在,函数会清除2个字节的空间,以此类推。当尾数的值为最大值7的时候,它会执行7次相同操作。 在这个算法中,不会出现尾数大于7,也就是8的情况,因为第一部分的指令已经清除了所有8字节的内存块。

换而言之,达夫装置就是循环展开技术的一种特例。在老式设备上,它显然比普通循环的运行速度更高。然而,对于现代的大多数CPU来说,一些体积短小的循环语句反而会比循环展开体的执行速度更快。也许对于目前低成本的嵌入式MCU(微控单元,例如单片机)处理器而言,达夫设备更有意义一些。

我们下面来看看优化后的MSVC 2012的一些行为。

dst$ = 8
count$ = 16
bzero    PROC
         test    rdx, -8
         je      SHORT $LN11@bzero
; work out 8-byte blocks
         xor     r10d, r10d
         mov     r9, rdx
         shr     r9, 3
         mov     r8d, r10d
         test    r9, r9
         je      SHORT $LN11@bzero
         npad    5
$LL19@bzero:
         inc     r8d
         mov     QWORD PTR [rcx], r10
         add     rcx, 8
         movsxd  rax, r8d
         cmp     rax, r9
         jb      SHORT $LL19@bzero
$LN11@bzero:
; work out the tail
         and     edx, 7
         dec     rdx
         cmp     rdx, 6
         ja      SHORT $LN9@bzero
         lea     r8, OFFSET FLAT:__ImageBase
         mov     eax, DWORD PTR $LN22@bzero[r8+rdx*4]
         add     rax, r8
         jmp     rax
$LN8@bzero:
         mov     BYTE PTR [rcx], 0
         inc     rcx
$LN7@bzero:
         mov     BYTE PTR [rcx], 0
         inc     rcx
$LN6@bzero:
         mov     BYTE PTR [rcx], 0
         inc     rcx
$LN5@bzero:
         mov     BYTE PTR [rcx], 0
         inc     rcx
$LN4@bzero:
         mov     BYTE PTR [rcx], 0
         inc     rcx
$LN3@bzero:
         mov     BYTE PTR [rcx], 0
         inc     rcx
$LN2@bzero:
         mov     BYTE PTR [rcx], 0
$LN9@bzero:
         fatret  0
         npad    1
$LN22@bzero:
         DD      $LN2@bzero
         DD      $LN3@bzero
         DD      $LN4@bzero
         DD      $LN5@bzero
         DD      $LN6@bzero
         DD      $LN7@bzero
         DD      $LN8@bzero
bzero    ENDP

这个函数的第一部分与源程序一一对应。第二部分的循环展开体也不难理解:switch语句通过转移指令直接跳到合适的位置。由于MOV/INC指令对之间没有其他代码,所以swtich语句在转移到指定标签后不会越过后续的转移标签,它会执行完所需的所有指令。

另外,我们注意到MOV/INC指令对占用固定的字节数(3+3=6字节)。在注意到这个问题之后,我们就可以舍去switch()语句的转移表结构,将输入值乘以6,并直接跳转到如下地址:目前的RIP地址+输入值*6。这样一来,由于省掉了从转移表的查询操作,执行速度会更快。对于乘法来说,数字6是一个计算效率不高的乘数因子,或许乘法运算的速度比表查询的转移指令更慢;不过所谓“深度优化”就是这个思路[1]。在介绍循环展开技术时,过去的教科书就是这样介绍“达夫设备”的。


[1] 作为一个练习,为了去掉跳转表,读者可以尝试重新编写代码。上述MOV/INC指令对可以重写成4字节或者8字节,当然一个字节也可以,比如STOSB指令。