HackMD
2017 q1 homework(phonebook)
contributed by <PerterTing>
Reviewed by king1224
- 關於 phonebook_opt_hash.c 中的 findName 實作，過程中呼叫了兩次 HashTableGet 來找查目標資料，第一次作為檢查，第二次重新找一次才 return，也就是說今天我打開電話簿要找一個人的號碼，當我找到後心想：「我找到了。」但立馬我將電話簿闔上，從頭再次翻閱找尋才能得到號碼
- 關於 HashTablePut 我覺得寫得很好，寫了一個 struct __HASH_TABLE 對於 hash array 的管理上清楚很多
- 關於 HashTableGet 對於資料的維護，今天 Hashtable 是以指標傳入，即有可能更動到資料庫，你在實作上就做了這件事：
while(isSame !=0 && table->e[hashCode]->pNext != NULL) {
table->e[hashCode] = table->e[hashCode]->pNext;
isSame = strcmp(lastName, table->e[hashCode]->lastName);
}
- 當你找到不合適的答案時，不斷的將該個 hash entry 的 head 往下推進，可像你在 HashTablePut 中有做到的，在最後將 head 設回該在的位置，或創立一個 tmp 變數往下探索，建議可在不想被更動的參數前加上 const 以確保資料安全
開發環境
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
型號： 61
Model name: Intel(R) Core(TM) i5-5250U CPU @ 1.60GHz
製程： 4
CPU MHz： 1941.699
CPU max MHz: 2700.0000
CPU min MHz: 500.0000
BogoMIPS: 3200.29
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 3072K
linux kernel:
peterting@peterting-MacBookAir:~$ uname -a
Linux peterting-MacBookAir 4.8.0-36-generic
未優化前
- 未優化前運行時間
peterting@peterting-MacBookAir:~/hw1/phonebook$ ./phonebook_orig
size of entry : 136 bytes
execution time of append() : 0.051368 sec
execution time of findName() : 0.005574 sec
- 未優化前運行狀況
Performance counter stats for './phonebook_orig' (5 runs):
3,436,226 cache-misses # 93.565 % of all cache refs ( +- 0.10% )
3,672,567 cache-references ( +- 0.32% )
262,370,280 instructions # 1.46 insn per cycle ( +- 0.10% )
179,856,008 cycles ( +- 0.24% )
0.070947689 seconds time elapsed ( +- 1.14% )
Optimization 1 Structure
第一次優化打算從structure著手，將除了lastName的資料存到另一個 struct 內，使 cache 內存放之資料都是 find 跟 append 所需要之資料，減少 cache miss 5 之情況發生。
- 優化後運行時間
size of entry : 32 bytes
execution time of append() : 0.044477 sec
execution time of findName() : 0.002213 sec
- 優化後運行狀況
Performance counter stats for './phonebook_opt' (5 runs):
1,197,064 cache-misses # 73.246 % of all cache refs ( +- 0.14% )
1,634,305 cache-references ( +- 0.61% )
244,447,128 instructions # 1.94 insn per cycle ( +- 0.06% )
125,893,965 cycles ( +- 1.15% )
0.052415026 seconds time elapsed ( +- 4.84% )
https://i.imgur.com/2h9euq5.png
- 效能對比圖
由此可看出改變 Structure 是可以改善效能的
中英文字間請以空白隔開! 前後都要~
課程助教
Optimation 2 Hash
這次要嘗試使用 hash function 來改善效能，而算法選擇 BKDRHash。
再程式碼完成之後，想試試看若給予 Hash Table 不同大小的話差異會有多大，因此試了兩種 array size，分別為 "20001" 和 "400001"
- "20001" 優化後執行時間
execution time of append() : 0.287863 sec
execution time of findName() : 0.000000 sec
從這裡我們就可以知道 Hash table 可以使 findName() 的時間趨近於零，不過 append() 所花的時間太多，因此試試看增加 Array size
- "20001" 優化後運行狀況
Performance counter stats for './phonebook_opt_hash' (5 runs):
5,679,587 cache-misses # 56.973 % of all cache refs ( +- 0.77% )
9,968,911 cache-references ( +- 0.18% )
351,744,117 instructions # 0.44 insn per cycle ( +- 0.01% )
803,512,165 cycles ( +- 0.59% )
0.313026708 seconds time elapsed ( +- 0.80% )
- "400001" 優化後執行時間
execution time of append() : 0.090783 sec
execution time of findName() : 0.000000 sec
- "400001" 優化後執行狀況
Performance counter stats for './phonebook_opt_hash' (100 runs):
2,272,194 cache-misses # 63.938 % of all cache refs ( +- 0.21% )
3,553,735 cache-references ( +- 0.11% )
309,229,723 instructions # 1.02 insn per cycle ( +- 0.03% )
302,219,971 cycles ( +- 0.19% )
0.120901158 seconds time elapsed ( +- 0.23% )
- 效能對比圖
長條圖檔到數據了課程助教
由此可以知道若增大 Hash table 之大小，可以縮短 append() 之時間，使得效能能夠提升(不過所耗時間仍然比其他方法多)，當然不能給予太多的空間，使用率大概在 0.75 % 為最好，不過在 cache miss 方面倒是沒有改善。
小結：
從這個作業中，學到了 Struct size 減小可以增加 cache 中能放的資料數，使 cache miss 的頻率降低，並且學會如何寫 hash table ，讓資料能夠更快速的被找尋到，還有關於 vim的使用以及設定和很多實用的小工具，像是 perf，因此我覺得收穫良多。不過可能因為背景不是資工，而且之前沒有學過很多東西，因此在這邊會花上很多查找資料和閱讀資料的時間，而同時其他人可能已經完成很多作業了。
我相信再經過一陣子的磨練後一定可以更迅速的上手。
