千里之行始于足下

CSAPP阅读笔记(7)-程序执行时间测算

Posted on By Peter Yang

这一章讨论如何计算程序中各部分的执行时间。从测量参数来说,分为两种方法,一种采用时间为单位进行计算,另一种采用时钟周期数进行计算。前者一般采用低频的定时中断来获取或更新,后者采用计数器,每个时钟周期自增1。

现在的计算机系统一般都是多任务多用户模式,然而其内部CPU只有一个(不考虑多核多CPU情况)。系统为用户营造了一个模拟的多任务同时运行的环境,对于看似同时运行的任务而言,就叫做并发。然而由于CPU的执行部件只有一个,所以实际上所有的任务都是串行完成的,只是系统将各个任务调度起来,一会儿做这个一会儿做那个,使各个任务看起来是并行在处理。并且,由于任务切换而造成的开销(比如保存现场等内核空间上的执行),也要考虑在内。所以,如果要测量一个进程中函数的处理或者执行时间,就势必要考虑这种种误差的存在。

再来看时钟周期计数法。这种方法是基于系统中存在一个计算系统自启动以来的时钟周期数的寄存器。该计数器在IA32架构下采用64bit的无符号整型数。如果机器主频为1 GHz,则可以支持计数大约570年。

这种测算方式和机器的性能无关,因为其实际上并没有直接测算时间,而是由时钟周期数代替。来看看各种情况的影响:

(1)上下文切换:上下文切换带来的影响是很大的,尤其当系统负载较重时,误差会加大。

可采取措施:尽可能减少需测算的时间间隔,避免其中出现上下文切换。

(2)高速缓存:由于高速缓存和内存访问速率的差异,再加上不同的置换算法。这一因素的影响虽然没有前者大,但也不可接受。

可采取措施:可在实际测算前,预先调用待测函数一次,起到warm-up缓存的作用。

如果数据访问不希望cache,可以先warm-up函数,然后清空其数据cache。这样就达到了仅有代码被缓存,而数据仍需从内存访问的情况。

下面来看看基于这种测量的K-best方法。

这种方法是说,对于测试数据而言,可选择测量时间值最快的K个数据,当然这K个数据需满足误差不超过给定上限d,并且给定一个测量数据的上限M。测量方法的收敛定义为已经选出K个数据并满足误差d,且测量总数未超过M。这种方法仅适用于测算时间间隔小于7ms的情况。

总结下,对于测算时间大于1s的情况,则中断计时法足够好了;测算时间在10ms~1s之间,则轻载时使用K-best方法;测算时间小于10ms,则K-best方法能取得较好效果。