# 2016q3 Homework 1 (phonebook)
contributed by <`FZzzz`>

### Reviewed by `believe7028`

- 可以對 perf 所量測得到的信息做說明更細緻的解釋，以及是否有其他事件數據可說明程式的狀況。
- Hash 取餘數採用的數`MAX_KEY_VALUES`使用質數是否比較好。
- 可以比較更多的雜湊函式。
- Hash 對資料表增加與刪除的操作會使得程式整體效能下降，也可以增加刪除的方法與效能評估。
- 如果未來資料一直增長，Hash 沒有機制應對而退化成Linked list。
- 如果資料一直增加，記憶體會放置不下。
- git commite message 可以增加細部說明來描述"remove useless"的詳細動作。

## 開發環境
* Destribution: Ubuntu 14.04.5 LTS (晚點更新)
* Kernel version: Linux4.4.0-38-generic
* CPU Cache:
* L1d: 32K
* L1i: 32K
* L2: 256K
* L3: 8192K

## 前情提要
我因為很久沒碰C了,所以想藉由這堂課重新摸一下和進一步去理解C和確認一下自己大學四年來學的東西
，另外原本是使用ubuntu 16.04 LTS的，但後來因為亂搞玩壞了,只好重灌成lubuntu 14.04 QQ，所以暫時應該是不會升上去（至少在完成作業前不會）
很久很久以前有看過一篇不錯的東西，分享上來給各位看看
[Deep C](http://www.slideshare.net/olvemaudal/deep-c)
分享上來的令一個理由是,我一年前看過現在又幾乎忘光了QAQ

## 準備工作
### perf
(參考網址：http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial)
指令如下

$ sudo apt-get install linux-tools-common

perf top 一次

WARNING: perf not found for kernel 4.4.0-18
You may need to install the following packages for this specific kernel:
    linux-tools-4.4.0-18-generic
    linux-cloud-tools-4.4.0-18-generic

:::warning
每個人的kernel版本需求有可能不同，請依照跳出的提醒作安裝
:::
照他講的裝

$ sudo apt-get install linux-tools-4.4.0-18-generic linux-cloud-tools-4.4.0-18-generic

### gcin
新酷音的很難用...，打這篇的時候一直被搞，所以推個 gcin。(感謝李奇霖大大告訴我)
不是功課重點不贅述,直接附上網址
http://blog.xuite.net/yh96301/blog/287374341-Ubuntu+14.04%E5%AE%89%E8%A3%9D%E9%8D%B5%E7%9B%A4%E8%BC%B8%E5%85%A5%E6%B3%95%E7%B3%BB%E7%B5%B1gcin

### gnuplot
用來畫圖表時的實用工具，可以撰寫script來作為畫圖時的腳本。

安裝

$ sudo apt-get install gnuplot

## Origin

$ make run
size of entry : 136 bytes
execution time of append() : 0.039465 sec
execution time of findName() : 0.009147 sec

perf stat -r 10 -e cache-misses,cache-references,L1-dcache-load-misses,L1-dcache-store-misses,L1-dcache-prefetch-misses,L1-icache-load-misses ./phonebook_orig

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

           992,786      cache-misses              #   80.752 % of all cache refs      ( +-  0.94% )
         1,229,426      cache-references                                              ( +-  0.38% )
         2,527,059      L1-dcache-load-misses                                         ( +-  0.20% )
   <not supported>      L1-dcache-store-misses   
   <not supported>      L1-dcache-prefetch-misses
            45,292      L1-icache-load-misses                                         ( +-  4.30% )

       0.067631317 seconds time elapsed                                          ( +-  0.79% )

## Struct變動( 縮小 entry )
因為搜尋 lastname 時不會用到細節部份，所以將細節部份拉出來，entry 裡只保留 pointer

typedef struct __PHONE_BOOK_ENTRY {
	char lastName[MAX_LAST_NAME_SIZE];
	phonebook_detail* detail;
	struct __PHONE_BOOK_ENTRY *pNext;

entry大小變動為136bytes->32bytes
大幅度的減少cache misses
(因為entry size變小了,cache所對應到的資料比數也增多,自然 cahce-misses 會大幅下降)

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

           162,512      cache-misses #   38.290 % of all cache refs ( +-  0.70% )
           424,425      cache-references ( +-  0.74% )
       245,576,974      instructions #    1.84  insns per cycle ( +-  0.02% )
       133,707,669      cycles ( +-  0.26% )

       0.037950422 seconds time elapsed ( +-  3.54% )

從原本的80.752％->38.290％
下圖為圖表的比對

## Hash function
實作的時候猶豫了很久要開多大的hash table，所以也就查了一些資料（詳細請見reference）
在這邊採用的是 channing 的方式，將 lastname 經過 hash 轉換後得到一個 value，在拿那個value 去除以一個定數取餘數，然後根據餘數來看是要放在哪個index底下, struct長這樣

typedef struct __CABINET {
    entry* value;
    struct __CABINET* next;
} cabinet;

實驗結果如下

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

           347,467      cache-misses              #   51.772 % of all cache refs      ( +-  0.98% )
           671,148      cache-references                                              ( +-  0.97% )
       436,845,193      instructions              #    1.74  insns per cycle          ( +-  0.01% )
       251,102,337      cycles                                                        ( +-  0.14% )

       0.067775080 seconds time elapsed                                          ( +-  0.16% )

可以看到hash function的作法，雖然在append的時間因為要建表而拉長不少,但在find的部份有極大的改善。雖然cache misses高了單純改動entry的方法20％,但因為時間複雜度從O(N) -> O(N/k)
(k取決於我們開多大的cabinet,這邊是1024),而有很大的改善。


## Reference
* [課程網站](http://wiki.csie.ncku.edu.tw/sysprog/schedule)
* [作業網站](https://hackmd.io/s/S1RVdgza)
* HackMD Tutorial---左上有個小小的問號，點下去就對了。
* [Gnuplot tutorial from duke university](http://people.duke.edu/~hpgavin/gnuplot.html)
* [Programming Small](https://hackmd.io/s/S1rbwmZ6)
* [CS50 Hash Table Youtube](https://www.youtube.com/watch?v=h2d9b_nEzoA)
* [Google到不錯的PDF - Hashing](https://www.csie.ntu.edu.tw/~hsinmu/courses/_media/dsa_12spring/hashing.pdf) by Michel Tsai
* [DeepC](http://www.slideshare.net/olvemaudal/deep-c)

###### tags: `Fzzzz` `sysprog`