# 2016q 3Homework4 (clz)
contributed by <`heathcliffYang`>, <`janetwei`>

>>請記得更新分組面中的 github 連結
>>[color=red][name=課程助教]

## 目標
* 閱讀[重新理解數值](https://hackmd.io/s/SkKZBXZT)
* 設計實驗，測試各個 clz 程式處理 32-bit 數值的效能差異，並分析原因
* 進行效能優化

## [重新理解數值](https://hackmd.io/s/SkKZBXZT)
### bite-wise operator
* `x & (x - 1) == 0`
在unsigned的情況下,可以判別X是否為2的N次方,若為true則是
* `x | (x + 1)`
確定最低位元的值
### Count leading zero
* ffs():回傳給定數值的first bit set的位置
例如
* 128 在 32-bit 表示為 `0x10000000`，ffs(128)會回傳 8
* 129 在 32bit 表示為 `0x10000001，`ffs(129) 會回傳 1
但是這裡發現錯誤,應該是寫成
* 128 在 32-bit 表示為`10000000`,ffs(128)會回傳 8
* 129 在 32bit 表示為 `10000001`,ffs(129) 會回傳 1

## 觀察與實驗設計
### 1. clz.c & clz.h : 將各個clz函式蒐集
* 現有材料為五種clz的函式:
iteration, binarySearch, byteShift, recursive, harley
- [ ] recursive 修正
32可以由16,8,4,2,1 組成 (有或沒有總共32種組合，0~31)

uint32_t count = 16;     // Global variable 讓 recursive 每一層知道shift到哪
int recursive(uint32_t x)
{
    int result;
    // shift upper half down, rest is filled up with 0s
    uint16_t upper = (x >> count);    // 另存shift之後的值以供檢查是否足夠shift

    if(x==0) return 32;

    // stopping condition
    if(count == 1) {
        return !(x >> 1);
        /* 01 & 10 為例，shift 1之後分別為0 & 1，
           前者是多一個0，但shift 1之後沒有值代表x還有一個0，所以要回傳1(也就是要+1)*/
    }

    // shifting count and go into recursive
    count >>= 1;
    result = upper ? recursive(upper) : (count << 1) + recursive(x);
    /* shift成功代表leading zero的數量不足count，shift之後繼續用更小的count去檢查
       shift不成功代表leading zero的數量足夠count，用shift前的值繼續檢查，而count<<1則把
    該次檢查計算的leading zero數量加上*/
    count <<= 1;  // 以防多次執行時count的值發生錯誤
    
    return result;
}

:::info
參考[黃鏡清](https://github.com/workfunction/clz-tests)同學的版本，並做一些修改，e.g. 拿掉`mask`，因為在mask後x跟lower的值會不同的情況下，必是做upper的
:::
>> for example 的縮寫是 [e.g.](https://en.wiktionary.org/wiki/e.g.)，不是 "ex" [name=jserv]

- [ ] harley
(仍在理解中)

int harley(uint32_t x)
{

    static int table[64] =
     {32,31, u,16, u,30, 3, u,15, u, u, u,29,10, 2, u,
       u, u,12,14,21, u,19, u, u,28, u,25, u, 9, 1, u,
      17, u, 4, u, u, u,11, u,13,22,20, u,26, u, u,18,
       5, u, u,23, u,27, u, 6, u,24, 7, u, 8, u, 0, u};

    /* Propagate leftmost 1-bit to the right */
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
    /*把最高位後的位元全部補為1*/
	
    /* x = x * 0x6EB14F9 */
    x = (x << 3) - x;   /* Multiply by 7. */
    x = (x << 8) - x;   /* Multiply by 255. */
    x = (x << 8) - x;   /* Again. */
    x = (x << 8) - x;   /* Again. */

    return table[x >> 26];
	/*用前面6個位元表示ｌｅａｄｉｎｇ　ｚｅｒｏ有幾個*/
}

* 第一部分 : **把最高不為零位之後的位元全部補為1**可以算是一種第一次的分類，歸類相同clz數值的數。
* 第二部分 : 之後用**一些運算**(尚在理解中)讓各個數產生一對一的對應，之後做表格 -> hash function 的概念應用。
* shift 26 bits，也就是用剩下的 6 bits 來表示0~32的 clz 可能值，但總數是64。根據程式碼的觀察結果，我們認為他是用 output 的結果去做 table
>> 延伸閱讀: [Fast, Deterministic, and Portable Counting Leading Zeros](http://embeddedgurus.com/state-space/2014/09/fast-deterministic-and-portable-counting-leading-zeros/) [name=jserv]

* [error](http://stackoverflow.com/questions/6131455/compile-error-c2099-initializer-is-not-a-constant) : initializer element is not constant ---> `const int` 在 C 裡面不算是 constant，要用`#define`

### 2. 測試效能 & 作圖
#### 測執行時間
* 用0 ~ 4000先小測試一次
>> 製圖不要用 "function1", "function2" 一類不容易看不出來的名稱 [name=jserv]

Performance counter stats for './benchmark_time_１':

      12,2282,3714      cache-misses                                                
 10,2295,7826,9347      cpu-cycles                                                  
 17,5241,2939,1061      instructions # 1.71  insns per cycle
      18,9201,5112      branch-misses

    8635.382627756 seconds time elapsed

>> 除了 cache miss，也用 [prefetch 案例](/s/ryTASBCT) 裡頭 perf 參數和分析方式去探討 [name=jserv]

#### 資料處理：
* 一開始嘗試用Makefile的`for`去做跑數值的輸入，但是常常跑到一段時間後電腦就掛了，錯誤訊息是: too long list。
* 把 list 移到 benchmark 裡面，也因為 csv 的檔案太大開不太起來，連圖也不太能畫
* ==目前正在改寫 Makefile，預計分別輸入到不同檔案，正在解決檔案名稱與變數相關的問題......==

我們試著用 iteration 函式執行一次0到2^32-1的時間,做圖結果如上
因為資料龐大,每執行一次就會耗費很多時間,因此我們還在思考簡化執行的方法


* 因為跑全部的資料檔案太大，所以我們只取 clz 的不同值跑了一次
* 用 perf top 觀察到函式熱點依序為harley-> iteration-> recursive-> binary-> byteSearch

#### 效能分析：
* iteration version:
當數字小的時候跑的很快,但是當數字很大時,迴圈裡面執行的行數更多,所以和其他函式比較起來效能不是很好
* binary version & byte Shift:
因為在判斷後做的事情一樣，可是判斷的方法略有不同，一個是直接去比值，一個是shift之後值是否為零，我們認為， byteShift 做的事情比較多，但是他的效能卻比較好;對於數值的大小來說,因為做的判斷次數一樣,所以執行時間和其他函式比相對穩定
* recursive version：
在數值較小時,叫用函式次數較多,所以執行時間較長;和其他函式相比,他的函式執行次數多了幾倍,因此效能最差
* harley's algorithm:
不管輸入的數值大小為何,函式所執行的動作都相同,因此他是執行時間最穩定的函式

### 3. 應用（not yet）
1. **null suppression**
2.

>>中英文關鍵字之間要使用空白區隔喔！[color=red][name=課程助教]