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

程式碼分析

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,所以必須改寫一下

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

uint8_t clz_recursive(uint32_t x)
{
    return x ? clz_recursive(x>>1) - 1 : 32; 
}

但這個版本的時間複雜度是O(N)，而且比iteration版本的clz多出了function call的成本

Iteration Version

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

此版本我是參考老師重新理解數值裡面的作法，從這個算法來看，時間複雜度為O(logN)

Byte-shift Version

一樣參考重新理解數值，這版本的算法的時間複雜度和binary search technique一樣為時間複雜度為O(logN)，只少了一次if比較，不過應該不會相差太多

Harley's Algorithm

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);

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結構

struct timespec {
    time_t   tv_sec;        /* seconds */
    long     tv_nsec;       /* nanoseconds */
};

實驗數據

這次的實驗環境是計算0X0~0XFFFF的clz，每個方法都跑100次，數據如下

從圖中可以看出兩件事情

執行時間會有振盪的現象
iteration和recursive雖然都是O(N)，但iteration因為少了call function的overhead，所以執行時間平均來說較recursive少

再把跑的次數拉大一點來看，一樣是0X0~0XFFFF各跑5000次

針對32 bits unsigned integer的極值(0~4294967296)各跑1次

演算法的重要性！recursive的版本花到487.10秒，也就是八分鐘，夠吃完一碗泡麵了

	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

最後總測試

應用實例

[WIP]