# 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>
![](https://i.imgur.com/NTqvGKL.png)
## 第二次優化
* 第二次的優化,我打算對儲存的結構下手,因為用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>
![](https://i.imgur.com/pqa180k.png)
---
## 參考資料
[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)