# 2017q1 Homework1 (phonebook)
contributed by <`ryanpatiency`>
### Reviewed by `changyuanhua`
* 我認為實做方面可以多添加一些方法，不要只用一個做觀察比較
* 記得問題的第二題，以及第三題還沒有回答
## 開發環境
Cache:

Intel® Core™ i5-4210U CPU @ 1.70GHz × 4

L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              3072K

linux kernel：

$ uname -a

Linux  4.4.0-62-generic 

## 目標

作業要求 [B01: phonebook](https://hackmd.io/MwJgHAplBsELQGMAMwCGcAsHjDgIwgBMBOOAdmlSULADMRiBWYiIA===?view)
* 觀察程式 [phonebook](https://github.com/sysprog21/phonebook/)中的 phonebook_orig 的 cache miss 以及 `append()`和`findName()`的執行時間
* 修改 phonebook_opt.c 和 phonebook_opt.h 兩個檔案，降低 cache miss 和`findName()`的執行時間，並使`append()`的執行時間不增加太多
* 以 gnuplot 繪製效能分析圖表
## 如何觀察程式效能
觀察 Makefile ，發現：
* 編譯：可用`make phonebook_orig`來 compile phonebook_orig ，其中的`-DIMPL $@.h`目的是用來指定 Micro IMPL 的值
* 執行：可用`make run`來執行程式，其中`echo 3 | sudo tee /proc/sys/vm/drop_caches`功能可見[這裡](http://unix.stackexchange.com/questions/17936/setting-proc-sys-vm-drop-caches-to-clear-cache)，
* 觀察 cache miss ：可用`make cache-test`，會重覆執行 orig 和 opt 各一百次，將結果寫進 orig.txt 和 opt.txt，記錄四個 event: cache-misses,cache-references,instructions,cycles ，印出結果
* 畫圖：可用 `make plot`畫圖，會執行 cache-test ,並畫圖
## 修改前的程式效能
* `findName()`和`append()`的執行時間:

size of entry : 136 bytes
execution time of append() : 0.068975 sec
execution time of findName() : 0.006140 sec

其中`append()`是用來將 DICT_FILE (這裡是./dictionary/words.txt) 建立成資料結構(這裡是linked list)，而`findName()`是用來在此資料結構尋找含一名字的節點
* cache miss:

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

         1,260,786      cache-misses              #   88.433 % of all cache refs      ( +-  0.43% )
         1,425,695      cache-references                                              ( +-  0.36% )
       261,104,813      instructions              #    1.35  insns per cycle          ( +-  0.02% )
       194,024,625      cycles                                                        ( +-  0.47% )

       0.076814845 seconds time elapsed                                          ( +-  0.62% )

## 實驗過程
### 實作一：減少資料節點的大小
重複[共筆demo](https://hackmd.io/s/BJRMImUPg#)中的優化版本 1 的實驗
* cache miss:

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

           153,395      cache-misses              #   29.770 % of all cache refs      ( +-  0.86% )
           515,261      cache-references                                              ( +-  1.02% )
       244,213,713      instructions              #    1.63  insns per cycle          ( +-  0.02% )
       149,662,137      cycles                                                        ( +-  1.04% )

       0.062095272 seconds time elapsed                                          ( +-  1.40% )

可見 cache miss 從 88% 減為 30%
* plot:
可見`findName()`的執行時間從 0.006255 減為 0.002870 (s)

### 實作二：
## 回答問題

Q1. 有代表性嗎？跟真實英文姓氏差異大嗎？
Ans: words.txt 中的名字前五個分別是：

aaaa
aaaaa
aaaaaa
aaaaaaa
aaaaaaaa

我覺得沒有代表性，與真實名字差異很多。
Q2. 資料難道「數大就是美」嗎？
Ans:
Q3. 如果我們要建立符合真實電話簿情境的輸入，該怎麼作？
Ans:
## 參考資料
[0140454](https://hackmd.io/s/Bkx3cYX6#)
[共筆demo](https://hackmd.io/s/BJRMImUPg#)