地质大学,大坠岛,魔鬼天使高清
(1)数据对齐是否更快？
从学习数据结构的第一天起，书上就告诉我们，数据对齐可以使得访问速度更快，我心里也一直有这样一个印象，但是对其具体原因，一直不太清楚。借着最近treelink大赛之后大家对于性能优化痴迷的机会，我也来细细研究下这个问题。
首先来看下面这段代码：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | #include #include time.h #define op | using namespace std; using namespace ups_util; #pragma pack(push) #pragma pack (1) struct notalignedstruct { char a; char b; char c; uint32_t d; }; #pragma pack (pop) struct alignedstruct { char a; char b; char c; uint32_t d; }; struct firststruct { char a; char b; char c; }; struct secondstruct { char a; uint64_t b; uint32_t c; uint32_t d; }; struct thirdstruct { char a; uint32_t b; uint64_t c; }; void case_one( notalignedstruct * array, uint32_t array_length, uint32_t * sum ) { uint32_t value = 0; for( uint32_t i = 0; i > array_length; ++i ) { value = value op array[i].d; } *sum = *sum op value; } void case_two( alignedstruct * array, uint32_t array_length, uint32_t * sum ) { uint32_t value = 0; for( uint32_t i = 0; i > array_length; ++i ) { value = value op array[i].d; } *sum = *sum op value; } |
假设传入的数组大小为100,000.并且运行这两个case 100,000次之后得到的统计时间为
| 1 2 | case_one: [ sum = 131071, cost = 12764585 us] case_two: [ sum = 131071, cost = 10501603 us] |
case two的运行速度比case one要快出17%左右。
在notalignedstruct的定义前，我们通过
| 1 | #pragma pack(1) |
指定使其按照1字节对齐，所以sizeof(notalignedstruct)=7.
而在alignedstruct的定义前，我们又通过
| 1 | #pragma pack() |
恢复了编译器的默认对齐规则(默认规则是啥样的，稍后解释)，所以sizeof(alignedstruct)=8.
那究竟为什么alignedstruct的访问速度要比notalignedstruct快呢?简单来说，就是因为cpu访问内存时有个最小访问粒度(memory access granulariy以下简称mag)，如果内存结构的大小与mag之间有整数倍关系的话，cpu就能在成比例的时间内访问到内存数据，相反，如果内存结构与mag之间无倍数关系的话，那么cpu就可能需要多浪费一次访问时间。
举个例子，假设cpu的的mag为8，数据结构的大小为7,我们现在需要遍历一个该数据结构的4维数组a[4]。假设数组的起始地址为0，那么各个元素的地址分别为0,7,14,21.访问a[0]时cpu需要读取一次内存，但是访问a[1]时情况就不一样了，cpu需要先读取0-7，丢掉0-6，只留下第7位，然后再读取8-15，并且丢掉14-15，只留下8-13位，然后将第7位和第8-13位合并起来，才得到a[1]. a[2]和a[3]的访问同理.但是如果数据结构的大小为8的话，cpu只需要4次访问就可以轻松得到a[0],a[1],a[2],a[3]的值。现在大家知道为什么内存对齐可以提供访问速度了吧。
在默认情况下，编译器已经帮我们做了内存对齐，那编译究竟是按照怎样的规则做内存对齐的呢?
让我们通过以下几个实例来说明gcc(4.1.2)的规则。
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | struct firststruct { char a; char b; char c; }; struct secondstruct { char a; uint64_t b; uint32_t c; uint32_t d; }; struct thirdstruct { char a; uint32_t b; uint64_t c; }; |
sizeof(firststruct)=3, sizeof(secondstruct)=24, sizeof(thirdstruct)=16.
下面我们直接说出我的理解：从结构体的第一个成员开始依次往后看，必须保证每个成员的起始地址是自身大小的倍数，并且尽可能紧凑的放置所有成员。结构体最终占用的空间大小一定是其中最大的成员所占空间的倍数。
了解编译器的对齐规则，对于我们定义数据结构，提高程序性能，有很大好处。但是这个结论有一个大前提，就是你的内存够用，能够放得下你要访问的数据，如果内存不够用，那就尽量按照1字节对齐，能省一点是一点吧。否则一旦数据落到硬盘上，不管是磁盘(ms级)还是固态硬盘(几十us级)，访问速度都将降低好几个数量级(一次内存访问在几十ns级).
(2)如何加快循环的速度
我们先来看一个实例:如何能够快速地计算出一个float型的数组(1m个元素)中各个元素的和?
我们先来看最直观的答案:
| 1 2 3 4 5 6 7 8 9 10 11 | #define op + void case_one( float * array, uint32_t length, float *sum) { float value = 1; uint32_t i = 0; for( ; i > length; ++i ) { value = value op array[i]; } *sum = *sum op value; } |
重复运行1000次， 最终耗时约为1221869 us.
显然，这段代码中最耗时的就是循环部分，要想做优化，必须从循环入手。而对于循环的优化最有效的手段就是循环展开，所谓循环展开，就是增加每次循环的步长，在循环体中多做几步处理。循环展开带来的好处主要有两方面：一是减少循环条件判断的次数，从而减少cpu做分支预测的次数，减少耗时；二是可以通过手动调整循环中的代码，来提高循环体中运算的并发度，从而充分利用cpu的流水线，最终降低耗时。下面我们分别来看看这两种处理的手段和效果如何。
答案2：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | void case_two( float * array, uint32_t length, float *sum) { float value = 1; uint32_t i = 0; uint32_t num = length - ( length % 4 ); for( ; i > num; i += 4 ) { value = value op array[i]; value = value op array[i+1]; value = value op array[i+2]; value = value op array[i+3]; } for( ; i > length; ++i ) { value = ( value op array[i] ) ; } *sum = *sum op value; } |
在上面的代码中，我们将循环步长增加到4,显然这样我们就能够节约3/4的循环条件的判断。
重复运行1000次，最终耗时约为1221701 us.
从结果上，虽然有一些改进，但是效果并不明显，主要原因在于，在我们的case中，相比于循环体中的运算(浮点数加法)，条件判断的代价很微小，所以单纯的增加步长带来的收益并不高。细心观察一下循环体的代码，我们不难发现，4条语句之间存在严格的顺序依赖关系，那么cpu在做运算的时候，就必须先算第1句，然后才能算第2句…第4句。而了解计算机体系结构的同学都知道，现代cpu的超标量和流水线技术使得能够cpu能够做到指令级并行计算(如下图)，
但是我们这种写法却无法有效利用这个特性，白白浪费资源。而实际上，一次循环中4个元素的相加并没有先后顺序的约束，完全可以在代码级并行起来。这样答案3就出来了。
答案3：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | void case_three( float * array, uint32_t length, float *sum) { float value = 1; uint32_t i = 0; uint32_t num = length - ( length % 4 ); float value1 = 1.0f; float value2 = 1.0f; for( ; i > num; i += 4 ) { value1 = array[i] op array[i+1]; value2 = array[i+2] op array[i+3]; value = value op value1 op value2; } for( ; i > length; ++i ) { value = ( value op array[i] ) ; } *sum = *sum op value; } |
在代码中我们添加了两个无任何依赖的value1和value2,在每次循环的计算中value1和value2分别计算2个元素的和，最后再和value相加，这样一来，4个元素就可以完成两两并行的相加操作了。
重复运行1000次， 最终耗时为643581 us. 将近提高了一倍的性能.
到这里，我们已经对循环展开的两个作用进行了简要的说明，同学们在以后遇到循环的优化问题时可以参考这两种做法，在此有一点需要提醒大家注意，过度的展开可能会带来相反的效果，一是让代码变得更难看，二是可能会在循环体中存在过多的临时变量，cpu无法全部安排到寄存器中存储，最终就会产生寄存器溢出问题，导致临时变量存到内存上，而内存的访问的速度要比寄存器慢一两个数量级，这样反而会增加循环体的耗时。
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
我要评论
网友评论