Dict.CN 在线词典, 英语学习, 在线翻译

学海苦作舟,书山勤为径

留下点回忆

常用链接

统计

积分与排名

Denoise

English study

Web技术

数据压缩

一些连接

最新评论

一段代码优化的讨论

 优化很多时候是必要的,特别对于瓶颈程序。这里讨论一段代码的优化过程,从而演示一段简单的代码优化过程,并希望得到一些建议。

先描述一下需求:

一个16位数的序列,将其奇数位置放到一个序列,偶数问题放到另外一个序列。注意奇数和偶数序列的长度不一定相同。

最简单的代码:

 

 1void CTestClass::SplitToEvenOddSeqs(short *sp,short *dp1,short *dp2,int evenLen,int oddLen)
 2
 3{
 4
 5            int i;
 6
 7            for(i = 0;i<oddLen;i++,sp+=2,dp1++,dp2++)
 8
 9            {
10
11                        dp1[0= sp[0];
12
13                        dp2[0= sp[1];
14
15            }

16
17            if(i != evenLen)
18
19                        dp1[0= sp[0];
20
21}

22
23

这段代码可以达到必要的功能,但他肯定不是优化的。

1.循环中,每次需要访问5个变量。

2.每次循环需要一个判断,4个加法

3.最后的不等式判断也

考虑到dp1dp2总是同时访问,于是定义一个结构体:

 

typedef struct tagDstData

{

            
short dp1;

            
short dp2;

}
TagDstData;

现在的算法为:

 

void CTestClass::SplitToEvenOddSeqs(short *sp,TagDstData *dp,int evenLen,int oddLen)

{

            
int i;

            
for(i = 0;i<oddLen;i++,sp+=2,dp++){

                        dp
->dp1 = sp[0];

                        dp
->dp2 = sp[1];

            }


            
if(i < evenLen)

                        dp
->dp1 = sp[0];

}


这样做以后CPU每次读取dp只需要一次。循环条件少了一次加法。

上面代码每次复制一个16bit的值,总共四个字节要复制两次,考虑把这个地方优化一下。优化后的代码如下:

 

void CTestClass::SplitToEvenOddSeqs2(short *sp,TagDstData *dp,int evenLen,int oddLen)

{

            
long *lSp = (long *)sp;

            
long *spEnd = (long *)(sp + (oddLen<<1));

            
long *lDp = (long *)dp;

            

            
while(lSp < spEnd){

                        
*lDp++ = *lSp++;

            }


            
if(oddLen < evenLen)

                        dp[evenLen].dp1 
= *((short *)lSp);

}


这里先不考虑字节序的问题。

这样优化后和前面比较起来有那些改进?

1.循环体内只有一个指令;对于++运算,很多处理器都能很好处理。

2.循环条件检查只有一条比较指令

其实这里的检查的比较指令还可以优化一下,因为比较指令比较长,看一下下面的改进:

反正是四个字节的复制,不如下计算好复制的4个字节数量;再循环。

void CTestClass::SplitToEvenOddSeqs3(short *sp,TagDstData *dp,int evenLen,int oddLen)

{

            
long *lSp = (long *)sp;

            
long *spEnd = (long *)(sp + (oddLen<<1));

            
long *lDp = (long *)dp;

            
long nDWORDs = oddLen>>1;

            

            
while(nDWORDs–){

                        
*lDp++ = *lSp++;

            }


            
if(oddLen - evenLen)

                        dp[evenLen].dp1 
= *((short *)lSp);

}



写好上面四段代码,拿VS2005编译一下发现,测试代码如下:

 

void CompareData(TagDstData *spDst,short *pSrcTest)

{

            
for(int i = 0;i<10240;i++)

            
{

                        
//if(spDst[0].dp1 )//if we access spDst here, the time will be longer

                        
if(spDst[0].dp1 > pSrcTest[0]|| spDst[0].dp2 >pSrcTest[1])

                        
{

                                    printf(”
Split arithmetic 
is not right!\n”);

                                    
break;

                        }


                        pSrcTest 
+=2;

            }


                        printf(”
Split arithmetic 
is right!\n”);

}


int _tmain(int argc, _TCHAR* argv[])

{

            
int i,f ;

            
int now;

            CTestClass testClass;

            
short spSrc[20480];     

            
short spDst1[10240];

            
short spDst2[10240];

            TagDstData spDst[
10240];

            
short *pSrcTest = spSrc;

            memset(spSrc,
2,20480<<1);

            memset(spDst1,
0,10240<<1);

            memset(spDst2,
0,10240<<1);

            memset(spDst,
0,20480<<1);

            CStopWatch stop1;

            stop1.Start();

            
for(i = 0;i<100000; i++)

                        testClass.SplitToEvenOddSeqs(spSrc,spDst1,spDst2,
10240,10240);

            now 
= stop1.Now();

            printf(”time2 
=%d\n”,now);

            stop1.Start();

            
for(i = 0;i<100000; i++)

                        testClass.SplitToEvenOddSeqs(spSrc,spDst,
10240,10240);

            now 
= stop1.Now();

            printf(”time3 
=%d\n”,now);

            
for(i=0;i<20480;i++)

                        spSrc[i] 
= i;

            memset(spDst,
0,10240<<1);

            CStopWatch stop2;

            
for(f = 0;f<100000; f++)

                        testClass.SplitToEvenOddSeqs2(spSrc,spDst,
10240,10240);

            now 
= stop2.Now();

            printf(”time4 
=%d\n”,now);

            CompareData(spDst,pSrcTest);

            memset(spDst,
0,10240<<1);

            CStopWatch stop3;

            
for(f = 0;f<100000; f++)

                        testClass.SplitToEvenOddSeqs3(spSrc,spDst,
10240,10240);

            now 
= stop3.Now();

            printf(”time5 
=%d\n”,now);

            CompareData(spDst,pSrcTest);

            
return 0;

}


注:其中CStopWatch是我写的用来计算时间的类。

如果把CompareData中访问spDst的代码注释掉,运行的结果:

Intel® Core™2 CPU 6400 2.13Ghz 1GB

time2 =753945 us

time3 =494852 us

time4 =0 us

time5 =0 us

Intel® Core™2 Duo CPU T7250 @2.00GHz 2.00 GHz 2GB

Time2 = 847431 us

Time3=523269 us

Time4=1 us

Time5 =1 us

Pentium® 4 CPU 2.6 GHz  512MB

Time2 = 613622 us

Time3=616545 us

Time4=1 us

Time5 =1 us

如果使用VC6编译,各种运行结果如下:

Intel® Core™2 CPU 6400 2.13Ghz 1GB

time2 =2041530 us

time3 =1352753 us

time4 =930849 us

time5 =501492 us

Intel® Core™2 Duo CPU T7250 @2.00GHz 2.00 GHz 2GB

time2 =1878766 ustime3 =1380009 ustime4 =959918 us

time5 =523022 us

Pentium® 4 CPU 2.6 GHz  512MB

time2 =2098438 us

time3 =1855219 us

time4 =1068678 us

time5 =610458 us

再把CompareData还原,在VC2005中编译,执行结果如下:

Intel® Core™2 CPU 6400 2.13Ghz 1GB

time2 =1007759 us

time3 =1364986 us

time4 =876046 us

time5 =437623 us

Intel® Core™2 Duo CPU T7250 @2.00GHz 2.00 GHz 2GB

time2 =1103970 ustime3 =1403941 ustime4 =630279 ustime5 =313330 us 

Pentium® 4 CPU 2.6 GHz  512MB

time2 =1218860 ustime3 =1743361 ustime4 =478785 us

time5 =241885 us

使用VC6重新编译:

Intel® Core™2 CPU 6400 2.13Ghz 1GB

time2 =2026392 us

time3 =1359155 us

time4 =946604 us

time5 =511307 us

Intel® Core™2 Duo CPU T7250 @2.00GHz 2.00 GHz 2GB

time2 =1921379 ustime3 =1410035 ustime4 =967616 ustime5 =528601 us 

Pentium® 4 CPU 2.6 GHz  512MB

time2 =2089173 ustime3 =1849719 ustime4 =1062956 ustime5 =610357 us 

当然这里有重复运算对算法的运行时间的影响;但考虑所有的算法都是对同样的内存操作,不考虑。那么我们发现的就是算法的效率提高是明显的。算法运行时间缩短为原来的1/31/4 

另外有几个问题需要在这里讨论一下:

1.演示了时间问题的同时,还看到一个奇怪的问题就是如果注释了CompareData,在VC2005上得到的后面两个算法的时间几乎为0。为什么?而VC6的编译没有这样的现象?

2.VC6上编译得到的结果与VC2005编译得到的结果相比,VC2005结果更好,为什么?(这个很弱智了)

3.我觉得程序还可以再优化,怎么样做?

欢迎大家就这个简单的优化问题,提出讨论。

posted on 2007-12-07 06:11 笨笨 阅读(2187) 评论(19)  编辑 收藏 引用 所属分类: 编码

评论

# re: 一段代码优化的讨论[未登录] 2007-12-07 08:28 cppexplore

根本原因要看编译器 优化 后的汇编代码
重构代码的出发点是可读性 可维护性 不是优化
系统性能依赖于设计阶段 之后就是关键算法 性能工具检测的性能瓶颈处了  回复  更多评论   

# re: 一段代码优化的讨论 2007-12-07 08:43 搞笑

搞笑,楼主连一点cache优化的意识都没有,却在加几次上面死磕,看来又是一个工作了3-4年的落伍人士,呵呵。  回复  更多评论   

# re: 一段代码优化的讨论 2007-12-07 09:08 笨笨

@搞笑
说的很好!看来你没有把文章看完。  回复  更多评论   

# re: 一段代码优化的讨论 2007-12-07 09:10 笨笨

@cppexplore
你的出发点我很赞同,就是算法的优劣比优化要好前百倍。
我这里的例子你也看到了,是一个非常简单的问题,好比memcpy或strcpy
所以这里算法的改进,以我的笨眼来看,应该没有什么余地了。
这里只是讨论一点优化的知识;我首先告诉大家,我是初学这个方面的人。  回复  更多评论   

# re: 一段代码优化的讨论 2007-12-07 09:16 笨笨

我希望大家能够给出一些真正的意见和想法,或者是代码来让这段代码运行的更快。这也是我的发这个贴的目的。

也希望大家可以了解到有的应该可以跑的比我们想像的快。
我不想得到一些无聊的建议或话。
谢谢!  回复  更多评论   

# re: 一段代码优化的讨论 2007-12-07 09:17 LouixG

你应该看看自己优化代码的汇编,你在文中说了一些读和写的计数,不知你是否是看了汇编后得出的结论。不同的编译器优化的结果也不一样,你用Intel的编译器试试,效果应该会更好。
我想到一些优化办法:
1,循环展开;
2,多线程;//这两个是高级语言代码优化,下面是面向特定机器的指令优化。
3,利用更强的单指令数据操纵能力:如果目标机器是32位,可以用浮点指令fld和fstp装载64位数据;如果目标机器是64位的那么可以直接使用64位寄存器;
4,利用SSE指令,SSE指令集对应的寄存器提供最多128位数据宽度;
5,如果你的目标机器不是兼容机而是PowerPC、SPARC或者嵌入式的架构,那推荐你查阅对应的CPU手册,在指令层次上寻找突破。

  回复  更多评论   

# re: 一段代码优化的讨论 2007-12-07 09:50 笨笨

@LouixG
谢谢。应该看出来是这方面的高手,希望多指点。
想得到一点建议就是:程序性能优化如何才能入门?  回复  更多评论   

# re: 一段代码优化的讨论 2007-12-07 11:46 梦在天涯

看了大家的回复,深有感触啊,

非常高兴可以看到C++ Blog这里聚集了越来越多的高手!

  回复  更多评论   

# re: 一段代码优化的讨论[未登录] 2007-12-07 12:35 cppexplore

@搞笑
这样说就不对了 文章写出来 大家share下 目的是互补长短 互相交流 互相进步
@笨笨
从本文中例子来说 这种“优化”,可读性更好,更好维护。的确是正确的。这种差异不是算法的造成的,是开始设计的不合理。另,我的建议真的不是无聊的建议 :)。
@LouixG
(1)展开循环的点滴性能不是问题
(2)多线程模型的目的一般系统设计层面的吧,主要是提高系统的吞吐能力,这种问题上的性能远远谈不上
(3)后面的问题带来移植性的问题,非底层的关键算法 也不会有人去做这种优化
@梦在天涯
blog里的文章真是多啊

@me
废话真多。。。。。。  回复  更多评论   

# re: 一段代码优化的讨论 2007-12-07 13:57 LouixG

@cppexplore
每种优化可能只提高很小的性能,但为了达到极致把这些方法综合就能产生质的飞跃。优化也分算法优化和代码优化,我的想法就是在楼主算法确定的情况下最大可能的优化实现代码。
提到多线程主要是为了利用多核,但小数据量不推荐多线程,提到多核就多说点,在多核上跑得快的代码不一定在单核上跑的好,请看代码:
int * src1 = src;
int * src2 = src + 1;
int * dst1 = dst;
int * dst2 = dst + 1;
while ( ... )
{
*dst1 = *src1;
*dst2 = *src2;
dst1 += 2;
dst2 += 2;
src1 += 2;
src2 += 2;
};
这个代码可以肯定在单核上跑得很烂,但是在多核上dst1和dst2被流水线确定为无关变量,不相互影响就会被双核同时执行,这样就比单核上跑得快。

在指令层面上思考优化不一定带来移植性问题,例如这段代码:
double * src_opt = ( ( double * ) src ) - 1;
double * dst_opt = ( ( double * ) dst ) - 1;
int src_ind = 0;
int dst_ind = 0;
int loop_time = ( src_len >> 1 ) + 1;
while ( --loop_time )
{
dst_opt[ ++dst_ind ] = src_opt[ ++src_ind ];
}
Intel编译器产生的while循环的汇编:
$B68$3:
add edx, 1
fld QWORD PTR [edi+edx*8-8]
add eax, 1
fstp QWORD PTR [esi+eax*8-8]
add ecx, -1
jne $B68$3
这样的代码可以在兼容机上编译+运行无阻,且不说前两个add可被替换inc获得一定效率提升,我相信这段代码要比楼主的代码快。

只有有没有人做这样的工作就仁者见仁了,肯定有需要这种工作的时候。  回复  更多评论   

# re: 一段代码优化的讨论 2007-12-07 14:22 金庆

怎么会 0 us? 计时有问题吧?
time4 =0 us
time5 =0 us

看代码
printf(”time5 =%d\n”,now);
没有打印"us". 应该保持代码与结果的一致.

即然输出与输出的内存结构一致,直接用memcpy就行了,不必循环赋值.  回复  更多评论   

# re: 一段代码优化的讨论[未登录] 2007-12-07 14:55 cppexplore

@LouixG
(1)这个问题不敢妄言,多核下编程重来没有接触过。不知道这种各个cpu的分配,是在编译期间由编译器完成的,还是在运行期间由额外的硬件决定把指令分配给某个cpu的?这种多核下的编程,值得探讨的问题就多了,尤其这种在一个线程内的数据被分配到多个cpu,如果真有这种情况,估计以后会有语言层面的东西支持。不同线程分配不同的cpu,这个到还好。
(2)这个例子的高性能我丝毫不怀疑,通过字节对齐提高性能。其实标准库函数也是这么做的。不过这个例子没意义啊,直接使用库函数就好。  回复  更多评论   

# re: 一段代码优化的讨论 2007-12-07 16:22 笨笨

感谢大家的回复
我没有说cppexplore说的是无聊的啊。

大家说的都很好。
我这段代码只是我自己在随便看了两片文章后对我以前一段代码进行的优化;这里面仅仅是用到了几点:
1.合并同时访问的两个数组
2.使用多字节复制
3.替换比较而用减法
4.减少指令的数目

实际上我正学习这方面的编程,没有想到这里竟然一下子碰到两个高手啊,这么不见你们的BLOG?

另外,我看到一个比系统的memcpy写的还要快的内存复制函数,大家不妨看一下:
http://www.vik.cc/daniel/portfolio/memcpy.htm  回复  更多评论   

# re: 一段代码优化的讨论 2007-12-07 16:24 笨笨

碰到二位强人真是我的幸运,希望能得到多多指点。  回复  更多评论   

# re: 一段代码优化的讨论 2007-12-07 17:04 haskell

如果是为优化而优化,那就管不了那么多了
void haha(short *sp,short *dp1,short *dp2,int count)
{
switch (count % 8) {
case 0: do { *dp1++ = *sp++;
case 7: *dp2++ = *sp++;
case 6: *dp1++ = *sp++;
case 5: *dp2++ = *sp++;
case 4: *dp1++ = *sp++;
case 3: *dp2++ = *sp++;
case 2: *dp1++ = *sp++;
case 1: *dp2++ = *sp++;
} while ((count -= 8) > 0);
}
}
可对for语句优化,看有帮助没^_^能编译的  回复  更多评论   

# re: 一段代码优化的讨论 2007-12-07 19:20 空明流转

最近在写一个软件渲染器,流水线还没通,哪管他优不优化。。。

大量的std::vector。。。等流水通了把Shader Register改成boost::array,再加上一个pool应该会快不少吧。反正debug下渲染一个512 * 512的要好几秒时间。。。  回复  更多评论   

# re: 一段代码优化的讨论 2007-12-08 01:39 笨笨

@haskell
你这个这么多的条件分支,CPU命中率不是很低???  回复  更多评论   

# re: 一段代码优化的讨论 2007-12-08 01:59 haskell

忘了这个方法叫什么了?
不会慢的  回复  更多评论   

# re: 一段代码优化的讨论 2007-12-12 11:14 no name

haskell的方法叫 达夫设备Duff's Device,google可找到更多解释。注意其中每个case都特意少了break,使用了switch的fall though特性。  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理