# 2017q1 Homework1 (phonebook)
contributed by<`jack81306`>
>中英文字間請記得以空白隔開
>進度落後，請繼續努力
>[name=課程助教][color=red]
###### tags:`jack81306`
### Reviewed by `laochanlam`
- 可嘗試使用 Memory pool 等方法減少 append() 的時間
- 在 GitHub 中可善用 **.gitignore** 檔案，避免把一些非必要及敏感的檔案上傳（如 hash.txt ）
- 中英文字之間還是可以隔開一下
- Hash Table 的確會影響到 append() 及 findName() 的時間，詳細分析可以參考[ierosodin的共筆](https://hackmd.io/s/SJ4uqs9Yx)
- 可以善用 Commit 中的 Description 補充 Why 及 How
## 開發環境

Architecture:          x86_64
CPU 作業模式：    32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
每核心執行緒數：2
每通訊端核心數：2
Socket(s):             1
NUMA 節點：         1
供應商識別號：  GenuineIntel
CPU 家族：          6
型號：              60
Model name:            Intel(R) Core(TM) i5-4210M CPU @ 2.60GHz
製程：              3
CPU MHz：             2463.049
CPU max MHz:           3200.0000
CPU min MHz:           800.0000
BogoMIPS:              5187.96
虛擬：              VT-x
L1d 快取：          32K
L1i 快取：          32K
L2 快取：           256K
L3 快取：           3072K
NUMA node0 CPU(s):     0-3

## 事前準備
* 灌 ubuntu 以及製作雙系統

當使用助教的方法無法成功安裝雙系統時,可以參考以下方式

1.製作開機碟

使用[Rufus](https://rufus.akeo.ie/?locale=zh_TW)軟體製作開機碟,**切記要使用UEFI格式**.

2.依照這篇[文章](https://blog.birkhoff.me/windows-10-and-ubuntu-14_04_3-lts-dual-boot/)的教學,並在最後依照最下方的留言在windos命令行進行操作.

* 學習Linux基礎知識
* [鳥哥的Linux私房菜](http://linux.vbird.org/linux_basic/)
* [安裝Vim插件](https://blog.gtwang.org/linux/vundle-vim-bundle-plugin-manager/)
* [git基本教學](http://www.liaoxuefeng.com/wiki/0013739516305929606dd18361248578c67b8067c8c017b000)
***

* 當安裝ubuntu時,發生無法挽回的問題時,可以參考以下方法移除ubuntu(親身經歷)

1.先進入windows修復模式,或者是用usb開機進入修復式,接著進入修復模式中的命令列指令.
2.輸入bootrec /fixmbr 並按Enter執行
3.輸入bootrec /fixboot 並按Enter執行
4.輸入bootrec /rebuildbcd 並按Enter執行
5.接著將裝有ubuntu的切割槽刪除並重新格式化

## 首次測試
* <big>未優化之運行時間</big>

    size of entry : 136 bytes
    execution time of append() : 0.040742 sec
    execution time of findName() : 0.005497 sec

* <big>未優化之運行狀況</big>

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

         1,168,316      cache-misses              #   84.397 % of all cache refs      ( +-  0.54% )
         1,384,317      cache-references                                              ( +-  0.26% )
       262,276,816      instructions              #    1.37  insn per cycle           ( +-  0.02% )
       191,687,162      cycles                                                        ( +-  0.27% )

       0.062230653 seconds time elapsed                                          ( +-  0.38% )

## 第一次優化

* <big>第一次優化後運行時間</big>

size of entry : 48 bytes
execution time of append() : 0.043589 sec
execution time of findName() : 0.002535 sec

* <big>第一次優化後運行狀況</big>

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

           185,465      cache-misses              #   42.045 % of all cache refs      ( +-  6.02% )
           441,114      cache-references                                              ( +- 11.64% )
       247,918,235      instructions              #    1.56  insn per cycle           ( +-  0.08% )
       158,515,495      cycles                                                        ( +-  2.72% )

       0.052320066 seconds time elapsed                                          ( +-  3.57% )

* 在phonebook這隻程式裡,我們可以發現findname和append這兩個funtion都只有用到lastname這個參數,因此我把除了lastname的其他資料做成一個struct,然後在entry裡添加一個指向其他資料的指標,以減少entry的size.

* 在減少size後,可以一次讀進cache的entry數量變多,所以可以減少cache misses的次數,增加hit的機率.
* <big>圖表分析</big>
## 第二次優化

* 第二次的優化,我打算對儲存的結構下手,因為用list逐一搜尋速度不夠快,所以我將電話簿儲存在hash table裡面,不過hash table的大小似乎也會影響append和findname的速度！？

* 而在各種雜湊函數裡,又以bkdrhash函數效率最高,因此我選擇bkdr_hash作為電話簿的雜湊函式.[bkdrhash介紹](http://blog.csdn.net/wanglx_/article/details/40400693)

* <big>第二次優化運行時間</big>

size of entry : 48 bytes
execution time of append() : 0.052069 sec
execution time of findName() : 0.000000 sec

* <big>第二次優化運行狀況</big>

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

           158,515      cache-misses              #   36.104 % of all cache refs      ( +-  1.44% )
           439,054      cache-references                                              ( +-  0.83% )
       242,535,965      instructions              #    1.41  insn per cycle           ( +-  0.02% )
       171,778,187      cycles                                                        ( +-  0.52% )

       0.056155463 seconds time elapsed                        

* 可以從運行狀況中得知,cache-missis的比率又稍微變低了,但是並沒有差多少,這裡可以再改進.而差別最大的是findname的運行時間,這根原本的相比相差十分的多.

* <big>圖表分析</big>

---
## 參考資料

[gdb教學](http://www.study-area.org/goldencat/debug.htm)
[cache詳解](https://www.csie.ntu.edu.tw/~r89004/hive/cache/page_1.html)
[hash function比較](https://www.byvoid.com/zhs/blog/string-hash-compare)
[c 的預編譯](http://blog.sina.com.cn/s/blog_4b4b54da0100r2l6.html)