您现在的位置是:网站首页> 编程资料编程资料

值得收藏的9个提高代码运行效率的小技巧(推荐)_相关技巧_

2023-05-27 772人已围观

简介 值得收藏的9个提高代码运行效率的小技巧(推荐)_相关技巧_

我们写程序的目的就是使它在任何情况下都可以稳定工作。一个运行的很快但是结果错误的程序并没有任何用处。在程序开发和优化的过程中,我们必须考虑代码使用的方式,以及影响它的关键因素。通常,我们必须在程序的简洁性与它的运行速度之间做出权衡。今天我们就来聊一聊如何优化程序的性能。

1. 减小程序计算量

 1.1 示例代码

 for (i = 0; i < n; i++) { int ni = n*i; for (j = 0; j < n; j++) a[ni + j] = b[j]; }

1.2 分析代码

  代码如上所示,外循环每执行一次,我们要进行一次乘法计算。i = 0,ni = 0;i = 1,ni = n;i = 2,ni = 2n。因此,我们可以把乘法换成加法,以n为步长,这样就减小了外循环的代码量。

1.3 改进代码

 int ni = 0; for (i = 0; i < n; i++) { for (j = 0; j < n; j++) a[ni + j] = b[j]; ni += n; //乘法改加法 }

计算机中加法指令要比乘法指令快得多。

2. 提取代码中的公共部分

2.1 示例代码

  想象一下,我们有一个图像,我们把图像表示为二维数组,数组元素代表像素点。我们想要得到给定像素的东、南、西、北四个邻居的总和。并求他们的平均值或他们的和。代码如下所示。

 up = val[(i-1)*n + j ]; down = val[(i+1)*n + j ]; left = val[i*n + j-1]; right = val[i*n + j+1]; sum = up + down + left + right;

2.2 分析代码

  将以上代码编译后得到汇编代码如下所示,注意下3,4,5行,有三个乘以n的乘法运算。我们把上面的up和down展开后会发现四格表达式中都有i*n + j。因此,可以提取出公共部分,再通过加减运算分别得出up、down等的值。

 leaq 1(%rsi), %rax # i+1 leaq -1(%rsi), %r8 # i-1 imulq %rcx, %rsi # i*n imulq %rcx, %rax # (i+1)*n imulq %rcx, %r8 # (i-1)*n addq %rdx, %rsi # i*n+j addq %rdx, %rax # (i+1)*n+j addq %rdx, %r8 # (i-1)*n+j

2.3 改进代码

 long inj = i*n + j; up = val[inj - n]; down = val[inj + n]; left = val[inj - 1]; right = val[inj + 1]; sum = up + down + left + right;

  改进后的代码的汇编如下所示。编译后只有一个乘法。减少了6个时钟周期(一个乘法周期大约为3个时钟周期)。

 imulq %rcx, %rsi # i*n addq %rdx, %rsi # i*n+j movq %rsi, %rax # i*n+j subq %rcx, %rax # i*n+j-n leaq (%rsi,%rcx), %rcx # i*n+j+n ...

  对于GCC编译器来说,编译器可以根据不同的优化等级,有不同的优化方式,会自动完成以上的优化操作。下面我们介绍下,那些必须是我们要手动优化的。

3. 消除循环中低效代码

3.1 示例代码

  程序看起来没什么问题,一个很平常的大小写转换的代码,但是为什么随着字符串输入长度的变长,代码的执行时间会呈指数式增长呢?

 void lower1(char *s) { size_t i; for (i = 0; i < strlen(s); i++) if (s[i] >= 'A' && s[i] <= 'Z') s[i] -= ('A' - 'a'); }

3.2 分析代码

  那么我们就测试下代码,输入一系列字符串。

lower1代码性能测试

  当输入字符串长度低于100000时,程序运行时间差别不大。但是,随着字符串长度的增加,程序的运行时间呈指数时增长。

  我们把代码转换成goto形式看下。

 void lower1(char *s) { size_t i = 0; if (i >= strlen(s)) goto done; loop: if (s[i] >= 'A' && s[i] <= 'Z') s[i] -= ('A' - 'a'); i++; if (i < strlen(s)) goto loop; done: }

  以上代码分为初始化(第3行),测试(第4行),更新(第9,10行)三部分。初始化只会执行一次。但是测试和更新每次都会执行。每进行一次循环,都会对strlen调用一次。

  下面我们看下strlen函数的源码是如何计算字符串长度的。

 size_t strlen(const char *s) { size_t length = 0; while (*s != '\0') { s++; length++; } return length; }

  strlen函数计算字符串长度的原理为:遍历字符串,直到遇到‘\0'才会停止。因此,strlen函数的时间复杂度为O(N)。lower1中,对于长度为N的字符串来说,strlen 的调用次数为N,N-1,N-2 … 1。对于一个线性时间的函数调用N次,其时间复杂度接近于O(N2)。

3.3 改进代码

  对于循环中出现的这种冗余调用,我们可以将其移动到循环外。将计算结果用于循环中。改进后的代码如下所示。

 void lower2(char *s) { size_t i; size_t len = strlen(s); for (i = 0; i < len; i++) if (s[i] >= 'A' && s[i] <= 'Z') s[i] -= ('A' - 'a'); }

  将两个函数对比下,如下图所示。lower2函数的执行时间得到明显提升。

lower1和lower2代码效率

4. 消除不必要的内存引用

 4.1 示例代码

  以下代码作用为,计算a数组中每一行所有元素的和存在b[i]中。

 void sum_rows1(double *a, double *b, long n) { long i, j; for (i = 0; i < n; i++) { b[i] = 0; for (j = 0; j < n; j++) b[i] += a[i*n + j]; } }

4.2 分析代码

  汇编代码如下所示。

 # sum_rows1 inner loop .L4: movsd (%rsi,%rax,8), %xmm0 # 从内存中读取某个值放到%xmm0 addsd (%rdi), %xmm0 # %xmm0 加上某个值 movsd %xmm0, (%rsi,%rax,8) # %xmm0 的值写回内存,其实就是b[i] addq $8, %rdi cmpq %rcx, %rdi jne .L4

  这意味着每次循环都需要从内存中读取b[i],然后再把b[i]写回内存 。 b[i] += b[i] + a[i*n + j]; 其实每次循环开始的时候,b[i]就是上一次的值。为什么每次都要从内存中读取出来再写回呢?

4.3 改进代码

 /* Sum rows is of n X n matrix a and store in vector b */ void sum_rows2(double *a, double *b, long n) { long i, j; for (i = 0; i < n; i++) { double val = 0; for (j = 0; j < n; j++) val += a[i*n + j]; b[i] = val; } }

  汇编如下所示。

 # sum_rows2 inner loop .L10: addsd (%rdi), %xmm0 # FP load + add addq $8, %rdi cmpq %rax, %rdi jne .L10

  改进后的代码引入了临时变量来保存中间结果,只有在最后的值计算出来时,才将结果存放到数组或全局变量中。

5. 减小不必要的调用

 5.1 示例代码

  为了方便举例,我们定义一个包含数组和数组长度的结构体,主要是为了防止数组访问越界,data_t可以是int,long等类型。具体如下所示。

 typedef struct{ size_t len; data_t *data; } vec;

  get_vec_element函数的作用是遍历data数组中元素并存储在val中。

 int get_vec_element (*vec v, size_t idx, data_t *val) { if (idx >= v->len) return 0; *val = v->data[idx]; return 1; }

  我们将以以下代码为例开始一步步优化程序。

 void combine1(vec_ptr v, data_t *dest) { long int i; *dest = NULL; for (i = 0; i < vec_length(v); i++) { data_t val; get_vec_element(v, i, &val); *dest = *dest * val; } }

5.2 分析代码

  get_vec_element函数的作用是获取下一个元素,在get_vec_element函数中,每次循环都要与v->len作比较,防止越界。进行边界检查是个好习惯,但是每次都进行就会造成效率降低。

5.3 改进代码

  我们可以把求向量长度的代码移到循环体外,同时抽象数据类型增加一个函数get_vec_start。这个函数返回数组的起始地址。这样在循环体中就没有了函数调用,而是直接访问数组。

 data_t *get_vec_start(vec_ptr v) { return v->data; } void combine2 (vec_ptr v, data_t *dest) { long i; long length = vec_length(v); data_t *data = get_vec_start(v); *dest = NULL; for (i=0;i < length;i++) { *dest = *dest * data[i]; } }

6. 循环展开

 6.1 示例代码

  我们在combine2的代码上进行改进。

6.2 分析代码

  循环展开是通过增加每次迭代计算的元素的数量减少循环的迭代次数

6.3 改进代码

 void combine3(vec_ptr v, data_t *dest) { long i; long length = vec_length(v); long limit = length-1; data_t *data = get_vec_start(v); data_t acc = NULL; /* 一次循环处理两个元素 */ for (i = 0; i < limit; i+=2) { acc = (acc * data[i]) * data[i+1]; } /* 完成剩余数组元素的计算 */ for (; i < length; i++) { acc = acc * data[i]; } *dest = acc; }

  在改进后的代码中,第一个循环每次处理数组的两个元素。也就是每次迭代,循环索引i加2,在一次迭代中,对数组元素i和

-六神源码网