计算程序运行时间

写的全面的一篇
还有一种
int getitimer(int which, struct itimerval *value);
int setitimer(int which, const struct itimerval *value,
              struct itimerval *ovalue);
顺便转载一下，以备不时之需
http://blog.chinaunix.net/u2/85233/showart_1856092.html

还有篇不错的,学习汇编后可以看看:
http://sites.google.com/a/kingofat.com/windstorm/Article/measure-execution-time-precisely

我们有时需要得到程序的运行时间，但我们也要知道，根本不可能精确测量某一个程序运行的确切时间­^[3]，文献[4]中说的很明白，现摘录如下。

       我 们平时常用的测量运行时间的方法并不是那么精确的，换句话说，想精确获取程序运行时间并不是那么容易的。也许你会想，程序不就是一条条指令么，每一条指令 序列都有固定执行时间，为什么不好算？真实情况下，我们的计算机并不是只运行一个程序的，进程的切换，各种中断，共享的多用户，网络流量，高速缓存的访 问，转移预测等，都会对计时产生影响。

       文献[4]中还提到：对于进程调度来讲，花费的时间分为两部分，第一是计时器中断处理的时间，也就是当且仅当这个时间间隔的时候，操作系统会选择，是继续当前进程的执行还是切换到另外一个进程中去。第二是进程切换时间，当系统要从进程A切换到进程B时，它必须先进入内核模式将进程A的状态保存，然后恢复进程B的状态。因此，这个切换过程是有内核活动来消耗时间的。具体到进程的执行时间，这个时间也包括内核模式和用户模式两部分，模式之间的切换也是需要消耗时间，不过都算在进程执行时间中了。

       那么有哪些方法能统计程序的运行时间呢？通过查找一些资料并结合自己的实践体会，摘录和总结了下面几种方法。

一、Linux的time命令

       Linux系统下统计程序运行实践最简单直接的方法就是使用time命令，文献[1, 2]中详细介绍了time命令的用法。此命令的用途在于测量特定指令执行时所需消耗的时间及系统资源等资讯，在统计的时间结果中包含以下数据：

       (1) 实际时间（real time）：从命令行执行到运行终止的消逝时间；

       (2) 用户CPU时间（user CPU time）：命令执行完成花费的系统CPU时间，即命令在用户态中执行时间的总和；

       (3) 系统CPU时间（system CPU time）：命令执行完成花费的系统CPU时间，即命令在核心态中执行时间的总和。

       其中，用户CPU时间和系统CPU时间之和为CPU时间，即命令占用CPU执行的时间总和。实际时间要大于CPU时间，因为Linux是多任务操作系统，往往在执行一条命令时，系统还要处理其他任务。另一个需要注意的问题是即使每次执行相同的命令，所花费的时间也不一定相同，因为其花费的时间与系统运行相关。

二、间隔计数^[4]

       上面介绍的time命令能测量特定进程执行时所消耗的时间，它是怎么做到的呢？

       操作系统用计时器来记录每个进程使用的累计时间，原理很简单，计时器中断发生时，操作系统会在当前进程列表中寻找哪个进程是活动的，一旦发现进程A正在运行立马就给进程A的 计数值增加计时器的时间间隔（这也是引起较大误差的原因）。当然不是统一增加的，还要确定这个进程是在用户空间活动还是在内核空间活动，如果是用户模式， 就增加用户时间，如果是内核模式，就增加系统时间。这种方法的原理虽然简单但不精确。如果一个进程的运行时间很短，短到和系统的计时器间隔一个数量级，用 这种方法测出来的结果必然是不够精确的，头尾都有误差。不过，如果程序的时间足够长，这种误差有时能够相互弥补，一些被高估一些被低估，平均下来刚好。从 理论上很难分析这个误差的值，所以一般只有程序达到秒的数量级时用这种方法测试程序时间才有意义。

       这种方法最大的优点是它的准确性不是非常依赖于系统负载。

       实现方法之一就是上面介绍的time命令，之二是使用tms结构体和times函数。

       在Linux中，提供了一个times函数，原型是

       clock_t times( struct tms * buf );

这个tms的结构体为

struct tms

{

       clock_t tms_utime;             //user time

       clock_t tms_stime;             //system time

       clock_t tms_cutime;    //user time of reaped children

