2017 q1 homework(phonebook)

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 是以指標傳入，即有可能更動到資料庫，你在實作上就做了這件事： ```clike= 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 以確保資料安全 ## 開發環境 ```shell 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 ``` ## 未優化前 * <big>未優化前運行時間</big> `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 ``` * <big>未優化前運行狀況</big> ``` 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 之情況發生。 * <big>優化後運行時間</big> ``` size of entry : 32 bytes execution time of append() : 0.044477 sec execution time of findName() : 0.002213 sec ``` * <big>優化後運行狀況</big> ``` 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 ``` * <big>效能對比圖</big> ![](https://i.imgur.com/2h9euq5.png) 由此可看出改變 Structure 是可以改善效能的 >>中英文字間請以空白隔開! 前後都要~ >>[name=課程助教][color=red] ## 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% ) ``` * <big>效能對比圖</big> ![](https://i.imgur.com/ARTfRoM.png) >>長條圖檔到數據了[name=課程助教][color=red] 由此可以知道若增大 Hash table 之大小，可以縮短 append() 之時間，使得效能能夠提升(不過所耗時間仍然比其他方法多)，當然不能給予太多的空間，使用率大概在 0.75 % 為最好，不過在 cache miss 方面倒是沒有改善。 ## 小結：從這個作業中，學到了 Struct size 減小可以增加 cache 中能放的資料數，使 cache miss 的頻率降低，並且學會如何寫 hash table ，讓資料能夠更快速的被找尋到，還有關於 vim的使用以及設定和很多實用的小工具，像是 perf，因此我覺得收穫良多。不過可能因為背景不是資工，而且之前沒有學過很多東西，因此在這邊會花上很多查找資料和閱讀資料的時間，而同時其他人可能已經完成很多作業了。我相信再經過一陣子的磨練後一定可以更迅速的上手。 ## 參考資料： [哈希表之bkdrhash算法解析及扩展 ](http://blog.csdn.net/wanglx_/article/details/40400693) [hash function 觀念和實務](https://hackmd.io/s/HJln3jU_e) [gnuplot 語法解說和示範](https://hackmd.io/s/Skwp-alOg#)