- 论坛徽章:
- 0
|
填充和拷贝经典方法分析
（ 转自：http://likunarmstrong.blogchina.com/2825625.html ）
填充
你知道的——就是拷贝同样的值到一个区间内的所有对象。C++标准库提供了两个填充函数：std::fill和std::uninitialized_fill。第二个操作假定被填充的对象完全没有初始化过。 最简单的泛型化内存填充函数可以是这样的//例1：一个简单的填充操作
template
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
void QuickCopy(const T* sourceBegin,
const T* sourceEnd, T* destination);
那么FillByCopy算法就是这样：
template
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 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'sdevice和拷贝填充比for循环快了12%）。
我们通过检查现代PC的架构来寻找这个现象的解释。处理器比主内存总线快5-10倍。为了加速内存访问有二级缓存。一级在处理器内（1级），另一级在处理器边上（在奔腾三中和处理器封装在一起）
最好情况是，一个操作的所有需要处理的内存都在1级缓存内。最坏情况是，你进行随机分散的内存存取操作，这样你总是不能命中缓存，最终都命中了主内存。 拷贝填充是不利于缓存的，因为每一轮它同时要命中的是两块内存区域—源和目标区域。比如说如果你填充1MB数据,最后一步会从一处拷贝512KB到另一处。这让缓存管理很不愉快。或者说不象处理直接填充循环那么愉快。这是为什么在填充大内存块时拷贝填充比for循环稍慢的原因。
（练习：你可以通过简单地修改FillByCopy一行代码来提高它的缓存友好度。提示：考虑局部存取）
当填充大量数据时，你不能从缓存中得益，所以填充速度会主要被限定在主内存带宽上。你对循环本身作的优化不能带来很大提高，因为瓶颈在内存，而不是处理器操作。不管你写的循环有多聪明，使用寄存器，或不展开循环，处理器总是会等待主内存。这是为什么Duff'sDevice和for循环对大内存块表现一样。 当填充较少量数据时情况起了变化。数据有更多可能被放在缓存内，而缓存和处理器一样快。现在处理器执行的代码决定了循环的速度。
memcpy（在我测试用例中FillByCopy最终使用的函数）使用了特殊的循环汇编语句（x86中的术语是rep stos）。对于缓存到缓存拷贝，这种汇编语句比建立在跳转（jump），赋值和比较基础上的循环要快。这是为什么FillByCopy在中等数量数据情况中最快。类似的，Duff'sDevice比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'sDevice中再次表现更好，比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 struct IsMemCopyable
{
enum { value = IsPrimitive::value != 0 };
};
}
然后你可以轻松地写出一个NativeCopy泛型代码段来在编译时TypeTraits::IsMemCopyable::value来分派调用memcpy或更保守的方法。这作为练习留给读者。
Duff's Device只有当被拷贝/填充类型的拷贝/填充动作花费足够低廉才有价值。否则，在比较上的花费和赋值本身相比变得微不足道。所以我们需要定义一个类型特性CheapToCopy，如下：
Namespace TypeTraits
{
template struct CheapToCopy
{
enum { value =
CopyThrows::value == 0 && sizeof(T) <=
4 * sizeof(T*) };
};
}
很有趣，CheapToCopy有点象歇洛克?福尔摩撕：一个类型被认为拷贝廉价当如果它的拷贝操作不抛出（这通常意味着没有分配资源的代价）并且它的大小低于一个设定值。如果一个类型大于一个指针的四倍，就意味着循环应该是正常开解的类型。使用TypeTraits::CheapToCopy::value，你能够在编译时确定使用Duff's Device或其
他什么方式。
总结
是不是有点晕头转向了？首先，有多于一种方法填充和拷贝对象对你可能是个意外。然后，没有一个单一的填充和拷贝方法在所有编译器，数据集规模，和硬件平台（我猜想如果我在一台有较小缓存的赛扬机器上测试同样的代码，我会得到非常不同的结果。更不用说其他硬件体系）上都工作得最好。
作为一个准则，尽可能地使用memcpy一般都很好（同样适用拷贝填充）——对于大数据集，用memcpy不会有什么不同，对较小数据集，可能会快上许多。对廉价拷贝对象，Duff's Device可能表现得比一个简单的for循环快。而所有这些最终都取决于你的编译器和硬件平台的突发奇想和特别行为。
这里有个非常深层和可悲的现实。我们生活在21世纪，太空旅行的时代。我们发展电子计算机已经有50多年，我们努力设计越来越多的复杂系统，得到的结果却不能让人满意。软件开发是杂乱无章的行为。这难道是因为我们使用的基本工具和方法是低层次的，低效率的，和不标准的吗？我们来跳出圈外回过头看看自己——50年后，我们仍旧在填充和拷贝内存上做不到完美。
我们回到程序本身，如何在电子领域领悟这个东西呢？我们来看看John_Lee 朋友在21ic上的分析：
这段代码的作用等效于 memcpy (to, from, count)，但有一点区别：两者的 count 参数定义域不同！
但作者为什么不用 memcpy 而要大费周章地写一段比较晦涩的程序呢？我们来仔细分析一下（因为这里是 AVR 论坛，我就以 AVR 为运行平台，编译程序用 avr-gcc）。
我把这段程序写成了一个函数，且称为 fast_memcpy：
#include
#include
void fast_memcpy (uint8_t *to, uint8_t *from, size_t count)
{
register size_t n = (count + 7) / 8; /* count > 0 assumed */
uint8_t c = count % 8;
switch (c)
{
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);
}
}
而标准的 memcpy，大家都想得到应该是：
#include
#include
void memcpy (uint8_t *to, uint8_t *from, size_t count)
{
while (count--)
{
*to = *from++;
}
}
编译后的结果正如我们预料的一样，fast_memcpy 编译出来的代码比 memcpy 的代码长，大家可以自己试一试。
既然 fast_memcpy 在代码长度上不占优势，那么就只有在运行速度上做文章了。我们先分析 memcpy：
编译后的代码如下：
void memcpy (uint8_t *to, uint8_t *from, size_t count)
{
0: dc 01 movw r26, r24
2: fb 01 movw r30, r22
while (count)
{
4: 41 15 cp r20, r1
6: 51 05 cpc r21, r1
8: 29 f0 breq .+10 ; 0x14
--count;
a: 41 50 subi r20, 0x01 ; 1
c: 50 40 sbci r21, 0x00 ; 0
*to = *from++;
e: 81 91 ld r24, Z+
10: 8c 93 st X, r24
}
12: f8 cf rjmp .-16 ; 0x4
}
14: 08 95 ret
在 avr 中，复制一个字节最基本的代码是：一个 ld 指令加 一个 st 指令，共 4 个 指令周期，这是最小开销了。
memcpy 程序执行主要开销在循环体中（循环体之前的开销可以忽略不计），每个循环复制一个字节，循环占 11 个左右时钟周期。它的效率就是 4 / 11 = 36%。
我们再看 fast_memcpy：
void fast_memcpy (uint8_t *to, uint8_t *from, size_t count)
{
0: dc 01 movw r26, r24
2: fb 01 movw r30, r22
4: ca 01 movw r24, r20
register size_t n = (count + 7) / 8; /* count > 0 assumed */
6: 07 96 adiw r24, 0x07 ; 7
8: 9c 01 movw r18, r24
a: 43 e0 ldi r20, 0x03 ; 3
c: 36 95 lsr r19
e: 27 95 ror r18
10: 4a 95 dec r20
12: e1 f7 brne .-8 ; 0xc
14: 07 97 sbiw r24, 0x07 ; 7
uint8_t c = count % 8;
16: 87 70 andi r24, 0x07 ; 7
switch (c)
18: 83 30 cpi r24, 0x03 ; 3
1a: d1 f0 breq .+52 ; 0x50
1c: 84 30 cpi r24, 0x04 ; 4
1e: 28 f4 brcc .+10 ; 0x2a
20: 81 30 cpi r24, 0x01 ; 1
22: d1 f0 breq .+52 ; 0x58
24: 82 30 cpi r24, 0x02 ; 2
26: b0 f4 brcc .+44 ; 0x54
28: 09 c0 rjmp .+18 ; 0x3c
2a: 85 30 cpi r24, 0x05 ; 5
2c: 69 f0 breq .+26 ; 0x48
2e: 85 30 cpi r24, 0x05 ; 5
30: 68 f0 brcs .+26 ; 0x4c
32: 86 30 cpi r24, 0x06 ; 6
34: 39 f0 breq .+14 ; 0x44
36: 87 30 cpi r24, 0x07 ; 7
38: 19 f0 breq .+6 ; 0x40
3a: 08 95 ret
{
case 0: do { *to = *from++;
3c: 81 91 ld r24, Z+
3e: 8c 93 st X, r24
case 7: *to = *from++;
40: 81 91 ld r24, Z+
42: 8c 93 st X, r24
case 6: *to = *from++;
44: 81 91 ld r24, Z+
46: 8c 93 st X, r24
case 5: *to = *from++;
48: 81 91 ld r24, Z+
4a: 8c 93 st X, r24
case 4: *to = *from++;
4c: 81 91 ld r24, Z+
4e: 8c 93 st X, r24
case 3: *to = *from++;
50: 81 91 ld r24, Z+
52: 8c 93 st X, r24
case 2: *to = *from++;
54: 81 91 ld r24, Z+
56: 8c 93 st X, r24
case 1: *to = *from++;
58: 81 91 ld r24, Z+
5a: 8c 93 st X, r24
} while (--n > 0);
5c: 21 50 subi r18, 0x01 ; 1
5e: 30 40 sbci r19, 0x00 ; 0
60: 69 f7 brne .-38 ; 0x3c
}
62: 08 95 ret
}
尽管 fast_memcpy 代码较长，但它仍然有一个循环体，循环体开销 36 个时钟周期，但和 memcpy 不同的是，它在循环体中一次循环复制 8 个字节。它的效率是 32 / 36 = 89%。
必须要提到的是 fast_memcpy 中循环体之前的程序在干什么？它的开销怎么说？
register size_t n = (count + 7) / 8; /* count > 0 assumed */
uint8_t c = count % 8;
switch (c)
这段程序的作用是：计算 count / 8 的“商”和“余数”，“商”用于循环次数计数，“余数”用于决定循环体的最初起点。简单地说：先复制“余数”个字节，在复制“商” * 8 个字节。它的开销大概有 14 ~ 35 个时钟周期。这对于只有几个字节的复制，总开销就比较大，效率可能还不如 memcpy。
开销对比如下：
memcpy 周期 fast_memcpy 周期
count * 11 14 ~ 35 + (count + count / 8) * 4
总的来说，fast_memcpy 是一个非常不错的编程技巧，它可以用在那些频繁复制内存，并且对效率要求很高的程序中。
[ 本帖最后由 pzz68 于 2007-8-18 10:59 编辑 ] |
|
免费注册
发表于 2007-08-18 10:56
