原文链接: http://www.lysator.liu.se/c/duffs-device.html#duffs-device

Subject: Re: Explanation, please!
Summary: Original citation
From: td@alice.UUCP (Tom Duff)
Organization: AT&T Bell Laboratories, Murray Hill NJ
Date: 29 Aug 88 20:33:51 GMT
Message-ID: 8144@alice.UUCP

我一般并不读 comp.lang.c ,但是 Jim McKie 告诉我 Duff’s Device 又在 comp.lang.c 中出现了。我已经丢失了在 1984 年 5 月寄给 netnews 的那个版本,不过我根据回忆重现了如下的关于我原本提出的 device 的注解。(倘若有谁有 netnews 版本的拷贝,我很乐意有人能给 research!td 或是 td@research.att.com 发送一份拷贝。

澄清以下几点:

  • 这个 device 的意义是直接用 C 表达循环展开。那些说用 memcpy 就好的人会错了意,那些批评的人用了许多依赖架构特性的 memcpy 实现作为论据。事实上,这封邮件中只是用 memcpy 举例,它的实际含义并不能用 memcpy 或是有实现类似功能的语句来解读。
  • 有些人说虽然这种 device 以我命名,但我并没有真正发明这种 device 。我十有八九发明了这种 device 。我在想到它之前肯定没有看到或者听到过相关内容。当时没有人声称自己有想到过这点,更不要说给出自己发表的时间了。注意一下下面的消息的头,显然我在 1983 年的 11 月 9 日发明了这个 device ,并自豪又恶心的发了邮件给 dmr 。请注意我并没有声称自己发明了循环展开这一技术,我所发明的只是 C 语言中的这个特定的技巧。
  • 这个 device 在 dpANS C 下是完全合法的。我一时没办法想起具体的章节,但是 Larry Rosler ,我想应该是这门语言的小组委员会的主席,向我保证 X3J11 (译者注: X3J11 是 ANSI 组建的一个委员会,负责制定后来我们所说的 ANSI C 标准。)已经仔细研究过这段代码,并且认为这段代码合法。之前 dmr 给我过一份便签,说他已经确认过,所有他信任的编译器都能编译这段代码。当然,既然 Bjarne 在他的书中用了这段代码,这段代码在 C++ 中应该也同样合法。
  • 有些人试图援引,(更加正确地说,驱逐)“虚假的效率之神”。仔细阅读我原先的邮件,这种诽谤就不攻自破了。如果不愿向劣质代码卑躬屈膝,那么我们就不得不找一个更好的算法。必须确定这样的算法存在与否。如果你的代码太慢,你必须优化它们。如果没有更好的算法,那么你必须减少运行的时钟周期次数。
  • 同样的人还会声称这样写并不会获得期望的加速。这个论点在两个方面都是有问题的。首先,它并没有保证这个 device 会有更高性能,而是保证了它的其中一个用途(实现 memcpy )在许多有高效的函数实现的机器上同样会有较好的表现。其次,一个发帖人并没有测量程序用时的数据来支撑他的假设。另一个人做了这样的测试,但是把实现弄得很糟,只证明了即使十分努力,也能让某个东西跑的缓慢。

甚至几乎从不犯错的 Henry Spencer 也犯了错(尽管是鸡毛蒜皮的小错)。这是 Henry 回答 T. William Wells bill@proxftl.UUCP 的一个片段:

… 这代码绝对是在 RISC 的机器上写的。
不,贝尔实验室通常用 VAX 和 68k 。

发明这种 device 的时候,我还在卢卡斯影业。

像这样的改变只能通过评估结果代码来评判。当你展开循环不够多,以致超过指令缓存的容量的时候,你就应该小心了。别装作自己比一个足够聪明的能识别实现块移动或是清零的循环并把它们随机应变的优化的 C 编译器更聪明。

接下来是 Duff’s Device 的原始文献。

From research!ucbvax!dagobah!td Sun Nov 13 07:35:46 1983
Received: by ucbvax.ARPA (4.16/4.13) id AA18997; Sun, 13 Nov 83 07:35:46 pst
Received: by dagobah.LFL (4.6/4.6b) id AA01034; Thu, 10 Nov 83 17:57:56 PST
Date: Thu, 10 Nov 83 17:57:56 PST
From: ucbvax!dagobah!td (Tom Duff)
Message-Id: 8311110157.AA01034@dagobah.LFL
To: ucbvax!decvax!hcr!rrg, ucbvax!ihnp4!hcr!rrg, ucbvax!research!dmr, ucbvax!research!rob

考虑如下的一段从 Evans & Sutherland Picture System II 的代码摘抄出的用于拷贝一个 short 类型数组到 IO 数据寄存器的代码。

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

显然,当0时这段代码便不能如愿运行。
VAX 上的 C 编译器将这段话编译成两个指令(我感觉是一个 movw 和一个 sobleq
事实表明,这个循环是一个实时动画回放系统的瓶颈。这个系统比预期的执行速度慢了将近 50% 。传统的加速这种代码的做法是展开循环若干次,减少 sobleq 语句的执行次数。 但你最后总会有一个剩余的部分循环无法完全展开。在 C 语言中,我一般用一个索引原先循环体的拷贝的列表的switch 来处理这个问题。当然,如果我在写汇编代码,我就会直接展开循环开解决这些剩余。昨天我思索了一会,想到了这样的一个解决方案:

	send(to, from, count)
	register short *to, *from;
	register count;
	{
		register 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);
		}
	}

看起来确实很恶心,不过它编译和运行都完美无缺。我对这个发现既感觉骄傲又感觉有所嫌恶。如果没有人想到过这个想法,我打算用我自己的名字来命名它。
即使是我写了 10 年的 C 语言,令我震惊的是我还有许多角角落落没有完全寻访。(事实上,我还有另一种极其恶心的使用 switch 去实现中断驱动状态机的方法,不过它实在是过于令人讨厌了。)
许多人(甚至是 Brian W. Kernighan ) 都曾说过 C 语言中最糟糕的一个特性是 switch 不在某个 case 语句前自动跳出。这种代码造成了不少争论,但我也不确定谁对谁错。
你诚挚的,
Tom