       clock_t tms_cstime;     //system time of reaped children

}

这里的cutime和cstime，都是对已经终止并回收的时间的累计，也就是说，times不能监视任何正在进行中的子进程所使用的时间。使用times函数需要包含头文件sys/times.h。

三、周期计数^[4]

       为了给计时测量提供更高的准确度，很多处理器还包含一个运行在始终周期级别的计时器，它是一个特殊的寄存器，每个时钟周期它都会自动加1。这个周期计数器呢，是一个64位无符号数，直观理解，就是如果你的处理器是1GHz的，那么需要570年，它才会从2的64次方绕回到0，所以你大可不必考虑溢出的问题。但是这种方法是依赖于硬件的。首先，并不是每种处理器都有这样的寄存器的；其次，即使大多数都有，实现机制也不一样，因此，我们无法用统一的，与平台无关的接口来使用它们。这下，就要使用汇编了。当然，在这里实际用的是C语言的嵌入汇编：

void counter( unsigned *hi, unsigned *lo )
{
asm(”rdtsc; movl %%edx,%0; movl %%eax, %1″
: “=r” (*hi), “=r” (*lo)
:
: “%edx”, “%eax”);
}

第一行的指令负责读取周期计数器，后面的指令表示将其转移到指定地点或寄存器。这样，我们将这段代码封装到函数中，就可以在需要测量的代码前后均加上这个函数即可。最后得到的hi和lo值都是两个，除了相减得到间隔值外，还要进行一些处理，在此不表。

       不得不提出的是，周期计数方式还有一个问题，就是我们得到了两次调用counter之 间总的周期数，但我们不知道是哪个进程使用了这些周期，或者说处理器是在内核还是在用户模式中。间隔计数的好处就是它是操作系统控制给进程计时的，我们可 以知道具体哪个进程呢个模式；但是周期计数只测量经过的时间，他不管是哪个进程使用的。所以，用周期计数的话必须很小心。举个例子：

       double time()

       {

              start_counter();

              p();

              get_counter();

}

这样一段程序，如果机器的负载很重，会导致p运行时间很长，而其实p函数本身是不需要运行这么长时间的，而是上下文切换等过程将它的时间拖长了。

       而且，转移预测和高速缓存的命中率，对这个计数值也会有影响。通常情况下，为了减少高速缓存不命中给我们程序执行时间带来的影响，可以执行这样的代码：

       double time_warm(void)

       {

              p();

              start_counter();

              p();

              get_counter();

}

它让指令高速缓存和数据高速缓存都得到了warm-up。

       接下来又有问题。如果我们的应用是属于那种每次执行都希望访问新的数据的那种呢？在这种情况下，我们希望让指令高速缓存warm-up，而数据高速缓存不能warm-up，很明显，time-warm函数低估我们的运行时间了。进一步修改：

       double time_cold( void )

       {

              p();

              clear_cache();

              start_counter();

              p();

              get_counter();

}

