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

CSAPP:代码优化【矩阵运算】

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

编程除了使顺序在所有可以的状况下都准确事情,还须要斟酌顺序的运转效力,上一节主要引见了关于读写的优化,本节将对运算的优化举行剖析。读写优化

编写高效顺序须要做到以下两点:

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

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

除了读写与运算的区分,本节与上一节最大的差别的是:本次的优化示例会影响顺序的可读性。

但这也是编程中时常会碰到的状况,在没有更好的优化手腕,但又对顺序有急切的机能需求时,采用空间换时候,或下落代码可读性调换运转效力的要领并不是不可取。

当你编写一个小工具暂时处置惩罚某种事件(或许今后并不重用),或许想考证本身的某个主意是不是可行时(比方测试某个算法是不是准确),如果编写了一个可读性不错但运转很慢的顺序,往往会糟蹋许多不必要的时候。这时候你就可以不须要那末在意代码的可读性,而是去多关注当前顺序的运转机能来更早取得想要的效果。

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

目的函数:图象腻滑处置惩罚

腻滑操纵请求:

  1. 修正图象矩阵的每一个像素点的值,
    新值 = 以该像素点为中心点所相邻的九个像素的平均值
  2. 图象矩阵的四个角点,只须请求角上四个像素的平均值
  3. 图象矩阵的四条边,只须请求当前点相邻的六个像素平均值

原理图:

1、2、3处离别代表角点、边沿点以及内部点的相邻像素

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

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

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

原腻滑函数以下:

static void accumulate_sum(pixel_sum *sum, pixel p) 
{
    sum->red += (int) p.red;
    sum->green += (int) p.green;
    sum->blue += (int) p.blue;
    sum->num++;
    return;
}
static void assign_sum_to_pixel(pixel *current_pixel, pixel_sum sum) 
{
    current_pixel->red = (unsigned short) (sum.red/sum.num);
    current_pixel->green = (unsigned short) (sum.green/sum.num);
    current_pixel->blue = (unsigned short) (sum.blue/sum.num);
    return;
}
static pixel avg(int dim, int i, int j, pixel *src) 
{
    int ii, jj;
    pixel_sum sum;
    pixel current_pixel;

    initialize_pixel_sum(&sum);
    for(ii = max(i-1, 0); ii <= min(i+1, dim-1); ii++) 
        for(jj = max(j-1, 0); jj <= min(j+1, dim-1); jj++) 
            accumulate_sum(&sum, src[RIDX(ii, jj, dim)]);

    assign_sum_to_pixel(&current_pixel, sum);
    return current_pixel;
}
void naive_smooth(int dim, pixel *src, pixel *dst) 
{
    int i, j;
    for (i = 0; i < dim; i++)
        for (j = 0; j < dim; j++)
            dst[RIDX(i, j, dim)] = avg(dim, i, j, src);
}

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

参数:

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

优化目的:使腻滑运算处置惩罚的更快

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

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

优化的主要要领

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

轮回主体只存在一条语句,该语句主如果举行大批的均值运算,而且挪用了多层的函数,如许运转时会涌现多个函数栈的挪用。

经由过程剖析,本节的优化手腕比上一节的矩阵读写要更直接。当前顺序主要的机能瓶颈在于两个方面:

  1. 多层函数挪用:增加了不必要的函数栈处置惩罚开支
  2. 大批反复运算:差别像素点在举行均值运算时,许多运算都是反复且不必要的

本节的优化就是针对这两点举行革新,

多层函数挪用比较轻易处理,只须要把被挪用函数转移在腻滑函数中完成就行(原代码下落了耦合度,但却致使了机能的下落)。

下面主要剖析反复运算的题目,如图:

盘算赤色地区平均值与黄色地区平均值时,有两行是反复运算的。响应的优化战略是以1*3小矩阵为组盘算和,如许每次盘算均值只须要3个已知的和相加除以9,削减了肯定的运算量。

响应的优化代码以下:

