# 2016q3 Homework1 (phonebook)
contributed by <`linachiu`>

### Reviewed by <`snoopy831002`>
* 建議可以加上perf觀察orig版本與opt版本的效能差異
* commit [e05558](https://github.com/linachiu/phonebook/commit/e055586b8437570728ff0736148ba174adc2214c) message “I hate gugu”超怪xd 這樣應該會忘記這個本的更新原因吧!
***
## 預期目標

* 準備 GNU/Linux 開發工具
- 在筆電上灌了 Ubuntu 16.04 LTS
* 學習使用 Git 與 GitHub
- 綁訂機器的 SSH key
* 安裝相關開發工具 (還不知道作業怎麼寫之前就先消極的sudo apt-get install 相關工具八)
- 基本編譯器
- 效能分析工具 (perf)
- astyle
- colordiff
- gnuplot

$ sudo apt-get update
$ sudo apt-get install build-essential
$ sudo apt-get install linux-tools-common linux-tools-generic
$ sudo apt-get install astyle colordiff gnuplot

* 研究軟體最佳化
----
# 研究軟體最佳化 (案例分析：Phone Book)
____

## 優化前

執行程式前先清空cache

$ echo 1 | sudo tee /proc/sys/vm/drop_caches
1

執行結果

$ ./phonebook_orig
size of entry : 136 bytes
execution time of append() : 0.096668 sec
execution time of findName() : 0.005940 sec

看看 cache-misses

$ make cache-test

發現 cache-misses 超高

size of entry : 136 bytes
execution time of append() : 0.054454 sec
execution time of findName() : 0.006213 sec

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

          201,0310      cache-misses              #   93.881 % of all cache refs      ( +-  0.51% )
          214,1343      cache-references                                              ( +-  0.44% )
       2,6080,7284      instructions              #    1.32  insns per cycle          ( +-  0.02% )
       1,9743,3320      cycles                                                        ( +-  0.79% )

       0.079924222 seconds time elapsed                                          ( +-  1.12% )

____
## 優化方法

- 更改 struct 結構

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

## 優化後

來看看結果

$ ./phonebook_opt

size of entry : 32 bytes
execution time of append() : 0.035469 sec
execution time of findName() : 0.002437 sec

cache-misses 從原本的93.8% 變成 67.7%

$ make cache-test

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

           39,5587      cache-misses              #   67.738 % of all cache refs      ( +-  0.22% )
           58,3992      cache-references                                              ( +-  0.87% )
       2,4400,9857      instructions              #    1.65  insns per cycle          ( +-  0.02% )
       1,4827,5161      cycles                                                        ( +-  1.02% )

       0.050210939 seconds time elapsed                                          ( +-  1.06% )

透過 gnuplot 建立執行時間比較圖表

$ make plot

____
## 結果分析
- 查看電腦 cache 大小

![](https://i.imgur.com/kLdVLhp.jpg)

____
## 參考資料
* [Linux 效能分析工具: Perf](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial)
* [hackmd語法介紹](https://hackmd.io/s/E1UakUq8)
* [GitHub介紹](http://wiki.csie.ncku.edu.tw/github)
* [DADA筆記](https://embedded2016.hackpad.com/ep/pad/static/YkqjhwgnQcA)
* [勃興筆記](/s/Bkx3cYX6)
* [澤哥筆記](/s/HJFN1B8T)