hi,你好!欢迎访问本站!登录
本站由网站地图腾讯云宝塔系统阿里云强势驱动
当前位置:首页 - 教程 - 杂谈 - 正文 君子好学,自强不息!

CSAPP:代码优化【矩阵读写】

2019-11-18杂谈搜奇网30°c
A+ A-

写递次最重要的目的就是使它在一切能够的状况下都准确事情,另一方面,在许多状况下,让递次运转得很快也是一个重要的斟酌要素。运算优化

编写高效递次须要做到以下两点:

  1. 挑选一组适宜的算法和数据构造
  2. 编写编译器能够有用优化以转换成高效可实行代码的源代码

第一点适宜的算法和数据构造往往是人人写递次时会起首斟酌到的,而第二点常被疏忽。这里我们就代码优化而言,重要议论怎样编写能够被编译器有用优化的源代码,个中明白优化编译器的才能和范围性是很重要的。

以下我们将举例对罕见的矩阵操纵举行代码优化。

目的函数:图象逆时针扭转90°

扭转操纵用下面两步操纵完成:

  1. Transpose: 对第(i,j)个像素,实行Mij和Mji交流
  2. Exchange rows:行i和行N-1-i交流

道理图:

即对原有图象矩阵先举行一次半数,然后再举行一次翻转,就能够获得我们须要的逆时针扭转90°以后的矩阵。

个中我们用以下构造体示意一张图象的像素点:

typedef struct { 
    unsigned short red;   /* R value */ 
    unsigned short green; /* G value */ 
    unsigned short blue;  /* B value */ 
} pixel;

red、green、blue离别示意一张彩色图象的红绿蓝三个通道。

原扭转函数以下:

#define RIDX(i,j,n) ((i)*(n)+(j))

void naive_rotate(int dim, pixel *src, pixel *dst) { 
    int i, j; 
    for(i=0; i < dim; i++) 
        for(j=0; j < dim; j++) 
            dst[RIDX(dim-1-j,i,dim)] = src[RIDX(i,j,dim)]; 
    return;
}

图象是规范的正方形,用一维数组示意,第(i,j)个像素示意为I[RIDX(i,j,n)],n为图象边长。

参数:

  • dim:图象的边长
  • src: 指向原始图象数组首地点
  • dst: 指向目的图象数组首地点

RIDX(i,j,dim)读取目的像素点,RIDX(dim-1-j,i,dim)将i、j参数位置交换,完成了斜角半数,dim-1-j完成了高低翻转。

优化目的:使扭转操纵运转的更快

当前我们具有一个driver.c文件,能够对原函数和我们优化的函数举行测试,获得示意递次运转机能的CPE(每元素周期数)参数。

我们的使命就是完成优化代码,与原有代码同时运转举行参数的对照,检察代码优化状况。

优化的重要要领

  1. 轮回展开
  2. 并行盘算
  3. 提早盘算
  4. 分块运算
  5. 防止庞杂运算
  6. 削减函数挪用
  7. 进步Cache命中率

轮回主体只存在一条语句,该语句为内存的读写(读取一个源像素,再写入目的像素),不触及函数挪用与盘算。所以我们的优化手腕有进步Cache命中率、防止庞杂运算、分块运算、轮回展开与并行盘算。

优化一:进步Cache命中率

在矩阵运算中,进步Cache命中率是最轻易想到的要领,罕见的是外轮回按行遍历与外轮回按列遍历的对照,因为存储递次是行序,所以前者的运转速率会显著优于后者。

在已给出的naive_rotate函数中,中心轮回语句触及到读取一个像素点与写入一个像素点,明显写入像素点比读取像素点更消耗时刻,这是由存储器的性子决议的,所以我们应当优先对写入像素点的索引举行优化。

上图形貌了8种数组索引递次,位于上方的蓝色方块代表原始图象,黄色箭头示意原始像素的读取递次,位于下方的蓝色方块代表扭转后图象,赤色箭头示意目的像素的写入递次。

因为轮回体实行速率重要与数据写入相干,所以我们优先斟酌赤色箭头也就是写入像素的cache命中率。

第一组到第四组的写入像素都是根据列序,理论上写入效果应当最差,第五第六组正向行序写入实行效果应当是最好的,第七第八组逆向行序应当稍差。下面我们给出离别根据8种差别递次索引的代码,运用driver测试出他们的运转效力:

