# 2017 q1 homework(phonebook)
contributed by <`asssde2002`>

### Reviewed by `henry0929016816`
* 可以用 ==lscpu== 這個指令取得電腦相關的資訊，例如 L1 cache 的大小
* git commit 只寫了一個 add another struct 看不出來目的是為什麼，可以再底下加入相關的資訊，例如 修改 data struct 是為了減少 cache miss

[github](https://github.com/asssde2002/phonebook)
>>請加快進度!! 進度停在六天前!
>>[color=red][name=課程助教]
## 開發環境
>請列出硬體相關資訊，如：cache, memory
>[color=red][name=課程助教]
## Original

* 執行 :

`$ ./phonebook_orig`

* 得到的結果：

size of entry : 136 bytes
execution time of append() : 0.045063 sec
execution time of findName() : 0.005203 sec

* Cache-test :

`$ sudo perf stat --repeat 100 -e cache-misses,cache-references,instructions,cycles ./phonebook_orig`

           567,234      cache-misses              #   64.188 % of all cache refs      ( +-  1.19% )
           883,711      cache-references                                              ( +-  0.36% )
       262,098,055      instructions              #    1.32  insn per cycle           ( +-  0.03% )
       198,258,590      cycles                                                        ( +-  0.58% )

       0.066059274 seconds time elapsed                                          ( +-  0.60% )
       

發現cache-misses有64.188%

## Optimization

### 1.Struct

從程式碼當中發現在執行 findname() 時只會用到 lastname 而已，但是其他的宣告也要跟著被讀取，因此造成整個效能降低，所以另外建構一個 struct 來宣告，如此就可以讓整體效能提升。

* 執行時間

size of entry : 32 bytes
execution time of append() : 0.040180 sec
execution time of findName() : 0.002094 sec

* Cache-test

127,624 cache-misses # 29.817 % of all cache refs ( +- 0.67% )
428,016 cache-references ( +- 0.67% )
243,002,108 instructions # 1.77 insn per cycle ( +- 0.02% )
137,275,891 cycles ( +- 0.63% )

0.045749571 seconds time elapsed ( +- 0.67% )

得到的結果告訴我們 cache-misses 從原本的 64.188% 降到了 29.817% 下降了將近 35%

* Plot


>進度加快[name=亮谷][color=#d49]
## 2.Binary Search Tree

## 3.Hash Function

## 4.壓縮

## 參考資料