phonebook
===
contributed by <`snoopy831002`>
## 開發環境
軟體：unbuntu 16

硬體：Macbook pro 2013(late)


*本專案搭配astyle+Git使"過去的我"、"現在的我"以及"未來的我"延續一致的coding style

## code review
### `#include IMPL`

在main.c裡面會使用到 gcc -DIMPL="" 的 macro。
這個marco可以使編譯時加入參數進去，以本案例來說gcc -DIMPL="phonebook_hash" 就是在編譯期間在main.c檔內加入一個IMPL的marco，其值為phonebook_hash

這個可以讓我們輕易的在同一個main.c執行多個版本的phonebook

:::danger
從shell傳入marco時必須以字串傳入，雙引號還必須要跳脫。
例如：
`gcc -DIMPL"\"phonebook_orig.h\""`
或是寫成下面這個版本(不用跳脫)：
`gcc -DIMPL'\"phonebook_orig.h\"'`
:::

## 開始分析
### 原始版本(未優化)
`./phonebook_orig`

執行時間：


cache-miss 高達89%:

* 作業中提到的目標是要讓執行時期的cache miss降低，但原本的結構體在佔用的空間達到136 Bytes，但電腦本身的L1 cache只有32KB = 32*1024 byte，計算出來可放的資料量約32*1024 / 136 = 240.941筆，但是讀取的檔案本身卻是有349900筆的資料量，也難怪cache miss的比例如此高了。

利用perf找熱點：
`./phonebook_orig & sudo perf top -p $!`

* 由此圖可以發現明明findName執行時(0.005552 sec)< append執行時間(0.056274)但是findName所佔效能(16.94%)卻是append(1.04%)的15倍左右
代表說findname內很可能有很多不必要的運算

### opt版本

在phonebook_opt.h中我縮小了struct的大小，因為在搜尋時只用lastname做搜尋，故保留之

typedef struct __LAST_NAME_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    struct entry_detail *detail
    struct __PHONE_BOOK_ENTRY *pNext;
} entry;

`./phonebook_orig`

執行時間：


執行時間比之前縮短約2秒

cache-miss 降為31%:


利用perf找熱點：


經由perf發現findName已經大幅減少佔據系統效能了

gnuplot:


### Hash版本(使用djb2)

`./phonebook_hash`


我們可以發現花在append()的時間比之前還要多 但是findName()所花的時間接進0秒！

cache-miss


cache-miss 比之前更少

perf找熱點


我們可以發現系統把大多數的時間拿去進行hash了，所以append()[下圖]才會比之前再多花一點時間


## 參考資料
* [Hash Table](https://www.youtube.com/watch?v=tjtFkT97Xmc)
* [詹欣達的共筆](https://embedded2016.hackpad.com/ep/pad/static/SS3c9W4KM1S)
* [吳勃興的共筆](https://embedded2016.hackpad.com/2016q1-Homework-1-DdP67a0ke8Q)
* [Zentorno 的共筆](https://embedded2016.hackpad.com/ep/pad/static/SS3c9W4KM1S)