第九章 测量程序执行时间
9.1 计算机系统上的时间流
9.1.1 进程调度和计时器中断
计算机有一个外部计时器，它周期性地向处理器发送中断信号，操作系统调度程序可以选择继续执行当前进程，或者切换到另一个进程。典型的周期时1~10ms。
9.1.2 从应用程序的角度看时间
从应用程序角度，把时间流看成是活动的和不活动的两种时间的交替。通过抓trace可以图形化的观察程序运行状态
9.2 通过 间隔计数（interval counting）来测量时间
操作系统也用计时器（timer）来记录每个机场使用的累计时间，这种信息提供的是对程序执行时间不那么准确的测量值。
9.2.1 操作
操作系统维护着每个进程使用的用户时间量和系统时间量的计数值，当计时器中断发生时，操作系统会确定哪个进程是活动的，并且对那个进程的一个计数值增加计时器间隔时间。如果系统是在内核模式执行的，那么就增加系统时间，否则增加用户时间。
9.2.2 读进程的计时器
在Unix shell中，可以在命令行前加“time”来测量命令的执行时间。
unix> time ./helloworld
执行完成后，会打印出总结运行时间的数据：
前两个是用户和系统时间的秒数。注意这两个数字的小数点第三位都是0.计时器间隔为10ms,所有的计时都是1%秒的倍数。
第三个数字是总经过的时间，以分钟和秒的形式表示。系统和用户时间加起来是2.49s，比总经过的时间6.52s的一半还少，说明处理器同时还在执行其他的进程。
第4个百分比代表用户和系统时间的和占总经过的比例（（2.23+0.26）/6.52 = 38.1%）
剩下的统计数据总结了页面调度和I/O行为。
程序员还可以通过调用库函数times来读进程的计时器
这些时间测量值是以时钟滴答（clock tick）为单位来表示的。定义的常数CLK_TCK指明每秒的时钟滴答数。数据类型clock_t通常定义为长整型。指明子时间的字段给出的是已经终止了并且被回收了的子进程使用的累计时间。因此，times不能用来监视任何正在进行的子进程所使用的时间。作为返回值，times返回的是从系统启动开始已经经过的时钟滴答总数。因此我们可以通过两次调用times，求差来计算一个程序中两个点的耗时。
ANSIC标准还定义了一个clock函数，它测量当前进程使用的总时间
虽然它的返回值和times的返回值都是clock_t类型，但是通常它们表达时间的单位是不一样的。要将clock函数的返回值转换成秒数，需要把它除以CLOCKS_PER_SEC.
9.2.3 进程计时器的准确性
前面介绍的测量时间的准确性未知，本节介绍了几个实验，实验表明进程计时器值对获得程序性能的近似值有用。它们的粒度太粗，不能用于持续时间小于100ms的测量。在这台机器上，这些进程计时器有系统偏差，过高地估计计算时间，平均大约4%。
9.3 周期计数器
许多处理器包含一个运行在时钟周期级的计时器，是一个特殊的寄存器，每个时钟周期它都会加1.可以用特殊的机器指令来读这个计数器的值。
9.3.1 IA32周期计数器
周期计数器是一个64位无符号数，使用rdtsc（read time stamp counter,读时间戳计数器）指令来访问。这条指令没有参数。它将寄存器%edx设置为计数器的高32位，而寄存器%eax设置为低32位。通过这个指令，可以获取两个时间点之间的时钟周期。
9.4 用周期计数器来测量程序执行时间
9.4.1 上下文切换的影响
下图是同一个程序，在不同负载下，测试一个求大小为131072整数数组18次的对比
这个示例说明，上下文切换导致执行时间差异极大。
9.4.2 高速缓存和其他因素的影响
高速缓存和分支预测的开销比上下文切换要小一些。下图是数组比上面小4倍的测控结果。这个执行时间是8ms，比计时器间隔短，所以执行不太可能受上下文切换的影响。
这里的时间变化受高速缓存影响造成的。执行一个代码块的时间非常依赖于在开始执行时，这个代码使用的数据和指令是否在数据和指令高速缓存中。
9.4.3 K次最优测量方法
9.5 基于gettimeofday函数的测量
gettimeofday函数用来查询系统时钟，以确定当前的日期和时间。
9.6 综合：一个实验协议
以协议的形式总结一下上面的实验，来确定“程序X在机器Y上运行速度”：
1、如果X预期的运行时间很长（例如大于1.0s）,那么间隔计数应该就工作得足够好了，而且对处理器负载不敏感；
2、如果X预期的运行时间在0.01~1.0s之间，那么在负载轻的系统上，使用准确的、基于周期的计时来进行测量就很重要了。应该执行gettimeofday函数测量，来确定它在机器Y上的实现是基于周期的，还是基于间隔的。
1）如果函数是基于周期的，那么它作为K次最优计时函数的基础。
2）如果函数是基于间隔的，那么必须找到一些使用机器的周期计数器的方法。这可能需要汇编语言编码。
3、如果X预期的运行时间小于0.01s，那么只有使用的是基于周期的计时，即使是在负责很重的机器上，也可以完成精度的测量。那么可以用gettimeofday或直接访问机器的周期计数器，来实现一个K次最优计时函数。
9.7 展望未来
系统中引入了几个对性能测量有很大影响的特性：
1、与进程相关的周期计时。对操作系统来说，管理周期计数器相对比较容易，所以它指明了某个进程经过的周期数。那么，当进程重新变为活动时，周期计数器被设置为当进程上次非活动时它的值，在进程不活动时有效地冻结了计数器。当然，计数器还是会受内核操作开销和高速缓存的影响，但是至少其他进程的影响不大。已经有一些系统支持这个特性了。根据我们的协议，这允许我们使用基于周期的计时来获得大于0.01s持续时间的准测测量值，即使是在负载很重的机器上。
2、频率变化的时钟。为了降低功耗，未来的系统会改变时钟频率，这样，我们不会有时钟周期与ns之间的一个简单的转换。甚至于很难知道应该用哪个单位来表达程序性能。对于代码优化器，通过计算周期，我们能获得更多的了解，但是对于实现带实时性能限制的应用的人来说，实际运行时间会更重要一些。
9.8 现实生活：K次最优测量方法
我们创建一个库函数fcyc，它使用K次最优方法来测量函数f所需要的时钟周期
参数params是一个指向整数的指针。一般而言，它可以指向一个整数数组，这个数组是被测量的函数的参数。例如，当测量大小写转换函数lower1和lower2时，我们传递一个指向int的 的指针作为参数，它是要转换的字符串的长度。在产生存储器山时，我们可能要传递一个指向大小为2的数组的指针，其中包括大小和步长。
有很多控制测量的参数，以及在每次测量之前是否要清除高速缓存。可以用同样在这个库中的函数来设置这些参数。
9.9 得到的经验教训
通过设计一种准确计时方法，以及在许多不同的系统上的验证，我们得要一些重要经验：
1、每个系统都是不同的。有关硬件、操作系统和库函数实现的细节对可以测量哪种程序以及精确度可以达到多少都有很大的影响。
2、试验可以是非常有启迪性的。通过运行简单试验以产生活动trace的方法，我们获得了对操作系统调度程序的深入了解。这产生了补偿方法，它极大地提高了在负载很轻的Linux系统上的准确性。一个系统和另一个系统是不同的，即使是一个OS内核也与下一个版本的不同，能够分析和理解影响一个系统性能的各个方面是很重要的。
3、在负载很重的系统上获得准确的计时特别困难。大多数系统研究者在专门的基准系统上进行他们所有的测量。他们常常关掉系统的许多OS和网络特性，以减少会引起不可预测活动的因素。不幸的是，普通的程序员没这么奢侈。即使是在负载很重的系统上，我们的K次最优方法对于测量 短于计时器间隔的持续时间来说，也是相当可靠的。
4、试验建立必须控制一些造成性能变化的因素。高速缓存能够极大地影响一个程序的执行时间。传统的技术是在计时开始之前，清空高速缓存中的所有有用的数据，或是在开始时，把通常会在高速缓存中的所有数据都加载进来。
