使用Gprof分析代码性能瓶颈

使用profiler来分析代码的性能比纯脑补分析起来更省力更详细也更直观。

Gprof是GNU binutils工具之一。可以分析出代码中每个函数的调用次数、每个函数消耗的处理器时间等。

更多的关于gprof的信息可以参照这两篇文章:gprof使用和介绍Linux性能评测工具之一:gprof篇

在这里就简单说下gprof的用法(更多的参数可以看上面的博文):

  1. 使用G++ 编译代码时需要加-pg参数
  2. 编译完成后运行生成的.exe文件,会生成gmon.out文件
  3. 导出分析结果:gprof -b runFileName.exe gmon.out>resault.txt

其实为了方便,我在我的Sublime Text的Build System中使用G++编译时就使用了gprof(-pg参数),关于我Sublime Text的配置可以看这里:配置SublimeText为C/C++的轻量级IDE

下面我们就来实践一下使用gprof分析代码:

就拿输出N以内的素数举例吧。

素数指在大於1的自然数中,除了1和此整数自身外,無法被其他自然数整除的数(也可定義為只有1和本身两个因数的数)。——维基百科

首先我们先写一份代码,由素数的定义可得,最简单的验证一个数N是否为素数的方式是依次让它对2至N-1取余,若2~N-1中存在一个数能够被N整除,所以我们就可以判定它不是素数。

如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 求1000以内的所有素数
bool prime(int n){
for (int i = 2; i < n; ++i){
if(n%i==0)
return false;
}
return true;
}
int main(void)
{
int n=1000;
// 统计N以内素数的个数
int index=0;
for (int i = 2; i < n; ++i){
if(prime(i)){
printf("%d\t",i);
++index;
}
}
printf("\nThe number of prime numbers within %d to %d\n",n,index);
return 0;
}

在1000以内共找到了168个素数。01_run

使用gprof来分析一下: 01

我们可以看到prime被调用了998次(因为是1000以内的数)。

这个算法是非常无脑的穷举(从2~N),下面我们来优化一下这个算法。

确定性演算法埃拉托斯特尼筛法(另一种试除法)

尝试从2到$\sqrt{N}$ 的整数是否整除N,来判定N是否为素数。

修改后的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int sqrt_n(int n){
return (int)sqrt((float)n);
}
bool prime(int n){
for (int i = 2; i <= sqrt_n(n); ++i){
if(n%i==0)
return false;
}
return true;
}
int main(void)
{
int n=1000;
for (int i = 2; i < n; ++i){
if(prime(i)){
printf("%d\t",i);
}
}
return 0;
}

同样来用gprof分析一下:

02

可以看到prime调用了998次,sqrt_n调用了5455次(对n实行了5455次sqrt操作)。

还有特别需要注意的一点是这句代码:

for (int i = 2; i <= sqrt_n(n); ++i)

这个循环每执行一次迭代都会调用一次sqqt_n,造成了prime函数每操作一个N就会调用N次sqrt_n函数,而实际上sqrt_n在prime中的作用只需要执行一次就足够了,所以我们可以修改一下代码:

int tmp=sqrt_n(n)
for (int i = 2; i <= tmp; ++i)

03

如何再一次优化?

思考一下:我们试除的顺序是这样的:

2 3 4 5 6 7 8 9 10 11 12 13 14......N-1

其中4,6,8,10,12,14...都是2的整数倍,所以我们只需要对N%2就可以替代对这些数字的取余

另外9,15,21,24....都是3的整数倍,所以我们只需要对N%3就可以替代这些数字

对于5的整数倍的也同理,我们可以将这几个测试的基准数据直接判断N与之的余数,如果为0则是合数,否则则为素数。

1
2
3
4
5
6
7
8
9
10
11
12
// 对prime函数添加对2,3,5的判断
bool prime(int n){
if(n%2==0){return false;}
if(n%3==0){return false;}
if(n%5==0){return false;}
int tmp=sqrt_n(n);
for (int i = 7; i <= tmp; ++i){
if(n%i==0)
return false;
}
return true;
}

分析结果:04

可以看到使sqrt_n的调用降低到了227。

但是,上面的代码在判断上也出现了一些问题:

运行结果: 05-run

1000以内的素数只找到了165个,但是我们通过穷举所有(第一份代码),得到的结果是168个。

通过上面的运行结果截图我们能看到2,3,5这三个并没有出现在列表中,因为当n=2,3,5时会导致返回false,所以我们要在代码返回表达式中添加一下判断语句:

// 如果N等于2,3,5就返回true
if(n%2==0){return n==2;}
if(n%3==0){return n==3;}
if(n%5==0){return n==5;}

再次运行:

06-run

全文完,若有不足之处请评论指正。
本文标题:使用Gprof分析代码性能瓶颈
文章作者:ZhaLiPeng
发布时间:2016年05月07日 13时32分
本文字数:本文一共有1.2k字
原始链接:https://imzlp.me/posts/34573/
许可协议: CC BY-NC-SA 4.0
转载请保留原文链接及作者信息,谢谢!
您的捐赠将鼓励我继续创作!