HackMD
2017q1 Homework1 (phonebook)
contributed by<jack81306>
中英文字間請記得以空白隔開
進度落後，請繼續努力
課程助教
tags:jack81306
Reviewed by laochanlam
- 可嘗試使用 Memory pool 等方法減少 append() 的時間
- 在 GitHub 中可善用 .gitignore 檔案，避免把一些非必要及敏感的檔案上傳（如 hash.txt ）
- 中英文字之間還是可以隔開一下
- Hash Table 的確會影響到 append() 及 findName() 的時間，詳細分析可以參考ierosodin的共筆
- 可以善用 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軟體製作開機碟,切記要使用UEFI格式.
2.依照這篇文章的教學,並在最後依照最下方的留言在windos命令行進行操作.
-
學習Linux基礎知識
-
當安裝ubuntu時,發生無法挽回的問題時,可以參考以下方法移除ubuntu(親身經歷)
1.先進入windows修復模式,或者是用usb開機進入修復式,接著進入修復模式中的命令列指令.
2.輸入bootrec /fixmbr 並按Enter執行
3.輸入bootrec /fixboot 並按Enter執行
4.輸入bootrec /rebuildbcd 並按Enter執行
5.接著將裝有ubuntu的切割槽刪除並重新格式化
首次測試
- 未優化之運行時間
size of entry : 136 bytes
execution time of append() : 0.040742 sec
execution time of findName() : 0.005497 sec
- 未優化之運行狀況
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% )
第一次優化
- 第一次優化後運行時間
size of entry : 48 bytes
execution time of append() : 0.043589 sec
execution time of findName() : 0.002535 sec
- 第一次優化後運行狀況
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的機率.
-
圖表分析
第二次優化
-
第二次的優化,我打算對儲存的結構下手,因為用list逐一搜尋速度不夠快,所以我將電話簿儲存在hash table裡面,不過hash table的大小似乎也會影響append和findname的速度！？
-
而在各種雜湊函數裡,又以bkdrhash函數效率最高,因此我選擇bkdr_hash作為電話簿的雜湊函式.bkdrhash介紹
* <big>第二次優化運行時間</big>
size of entry : 48 bytes
execution time of append() : 0.052069 sec
execution time of findName() : 0.000000 sec
- 第二次優化運行狀況
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的運行時間,這根原本的相比相差十分的多.
-
圖表分析