void rotate_leftup(int dim, pixel *src, pixel *dst) 
{
    int i, j;
    for (i = 0; i < dim; i++)
    for (j = 0; j < dim; j++)
        dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)];
}
void rotate_leftdown(int dim, pixel *src, pixel *dst) 
{
    int i, j;
    for (i = dim-1; i > -1; i--)
    for (j = 0; j < dim; j++)
        dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)];
}
void rotate_rightup(int dim, pixel *src, pixel *dst) 
{
    int i, j;
    for (i = 0; i < dim; i++)
    for (j = dim-1; j > -1; j--)
        dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)];
}
void rotate_rightdown(int dim, pixel *src, pixel *dst) 
{
    int i, j;
    for (i = dim-1; i > -1; i--)
    for (j = dim-1; j > -1; j--)
        dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)];
}
void rotate_upleft(int dim, pixel *src, pixel *dst) 
{
    int i, j;
    for (j = 0; j < dim; j++)
    for (i = 0; i < dim; i++)
        dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)];
}
void rotate_upright(int dim, pixel *src, pixel *dst) 
{
    int i, j;
    for (j = dim-1; j > -1; j--)
    for (i = 0; i < dim; i++)
        dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)];
}
void rotate_downleft(int dim, pixel *src, pixel *dst) 
{
    int i, j;
    for (j = 0; j < dim; j++)
    for (i = dim-1; i > -1; i--)
        dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)];
}
void rotate_downright(int dim, pixel *src, pixel *dst) 
{
    int i, j;
    for (j = dim-1; j > -1; j--)
    for (i = dim-1; i > -1; i--)
        dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)];
}

CPE与机器运转速率有关,测试机比较老,又是虚拟机环境,所以测得的CPE很低

  • Dim:图象大小
  • Your CPEs:对应函数CPE
  • Baseline CPEs:参考基线CPE
  • Speedup:加速比 = Baseline CPEs / Your CPEs

与理论预计的一样,前4组表现显著最差,个中的第一组恰是原始待优化的函数,与理论预计符合。

第5-8组差别不大,第五第六组比第七第八组效果略好,但整体优化效果很不显著,从新搜检轮回体的实行语句,发如今索引时宏定义中包含了乘法运算,严峻障碍了递次的实行效力。

优化二:防止庞杂运算

之前在索引像素点时,是经由历程乘法运算举行索引,加大了不必要的开支。假如运用矩阵的分块运算,虽然能够应用局部性道理在肯定程度上优化递次,但依旧会遭到乘法运算的严峻影响,因而我们盘算防止庞杂运算经由历程轮回展开的体式格局来对递次进一步优化。

详细的操纵逻辑是,运用指针对元素举行索引,能够把之前的8种图象索引中的箭头,分拆成32个平行的箭头,经由历程指针运算一次处置惩罚32个像素,下面给出代码来更好的明白:

//1
void rotate_pleftup(int dim, pixel *src, pixel *dst) 
{
    int i,j;
    for(i=0;i<dim;i+=32)
        for(j=0;j<dim;j++){       
            pixel *dptr=dst+RIDX(dim-1-j,i,dim);
            pixel *sptr=src+RIDX(i,j,dim);
            int step = -1;
            while(++step < 32){
                *(dptr++) = *sptr;
                sptr += dim;
            }
        }
}
//2
void rotate_pleftdown(int dim, pixel *src, pixel *dst) 
{
    int i,j;
    for(i=dim-1;i>30;i-=32)
        for(j=0;j<dim;j++){       
            pixel *dptr=dst+RIDX(dim-1-j,i,dim);
            pixel *sptr=src+RIDX(i,j,dim);
            int step = 1;
            while(--step > -32){
                *(dptr--) = *sptr;
                sptr -= dim;
            }
        }
}
//3
void rotate_prightup(int dim, pixel *src, pixel *dst) 
{
    int i,j;
    for(i=0;i<dim;i+=32)
        for(j=dim-1;j>-1;j--){       
            pixel *dptr=dst+RIDX(dim-1-j,i,dim);
            pixel *sptr=src+RIDX(i,j,dim);
            int step = -1;
            while(++step < 32){
                *(dptr++) = *sptr;
                sptr += dim;
            }
        }
}
//4
void rotate_prightdown(int dim, pixel *src, pixel *dst) 
{
    int i,j;
    for(i=dim-1;i>30;i-=32)
        for(j=dim-1;j>-1;j--){       
            pixel *dptr=dst+RIDX(dim-1-j,i,dim);
            pixel *sptr=src+RIDX(i,j,dim);
            int step = 1;
            while(--step > -32){
                *(dptr--) = *sptr;
                sptr -= dim;
            }
        }
}
//5
void rotate_pupleft(int dim, pixel *src, pixel *dst) 
{
    int i,j;
    for(j=0;j<dim;j+=32)
        for(i=0;i<dim;i++){       
            pixel *dptr=dst+RIDX(dim-1-j,i,dim);
            pixel *sptr=src+RIDX(i,j,dim);
            int step = -1;
            while(++step < 32){
                *dptr = *(sptr++);
                dptr -= dim;
            }
        }
}//6
void rotate_pupright(int dim, pixel *src, pixel *dst) 
{
    int i,j;
    for(j=dim-1;j>30;j-=32)
        for(i=0;i<dim;i++){       
            pixel *dptr=dst+RIDX(dim-1-j,i,dim);
            pixel *sptr=src+RIDX(i,j,dim);
            int step = -1;
            while(++step < 32){
                *dptr = *(sptr--);
                dptr += dim;
            }
        }
}
//7
void rotate_pdownleft(int dim, pixel *src, pixel *dst) 
{
    int i,j;
    for(j = 0; j < dim; j+=32)
        for(i = dim-1; i > -1; i--){       
            pixel *dptr=dst+RIDX(dim-1-j,i,dim);
            pixel *sptr=src+RIDX(i,j,dim);
            int step = -1;
            while(++step < 32){
                *dptr = *(sptr++);
                dptr -= dim;
            }
        }
}
//8
void rotate_pdownright(int dim, pixel *src, pixel *dst) 
{
    int i,j;
    for(j = dim-1; j > 30; j -= 32)
        for(i = dim-1; i > -1; i--){       
            pixel *dptr=dst+RIDX(dim-1-j,i,dim);
            pixel *sptr=src+RIDX(i,j,dim);
            int step = -1;
            while(++step < 32){
                *dptr = *(sptr--);
                dptr += dim;
            }
        }
}