注意，程序中加入了一个清除数据缓存的函数，这个函数的具体实现很简单，依情况而定，比如举个例子：

       volatile int tmp;

       static int dummy[N];     //N是需要清理缓存的字节数

 

       void clear_cache( void )

       {

              int i, sum = 0;

              for( i=1; i

                     dummy[i] = 2;

              for( i=1; i

                     sum += dummy[i];

              tmp = sum;

}

具体原理很简单，定义一个数组并在其上执行一个计算，计算过程中的数据会覆盖高速数据缓存中原有的数据。每一次的store和load都会让高速数据缓存cache这个数组，而定义为volatile的tmp则保证这段代码不会被优化。

       这样做，是不是就万无一失了呢？不是的，因为大多数处理器，L2高速缓存是不分指令和数据的，这样clear_cache会让所有p的指令也被清除，只不过：L1缓存中的指令还会保留而已。

       其实上面提到的诸多原因，都是我们不能控制的，我们无法控制让高速缓存去加载什么，不去加载什么，加载时去掉什么。保留什么。而且，这些误差通常都是会过高估计真实的运行时间。那么具体使用时，有没有什么办法来改善这种情况呢？有，就是The K-Best Measurement Scheme。这其实很麻烦，所以在具体实践中都不用它。

四、gettimeofday函数计时^[4]

       gettimeofday是一个库函数，包含在time.h中。它的功能是查询系统时钟，以确定当前的日期和时间。相对于间隔计数的小适用范围和周期计数的麻烦性，gettimeofday是一个可移植性更好相对较准确的方法。它的原型如下：

       struct timeval

       {

              long tv_sec;  //秒域

              long tv_usec;       //微妙域

}

int gettimeofday( struct timeval *tv, NULL);

       这个机制呢，具体的实现方式在不同系统上是不一样的，而且具体的精确程度是和系统相关的：比如在Linux下，是用周期计数来实现这个函数的，所以和周期计数的精确度差不多，但是在Windows NT下，是使用间隔计数实现的，精确度就很低了。

       具体使用，就是在要计算运行时间的程序段之前和之后分别加上gettimeofday( &tvstart, NULL)、gettimeofday( &tvend, NULL)，然后计算：

(tvend.tv_sec-tvstart.tv_sec)+(tvend.tv_usec-tvstart.tv_usec)/1000000

就得到了以秒为单位的计时时间。

五、clock函数

       clock也是一个库函数，仍然包含在time.h中，函数原型是：

       clock_t clock( void );

功能：返回自程序开始运行的处理器时间，如果无可用信息，返回-1。转换返回值若以秒计需除以CLOCKS_PER_SECOND。（注：如果编译器是POSIX兼容的，CLOCKS_PER_SECOND定义为1000000。）^[5]

       使用clock函数也比较简单：在要计时程序段前后分别调用clock函数，用后一次的返回值减去前一次的返回值就得到运行的处理器时间，然后再转换为秒。举例如下：

       clock_t starttime, endtime;

       double totaltime;

       starttime = clock();

       …

       endtime = clock();

       totaltime = (double)( (endtime - starttime)/(double)CLOCKS_PER_SEC );

六、time函数

       在time.h中还包含另一个时间函数：time。文献[6]对其进行了详细的介绍。通过time()函数来获得日历时间（Calendar Time），其原型为：time_t time( time_t * timer )。通过difftime函数可以计算前后两次的时间差：double difftime( time_t time1, time_t time0 )。用time_t表示的时间（日历时间）是从一个时间点（例如：1970年1月1日0时0分0秒）到此时的秒数，则此函数的前后两次时间差也是以秒为单位。

       比如：

       time_t startT, endT;

       double totalT;

       startT = time( NULL );

       …

       endT = time( NULL );

       totalT = difftime( startT, endT);

       关于此函数的其他应用请参见文献[6]。

总结：

       使用相应的方法，调用相应的函数，还需要关注它们可以表示的范围和精度，这样才能“挑肥拣瘦”。先来看看时间函数中经常用到的两个数据类型的定义：

       // clock_t 的定义

#ifndef _CLOCK_T_DEFINED
typedef long clock_t;
#define _CLOCK_T_DEFINED
#endif

 

// time_t 的定义

#ifndef _TIME_T_DEFINED
typedef long time_t;

 

 

#define _TIME_T_DEFINED

#endif

 

       long型数据的取值范围是-2147483648 ~ [phone]。所以，gettimeofday函数取得的时间最大值为2147483647 + 2147483647 / 1000000 = 2147485794.483647 s，大约为68.096年；clock函数取得的时间最大值为2147483647 / 1000000 = 2147.483647 s，大约为35.79分钟；

time函数取得的时间最大值为2147483647 s，大约为68年。

 

       这里只是介绍Linux平台下c语言中计算程序运行时间的方法，它们各有利弊，依据自己的需要可以使用对应的方法。在Windows平台下还有其他计算程序运行时间的方法，在此不叙。

 

参考文献

[1] “linux time命令详解”，；

[2] “Linux命令详解——time”，

http://blog.csdn.net/thinkerABC/archive/2006/04/01/647272.aspx；

[3] “测量程序运行时间的几种方法”，http://oss.lzu.edu.cn/blog/article.php?tid_905.html；

[4] “如何精确测量程序运行时间”，；

[5] “clock”，http://blog.csdn.net/xxyakoo/archive/2008/12/17/3539590.aspx；

[6] “c语言对时间的处理函数和计时的实现”，

http://blog.csdn.net/adm_qxx/archive/2007/05/02/1594788.aspx。