# 2018q1 Homework1 (phonebook)
contributed by < `BroLeaf `>
###### tags `BroLeaf`
### Reviewed by `TingL7`
* github commit只有標題，應有具體的內文敘述做了什麼及為什麼做。
* 請重新思考segmentation fault的意思。在宣告太大的陣列時，應該會出現如下的error，而不會讓你執行。且hash size採用4096時，其所需的記憶體空間為4096\*8(entry\* size) byte=32kb，不算很大。
``main.c:(.text+0x1f0): relocation truncated to fit: R_X86_64_32S against symbol `Head' defined in .bss section in /tmp/cciv5DkZ.o``
* 沒有在.h檔宣告function，編譯器不確定function是否存在，因此會丟出一個警告，而警告會被蓋住看不見是因為，警告只會在第一次編譯的時候出現。
* 是否在標頭檔宣告hash()，結果相差很大，可能要重新思考，沒有宣告時，是否有正確呼叫hash()？
* Hash修正有提到實做了好幾個hash function，應把實驗過程、效能比較一併show出來，而不是只給結論。

### Reviewed by `bauuuu1021`
* commit message 可以再加上內文，較容易讓人了解改變內容
* [Implement Hash function](https://github.com/BroLeaf/phonebook/commit/111f8f052ad616348cc5db48350fb78da8e518d0) 建議將 Implement 改為 Modify ，較貼近你所做的變更
* 針對之前我們討論過的 miss rate 問題做了點推論，可見 [連結](https://hackmd.io/VWXiZmtoTyWP9LRSf-pmBw?view#%E7%92%B0%E5%A2%83%E5%B0%8D-Cache-miss-%E4%B9%8B%E5%BD%B1%E9%9F%BF)

### Reviewed by `HexRabbit`
* "若採用 4096 或是更大的數字會造成部份結果，可能是 array 使用空間過大導致 segmentation fault"，`sizeof(entry *)*4096`的大小應該不至於使用過大的空間造成 segfault，或許可能是存取越界，應該繼續分析問題。
* [Reduce entry size and Use hash function](https://github.com/BroLeaf/phonebook/commit/2817ebe931c810e57fadbc573dde419729a74817 "Reduce entry size and Use hash function") 建議將兩個實做的commit拆開，而不是寫在一起。

## 開發環境

$ uname -a
Linux broleaf-X550JX 4.13.0-36-generic #40~16.04.1-Ubuntu SMP Fri Feb 16 23:25:58 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux

$ lscpu
Architecture:          x86_64
CPU 作業模式：           32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                8
On-line CPU(s) list:   0-7
每核心執行緒數：          2
每通訊端核心數：          4
Socket(s):             1
NUMA 節點：             1
供應商識別號：            GenuineIntel
CPU 家族：              6
型號：                  60
Model name:            Intel(R) Core(TM) i7-4720HQ CPU @ 2.60GHz
製程：                  3
CPU MHz：              2593.812
CPU max MHz:           3600.0000
CPU min MHz:           800.0000
BogoMIPS:              5187.62
虛擬：                  VT-x
L1d 快取：              32K
L1i 快取：              32K
L2 快取：               256K
L3 快取：               6144K
NUMA node0 CPU(s):     0-7
Flags:                 fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt aes xsave avx f16c rdrand lahf_lm abm cpuid_fault epb invpcid_single pti retpoline tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt dtherm ida arat pln pts

## 系統設定

根據 [助教影片](https://www.youtube.com/watch?v=rjpBTT6AmeU) 完成 linux 系統安裝，說明淺顯易懂：
分割硬碟 -> USB開機 -> linux安裝

重開機後如果要切換 OS 必須進入 BIOS 去修改 boot 的順序，不知為何 linux 的開機選單沒有辦法成功啟動 Windows 的 boot loader 。不過問題不大就先擱置了。

題外話：第一次裝完想裝一個看起來很酷的輸入法，使用說明說如果不能用，就移除 ibus 重開機就好了。我就用了

sudo apt-get autoremove --purge ibus

想說既然用不到不如連一些套件都清掉，下場就是重開機後 ubuntu 整個進不去，只好整個重灌重來一次QQ，後來才知道，原來這樣會多刪掉不該刪的套件，移除後還要再多下指令

sudo apt-get install unity-control-center

把重要套件裝回來，這件事只好當個慘痛教訓。

## 實驗紀錄

實驗一開始：

Performance counter stats for './phonebook_orig' (100 runs):

         1,204,781      cache-misses              #   84.552 % of all cache refs      ( +-  0.46% )
         1,424,900      cache-references                                              ( +-  0.39% )
       263,081,146      instructions              #    1.27  insn per cycle           ( +-  0.02% )
       207,675,353      cycles                                                        ( +-  0.35% )

       0.061335207 seconds time elapsed                                          ( +-  0.43% )

plot：

* cache miss 居然高達84.55%

### 1.縮減 entry size

entry *findName(char lastName[], entry *pHead)
{
    while (pHead != NULL) {
        if (strcasecmp(lastName, pHead->lastName) == 0)
            return pHead;
        pHead = pHead->pNext;
    }
    return NULL;
}

* 會造成 cache-miss 就是因為 CPU 在 cache 中找不到資料，而透過程式碼就會發現，資料只有比對 lastName 若把其他資料用另一個 struct 包起來，那麼同樣大小的 cache 是否能放入更多筆資料，進而減少 cache-miss 。
* 結果：

Performance counter stats for './phonebook_opt' (100 runs):

           159,328      cache-misses              #   40.656 % of all cache refs      ( +-  1.35% )
           391,897      cache-references                                              ( +-  1.24% )
       244,816,352      instructions              #    1.88  insn per cycle           ( +-  0.02% )
       129,924,966      cycles                                                        ( +-  0.28% )

       0.038443079 seconds time elapsed                                          ( +-  0.37% )

* cache miss 直接掉到剩40%
* 而 findName 耗時沒有什麼改變

### 2. Hash Table
* [hash function 觀念和實務](https://hackmd.io/s/HJln3jU_e)
* [hash 詳細運作](http://alrightchiu.github.io/SecondRound/hash-tableintrojian-jie.html#ht)

參考了 [HMKRL](https://hackmd.io/s/HyyHC6moW#) 這位同學的作法，採用 [dj2b hash function](http://www.cse.yorku.ca/~oz/hash.html) 來作為 hash 的演算法
HASH_SIZE 大小為 2048 ，是我實測出最好的結果，若採用 4096 或是更大的數字會造成部份結果，可能是 array 使用空間過大導致 segmentation fault
配合上面縮減 struct size 實作：

unsigned long hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c = 0;
    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    return hash;
}

entry *findName(char lastName[], entry **pArr)
{
    entry *pHead = pArr[hash((unsigned char*)lastName) % HASH_SIZE];
    while (pHead != NULL) {
        if (strcasecmp(lastName, pHead->lastName) == 0)
            return pHead;
        pHead = pHead->pNext;
    }
    return NULL;
}

entry *append(char lastName[], entry **pArr)
{
    unsigned long index = hash((unsigned char*)lastName) % HASH_SIZE;
    entry *e = (entry *) malloc(sizeof(entry));
    e->pNext = pArr[index];
    pArr[index] = e;
    strcpy(e->lastName, lastName);

    return e;
}

 Performance counter stats for './phonebook_opt' (100 runs):

           677,197      cache-misses              #   75.195 % of all cache refs      ( +-  0.70% )
           900,588      cache-references                                              ( +-  0.51% )
       285,733,335      instructions              #    1.14  insn per cycle           ( +-  0.02% )
       249,778,339      cycles                                                        ( +-  0.92% )

       0.073731479 seconds time elapsed                                          ( +-  0.99% )

* 可以看到 findName() 所花費的時間已經大量減少，到看不見了
* 但是 cache-miss 數仍不太理想
* 結果呈獻出來和同學之前所實測的差不多。
>我後來又觀察其他同學的共筆，發現這位同學的程式碼有些奇怪的地方，需要再 phonebook.h 檔宣告 hash function 以我自己的例子要加上：
>```
>unsigned long hash(char *str);
>```
>原本編譯會跳出警告說 hash 宣告有問題，但是如果直接
>```
>sudo make cache-test
>```
>警告就會直接被結果蓋住，看不到QQ
>而最新的結果：
>```
> Performance counter stats for >'./phonebook_opt' (100 runs):
>
> 81,644 cache-misses ># 19.681 % of all cache refs ( +- >2.60% )
> 414,839 cache-references >( +- 0.92% )
> 234,057,482 instructions ># 1.65 insn per cycle ( +- >0.02% )
> 141,818,166 cycles >( +- 0.57% )
>
> 0.042343138 seconds time elapsed >( +- 0.59% )
>```
>cache-miss 結果直接掉到19.681%阿!!!
### 3. Hash function 修正
* [Hash funcion 比較表](http://blog.csdn.net/qq7366020/article/details/8730425)
* 我根據上面的聯結，也實做出好幾個 Hash function 大致上的 cache-miss rate 都差不多，目前我測試出最好的結果是用 APHash function 下去實作， HASH_SIZE 是 1024

 Performance counter stats for './phonebook_opt' (100 runs):

            72,442      cache-misses              #   17.652 % of all cache refs      ( +-  0.31% )
           410,390      cache-references                                              ( +-  0.70% )
       264,714,706      instructions              #    1.85  insn per cycle           ( +-  0.02% )
       143,473,401      cycles                                                        ( +-  0.41% )

       0.042652042 seconds time elapsed                                          ( +-  0.55% )


---
## 因為自動飲料機而延畢的那一年
[讀後心得](https://hackmd.io/Y21y1QgnQCOOTl5BqRkNdQ?view)