江苏龙网

  1. 首页 > 人文 > >

程序的“听诊器”——性能监视工具( 二 )


过程时间性能监视说明 ， sqrt占用CPU时间的最多：该函数共被调用5456次 ， for循环的每次测试都要调用一次sqrt 。 程序P3通过把sqrt调用移到循环之外 ， 使得在prime的每次调用中只调用一次费时的sqrt过程 。
程序P3
int prime(int n){int i, bound;999bound = root(n);999for (i = 2;　i < = bound;　i++)5288if (n % i == 0)831return 0;168return 1;}当n=1000时 ， 程序P3的运行速度大约是程序P2的4倍 ， 而当n= 100 000时则超过10倍 。 以n= 100 000的情形为例 ， 过程时间性能监视显示 ， sqrt占用了程序P2的88%的运行时间 ， 但是只占用了程序P3的48%的运行时间 。 这好多了 ， 但仍然是循环的累赘 。
程序P4合并了另外两个加速措施 。 首先 ， 程序P4通过对被2、3和5整除的特殊检验 ， 避免了近3/4的开方运算 。 语句计数表明 ， 被2整除的性质大约把一半的输入归入合数 ， 被3整除把剩余输入的1/3归入合数 ， 被5整除再把剩下的这些数的1/5归入合数 。 其次 ， 只考虑奇数作为可能的因子 ， 在剩余的数中避免了大约一半的整除检验 。 它比程序P3大约快两倍 ， 但是也比P3的错误更多 。 下面是（带错的）程序P4 ， 你能通过检查语句计数看出问题吗？
【程序的“听诊器”——性能监视工具】程序P4
int root(int n)265{return (int) sqrt((float) n);　}int prime(int n){int i, bound;999if (n % 2 == 0)500return 0;499if (n % 3 == 0)167return 0;332if (n % 5 == 0)67return 0;265bound = root(n);265for (i = 7; i <= bound; i = i+2)1530if (n % i == 0)100return 0;165return 1;}main(){int i, n;1n = 1000;1for (i = 2;　i <= n; i++)999if (prime(i))165printf("%d\n", i);}先前的程序找到168个素数 ， 而程序P4只找到165个 。 丢失的3个素数在哪里？对了 ， 我把3个数作为特殊情形 ， 每个数都引入了一处错误：prime报告2不是素数 ， 因为它被2整除 。 对于3和5 ， 存在类似的错误 。 正确的检验是
if (n % 2 == 0)return (n　== 2);依此类推 。 如果n被2整除 ， 如果n是2就返回1 ， 否则返回0 。 对于n=1000、10 000和100 000 ， 程序P4的过程时间性能监视结果总结在下表中 。
程序的“听诊器”——性能监视工具文章插图
程序P5比程序P4快 ， 并且有个好处：正确 。 它把费时的开方运算换成了乘法 ， 如以下程序片段所示 。
程序P5的片段
265for　(i　= 7;　i*i　<= n;　i　= i+2)1530if (n % i == 0)100return 0;165return 1;它还加入了对被2、3、5整除的正确检验 。 程序P5总的加速大约有20% 。
最后的程序只对已被判定为素数的整数检验整除性；程序P6在1.4节 ， 用Awk语言写成 。 C实现的过程时间性能监视结果表明 ， 在n=1 000时 ， 49%的运行时间花在prime和main上（其余是输入/输出）；而当n=100 000时 ， 88%的运行时间花在这两个过程上 。
下面这个表总结了我们已经看到的这几个程序 。 表中还包含另外两个程序作为测试基准 。 程序Q1用习题答案2中的埃氏筛法程序计算素数 。 程序Q2测量输入/输出开销 。 对于n=1 000 ， 它打印整数1, 2,…, 168；对于一般的n ， 它打印整数1, 2,…, P(n) ， 其中P(n)是比n小的素数的个数 。
程序的“听诊器”——性能监视工具文章插图
以上集中讲述了性能监视的一种用途：当你调优单个子过程或函数的性能时 ， 性能监视工具能告诉你运行时间都花在了哪里 。
2　使用性能监视工具对于小程序来说 ， 性能监视很容易实现 ， 因此性能监视工具是可有可无的；但是对于开发大软件来说 ， 性能监视工具则是不可或缺的 。 Brian Kernighan曾经使用行计数性能监视工具 ， 研究了一个用于解释Awk语言程序的4000行的C程序 。 那时这个Awk解释程序已广泛使用了多年 。 扫描该程序75页长的程序清单就会发现 ， 大多数计数都是成百上千的 ， 有些甚至上万 。 一段晦涩的初始化代码 ， 计数接近百万 。 Kernighan对一个6行的循环做了几处修改 ， 程序速度就提高了一倍 。 他自己可能永远也猜不出程序的问题源头所在 ， 但是性能监视工具引导他找到了 。


推荐阅读


上一篇：「书讯」移动互联网对企业核心能力影响研究

下一篇：美国封杀华为，中国感谢特斯拉