int rsum[4096][4096];
int gsum[4096][4096];
int bsum[4096][4096];
void smooth(int dim, pixel *src, pixel *dst) 
{
    int dim2 = dim * dim;
    for(int i = 0; i < dim; i++){
        for(int j = 0; j < dim-2; j++){
            int z = i*dim;
            rsum[i][j] = 0, gsum[i][j] = 0, bsum[i][j] = 0;
            for(int k = j; k < j + 3; k++){
                rsum[i][j] += src[z+k].red;
                gsum[i][j] += src[z+k].green;
                bsum[i][j] += src[z+k].blue;
            }
        }
    }
    // 四个角
    dst[0].red = (src[0].red + src[1].red + src[dim].red + src[dim+1].red) / 4;
    dst[0].green = (src[0].green + src[1].green + src[dim].green + src[dim+1].green) / 4;
    dst[0].blue = (src[0].blue + src[1].blue + src[dim].blue + src[dim+1].blue) / 4;
    
    dst[dim-1].red = (src[dim-2].red + src[dim-1].red + src[dim+dim-2].red + src[dim+dim-1].red) / 4;
    dst[dim-1].green = (src[dim-2].green + src[dim-1].green + src[dim+dim-2].green + src[dim+dim-1].green) / 4;
    dst[dim-1].blue = (src[dim-2].blue + src[dim-1].blue + src[dim+dim-2].blue + src[dim+dim-1].blue) / 4;
    
    dst[dim2-dim].red = (src[dim2-dim-dim].red + src[dim2-dim-dim+1].red + src[dim2-dim].red + src[dim2-dim+1].red) / 4;
    dst[dim2-dim].green = (src[dim2-dim-dim].green + src[dim2-dim-dim+1].green + src[dim2-dim].green + src[dim2-dim+1].green) / 4;
    dst[dim2-dim].blue = (src[dim2-dim-dim].blue + src[dim2-dim-dim+1].blue + src[dim2-dim].blue + src[dim2-dim+1].blue) / 4;

    dst[dim2-1].red = (src[dim2-dim-2].red + src[dim2-dim-1].red + src[dim2-2].red + src[dim2-1].red) / 4;
    dst[dim2-1].green = (src[dim2-dim-2].green + src[dim2-dim-1].green + src[dim2-2].green + src[dim2-1].green) / 4;
    dst[dim2-1].blue = (src[dim2-dim-2].blue + src[dim2-dim-1].blue + src[dim2-2].blue + src[dim2-1].blue) / 4;
    // 四条边
    for(int j = 1; j < dim-1; j++){
        dst[j].red = (rsum[0][j-1]+rsum[1][j-1]) / 6;
        dst[j].green = (gsum[0][j-1]+gsum[1][j-1]) / 6;
        dst[j].blue = (bsum[0][j-1]+bsum[1][j-1]) / 6;
    }
    for(int i = 1; i < dim-1; i++){
        int a = (i-1)*dim, b = (i-1)*dim+1, c = i*dim, d = i*dim+1, e = (i+1)*dim, f = (i+1)*dim+1;
        dst[c].red = (src[a].red + src[b].red + src[c].red + src[d].red + src[e].red + src[f].red) / 6;
        dst[c].green = (src[a].green + src[b].green + src[c].green + src[d].green + src[e].green + src[f].green) / 6;
        dst[c].blue = (src[a].blue + src[b].blue + src[c].blue + src[d].blue + src[e].blue + src[f].blue) / 6;
    }
    for(int i = 1; i < dim-1; i++){
        int a = i*dim-2, b = i*dim-1, c = (i+1)*dim-2, d = (i+1)*dim-1, e = (i+2)*dim-2, f = (i+2)*dim-1;
        dst[d].red = (src[a].red + src[b].red + src[c].red + src[d].red + src[e].red + src[f].red) / 6;
        dst[d].green = (src[a].green + src[b].green + src[c].green + src[d].green + src[e].green + src[f].green) / 6;
        dst[d].blue = (src[a].blue + src[b].blue + src[c].blue + src[d].blue + src[e].blue + src[f].blue) / 6;
    }   
    for(int j = 1; j < dim-1; j++){
        dst[dim2-dim+j].red = (rsum[dim-1][j-1]+rsum[dim-2][j-1]) / 6;
        dst[dim2-dim+j].green = (gsum[dim-1][j-1]+gsum[dim-2][j-1]) / 6;
        dst[dim2-dim+j].blue = (bsum[dim-1][j-1]+bsum[dim-2][j-1]) / 6;
    }
    // 中心部份
    for(int i = 1; i < dim-1; i++){
        int k = i*dim;
        for(int j = 1; j < dim-1; j++){
            dst[k+j].red = (rsum[i-1][j-1]+rsum[i][j-1]+rsum[i+1][j-1]) / 9;
            dst[k+j].green = (gsum[i-1][j-1]+gsum[i][j-1]+gsum[i+1][j-1]) / 9;
            dst[k+j].blue = (bsum[i-1][j-1]+bsum[i][j-1]+bsum[i+1][j-1]) / 9;
        }
    }
}

运转效力以下:

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

原函数加快比为10.5,优化后加快比提升到24.5,虽然肯定程度上丧失了些代码的可读性,但提升了我们想要的运转效力。

优化在肯定程度上削减了反复的运算,但并没有完整消弭反复运算,如果有更好的优化要领迎接交换。

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

  选择打赏方式
微信赞助

打赏

QQ钱包

打赏

支付宝赞助

打赏

  移步手机端
CSAPP:代码优化【矩阵运算】

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

本文来源:搜奇网

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

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

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

发表评论

选填

必填

必填

选填

请拖动滑块解锁
>>