指针每轮回找到一个像素,会对其地点的某一行或某一列的32个像素举行变更,如许既经由历程局部性进步了cache命中率,也能够有用的避开乘法运算形成的机能丧失。以下是对优化一中的8个函数举行轮回展开的优化状况:


能够看到,1、3的运转效果最好,2、4的运转效果相对略低,5-8运转效果最差,但即便是根据最差的递次轮回展开,也远远超过了优化一中最好的索引递次,这也证明了乘法运算是障碍之前优化的重要要素。

优化二中为何变成了1、3运转效力最好?

经由历程之前的8种轮回序次的剖析图,我们能够看到1、3两组在写入的时刻,假如运用32路轮回展开,每次都能够经由历程指针索引到背面31个像素(黑色箭头代表其他31路的写入),cache命中率最高:

优化三:并行盘算

优化二中的轮回展开,实在也能够看做是一种特别的分块运算,分块大小为1*32的小矩阵,种种优化要领之间整体来讲具有相干性,大多都是基于cache缓存斟酌。

优化三中我们进步轮回主语句运转的并行性,这里我们须要在32路轮回时到场一个新的指针,在宏观上来看轮回主体每条语句是没法并行的,但每一行代码并非一个原子操纵,微观到线程级别来看是能够涌现并行的,这里我们只对优化二中最好的第一组举行修正:

void rotate_pleftup_4(int dim, pixel *src, pixel *dst) 
{
    int i,j;
    for(i=0;i<dim;i+=32)
        for(j=0;j<dim;j++)
        {       
            pixel* dptr=dst+RIDX(dim-1-j,i,dim);
            pixel* sptr=src+RIDX(i,j,dim);

            pixel* dptr_ = dptr+1;
            pixel* sptr_ = sptr+dim;
            
            int step = -1;
            while(++step < 16){
                *dptr = *sptr;
                sptr += dim+dim;
                dptr += 2;
            
                *dptr_ = *sptr_;
                sptr_ += dim+dim;
                dptr_ += 2;
            }
        }
}

测试效果以下:

屡次运转的话,获得的测试效果基础没有机能差异,然则假如将轮回指针继承增添,运用4指针或许8指针轮回,反而会涌现机能下落的状况。

从新对原函数举行剖析,函数重要实行的只是像素点的读写罢了,而且我们已去掉了耗时的乘法运算。如许一来,没什么能并行运算的处所,代码的并行性实际上并没有什么提拔的空间,反而会跟着多个指针的到场使得轮回历程变得庞杂增大开支,以至能够会下降递次编译时的效力。

别的,在没什么机能提拔的状况下,采纳多个指针变量使得代码可读性变差,所以这里我们挑选优化二的版本。

这并不意味着进步并行性的要领不好,只是在当前环境下不实用罢了,假如运用妥当会在原有基础上给递次带来更好的机能提拔。

下面对照一下优化前和优化后的代码:

多出了5行轮回语句,但加速比却从1.2到了7.8,提拔了6.5倍,不采纳并行优化的状况下代码可读性也未下落,这明显是值得的。

我们经常会触及到关于矩阵的处置惩罚,特别是图象处置惩罚方面,而图象处置惩罚对机能有很高的需求。这只是一个矩阵操纵/二维数组的简朴例子,代码优化不范围于此,我们日常平凡编码中许多时刻并没有斟酌那么多,都是根据通例写法逐渐完成,这并没有什么不妥。然则当最先对本身的递次有提拔机能的需求时,尝试对本身的代码做出优化无妨是一种更好的挑选,这是写出高质量代码的必要门路。

转载请说明出处:https://www.cnblogs.com/ustca/p/11790314.html

  选择打赏方式
微信赞助

打赏

QQ钱包

打赏

支付宝赞助

打赏

  移步手机端
CSAPP:代码优化【矩阵读写】

1、打开你手机的二维码扫描APP
2、扫描左则的二维码
3、点击扫描获得的网址
4、可以在手机端阅读此文章
未定义标签

本文来源:搜奇网

本文地址:https://www.sou7.cn/282222.html

关注我们:微信搜索“搜奇网”添加我为好友

版权声明: 本文仅代表作者个人观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。请记住本站网址https://www.sou7.cn/搜奇网。

发表评论

选填

必填

必填

选填

请拖动滑块解锁
>>