# 2016q3 Homework1 (phonebook) contributed by <`shelly4132`> ### Reviewed by `HaoTse` - 目前只實作了減少資料結構與使用 hash function 兩種方式，尚有許多方式可以增進效能，例如使用 字串壓縮演算法、二元搜尋樹等等的方法 - 未對 `append()` 效能增進方法做討論 - 使用的 data set 為無意義的英文字母，未使用符合現實的英文姓氏做實驗 - 只使用了 BKDRhash 做實驗，可以繼續探討其他 hash function，並探討對應各個 data set 適合哪一種 hash function - [commit 6af1b](https://github.com/shelly4132/phonebook/commit/6af1b8913ed48cc728e879bc1451eaec602cda7b) 好像可以不用把 `hash.txt` push 上去，並且 commit 的風格可參考 [How to Write a Git Commit Message](https://hackmd.io/s/BkhIF92p) ## 開發環境 * ### 作業系統：Ubuntu 16.04 LTS * ### Cache： ```$ lscpu | grep cache``` * L1d cache：32K * L1i cache：32K * L2 cache：256K * L3 cache：3072K ## 事前準備 1. 在筆電安裝Ubuntu 2. 照老師的教學先安裝相關開發工具 ``` $ sudo apt-get update $ sudo apt-get install build-essential $ sudo apt-get install linux-tools-common linux-tools-generic $ sudo apt-get install astyle colordiff gnuplot ``` 3. [Linux 效能分析工具: Perf ](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial) 4. [Programming Small](https://hackmd.io/s/S1rbwmZ6) ## 案例分析：Phone Book ### 未優化版本 原本phonebook的entry中存了很多詳細的資料，每個entry的大小為136bytes。 而我的電腦L1 Cache為32KB = 321024，所以321024 / (136*8) = 30.12，代表裡面只能存 30 筆左右。 ``` ./phonebook_orig ``` ``` size of entry : 136 bytes execution time of append() : 0.067210 sec execution time of findName() : 0.005578 sec ``` 從以下結果可以看到未優化前的cache miss高達87.762%。 ``` Performance counter stats for './phonebook_orig' (100 runs): 96,7265 cache-misses # 87.762 % of all cache refs ( +- 0.37% ) 110,2146 cache-references ( +- 0.45% ) 2,6092,3829 instructions # 1.38 insns per cycle ( +- 0.02% ) 1,8918,5981 cycles ( +- 0.72% ) 0.076236355 seconds time elapsed ``` ### 優化版本 #### 第一種優化：縮減struct的大小 其實findName跟append都只用到lastName，所以我們其實可以把那些多餘的訊息都去掉不要，因此我新增了一個比較簡單的struct。 ```clike= typedef struct __PHONE_BOOK_ENTRY { char lastName[MAX_LAST_NAME_SIZE]; char firstName[16]; char email[16]; char phone[10]; char cell[10]; char addr1[16]; char addr2[16]; char city[16]; char state[2]; char zip[5]; struct __PHONE_BOOK_ENTRY *pNext; } detailEntry; typedef struct __LAST_NAME_ENTRY{ char lastName[MAX_LAST_NAME_SIZE]; detailEntry *detail; struct __LAST_NAME_ENTRY *pNext; } entry; ``` ``` ./phonebook_opt ``` ``` size of entry : 32 bytes execution time of append() : 0.044284 sec execution time of findName() : 0.002463 sec ``` 從下面的資訊可以看到，只是單純的把entry的大小減小，就大幅的降低了cache miss，從原本的87.762 %降低到了29.548 %，效果非常驚人。 ``` Performance counter stats for './phonebook_opt' (100 runs): 11,1935 cache-misses # 29.548 % of all cache refs ( +- 0.90% ) 37,8822 cache-references ( +- 1.18% ) 2,4392,7456 instructions # 1.75 insns per cycle ( +- 0.02% ) 1,3909,4113 cycles ( +- 0.97% ) 0.056542530 seconds time elapsed ``` ![](https://i.imgur.com/Ww0S0QX.png) #### 第二種優化：hash function 參考：[BKDRHash](http://www.cnblogs.com/liuliuliu/p/3966851.html)、[vvn](https://hackmd.io/MwUwrAnAZlDGAMBaWAOAhixAWLB2AbImsFoSAEbz4BMWKUwuaAjEA===#) 當我們需要比較的字串數量太龐大的話，我們可以使用hash function來將每個字串轉換成一個數字，而這次我使用的hash function是比較簡單快速的BKDRHash，hash table的大小我設成比較大的質數42737，並且把乘法的部份改成位移運算子，不過我自己測的結果這對於速度的提升似乎沒有太大的幫助。 collision：當兩個不同的字串算出的key一樣時，就發生碰撞。 ```clike= unsigned int BKDRHash(char lastName[]) { //unsigned int seed=31; unsigned int hash=0; int i=0; while(i<strlen(lastName)) { //hash = hash * seed + lastName[i]; hash = (hash << 5) - hash + lastName[i]; ++i; } return hash % DICLEN; } ``` 從結果可以看到因為findName()不用再從頭開始找，所以花的時間大幅的往下降，但append()的時間卻往上升了，原因應該是因為每次append()我們都還要再去呼叫一次hash function。 ``` ./hash_func ``` ``` size of entry : 32 bytes execution time of append() : 0.087076 sec execution time of findName() : 0.000000 sec ``` 而cache miss也下降到了63.635%。 ``` Performance counter stats for './hash_func' (100 runs): 109,3919 cache-misses # 63.635 % of all cache refs ( +- 0.71% ) 171,9051 cache-references ( +- 0.31% ) 3,7554,6986 instructions # 1.40 insns per cycle ( +- 0.14% ) 2,6852,9326 cycles ( +- 0.46% ) 0.110592162 seconds time elapsed ``` ![](https://i.imgur.com/XA4Y0Jq.png)