C优化篇之减少运算量

Tags: c语言

程序优化的另一个出发点是减少运行过程中的运算量,有两个大的思路:

1)把部分计算量转移到离线,或者说把一部分工作挪到程序之外,人为处理,以减轻程序本身压力。比如查表、浮点转定点以及其他数学算法的优化等。

2)分析和剔除代码中的多余水分,由于编译器能把一些简单的无效语句剔除,所以程序员可以做文章的地方一般就是循环体。

查表

有些算法输入有限离散整数,输出固定的数据集合,这种模块本质只是提供一个有限数据集或者说常量数组,在程序里现场计算完全是浪费CPU资源,完全可以事先算好,形成数据表放在内存数据区,运行中只要查表而无需计算,是一种空间换时间的策略。如:

long factorial(int i)

{

if (i == 0) { return 1; }

else { return i * factorial(i - 1); }

}

新代码:

static long factorial_table[] = {1, 1, 2, 6, 24, 120, 720 /* etc */ };

long factorial(int i)

{

return factorial_table[i];

}

浮点转定点

很多CPU没有专门针对浮点运算的硬件,而是通过软件库模拟浮点运算,效率非常低。如果程序中有大量浮点运算,应该用定点替代。基本原理是,确定某运算模块的浮点输入数据集的范围,在此基础上缩放2Q,把浮点数缩放为定点整数,然后进行整数运算,之后再把结果重新转换回浮点。简单说:

float Mod1(float x, float y)

{

float z;

//系列x,y的浮点运算,得到结果z

return z;

}

假设x,y 的数据集范围都在[0.125,1 ],函数可大体改成

float Mod1(float x, float y)

{

int ix =(int)x*8;

int iy=(int)y*8;

int iz;

//系列 ix,iy的整数运算得到结果iz

return (float )iz/float(8*8);

}

这一过程的原理在DSP资料中有详细论述,关键在于为不同模块的浮点运算确定合适的小数点变换位置,使变换后的运算既不溢出整数范围,又能保持足够精度,即所谓合理定标。这部分内容大家可自行查阅参考相关资料?。

循环优化

循环往往是profiler工具标识的程序计算集中的“热点”,因而是软件优化的重点对象,着眼点包括:

a. 优化计数器访问

C的while /for循环中都需要一个计数器(counter),这个counter最好设计成递减到零,而不要用递增计数,两个原因:一是与0做比较的判断指令在某些芯片(ARM)中附加在算术运算指令之后,合2条指令为1条,这样每次递减循环少用一条判断指令(参考ARM汇编);二是递减循环不必保存counter的最大极限值,如果这个极限值是一个变量,那么用递增计数就要多占用一个寄存器。

b.把循环内的重复运算提取到循环之外

仔细观察,把循环内部确定的分支或计算提到循环外,以消除重复,如:

for(i=0; i

if (n== 0) a(i) = a(i) + b(i) * c ;

else a(i) = 0;

}

这里n是否为0的判断和循环内其它运算没有关系,没必要每次重复判断,可改为:

if (n == 0) {

for(i = 0;i

}else{

for(i= 0;i

}

代码似乎多了,但执行效率要高,再比如:

int GetCRC(char *instr)

{

int a;

int x = -1;

for(a = 0; a

return x;

}

strlen是一个函数,编译器根据已有条件并不知道strlen结果始终不变,所以会笨笨的重复计算。很明显应增加一个局部变量int b,在for循环前计算b=strlen(instr),把循环变为for(a=0;a

c.循环展开

循环展开可以减小循环次数,降低循环判断的开销。如: for(i=0; i

这个循环内部运算很简单,但每次i

temp = temp*(array[0]);

......

temp = temp*(array[99]);

这样展开虽然看上去把原来两句话增加到100句,但实际可以减少100条判断指令。

再举例有一幅24位真色彩图像,每像素包含R、G和B三分量,RGB分量各占8位,在0~255间取值。下面函数实现图像取反色,即每像素每分量都被255减。

void NegPixel(Uint8* InPixel, Uint8 *OutPixel, int Width, int Height)

{

int sum = Width * Height * 3;

for(int i=0;i

}

循环体中的i

void NegPixel (Uint8 * InPixel, Uint8 * OutPixel,int Width, int Height)

{

int sum = Width * Height ;

for(int i =0;i

{

OutPixel[i]=255-InPixel[i];

OutPixel[i+1]=255-InPixel[i+1];

OutPixel[i+2]=255-InPixel[i+2];

}

}

循环次数变为原来三分之一,减少了2*sum/3个条件判断指令,这种部分展开能兼顾优化和代码密度。那如果循环次数是变量或某素数,怎么部分展开呢?首先确保第一次循环不超过数组边界,如原先循环长度为n,展开3次,可将循环限制设为n-2,使循环体内数组最大索引不超过数组长度n。如:

void function(int array[],int *dest, int len)

{

int temp=1;

for(int i=0;i

*dest = temp;

}

展开为

void function(int array[],int *dest, int len)

{

int temp=1;

int limit=len-2;

for(int i=0;i

for(; i

*dest = temp;

}

所以如果循环展开k次,就把上限设为n-k+1,最大循环索引将会比n小,最后再处理掉余下的最后几个元素。

不过天下没有免费的午餐,循环展开固然能降低分支判断的开销,却会增加代码量,所以最优展开位置要具体分析。且还要注意,在有指令cache的CPU上,如果循环展开后代码超出cache line,展开代码可能导致cache miss,因此这时展开循环有可能反而变慢。另外一些编译器在优化级别足够高时会自动展开循环。所以是否要手工展开也要具体情况具体分析。

本文链接:http://www.4byte.cn/learning/53386.html