登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

我的博客

生命的意义在于延伸你的轨迹......

 
 
 

日志

 
 

编写高效的C代码  

2009-02-12 13:22:51|  分类: C语言程序编写 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
编写高效的C代码(一) (2006-07-12 16:42:10)
  分类:软件

编写高效的C代码
原文标题:Writing Efficient C and C Code Optimization
原文地址:http://www.codeproject.com/cpp/C___Code_Optimization.asp
原文作者:Koushik Ghosh
译文作者:zhigang

前言
    前段时间,我开发了一个轻量级的JPEG库,用来在某种移动设备上不失真地显示图像。我注意到一些技巧可以使程序运行的更快。在这篇文章里,我收集和整理了所有的这些方法,用来在运行速度和内存占用方面对C代码进行优化。
    尽管编写C代码,已经有了许多指导原则可以参考,但这并不表示你已经彻底的了解你正在使用的编译器和CPU。
    经常的,为了使代码运行的更快,会导致代码长度的增加,所谓以空间换时间,但是代码长度的增加有一种负面作用就是使程序的复杂度增加、可读性减弱。尤其是 当你的程序最终运行环境是手机、PDA之类的对内存要求比较苛刻的设备的时候,这将会是不可接受的。所以,我们优化的宗旨就是使程序在内存占用和运行速度 两个方面都要得到优化。

声明
    实际上,在我的那个项目中,我使用了ARM公司的一篇文章中提到的技巧,因为我的程序是基于ARM平台的,你可以从这里http://www.arm.com/pdfs/DAI0034A_efficient_c.pdf取得这篇文章,我也从Internet上收集了许多其它的文章。但并不是每篇文章中提到的所有技巧都有用,所以,在这里,我只收集了有用且有效的,还有,我修改了其中的一些技巧使它几乎适用于所有情况,而不仅仅是ARM。
    我所作的工作只是将各个站点的技巧收集到一起,尤其是我在上面提到的那个PDF文件,我从来没有说过这些技巧使我自己的发明。在本文末尾的参考文献部分,我罗列了所有技巧的来源。

哪里需要优化
    没有这一点,所有的讨论都无从谈起。首先也是最重要的是要找出哪里需要优化,程序的那一部分或者那个模块运行速度慢或者使用大量内存。程序的每个部分都被分别优化,自然而然的整个程序又会变得运行的比较快了。
    优化应该主要针对程序中最经常运行的部分,尤其是被内部循环反复调用的函数。
    一个经验丰富的程序员会很容易找出程序中需要着重优化的部分,另外,还有许多工具可以用来确定这些部分。我曾经用Visual C++ 的IDE内建的Profiler,另外一个我用过的工具是Intel Vtune,这是一个非常好用的Profiler,都可以用来寻找程序中最费时的地方。以我的经验来看,导致程序运行速度慢得罪魁祸首可能就是某个内部或嵌套循环,也可能是对第三方库函数的调用。

整型数 / Integers
  如果一个变量的取值范围是非负的,我们应该使用unsigned int,而不是int。一些处理器在处理无符号整型数要比处理符号整型数快得多,这也是一个好的习惯,有利于代码的自我文档化(self-documenting)。
  那么,在一个小循环(tight loop)中,定义一个整型变量,最好类似这样:
register unsigned int variable_name;
然而,我们不能保证编译器会注意到那个register关键字,也有可能,对某种处理器来说,有没有unsigned是一样的。这两个关键字并不是可以在所有的编译器中应用。
记住,整形数运算要比浮点数运算快得多,因为处理器可以直接进行整型数运算,浮点数运算需要依赖于外部的浮点数处理器或者浮点数数学库。
我们处理小数的时候要精心些,比方说我们在做一个简单的统计程序时,要限制结果不能超过100,要尽可能晚的把它转化成浮点数。

除法和余数 / Division and Remainder
  在一般的处理器中,根据分子和分母的不同,一个32位的除法需要20-140个时钟周期,等于一个固定的时间加上每个位被除的时间。
Time (分子/ 分母) = C0 + C1* log2 (分子/分母)
      = C0 + C1 * (log2 (分子) - log2 (分母)).
  现在的ARM处理器需要消耗20+4.3N个时钟周期,这是一个非常费时的操作,要尽可能的避免。在有些情况下,除法表达式可以用乘法表达是来重写。 比方说,(a/b)>c可以写成a>(c*b),条件是我们已经知道b为非负数而且b*c不会超过整型数的取值范围。如果我们能够确定其中的 一个操作数为unsigned,那么使用无符号除法将会更好,因为它要比有符号除法快得多。

合并除法运算和取余运算 / Combining division and remainder
  在一些情况下,除法运算和取余运算都需要用到,在这种情况下,编译器会将除法运算和取余运算合并,因为除法运算总是同时返回商和余数。如果两个运算都要用到,我们可以将他们写到一起(译者:不要细究下面的代码的含义,只是阐述写到“一起”)
int func_div_and_mod (int a, int b) {
        return (a / b) + (a % b);
    }

