# 2016q3 Homework1 (clz) contributed by <`CheHsuan`> ## 目標 閱讀 重新理解數值 裡頭關於 count leading zero (clz) 的描述，設計實驗，比較 32-bit 數值對以下實做的效能差異： * recursive version * iteration version * binary search technique * byte-shift version * Harley’s algorithm ## 程式碼分析 ```c uint8_t clz(uint32_t x) { /* shift upper half down, rest is filled up with 0s */ uint16_t upper = (x >> 16); // mask upper half away uint16_t lower = (x & 0xFFFF); return upper ? clz(upper) : 16 + clz(lower); } ``` 老師給的版本有一個問題，就是沒有中止條件使程式跳出recursive call,所以必須改寫一下 ```c uint8_t clz_binary_recursive(uint32_t x, int shift) { if (x == 0) return 32; if (shift == 0) return 0; if (x <= (0xFFFFFFFF >> shift)) return shift + clz_binary_recursive(x << shift, shift / 2); return clz_binary_recursive(x, shift / 2); } ``` 這個寫法是類似binary search的方式，理論上時間複雜度為O(logN) ## Recursive Version ```c uint8_t clz_recursive(uint32_t x) { return x ? clz_recursive(x>>1) - 1 : 32; } ``` 但這個版本的時間複雜度是O(N)，而且比iteration版本的clz多出了function call的成本 ## Iteration Version ```c uint8_t clz_iteration(uint32_t x) { int count = 0; while(x != 0) { x = x >> 1; count++; } return 32 - count; } ``` 時間複雜度為O(N) ## Binary Search Technique 此版本我是參考老師[重新理解數值](https://hackmd.io/s/SkKZBXZT#count-leading-zero)裡面的作法，從這個算法來看，時間複雜度為O(logN) ## Byte-shift Version 一樣參考[重新理解數值](https://hackmd.io/s/SkKZBXZT#count-leading-zero)，這版本的算法的時間複雜度和binary search technique一樣為時間複雜度為O(logN)，只少了一次if比較，不過應該不會相差太多 ## Harley's Algorithm ```c static uint8_t Table[64] = { 32, 31, 0, 16, 0, 30, 3, 0, 15, 0, 0, 0, 29, 10, 2, 0, 0, 0, 12, 14, 21, 0, 19, 0, 0, 28, 0, 25, 0, 9, 1, 0, 17, 0, 4, 0, 0, 0, 11, 0, 13, 22, 20, 0, 26, 0, 0, 18, 5, 0, 0, 23, 0, 27, 0, 6, 0, 24, 7, 0, 8, 0, 0, 0}; ``` 修改table內數字,OK成功 ## 時間量測方法 參考compute-pi作法，使用`clock_gettime()`函式 man一下 `int clock_gettime(clockid_t clk_id, struct timespec *tp);` :::info The clk_id argument is the identifier of the particular clock on which to act. A clock may be system-wide and hence visible for all processes, or per-process if it measures time only within a single process. ::: ### CLOCK_REALTIME 在manual裡面指出，clock_gettime可以指定量測system-wide time,也就是wall clock time，因此會因機器假如同時運行其他程式的話，會影響到時間量測的準確度，所以我們不考量使用這方法 ### CLOCK_MONOTONIC和CLOCK_MONOTONIC_RAW 利用系統的jiffies來計算時間，當發生time interrupt時，便把紀錄+1 ### CLOCK_PROCESS_CPUTIME_ID 計算整個process在kernel space和user space所花費的時間，假如是多執行緒，會將每個thread所花的時間加起來 ### CLOCK_THREAD_CPUTIME_ID 計算單個thread在kernel space和user space所花費的時間 ### timespec結構 ```c struct timespec { time_t tv_sec; /* seconds */ long tv_nsec; /* nanoseconds */ }; ``` ## 實驗數據 這次的實驗環境是計算0X0~0XFFFF的clz，每個方法都跑100次，數據如下 ![](https://i.imgur.com/Ero1w5D.png) 從圖中可以看出兩件事情 1. 執行時間會有振盪的現象 2. iteration和recursive雖然都是O(N)，但iteration因為少了call function的overhead，所以執行時間平均來說較recursive少 再把跑的次數拉大一點來看，一樣是0X0~0XFFFF各跑5000次 ![](https://i.imgur.com/dY9VWJV.png) 針對32 bits unsigned integer的極值(0~4294967296)各跑1次 ![](https://i.imgur.com/SoIitho.png) 演算法的重要性！recursive的版本花到487.10秒，也就是八分鐘，夠吃完一碗泡麵了 :smile: ![](https://i.imgur.com/fGAj3Vb.png) ||recursive|binary recursive|iteration|byte-shift|binary search technique | :------ | ------: | ------: |------: | ------: | :------: | |0| 486.492851| 110.374512|264.005961| 22.064742| 21.832292 |1| 485.631612| 110.86067| 263.157863| 22.039492| 21.640222 OK，把recursive的版本用O(N)和O(logN)的方法來比較一下，執行時間相差了約4倍(486：110) 而同樣都是O(logN)的算法，recusive function call和one function call with multiple if-else的方法來比較，時間也差了大概5倍(110：22) 加入Harley ![](https://i.imgur.com/uFDyH1N.png) 最後總測試 ![](https://i.imgur.com/vBMNiGr.png) ## 應用實例 [WIP]