contributed by < Hsiang
>
作業解說 video
yangyang95
作業系統:
設定一般user sudo sh -c 'echo 1 >/proc/sys/kernel/perf_event_paranoid'
./phonebook_orig
由於0.996 CPUs utilized非常接近1屬CPU BOUND型
Cache-misses 的比例92.475
根據Hotspot分析出來 前三個function是造成cache-miss主要的原因:
由函數指出字串比對次數過多導致miss次數變多
由上面的分析數據顯示以下:
L1d Cache size = 32KB,Cache line size = 64Bytes
Cache Line的個數
32 * 1024 / 64 = 512
每筆Entry有136Bytes,因此一次存入L1d的數量就只有
32 * 512 / 136 大約 120筆 Entry
根據大小改善的原始結構後
每筆Entry剩下24Bytes,因此一次存入L1d的數量增加為
32 * 512 / 24 大約 682筆 Entry
時間上的成長
減少不必要的欄位空間,使cache-misses率下降了約20%,搜尋以及儲存資料的時間也有些微下降
整理了 Hash Function
先是建立了一張3571大小的TABLE,再不減少Entry的情況下進行分析
減少大小後
由數據分析換上Hash Function後
Cache-miss的比例降低不少 92.475 -> 56.257
append時間多出0.03 sec
findName時間則下降至0.000001 sec
然而減少Hash大小也減少的些微Cache-miss的比例 56.257 -> 45.586
append時間下降 0.011 sec
Cache-misses 45.586% 依然偏高
學習ierosodin的分析,也著手分析大小對於分佈的影響
根據結果
當把TABLE_SIZE設成9997時,search時間下降到小於 10-6 sec
且append時間只增加了0.002 sec,Cache-misses 也多下降了 2%
也驗證了分佈越均勻確實可以下降Cache-misses的比例
根據顯示 malloc的部分還是造成了許多Cache-misses的情況,也因此在釋放記憶體的時間增加了Caches misses的比例。
著手改善的方向memory pool