CWYAlpha

Just another WordPress.com site

Thought this was cool: 性能优化tips(一)

leave a comment »


(1)数据对齐是否更快?

从学习数据结构的第一天起,书上就告诉我们,数据对齐可以使得访问速度更快,我心里也一直有这样一个印象,但是对其具体原因,一直不太清楚。借着最近TreeLink大赛之后大家对于性能优化痴迷的机会,我也来细细研究下这个问题。

首先来看下面这段代码:

#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次之后得到的统计时间为

case_one:       [ sum = 131071, cost = 12764585 us]
case_two:       [ sum = 131071, cost = 10501603 us]

case two的运行速度比case one要快出17%左右。

在NotAlignedStruct的定义前,我们通过

#pragma pack(1)

指定使其按照1字节对齐,所以sizeof(NotAlignedStruct)=7.

而在AlignedStruct的定义前,我们又通过

#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)的规则。

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个元素)中各个元素的和?

我们先来看最直观的答案:

#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:

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能够做到指令级并行计算(如下图),

cpu流水线

但是我们这种写法却无法有效利用这个特性,白白浪费资源。而实际上,一次循环中4个元素的相加并没有先后顺序的约束,完全可以在代码级并行起来。这样答案3就出来了。

答案3:

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无法全部安排到寄存器中存储,最终就会产生寄存器溢出问题,导致临时变量存到内存上,而内存的访问的速度要比寄存器慢一两个数量级,这样反而会增加循环体的耗时。

参考资料:

(1) http://www.ibm.com/developerworks/library/pa-dalign/

(2) 深入理解计算机系统


0

   

0

udpwork.com 聚合
|
评论: 0
|
要! 要! 即刻! Now!

from IT牛人博客聚合网站: http://www.udpwork.com/item/9631.html

Written by cwyalpha

四月 11, 2013 在 11:08 上午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: