Re: [問題] 執行時間的問題

看板C_and_CPP作者tropical72 (藍影)時間14年前 (2011/08/22 23:48)推噓6(6推 0噓 3→)

留言9則, 5人參與討論串2/2 (看更多)

※ 引述《scott90213 (剛好而已)》之銘言： : 想要計算一個程式中執行某個function所需的時間 : 使用了 clock 和 GetTickCount 建議用 GetTickCount，雖與 clock_t 精度都是毫秒級，但 GetTickCount 誤差應較小。要再高效的話用 QueryPerformanceCount / QueryPerformanceFrequency，這對計時器精度達微秒，但 MSDN 說要硬體支援 (恕我不知道要什麼硬體)，若硬體不支援，會間接調用 GetTickCount，精度變毫秒級。 : 結果都是0.000000 : 在計時結束之後，我分別印出t1和t2來監視 : 發現都是同樣時間，所以結果當然會是0.000000 : 那個function只有傳入2個參數 : 從一個array中的2個參數位置取出值然後回傳相減值 : 是因為執行時間太短嗎? 這也有可能，所以一般在做測 wall time，會測大量數據，如果你只是想測那種加、減、乘、除，過於基本運算的話，搞 asm 、用 profile 應該會好點。 : 有想過用while包住讓他執行很多次，是可以出現差距 : 但是空迴圈本身好像也會有執行時間你說對了，空回圈本身用到的是加法/減法和比較指令，如 int i=INT_MAX; while(i--); while loop 裡面本身就用到了減法與比較指令，這部份測時誤差在 wall time 裡面幾乎不可避免，我的心得是，只要你的副函式所花費時間，遠大於減法與比較指令時間，即使在 loop 那裡對測時有所影響，但並不會對整體 Function Performance Rank 有所影響。 : 這樣是不是就不準確了? : 有什麼辦法可以測得這種小函式的時間嗎? --- 1. 哪種程式適合 Wall Time 分析？一般而言，比較不建議「指令細節」上的研究做測時，因這樣測出來結果還蠻不準的；如 int i, ret, arr[100]; /* method 1 */ for(ret=i=0; i!=100; ++i) if(arr[i]==1) ++ret; /* method 2 */ for(ret=i=0; i!=100; ++i) ret += (arr[i]==1); 這在很多論壇、網站、比較進階的書上，都會提到， method 2 is better than method 1，可是很莫名奇妙的是，拿這二支程式去測時，測出來 100 次未必每個 Rank 都一樣，一方面可能是，這二個編出來的 asm code 本來就一樣，由於計時器本身之誤差，所以 Rank 會不一樣；即使編出來的 asm code 不一樣，但本身 ret 在做累加動作之計時誤差，可能便與 for loop index 之計時誤差相仿， Rank 也會不一樣，甚至可能遇到其他的情況是，compiler 有沒有開 Opt. 出來的 Rank 也不一樣，此處點到就好。像這種小技巧，我覺得沒計算機組織底的話，就多看一些別人的文章，把結論記下來就好了 ( 合理簡化 branch 是我看到的技巧 ) 若你的程式不是像上面這種小兒般的測試，可能是測試演算法 Wall Time，希望你有先分析過複雜度。若複雜度相同、coding 方式不同，一樣，Performance 量測方式順序 : asm 分析, profile, wall time 分析，如果不會 asm 分析、profile 不會用，剩下的只有 wall time 分析。唯一的例外是，如果你非資訊相關科系因為論文需要數據，而參考文獻也都用 wall time 分析，那你也用 wall time 分析，但提醒一點的是，目前學術用 wall time 分析，基本上測試機台都以 intel 為主 (至少我看得文獻似乎都這樣) 其它的測試環境該註明的，此處不再多說。 ---- 2. Compiler Optimized 下述必須先假設一件事，compiler 最後會開 Optimize，討論的 code 放在二個 func. int func1(int n) { int i, sum; for(sum=i=0; i<=n; ++i) sum+=i; return sum; } int func2(int n) { if(n&1) return (n+1)/2*n; else return n/2*(n+1); } 寫得好一點的 compiler，所有的問題、動作，都在 main 怎麼寫產生。不少人剛開始寫測時，只要確定他的副函式是對的，甚至連 main 裡面都不去接結果 int main() { DWORD t1, t2; int n = INT_MAX-1; t1 = GetTickCount(), func1(n) ,t2 = GetTickCount(); printf("func1 elaspes %u (ms)", t2-t1); t1 = GetTickCount(), func2(n) ,t2 = GetTickCount(); printf("func2 elaspes %u (ms)", t2-t1); } 以上面這段程式碼而言，比較聰明的 compiler 知道 func1, func2 是白跑的，在 Opt. 過程中，直接把這兩段拿掉，於是你得到的會是 t1=t2，白測。另外這份 code 也是無效的 int main() { DWORD t1, t2; int rst ,n = INT_MAX-1; t1 = GetTickCount(), rst = func1(n) ,t2 = GetTickCount(); printf("func1 elaspes %u (ms)", t2-t1); t1 = GetTickCount(), rst = func2(n) ,t2 = GetTickCount(); printf("func2 elaspes %u (ms)", t2-t1); } 即使你用了 rst 去接結果，但程式碼最後根本就用不到 rst ，這部份還是很容易被 compiler 吃掉。 ---- 3. Compiler Optimized Testing 要解決上述問題其實不難，架構也不只一種，最簡單的方式是直接再輸出 rst 即可，上面程式碼在我環境裡，加上輸出即可正常測得時間。比較麻煩的是另一種，即使用 rst 去接結果並輸出，卻測不出來，這情況其實不少見，我沒詳細去追原因，但也推被 Opt. 拿掉了， #1DoEorL- ，可參考裡面提到的例子。比較建議，也是最後解決方案，包成 function pointer，這部份較少 compiler 會拿掉，但也不可否認，這些都是看 compiler 怎麼 Opt. typedef int (*pFunc)( int); DWORD t1, t2; int i, rst, n=INT_MAX-1; pFunc pFuncArr[] = {func1, func2}; int Size = sizeof(pFuncArr) / sizeof(*pFuncArr); for(i=0; i!=Size; ++i){ t1=GetTickCount(), pFuncArr[i](n), t2=GetTickCount(); printf("func %d elaspes : %u (ms)\n", i,t2-t1); } 用 function pointer array 方式之後，甚至連 rst 都不用去接，結果一樣跑得出來。建議用 function pointer array 方式原因在於，這對於一份完整的測試，可能會有 20 個 sub function 要寫，也可能想到就突然再加一個 sub function，這種架構我認為會好點。 ---- 4. 短暫性測性若副函式本身符合第一點所述，不是在做簡單的 + - * / 這種太誇張簡單的運算，但執行還是太快，而又沒辦法將參數調大拉長時間，除了符合上述 (2. 3) 測試方式外，的確最常用的是設一個很大的 loop 下去跑，做為測試次數。如，跑一萬次、一億次副函式，至於計時方式也有兩種，程式碼供參考。 int i; const int TIMES = INT_MAX; const int n = INT_MAX-1; DWORD t1, t2, ts; // test 1 for(i=0; i!=TIMES; ++i){ t1 = GetTickCount(), func1(i), t2 = GetTickCount(); ts+= (t2-t1); } // test 2 t1=GetTickCount(); for(i=0; i!=TIMES; ++i){ func2(i); } t2 = GetTickCount(); ts = t2 - t1; 要用 test 1 還是 test 2 ? 不少人會用 test 1 ，選用 test 1 原因是，test 2 連 for loop 裡面的 inc, compare 都一起算進去。通常，我是選 test 2。以目前的 PC 而言，加法、比較指令應都只佔一個時脈週期，意指，一個加法、一個比較指令，會影響的時間是 ns 級的時間，但計時器本身的誤差，以 GetTickCount 而言，誤差是在 ms 級；即使用最好的 QueryPerformanceCount，誤差仍在 us 級，這樣下來，計時器本身在做「分佈累加」動作時的誤差，往往大於 for index 本身計時之誤差，這是我選用 test 2 原因。 >> 科學家估算地球到太陽的距離，絕對找不到一把夠大的尺去量的就我所知，目前估算地球到太陽距離大概有三、四種方法， Hubble Rule、parallax、open star clusters，簡而言之，大多都是用比率方式在估算，像地球密度怎麼算出來的？沒記錯的話也是用三角函式再加上比率概念去估算。故這提示，我認為是用多次測試做平均估算之提示。 ---- 5. task timeslice 這問題我不知道是不是只有我遇過，也不確定是這問題。之前寫過一些程式碼(不只一份)，進行多次測時，很妙的是，1000 次測時裡面，一定會有「少數」幾次是 16ms，其它都是 0 ms，那份原始碼數據我沒留，有機會的話可觀查這現象。後來碰了一點 OS 的東西，很自然想到，那個 16ms 和 windows task timeslice, 約 15.75 ms 極為相近，故我「一廂情願」認為，那此測試碼明明每次都是 0 ms，有少數跑到 16ms，是因 task timeslice 關係，故後來所有測試，至少測 10 次以上再做比較。這部份若有人有經驗或有不同看法，歡迎提出指教。 ---- 以上說明，應都有回答到問題，再次聲明的是，有必要到測 wall time 的情況 1. 分析過演算法複雜度 2. 分析過 asm, 或不會分析 asm 3. 跑過 profile , 看不出所以然 4. 老師或學術文獻要 wall time 測時，沒辦法，一定要測。若是非資訊學術文獻要 wall time 的話，不要想太多，大多都是配置、環境註明好，直接把數據放上去，根本沒人在放 asm 分析結果、profile 分析結果。 -- YouLoveMe() ? LetItBe() : LetMeFree(); -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 180.177.78.41

推

scott90213

08/22 23:54, , 1^F

08/22 23:54, 1^F

推

purpose

08/23 00:08, , 2^F

08/23 00:08, 2^F

→

tropical72

08/23 00:22, , 3^F

08/23 00:22, 3^F