除数是2的幂的除法和取余 / Division and remainder by powers of two
  如果除法运算中的除数是2的幂,我们对这个除法运算还可以进一步优化,编译器会使用移位运算来进行这种除法运算。所以,我们要尽可能缩放比例为2的幂(比方说要用64而不用66)。如果是无符号数,它要比有符号的快得多。
    typedef unsigned int uint;
    uint div32u (uint a) {
     return a / 32;
    }
    int div32s (int a){
     return a / 32;
    }
这两个除法都会避免调用除法函数,另外,无符号的除法要比有符号的除法使用更少的指令。有符号的除法要耗费更多的时间,因为除法是使最终结果趋向于零的,而移位则是趋向于负无穷。

取模运算的变通 / An alternative for modulo arithmetic
    我们一般使用取余运算进行取模,不过,有时候使用if语句也是可行的。考虑下面的两个例子:
    uint modulo_func1 (uint count)
    {
       return (++count % 60);
    }
    uint modulo_func2 (uint count)
    {
       if (++count >= 60)
      count = 0;
      return (count);
    }
第二个例子要比第一个更可取,因为由它产生的代码会更快,注意:这只是在count取值范围在0 – 59之间的时候才行。

使用数组索引 / Using array indices
    假设你要依据某个变量的值,设置另一个变量的取值为特定的字符,你可能会这样做:
    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];

全局变量 / Global variables
    全局变量不会被分配在寄存器上,修改全局变量需要通过指针或者调用函数的方式间接进行。所以编译器不会将全局变量存储在寄存器中,那样会带来额外的、不必要的负担和存储空间。所以在比较关键的循环中,我们要不使用全局变量。
如果一个函数要频繁的使用全局变量,我们可以使用局部变量,作为全局变量的拷贝,这样就可以使用寄存器了。条件是本函数调用的任何子函数不使用这些全局变量。
举个例子:
    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分配在寄存器上,只需要一条指令。

使用别名 / Using Aliases
考虑下面的例子:
    void func1( int *data )
    {
        int i;
        for(i=0; i<10; i++)
        {
              anyfunc( *data, i);
        }
    }
即使*data从来没有变化,编译器却不知道anyfunc()没有修改它,于是程序每次用到它的时候,都要把它从内存中读出来,可能它只是某些变量的别名,这些变量在程序的其他部分被修改。如果能够确定它不会被改变,我们可以这样写:
    void func1( int *data )
    {
        int i;
        int localdata;
        localdata = *data;
        for(i=0; i<10; i++)
        {
              anyfunc ( localdata, i);
        }
    }
这样会给编译器优化工作更多的选择余地。

活的变量和泄漏 / Live variables and spilling
    寄存器的数量在每个处理器当中都是固定的,所以在程序的某个特定的位置,可以保存在寄存器中的变量的数量是有限制的。
    有些编译器支持“生命周期分割”(live-range splitting),也就是说在程序的不同部分,变量可以被分配到不同的寄存器或者内存中。变量的生命范围被定义成,起点是对该变量的一次空间分配,终 点是在下次空间分配之前的最后一次使用之间。在这个范围内,变量的值是合法的,是活的。在生命范围之外,变量不再被使用,是死的,它的寄存器可以供其他变 量使用,这样,编译器就可以安排更多的变量到寄存器当中。
可分配到寄存器的变量需要的寄存器数量等于经过生命范围重叠的变量的数目,如果这个数目超过可用的寄存器的数量,有些变量就必须被暂时的存储到内存中。这种处理叫做“泄漏(spilling)”。
    编译器优先泄漏最不频繁使用的变量,将泄漏的代价降到最低。可以通过以下方式避免变量的“泄漏”:
? 限制活变量的最大数目:通常可以使用简单小巧的表达式,在函数内部不使用太多的变量。把大的函数分割成更加简单的、更加小巧的多个函数,也可能会有所帮助。
? 使用关键字register修饰最经常使用的变量:告诉编译器这个变量将会被经常用到,要求编译器使用非常高的优先级将此变量分配到寄存器中。尽管如此,在某些情况下,变量还是可能被泄漏。

变量类型 / Variable Types
    C编译器支持基本的变量类型:char、short、int、long(signed、unsigned)、float、double。为变量定义最恰当的类型,非常重要,因为这样可以减少代码和数据的长度,可以非常显著的提高效率。

局部变量 / Local variables
    如果可能,局部变量要避免使用char和short。对于char和short类型,编译器在每次分配空间以后,都要将这种局部变量的尺寸减少到8位或 16位。这对于符号变量来说称为符号扩展,对无符号变量称为无符号扩展。这种操作是通过将寄存器左移24或16位,然后再有符号(或无符号的)右移同样的 位数来实现的,需要两条指令(无符号字节变量的无符号扩展需要一条指令)。
    这些移位操作可以通过使用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;
    }
他们的运算结果是相同的,但是第一个代码片断要比其他片断运行的要快。

  评论这张
 
阅读(564)| 评论(1)

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018