达夫装置(Duff’s Device)是一种综合了多种控制语句的循环展开技术,可大幅度地减少代码的分支总数。这种循环展开技术巧妙地利用了swtich语句的滑梯(fallthrough)效应。
本章对Tom Duff的原始程序进行了轻度简化。
现在假设我们要编写一个清除一块连续内存的函数。当然,我们可以使用循环语句、逐个字节的复写数据。但是现代的计算机内存总线都很宽,以字节为单位地清除效率会非常低。若以4字节或8字节为操作单位进行io操作,那么操作效率会高一些。由于本例演示的是64位应用程序,所以我们就以8字节为单位进行操作。不过,我们又当如何应对那些不足8字节的内存空间?毕竟我们的函数也可能清除容量不足8字节的内存空间。
因此,合理的算法应当是:
首先统计目标空间含有多少个连续的8字节空间,继而以8字节(64位)为操作单位将其清除。
然后统计那些大小不足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指令。