# 2016q3 Homework1 (clz)
contributed by <`aweimeow`>
###### tags: `sysprog21` `aweimeow`
>> 注意命名方式 Homework1 表示「第一週」，不是第一個，每週都有「若干多份作業」
### 作業環境
* OS: Ubuntu 14.04.4 LTS
* CPU: Intel(R) Core(TM) i5-4210M CPU @ 2.60GHz
* Memory: 8G
* Cache:
* L1d cache: 32KB
* L1i cache: 32KB
* L2 cache: 256KB
* L3 cache: 3072KB
### recursive clz
把作業有瑕疵的版本修改一下變成：
```C=
unsigned clz(uint32_t x, int c)
{
if (!x) return 32;
if (c == 0) return 0;
/* shift upper half down, rest is filled up with 0s */
uint16_t upper = (x >> c);
// mask upper half away
uint16_t lower = (x & (0xFFFF >> (16 - c)));
return upper ? clz(upper, c / 2) : c + clz(lower, c / 2);
}
```
不過看了 [louielu的共筆](https://hackmd.io/IwMwDCCsCmAsCcBaeBmA7AJkbDIAciAhgEazGK4aGQrzTQDGTQA=#) 得知有 `__builtin_clz`，也感謝他的踩雷，我會小心避開地雷 XD
### About Testing
這邊在寫 Testing 的時候不知道為什麼碰到困難了，弄了二十分鐘還是找不到原因 QQ
```C
assert(result && printf("Test Fault: %d", i));
```
`result` 是一個布林值，將 `recursive clz` 與 `builtin_clz` 互相比較結果，相等為 1，不同為 0。
但是這樣子 assert 時，不會有 assert Error (這個當然沒有錯），問題出在後面應該是錯誤時才會 print 的訊息也跟著出來了。
我思考了之後認為發生的原因是出在於 `result = 1` 因此 && 後面的句子理所當然也會執行了。
可是這樣就與老師上課時所提到的技巧不一樣，是不是我哪邊記錯了，在這篇 [StackOverflow](http://stackoverflow.com/a/5868001) 的文章也有提到相同的用法。
>> assert 中的參數 expression 本身就是 scalar (純量，當然是數值)，於是你應該改成 `assert(result && "messages")`，這樣才符合期望。 [name=jserv]
暫時不知道怎麼解決，只好先把 printf 拿掉了，如果有人知道怎麼解請編輯我的紀錄留言告訴我，感謝 QQ。
以下是我的 Test Function
```C=
bool test_clz(void *test_func)
{
unsigned (*clz)(uint32_t, int) = test_func;
assert(clz(0, 16) == 32);
for (uint32_t i = 1; i < UINT_MAX; i++) {
bool result = (clz(i, 16) == __builtin_clz(i));
assert(result);
if (!result)
return 0;
}
return 1;
}
```
不過這個要跑多久呢 ... 先看看 __builtin_clz 跑完 UINT_MAX 會多久，
在編譯的時候我用的是：
```shell
$ gcc -o main -O0 -std=gnu99 main.c -lm
```
然後執行結果：
```shell
$ ./main
execution time: 10.105143 sec
```
再來跑 recursive version：
```shell
$ ./main
execution time: 168.580997 sec
```
阿阿阿阿我的眼睛業障真重阿！！！跑一次實驗就要這麼久，更不用提要跑 Test Function 會跑多久了 ...
但是最久的 recursive ver. 都跑完了，iteration ver 不可能比這個還久吧，總之就先把這些都跑一輪吧。
iteration version:
```shell
$ ./main
execution time: 91.110889 sec
```
binary search version:
```shell
$ ./main
execution time: 29.033097 sec
```
Byte Shift Version:
```shell
$ ./main
execution time: 28.998363 sec
```
為什麼 builtin 可以這麼快 Orz
### gnuplot
接下來是把剛剛的結果們變成以 gnuplot 作圖，這邊先說明一下我給 gnuplot 的 input 是：
:::info
因為在這個題目當中，我們的 range 非常大，從 0 至 4294967295（大約是 42.9 億），這個要把這麼多筆寫到檔案也是一個很可怕的數字，所以在此我就不這麼作，我以 100萬 作為一個單位，也就是說，假設 x 是 input 的話，0 <= x < 1000000，會作為一筆資料寫入檔案當中。
檔案會長成這樣子：
```
1000000 0.010095
2000000 0.006899
3000000 0.006891
4000000 0.007032
5000000 0.006054
6000000 0.006080
7000000 0.005785
8000000 0.005898
9000000 0.005836
10000000 0.005786
```
第一筆資料表示是 0 ~ 1000000 所計算的秒數，時間長達0.010095 秒
而在產出來的結果，X 軸表示我輸入的數值，Y 軸表示我執行的時間。
:::
Byte-Shift Version
Binary-Search Version
Iterate Version
Recursive Version
### 查表法？
如果說，程式在執行的時候有一個表可以查，那應該會快很多，在一個 32 bits 的狀況當中，我只需要建立出一個 16 bits 的表，與前面的 recursive 作法相似，把 32 bits 切成高、低兩組。
如果高位那半部非 0，那就直接回傳高位在 16 bits 表查出的結果。否則就回傳 16 + 低位在 16 bits 表查出的結果。
那麼這個表總共會有 65536 格，0 ~ 65535！
Table Initialize
```cpp=
#define L 65536
int T[L] = {0};
void init(int *T){
int i,j;
for ( i=0 ; i<L ; ++i ){
for ( j=i^0xffff ; j ; j>>=1 ){
T[i] = ((j&1) ? T[i]+1 : 0);
}
}
}
```
Calculate clz
```cpp
int clz_T(uint32_t x, int *T){
return T[x>>16] + ( (T[x>>16]==16) ? T[x&0xffff] : 0 );
```
解釋一下程式在做什麼：
:::info
當 Table 要初始化的時候，會有 0 ~ 65535 的 Index，分別代表著 0 的 clz 計算後 value 應該是 32, 1 的結果是 31, ... 等。
所以一開始會有一個 for loop(line 5)，然後 j 是一個 i 與 0xFFFF 互斥或後的結果，0 會變成 1111，且只要 j 不為 0 就會繼續執行，每次迴圈 j 會右移一位。
再來是檢查 j 的最後一位（j&1），如果結果為 1(True)，則代表在還沒互斥或之前的 i 的這個位置是 0，把 T[i] 累加上去。那如果 j&1 是 0(False) 呢，代表我們現在撞到 1 了，所以前面所計算的 0 都不能算數，因此把 T[i] 歸零。
===
再來是 clz_T 的部份，return 把他切成左右兩部份來看，左部份表示要查 x 的 higher part 的值是多少。右半部則是如果左半部高位結果為 16 （代表全部都是 0 組成），這時我們才需要繼續去看低位部份的結果，並把他加起來。反之，如果左半部非 16，那就直接回傳左半部的結果即可
:::
#### 實測數據
```
create table execution time: 0.004787 sec
execution time: 17.292436 sec
```
建立這個表格花費 0.004787 秒，而從 0 查到 2^32^-1 總共花了 17.292436 秒。
！突然想到用前面學過的重複執行來平均執行的時間
```
$ perf stat --repeat 10 -e cache-misses,cache-references,instructions,cycles ./test
Performance counter stats for './test' (10 runs):
699,734 cache-misses # 35.430 % of all cache refs
1,374,100 cache-references
133,179,793,211 instructions # 2.55 insns per cycle
51,319,436,287 cycles
18.757043258 seconds time elapsed ( +- 2.60% )
```
但是這個作法並不是這麼的實用，因為 clz 不見得會需要查那麼多次阿 XDD 只是因為測試需求測完 32 bits 的所有輸入才比較實用而已。
再來用著 OpenMP 加速看看：
```
create table execution time: 0.014015 sec
execution time: 12.710633 sec
```
發現建立表格的時間變長了。不過這個時間與我使用 `builtin clz` 跑的 `10.105143 sec` 只差一點點了！心滿意足 XD
>> 這會導致嚴重的 cache miss，應該透過數學分析法去降低表格大小，請研究 Harley’s algorithm [name=jserv]
最後再加上沒有開 OpenMP 的圖，不開的原因是因為開了之後時間飄很大，而且開了也沒快很多。
Sign in with Wallet
Connect another wallet