泛型<编程>：类型化缓存(II)
Andrei Alexandrescu
我们以电视剧中常见的方式来回顾一下前文的重点。我们勾画了一个非常类似于
std::vector的模板类buffer，除了buffer没有容积概念，并且增加了一些基本函数，比如
grow_noinit和shrink_nodestroy。此外，前文提到把类型特性(type traits)作为一个提供优化的
技术手段。最后，有个恶棍威胁说将要讲到拷贝对象和内存分配的问题。
本文不直接讲buffer，而是要讲两个你经常用在buffer上的操作：用值填充一个buffer，
在buffer间和buffer与不同容器间拷贝对象。我们会在几个填充和拷贝方法间通过计算来做
出比较。
填充
你知道的——就是拷贝同样的值到一个区间内的所有对象。C++标准库提供了两个填充
函数：std::fill和std::uninitialized_fill。第二个操作假定被填充的对象完全没有初始化过。
最简单的泛型化内存填充函数可以是这样的
//例1：一个简单的填充操作
template <typename T>
void Fill(T* beg, T* end, const T& value)
{
for (; beg != end; ++beg) *beg = value;
}
问题在于，这是否是最优实现？通常回答是：“产生优化代码是编译器的责任“——那
么我就来测试一下
首先，我查看了一下Microsoft Visual C++ 6.0 (MSVC)和Metrowerls CodeWarrior 6.8
(MWCW)为Fill产生的代码。它们都产生了一段简单循环的汇编代码。但是，x86，和其他
许多现代的处理器一样，提供了专门的汇编指令来快速填充内存块。C库函数memset可能
就用了这些指令。不幸的是，memset只能把内存设成同样的字节，只要你需要以长于一个
字节的方式来设内存，你就不再能使用memset了，所以memset对通用代码没有扩展性。
（这里我讲几句题外话。C的内存操作函数memset,memcpy和memcmp是无与伦比的。
这些函数可能被编译器厂商高度优化，优化范围包括编译器可能检测到对这些函数的调用并
且用内联汇编指令代替它们——MSVC是这样做的。从而，对渴望速度的程序员，使用mem*
函数被认为是很酷的方式）
使用拷贝来实现填充是一种方式。就是说，你可以利用这一点：一旦你部分填充了目标
区间，你能够使用快速拷贝方式来拷贝已填充部分到未填充部分！酷的是你可以倍增每次被
拷贝内存块的尺寸。比如说，你要用1.0填充一个有1000个double型成员的区间。第一步，
你对第一个位值赋以1.0。第二步，你拷贝刚才赋的位置到它相邻位置。第三步，你拷贝新
赋的两个位置到下两个紧邻的位置。第四步，你拷贝四个值然后后你得到八个——以此类推。
10步内，你填充了整个1000个double的区间。你需要做的大部分事情实际上在最后一步，
当512个位置已被填充，那么它们中的488个被拷贝到剩下的488个位置里。假设你的可供
利用的快速拷贝函数的原型是：
template<typename T>
void QuickCopy(const T* sourceBegin,
const T* sourceEnd, T* destination);
那么FillByCopy算法就是这样：
template <typename T>
void FillByCopy(T* beg, T* end, const T& value)
{
if (beg == end) return;
*beg = value;
T* dest = beg + 1;
for (;;)
{
const size_t alreadyFilled = dest – beg;
if (alreadyFilled >= end – dest)
{
QuickCopy(beg, beg + (end – dest), dest);
break;
}
else
{
QuickCopy(beg, dest, dest);
dest + = alreadyFilled;
}
}
}
如果QuickCopy确实是个很快的函数，FillByCopy就是个很酷的算法。FillByCopy某
种程度上类似于“俄国农民算法”，这个算法用最少步骤来计算整数幂[1]。许多人在不同领
域发明拷贝填充——其中一个算法是用一个单字节文件来塞满整个磁盘。如果这是我原创的
想法，我会赶快把拷贝填充叫做“罗马尼亚农民”算法。（译注：作者是罗马尼亚裔）
然后我迫不及待地写了个测试，得到了有趣的结果。但首先，让我来为你介绍参赛的另
一个算法。
Duff's Device
Duff's Device[2]是一个加速循环语句的C编码技巧。其基本思想是，如果在一个for循
环中，其中操作执行得如果足够快（比如说，嗯，一个赋值）——那么测试循环条件（上面
例1中是beg != end）占用了循环所用时间的很大部分。循环应该被部分解开，这样数个操
作一次完成，测试操作也做的较少。比如，如果你填充一个对象区间，你可能要在一次循环
中赋二个或更多连续对象的值。
你必须注意终止条件的细节及其他。在这里Duff's Device是个新颖的，有创造力的解
决方案。我们来很快地看一个基于Duff's Device的泛型填充算法的实现。
template <class T> inline void FillDuff
(T* begin, T* end, const T& obj)
{
switch ((end – begin) & 7)
{
case 0:
while (begin != end)
{
*begin = obj; ++begin;
case 7: *begin = obj; ++ begin;
case 6: *begin = obj; ++ begin;
case 5: *begin = obj; ++ begin;
case 4: *begin = obj; ++ begin;
case 3: *begin = obj; ++ begin;
case 2: *begin = obj; ++ begin;
case 1: *begin = obj; ++ begin;
}
}
}
现在，如果你以前从没看过这样的代码，再回过头看一次，因为可能你看漏了什么。函
数包含一个switch语句，它的case语句同时位于一个while循环体内（有一个case语句在
外面）。switch内的表达式计算被八除的余数。执行开始于while循环内的哪个位置由这个
余数决定。最终循环退出。（没有break）Duff's Device这样就简单漂亮地解决了边界条件的
问题。顺便提一下，为什么“case 0”标记在循环外面呢？这样不是打破了对称的美观吗？
这样做的唯一理由是为了处理空序列。当余数为零，“case 0”内就需要执行一个多余的测试
来判断空序列的可能性。总之所有这些都无懈可击。
结果是begin != end测试少执行八倍。这样，测试本身在循环持续期间所占的开销比例
下降了八倍这个因数。当然，你也同样可以尝试用其他因数。
Duff's Device对效率的负面影响可能来自于代码膨胀（一些处理器更善于处理紧凑的循
环而不是大的循环）和特别的结构。优化器被做成当遇到更熟悉简单的循环代码时说“啊
哈！”，而遇到一些更加技巧性的结构时可能会不知所措从而生成比较保守的代码。
数量
必须要知道关于优化的一点是（在你度过了“不要这样做”和“还是不要这样做”的阶
段后），被实际测量过的优化才是有效的优化。上述的填充算法可能听上去不错，但只有测
试才能证明它们有效。
我写了个简单的测试程序，填充一个类型为double大小为COUNT的数组，分别使用
了上述的三个算法：for循环，拷贝填充，和Duff's Device。测试重复REPEAT次。我在一
台PIII750 MHz上用了三个编译器：MSVC, MWCW,和GNU的g++ 2.95.2，测试每个算法
若干次。通过改变COUNT和REPEAT，我得到如下结果
* 当填充一个大的缓存（COUNT 为100,000和更多），直接for循环和Duff's Device表现
几乎一样。拷贝填充算法实际表现慢了1-5%[3]
* 当填充12,000个double的区间时，MSVC和MWCW上的拷贝填充快了23%，但g++
是最喜欢for循环的，产生的结果是目前为止所有编译器和所有方法中最好的
（20%-80%）。
* 当填充1,000个double的区间时，MSVC和MWCW产生类似的结果。Duff's Device
快了20%，拷贝填充快了75%，相比较直接for循环而言。再一次的，g++有不同表现，
在所有方法上产生的结果都令人惊讶的快（比其他编译器最快的方法快了100%）
* 100个double，MSVC和MWCW结果一样，再一次g++用一半的时间完成任务（Duff's
device和拷贝填充比for循环快了12%）。
我们通过检查现代PC的架构来寻找这个现象的解释。处理器比主内存总线快5-10倍。
为了加速内存访问有二级缓存。一级在处理器内（1级），另一级在处理器边上（在奔腾三
中和处理器封装在一起）
最好情况是，一个操作的所有需要处理的内存都在1级缓存内。最坏情况是，你进行
随机分散的内存存取操作，这样你总是不能命中缓存，最终都命中了主内存。
拷贝填充是不利于缓存的，因为每一轮它同时要命中的是两块内存区域——源和目标区
域。比如说如果你填充1MB数据,最后一步会从一处拷贝512KB到另一处。这让缓存管理
很不愉快。或者说不象处理直接填充循环那么愉快。这是为什么在填充大内存块时拷贝填充
比for循环稍慢的原因。
（练习：你可以通过简单地修改FillByCopy一行代码来提高它的缓存友好度。提示：
考虑局部存取）
当填充大量数据时，你不能从缓存中得益，所以填充速度会主要被限定在主内存带宽上。
你对循环本身作的优化不能带来很大提高，因为瓶颈在内存，而不是处理器操作。不管你写
的循环有多聪明，使用寄存器，或不展开循环，处理器总是会等待主内存。这是为什么Duff's
Device和for循环对大内存块表现一样。
当填充较少量数据时情况起了变化。数据有更多可能被放在缓存内，而缓存和处理器一
样快。现在，处理器执行的代码决定了循环的速度。
memcpy（在我测试用例中FillByCopy最终使用的函数）使用了特殊的循环汇编语句（x86
中的术语是rep stos）。对于缓存到缓存拷贝，这种汇编语句比建立在跳转（jump），赋值和
比较基础上的循环要快。这是为什么FillByCopy在中等数量数据情况中最快。类似的，Duff's
Device比for循环也有优势，因为它执行了较少比较。
快速拷贝
另一个通常的内存操作是拷贝数据到缓存或从缓存拷贝数据。为了找到一个快速拷贝的
方法，我测试了对类型double数据的三种不同拷贝方法：一种是直接的for循环，一种是基
于Duff's Device的实现，和memcpy（奇怪的是，尽管有拷贝填充算法，却不存在填充拷贝
算法）
我们不期望什么意外发生——memcpy应该把所有其他的方法都抛在后面。无论如何，
memcpy是由你的标准库实现提供的高度优化的，非常成熟的拷贝方式。它不能被用在所有
类型上实在是太糟糕了！另外Duff's Device比较for循环应该和在填充情况下结果一样。当
然，正如经常发生的那样，真实结果有些不同。结果如下：
* 当拷贝大量数据（以兆字节计），所有方法（和所有编译器）的速度基本一样。这一样
是因为对大量数据来说内存带宽制约了操作速度。
* 当拷贝较少量数据时，编译器开始不一致。比如当拷贝100,000个类型double的对象时：
* MWCW的for循环非常慢，Duff's Device和memcpy都超过它20%
* MSVC和g++产生的可以说是同样的代码，所有方法的表现几乎一样——和
NWCW最快的一样快。
* 当进一步减少被拷贝的数据量，不同变得更明显。下面是拷贝10,000个double的结果。
* MSVC产生的代码中Duff's Device快25%，memcpy快67%。
* NWCW（be prepared）产生的代码中，Duff's Device快9%， memcpy慢20%，相
比较一个for循环而言。for循环的速度基本和MSVC的一样。
* g++真的很酷。一开始，g++的for循环比MSVC和MWCW的快42%。然后，memcpy
的表现和MSVC的memcpy一样，比g++的for循环快10%，但g++的实现者肯定
热爱Duff's Device，因为它的基于Duff的拷贝方式打败了所有竞争者，比memcpy
快了11%,，而这本应是最快的。
* 当把数据量减到1,000个double时：
* MSVC的for循环非常慢。Duff快90%,memcpy快200%.
* MWCW产生更快的for循环，Duff比它快5%，memcpy比它快130%。
* g++的for循环和NWCW的一样快，Duff快了75%，memcpy快了130%。
* 所有编译器对memcpy产生类似的，最快的结果。
* 最后，当拷贝100个double，我得到和1,000个double类似的结果，除了g++在Duff's
Device中再次表现更好，比for循环快了75%，比memcpy快了40%。
如果你觉得疑惑，我也一样。看上去找到适合所有编译器和所有数据量的最好方法很困
难。同样让我惊讶的是作为一个免费，开源的编译器不单是超过而是击垮了两个著名的商业
编译器。
所有这些测试都让我忌妒那些写编译器用库的作者们——他们有这个特权来对一个编
译器和一种计算机架构优化他们的代码。但是本文题目是“泛型<编程>”而不是“专门<编
程>”——尽管这更有挑战性也更有趣。顺便说一句，我们现在讨论在“泛型编程”的泛型
——我们刚才提及的方法到底有多“泛”？
对泛型的考量
目前为止，我们假定测试的类型都能用memcpy来拷贝，事实上，只有部分的C++类型
有此特性。这一部分类型被称为POD（“直接旧数据”）。POD集合中包括所有基本类型和类
似C的不带构造和析构函数及虚函数的结构。对于其他所有类型，对它们使用memcpy结
果是未定义行为。
这样Duff's Device相对FillByCopy和memcpy就有一个重要的优势。Duff's Device对
各种类型100%“通用”。更好的是，Duff's Device不单能和指向内存区间的指针，也能和任
意的随机迭代器（random iterator）类型配合工作。
但是你能够知道你是否能用memcpy来拷贝一个类型还是很重要。这非常有意思，不仅
是为了速度的目的，也是，尽管有些矛盾，为了内存分配的目的，正如你在下个部分会看到
的那样。定义一个MemCopyabel标志需要打开TypeTraits命名空间（定义在上一部分）和
植入下面的定义：
namespace TypeTraits
{
template <typename T> struct IsMemCopyable
{
enum { value = IsPrimitive<T>::value != 0 };
};
}
然后你可以轻松地写出一个NativeCopy<T>泛型代码段来在编译时靠
TypeTraits::IsMemCopyable<T>::value来分派调用memcpy或更保守的方法。这作为练习留
给读者。
Duff's Device只有当被拷贝/填充类型的拷贝/填充动作花费足够低廉才有价值。否则，
在比较上的花费和赋值本身相比变得微不足道。所以我们需要定义一个类型特性
CheapToCopy，如下：
Namespace TypeTraits
{
template <typename T> struct CheapToCopy
{
enum { value =
CopyThrows<T>::value == 0 && sizeof(T) <=
4 * sizeof(T*) };
};
}
很有趣，CheapToCopy有点象歇洛克?福尔摩撕：一个类型被认为拷贝廉价当如果它的
拷贝操作不抛出（这通常意味着没有分配资源的代价）并且它的大小低于一个设定值。如果
一个类型大于一个指针的四倍，就意味着循环应该是正常开解的类型。
使用TypeTraits::CheapToCopy<T>::value，你能够在编译时确定使用Duff's Device或其
他什么方式。
总结
是不是有点晕头转向了？首先，有多于一种方法填充和拷贝对象对你可能是个意外。然
后，没有一个单一的填充和拷贝方法在所有编译器，数据集规模，和硬件平台（我猜想如果
我在一台有较小缓存的赛扬机器上测试同样的代码，我会得到非常不同的结果。更不用说其
他硬件体系）上都工作得最好。
作为一个准则，尽可能地使用memcpy一般都很好（同样适用拷贝填充）——对于大数
据集，用memcpy不会有什么不同，对较小数据集，可能会快上许多。对廉价拷贝对象，
Duff's Device可能表现得比一个简单的for循环快。而所有这些最终都取决于你的编译器和
硬件平台的突发奇想和特别行为。
这里有个非常深层和可悲的现实。我们生活在21世纪，太空旅行的时代。我们发展电
子计算机已经有50多年，我们努力设计越来越多的复杂系统，得到的结果却不能让人满意。
软件开发是杂乱无章的行为。这难道是因为我们使用的基本工具和方法是低层次的，低效率
的，和不标准的吗？我们来跳出圈外回过头看看自己——50年后，我们仍旧在填充和拷贝
内存上做不到完美。
我到了本文的字数限制却没有排除掉所有这些问题，对不起，buffer。移动对象是另一
个重要的主题，而且我们甚至还没有讲到内存分配。但是，就象电影里常说的那样，脑袋里
一次装不下太多东西（恩？什么电影？）。所以我不得不现在停下来。再见。
参考书目与注解
[1] Matt Austern. "The Russian Peasant Algorithm," C++ Report, June 2000. Matt没有发
明这个算法，但他的文章对算法有很好的论述。
[2] 参见 <www.lysator.liu.se/c/duffs-device.html>.
[3]我得说g++肯定在使用某种填充数据的特殊方法。这个方法只是有时有效。重复测试填
充1千万double时，用g++编译的Duff's Device代码有时比任何其他方法快40~50%，这
是速度测试的问题吗。
Andrei Alexandrescu 是位于西雅图的华盛顿大学的博士，也是受到好评的《Modern
C++ Design》一书的作者。可以通过www.moderncppdesign.com. 来联系他。Andrei
同时也是C++研讨会 (<www.gotw.ca/cpp_seminar>).的一名有号召力的讲师。
你可以从CUJ网站或http://merced.go.nease.net/code/buffer.zip获得本文源代码。
、
