轉載自:http://blog.chinaunix.net/uid-23208702-id-75182.html
計算程式運作時間(time_t, clock_t)-whyliyi-ChinaUnix部落格
我們有時需要得到程式的運作時間,但我們也要知道,根本不可能精确測量某一個程式運作的确切時間 [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 ~ +2147483647 。是以, 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 指令詳解”, http://www.admin99.net/read.php/185.htm ;
[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] “如何精确測量程式運作時間”, http://www.forwind.cn/2008/05/10/measure-time-preciely/ ;
[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 。