在本篇文章中,我收集了很多经验和方法。应用这些经验和方法,可以帮助我们从执行速度和内存使用等方面来优化C语言代码。
  简介
  在近的一个项目中,我们需要开发一个运行在移动设备上但不保证图像高质量的轻量级JPEG库。期间,我总结了一些让程序运行更快的方法。在本篇文章中,我收集了一些经验和方法。应用这些经验和方法,可以帮助我们从执行速度和内存使用等方面来优化C语言代码。
  尽管在C代码优化方面有很多的指南,但是关于编译和你使用的编程机器方面的优化知识却很少。
  通常,为了让你的程序运行的更快,程序的代码量可能需要增加。代码量的增加又可能会对程序的复杂度和可读性带来不利的影响。这对于在手机、PDA等对于内存使用有很多限制的小型设备上编写程序时是不被允许的。因此,在代码优化时,我们的座右铭应该是确保内存使用和执行速度两方面都得到优化。
  声明
  实际上,在我的项目中,我使用了很多优化ARM编程的方法(该项目是基于ARM平台的),也使用了很多互联网上面的方法。但并不是所有文章提到的方法都能起到很好的作用。所以,我对有用的和高效的方法进行了总结收集。同时,我还修改了其中的一些方法,使他们适用于所有的编程环境,而不是局限于ARM环境。
  哪里需要使用这些方法?
  没有这一点,所有的讨论都无从谈起。程序优化重要的是找出待优化的地方,也是找出程序的哪些部分或者哪些模块运行缓慢亦或消耗大量的内存。只有程序的各部分经过了优化,程序才能执行的更快。
  程序中运行多的部分,特别是那些被程序内部循环重复调用的方法该被优化。
  对于一个有经验的码农,发现程序中需要被优化的部分往往很简单。此外,还有很多工具可以帮助我们找出需要优化的部分。我使用过Visual C++内置的性能工具profiler来找出程序中消耗多内存的地方。另一个我使用过的工具是英特尔的Vtune,它也能很好的检测出程序中运行慢的部分。根据我的经验,内部或嵌套循环,调用第三方库的方法通常是导致程序运行缓慢的主要的起因。
  整形数
  如果我们确定整数非负,应该使用unsigned int而不是int。有些处理器处理无符号unsigned 整形数的效率远远高于有符号signed整形数(这是一种很好的做法,也有利于代码具体类型的自解释)。
  因此,在一个紧密循环中,声明一个int整形变量的好方法是:
  register unsigned int variable_name;
  记住,整形in的运算速度高浮点型float,并且可以被处理器直接完成运算,而不需要借助于FPU(浮点运算单元)或者浮点型运算库。尽管这不保证编译器一定会使用到寄存器存储变量,也不能保证处理器处理能更高效处理unsigned整型,但这对于所有的编译器是通用的。
  例如在一个计算包中,如果需要结果精确到小数点后两位,我们可以将其乘以100,然后尽可能晚的把它转换为浮点型数字。
  除法和取余数
  在标准处理器中,对于分子和分母,一个32位的除法需要使用20至140次循环操作。除法函数消耗的时间包括一个常量时间加上每一位除法消耗的时间。
  Time (numerator / denominator) = C0 + C1* log2 (numerator / denominator)
  = C0 + C1 * (log2 (numerator) - log2 (denominator)).
  对于ARM处理器,这个版本需要20+4.3N次循环。这是一个消耗很大的操作,应该尽可能的避免执行。有时,可以通过乘法表达式来替代除法。例如,假如我们知道b是正数并且b*c是个整数,那么(a/b)>c可以改写为a>(c*b)。如果确定操作数是无符号unsigned的,使用无符号unsigned除法更好一些,因为它比有符号signed除法效率高。
  合并除法和取余数
  在一些场景中,同时需要除法(x/y)和取余数(x%y)操作。这种情况下,编译器可以通过调用一次除法操作返回除法的结果和余数。如果既需要除法的结果又需要余数,我们可以将它们写在一起,如下所示:
  int func_div_and_mod (int a, int b) {
  return (a / b) + (a % b);
  }
  通过2的幂次进行除法和取余数
  如果除法中的除数是2的幂次,我们可以更好的优化除法。编译器使用移位操作来执行除法。因此,我们需要尽可能的设置除数为2的幂次(例如64而不是66)。并且依然记住,无符号unsigned整数除法执行效率高于有符号signed整形出发。
  typedef unsigned int uint;
  uint div32u (uint a) {
  return a / 32;
  }
  int div32s (int a){
  return a / 32;
  }
  上面两种除法都避免直接调用除法函数,并且无符号unsigned的除法使用更少的计算机指令。由于需要移位到0和负数,有符号signed的除法需要更多的时间执行。
  取模的一种替代方法
  我们使用取余数操作符来提供算数取模。但有时可以结合使用if语句进行取模操作。考虑如下两个例子:
  uint modulo_func1 (uint count)
  {
  return (++count % 60);
  }
  uint modulo_func2 (uint count)
  {
  if (++count >= 60)
  count = 0;
  return (count);
  }
  优先使用if语句,而不是取余数运算符,因为if语句的执行速度更快。这里注意新版本函数只有在我们知道输入的count结余0至59时在能正确的工作。
  使用数组下标
  如果你想给一个变量设置一个代表某种意思的字符值,你可能会这样做:
  switch ( queue ) {
  case 0 :   letter = 'W';
  break;
  case 1 :   letter = 'S';
  break;
  case 2 :   letter = 'U';
  break;
  }
  或者这样做:
  if ( queue == 0 )
  letter = 'W';
  else if ( queue == 1 )
  letter = 'S';
  else
  letter = 'U';
  一种更简洁、更快的方法是使用数组下标获取字符数组的值。如下:
  static char *classes="WSU";
  letter = classes[queue];
  全局变量
  全局变量绝不会位于寄存器中。使用指针或者函数调用,可以直接修改全局变量的值。因此,编译器不能将全局变量的值缓存在寄存器中,但这在使用全局变量时便需要额外的(常常是不必要的)读取和存储。所以,在重要的循环中我们不建议使用全局变量。
  如果函数过多的使用全局变量,比较好的做法是拷贝全局变量的值到局部变量,这样它才可以存放在寄存器。这种方法仅仅适用于全局变量不会被我们调用的任意函数使用。例子如下:
  int f(void);
  int g(void);
  int errs;
  void test1(void)
  {
  errs += f();
  errs += g();
  }
  void test2(void)
  {
  int localerrs = errs;
  localerrs += f();
  localerrs += g();
  errs = localerrs;
  }
  注意,test1必须在每次增加操作时加载并存储全局变量errs的值,而test2存储localerrs于寄存器并且只需要一个计算机指令。
  使用别名
  考虑如下的例子:
  void func1( int *data )
  {
  int i;
  for(i=0; i<10; i++)
  {
  anyfunc( *data, i);
  }
  }
  尽管*data的值可能从未被改变,但编译器并不知道anyfunc函数不会修改它,所以程序必须在每次使用它的时候从内存中读取它。如果我们知道变量的值不会被改变,那么应该使用如下的编码:
  void func1( int *data )
  {
  int i;
  for(i=0; i<10; i++)
  {
  anyfunc( *data, i);
  }
  }
  这为编译器优化代码提供了条件。
  变量的生命周期分割
  由于处理器中寄存器是固定长度的,程序中数字型变量在寄存器中的存储是有一定限制的。
  有些编译器支持“生命周期分割”(live-range splitting),也是说在程序的不同部分,变量可以被分配到不同的寄存器或者内存中。变量的生命周期开始于对它进行的后一次赋值,结束于下次赋值前的后一次使用。在生命周期内,变量的值是有效的,也是说变量是活着的。不同生命周期之间,变量的值是不被需要的,也是说变量是死掉的。这样,寄存器可以被其余变量使用,从而允许编译器分配更多的变量使用寄存器。
  需要使用寄存器分配的变量数目需要超过函数中不同变量生命周期的个数。如果不同变量生命周期的个数超过了寄存器的数目,那么一些变量必须临时存储于内存。这个过程称之为分割。
  编译器首先分割近使用的变量,用以降低分割带来的消耗。禁止变量生命周期分割的方法如下:
  限定变量的使用数量:这个可以通过保持函数中的表达式简单、小巧、不使用太多的变量实现。将较大的函数拆分为小而简单的函数也会达到很好的效果。
  对经常使用到的变量采用寄存器存储:这样允许我们告诉编译器该变量是需要经常使用的,所以需要优先存储于寄存器中。然而,在某种情况下,这样的变量依然可能会被分割出寄存器。
  变量类型
  C编译器支持基本类型:char、short、int、long(包括有符号signed和无符号unsigned)、float和double。使用正确的变量类型至关重要,因为这可以减少代码和数据的大小并大幅增加程序的性能。
  局部变量
  我们应该尽可能的不使用char和short类型的局部变量。对于char和short类型,编译器需要在每次赋值的时候将局部变量减少到8或者16位。这对于有符号变量称之为有符号扩展,对于无符号变量称之为零扩展。这些扩展可以通过寄存器左移24或者16位,然后根据有无符号标志右移相同的位数实现,这会消耗两次计算机指令操作(无符号char类型的零扩展仅需要消耗一次计算机指令)。
  可以通过使用int和unsigned int类型的局部变量来避免这样的移位操作。这对于先加载数据到局部变量,然后处理局部变量数据值这样的操作非常重要。无论输入输出数据是8位或者16位,将它们考虑为32位是值得的。
  考虑下面的三个函数:
  int wordinc (int a)
  {
  return a + 1;
  }
  short shortinc (short a)
  {
  return a + 1;
  }
  char charinc (char a)
  {
  return a + 1;
  }
  尽管结果均相同,但是第一个程序片段运行速度高于后两者。
  指针
  我们应该尽可能的使用引用值的方式传递结构数据,也是说使用指针,否则传递的数据会被拷贝到栈中,从而降低程序的性能。我曾见过一个程序采用传值的方式传递非常大的结构数据,然后这可以通过一个简单的指针更好的完成。
  函数通过参数接受结构数据的指针,如果我们确定不改变数据的值,我们需要将指针指向的内容定义为常量。例如:
  void print_data_of_a_structure ( const Thestruct  *data_pointer)
  {
  ...printf contents of the structure...
  }
  这个示例告诉编译器函数不会改变外部参数的值(使用const修饰),并且不用在每次访问时都进行读取。同时,确保编译器限制任何对只读结构的修改操作从而给予结构数据额外的保护。
  指针链
  指针链经常被用于访问结构数据。例如,常用的代码如下:
  typedef struct { int x, y, z; } Point3;
  typedef struct { Point3 *pos, *direction; } Object;
  void InitPos1(Object *p)
  {
  p->pos->x = 0;
  p->pos->y = 0;
  p->pos->z = 0;
  }
  然而,这种的代码在每次操作时必须重复调用p->pos,因为编译器不知道p->pos->x与p->pos是相同的。一种更好的方法是缓存p->pos到一个局部变量:
  void InitPos2(Object *p)
  {
  Point3 *pos = p->pos;
  pos->x = 0;
  pos->y = 0;
  pos->z = 0;
  }
  另一种方法是在Object结构中直接包含Point3类型的数据,这能完全消除对Point3使用指针操作。
  条件执行
  条件执行语句大多在if语句中使用,也在使用关系运算符(等)或者布尔值表达式(&&,!等)计算复杂表达式时使用。对于包含函数调用的代码片段,由于函数返回值会被销毁,因此条件执行是无效的。
  因此,保持if和else语句尽可能简单是十分有益处的,因为这样编译器可以集中处理它们。关系表达式应该写在一起。
  下面的例子展示编译器如何使用条件执行:
  int g(int a, int b, int c, int d)
  {
  if (a > 0 && b > 0 && c < 0 && d < 0)
  // grouped conditions tied up together//
  return a + b + c + d;
  return -1;
  }
  由于条件被聚集到一起,编译器能够将他们集中处理。
  布尔表达式和范围检查
  一个常用的布尔表达式是用于判断变量是否位于某个范围内,例如,检查一个图形坐标是否位于一个窗口内:
  bool PointInRectangelArea (Point p, Rectangle *r)
  {
  <span class="hljs-keyword">return</span> (p.x &gt;= r-&gt;xmin &amp;&amp; p.x &lt; r-&gt;xmax &amp;&amp;
  p.y &gt;= r-&gt;ymin &amp;&amp; p.y &lt; r-&gt;ymax);
  }
  这里有一种更快的方法:x>min && x
  bool PointInRectangelArea (Point p, Rectangle *r)
  {
  return ((unsigned) (p.x - r->xmin) < r->xmax &&
  (unsigned) (p.y - r->ymin) < r->ymax);
  }
  布尔表达式和零值比较
  处理器的标志位在比较指令操作后被设置。标志位同样可以被诸如MOV、ADD、AND、MUL等基本算术和裸机指令改写。如果数据指令设置了标志位,N和Z标志位也将与结果与0比较一样进行设置。N标志表示结果是否是负值,Z标志表示结果是否是0。
  C语言中,处理器中的N和Z标志位与下面的指令联系在一起:有符号关系运算x=0,x==0,x!=0;无符号关系运算x==0,x!=0(或者x>0)。
  C代码中每次关系运算符的调用,编译器都会发出一个比较指令。如果操作符是上面提到的,编译器便会优化掉比较指令。例如:
  int aFunction(int x, int y)
  {
  if (x + y < 0)
  return 1;
  else
  return 0;
  }
  尽可能的使用上面的判断方式,这可以在关键循环中减少比较指令的调用,进而减少代码体积并提高代码性能。C语言没有借位和溢出位的概念,因此,如果不借助汇编,不可能直接使用借位标志C和溢出位标志V。但编译器支持借位(无符号溢出),例如:
  int sum(int x, int y)
  {
  int res;
  res = x + y;
  if ((unsigned) res < (unsigned) x) // carry set?  //
  res++;
  return res;
  }
  懒检测开发
  在if(a>10 && b=4)这样的语句中,确保AND表达式的第一部分可能较快的给出结果(或者早、快计算),这样第二部分便有可能不需要执行。
  用switch()函数替代if…else…
  对于涉及if…else…else…这样的多条件判断,例如:
  if( val == 1)
  dostuff1();
  else if (val == 2)
  dostuff2();
  else if (val == 3)
  dostuff3();
  使用switch可能更快:
  switch( val )
  {
  case 1: dostuff1(); break;
  case 2: dostuff2(); break;
  case 3: dostuff3(); break;
  }
  在if()语句中,如果后一条语句命中,之前的条件都需要被测试执行一次。Switch允许我们不做额外的测试。如果必须使用if…else…语句,将可能执行的放在前面。
  二分中断
  使用二分方式中断代码而不是让代码堆成一列,不要像下面这样做:
  if(a==1) {
  } else if(a==2) {
  } else if(a==3) {
  } else if(a==4) {
  } else if(a==5) {
  } else if(a==6) {
  } else if(a==7) {
  } else if(a==8)
  {
  }
  使用下面的二分方式替代它,如下:
  if(a<=4) {
  if(a==1)     {
  }  else if(a==2)  {
  }  else if(a==3)  {
  }  else if(a==4)   {
  }
  }
  else
  {
  if(a==5)  {
  } else if(a==6)   {
  } else if(a==7)  {
  } else if(a==8)  {
  }
  }
  或者如下:
if(a<=4)
{
if(a<=2)
{
if(a==1)
{
/* a is 1 */
}
else
{
/* a must be 2 */
}
}
else
{
if(a==3)
{
/* a is 3 */
}
else
{
/* a must be 4 */
}
}
}
else
{
if(a<=6)
{
if(a==5)
{
/* a is 5 */
}
else
{
/* a must be 6 */
}
}
else
{
if(a==7)
{
/* a is 7 */
}
else
{
/* a must be 8 */
}
}
}
  比较如下两种case语句:
  慢而低效的代码快而高效的代码
c=getch();
switch(c){
case 0:
{
do something;
break;
}
case 1:
{
do something;
break;
}
case 2:
{
do something;
break;
}
}