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

刘邓

每天收获一点点-目标:富足

 
 
 

日志

 
 

深入理解计算机系统——优化程序代码  

2012-07-06 17:43:44|  分类: 读书笔记 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1.编写程序需要的三类活动:
第一.选择合适的算法和数据结构 第二.编写出编译器能够有效优化以转化为高效可执行代码的源代码 第三.针对处理运算量特别大的计算,将任务分为多个部分,这些部分可以在多核和多处理器上并行计算
2.程序优化的第一步是消除不必要的内容:消除不必要的函数调用,条件测试和存储器引用。
3.对于极端需要优化的情况,需要针对特殊的处理器架构来进行相应的代码定制,以期最大利用处理器的指令级并行功能
代码优化实践:
先看下面一段快速排序的代码:

#include<time.h>
#include<iostream>
#include<cstdlib>
using namespace std;
void QSort(int l,int r,int*p);
void Swap(int &a,int&b);
int main()
{
    srand(10);
 clock_t t1,t2;
    int n;
    cout<<"Please Enter The Number Of The Integes:";
    cin>>n;
 t1 = clock();
    int *Array= new int[n];
    for(int i = 0;i<n;i++)
        Array[i] = rand()%20;

   QSort(0,n-1,Array);

    //for(int i=0;i<n;i++)
       // cout<<Array[i]<<" ";
    cout<<endl;
    t2 = clock();
    cout<<"Total Time:"<<t2-t1<<endl;
    return 0;
    }
void Swap(int &a,int&b)
{
    int tmp = a;
    a = b;
    b = tmp;
    }
void QSort(int l,int r,int *p)
{
    int tmpL = l,tmpR = r;
    int val = p[(l+r)/2];
    while(tmpL<tmpR)
    {
        while(p[tmpR]>val)
        {
            tmpR--;
            }
  while(p[tmpL]<val)
        {
            tmpL++;
            }
  if(tmpL>=tmpR) break;
  //int tmp = p[tmpL];
  //p[tmpL] = p[tmpR];
  //p[tmpR] = tmp;

  Swap(p[tmpL],p[tmpR]);
  tmpL++;
  tmpR--;

    }
    if(tmpL>l) QSort(l,tmpL-1,p);
    if(tmpR<r) QSort(tmpR+1,r,p);
}


先观察上面红色代码(通过过程调用来实现2个数的对换)生成1000000个随机整数并通过快速排序所用时间为:
深入理解计算机系统——优化程序代码 - 刘邓 - 刘邓
 
下面再看看把红字部分注释掉,用代码嵌入实现所得到的结果:
深入理解计算机系统——优化程序代码 - 刘邓 - 刘邓
 时间由原来的468减少到了207!!!!
——————————————————————————————————————————————
上面的结果是以牺牲模块性为代价的,本来我以为将Swap声明为内联函数应该会有和直接嵌入代码有相似的结果,但是事实却并非如此,下面是我将Swap内联以后得到的运行结果:
深入理解计算机系统——优化程序代码 - 刘邓 - 刘邓
 我不解的发现时间没有变短反而增长了部分!!!这是为神马???不得其解!!!
————————————————————————————————————————————————————
以《深入理解计算机系统》书本知识来分析前2个效率之间的巨大差别:
1.多次的过程调用费时费力!!!压栈,调用,恢复做了很多无用功。
2.红字部分代码每过程调用一次则会在寄存器中读取临时变量,a,b,tmp而每次调用的时候寄存器里面都是没有a,b,tmp的这就需要从存储器来读取每次的交换以后还要进行存储器写!!这个代码片段的时间局部性非常差,远远偏离了程序的局部性原则。
反观绿字部分:tmp是局部变量在QSort调用未结束之前都存在于寄存器中,读写迅速,时间局部性高;不需要过程调用!
—————————————————————————————————————————————————————

下面是尝试了一下《深入理解计算机系统》5.4节中消除循环的低效率问题,先上代码:

 

#include<time.h>
#include<iostream>
#include<cstdlib>
#include<vector>
using namespace std;
int main()
{
    clock_t t1,t2;
    vector<int> v;
    for(int i =0;i<100000000;i++)
        v.push_back(rand());
    t1 = clock();
    int size = v.size();
    for(int i = 0;i<v.size();i++) //将红字部分改为 i<size;
        v[i] = v[i]+1;
    t2 = clock();
    cout<<"Total Time:"<<t2-t1<<endl;
    system("pause");
    return 0;
    }

第一个呈现的是红字部分代码出现的结果:
深入理解计算机系统——优化程序代码 - 刘邓 - 刘邓
 
下面是将红字部分转化为i<size;以后的结果:
深入理解计算机系统——优化程序代码 - 刘邓 - 刘邓
 产生这个结果的原因是显而易见的,综合了多余的过程调用,局部性等因素。
PS:以前图省事都是i<XX.size();i<XX.length();以后可不能这么干啊!!!
————————————————————————————————————————————————

《深入理解计算机系统》5.6节所说的消除不必要的存储器引用,从这一节联系实际的情况就是在传值调用和传引用调用的函数中,当函数体内有多次对参数的修改时,应该为参数在函数体内设置临时变量,减少程序对存储器的引用:

 

#include<time.h>
#include<iostream>
#include<cstdlib>
#include<vector>
using namespace std;
void F(int &s);
int main()
{
    clock_t t1,t2;
    int i =10;
    t1 = clock();
    F(i);
    t2 = clock();
    cout<<"Total Time:"<<t2-t1<<endl;
    system("pause");
    return 0;
    }
void F(int &s)
{
    int tmp = s;
    for(int i = 0;i<100000000;i++)
    tmp = tmp + i;
    s = tmp;
    }

void F(int &s)

    for(int i = 0;i<100000000;i++)
    s = s + i;
    }

上面红字的运行结果为:
深入理解计算机系统——优化程序代码 - 刘邓 - 刘邓
相对的绿字运行结果为:
深入理解计算机系统——优化程序代码 - 刘邓 - 刘邓
 因为只有一个变量而且变化,估计编译器已经对代码进行了优化所以差别仅仅为2毫秒,但是这个只是为了演示时间下书本所说只是,这个的确可能成为制约程序性能的因素!
————————————————————————————————————————————————————————————
总结:细节处提高程序性能,《深入理解计算机系统》你值得拥有!
 
  评论这张
 
阅读(455)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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