# 2017q1 Homework1 (phonebook) contributed by <`Hong`> ###### tags: `sysprog2017` `phonebook` `perf` `gnuplot` `king1224` ### Reviewed by `laochanlam` - 可嘗試使用 Memory Pool 等方法加速 append() 的時間。 - 在合併 branch 時可考慮嘗試 fast-forward merge 的方法。 - 看到您在Github中有要修改Commit的需求，[推薦讀物](https://blog.yorkxin.org/2011/07/29/git-rebase)。 ### Reviewed by `harryoooooooooo` - djb2演算法碰撞率非常高，有許多更好的hash function。 - 根據這種hash方式，hash結果只跟字串的最後13個字元有關，不如改成前13個字相關而捨棄後面。 ## 開發環境 ``` OS: 16.04.1 Ubuntu 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-4200H CPU @ 2.80GHz 製程： 3 CPU MHz： 2913.305 CPU max MHz: 3400.0000 CPU min MHz: 800.0000 BogoMIPS: 5587.41 虛擬： VT-x L1d 快取： 32K L1i 快取： 32K L2 快取： 256K L3 快取： 3072K NUMA node0 CPU(s): 0-3 ``` ## 未優化版本 * 執行 `$ ./phonebook_orig` 的效能如下 ``` size of entry : 136 bytes execution time of append() : 0.068915 sec execution time of findName() : 0.005761 sec ``` * 執行 `$ make cache-test` 的結果 * cache-misses 為 85% ``` Performance counter stats for './phonebook_orig' (100 runs): 1,029,464 cache-misses # 85.150 % of all cache refs 1,209,005 cache-references 262,181,324 instructions # 1.39 insn per cycle 188,984,542 cycles 0.057192758 seconds time elapsed ``` ## 優化版本 1 - 減少資料結構大小 在 findName 中只需要用到 lastName，因此將 __PHONE_BOOK_ENTRY 中除了 lastName 以外的成員放到 __DETAL_DATA 裡。 ```clike= typedef struct __DETAL_DATA { 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]; } detal; typedef struct __PHONE_BOOK_ENTRY { char lastName[MAX_LAST_NAME_SIZE]; detal *data; struct __PHONE_BOOK_ENTRY *pNext; } entry; ``` * 執行 `$ ./phonebook_opt` 的效能如下 ``` size of entry : 32 bytes execution time of append() : 0.034895 sec execution time of findName() : 0.002084 sec ``` * 執行 `$ make cache-test` 的結果 * cache-misses 從85%降為 43% ``` Performance counter stats for './phonebook_opt' (100 runs): 133,252 cache-misses # 43.244 % of all cache refs 308,140 cache-references 244,852,848 instructions # 1.86 insn per cycle 131,461,588 cycles 0.040430371 seconds time elapsed ``` 將資料結構縮小之後，level1 的 cache 可以暫存更多筆資料，因此提高了在 level1 就 cache hit 的可能性，同理 L2, L3 cache 也是，不僅降低了 cahce miss，還提高了程式效能。 * Perfomance comparison ![](https://i.imgur.com/Ckp9kIP.png) ## 優化版本 2 - 使用 Hash Function 對於龐大的資料量，在搜尋上難免會多花一些時間，這邊採用 Hash 結構來增加搜尋的效率。而我選擇的是 [djb2](http://www.cse.yorku.ca/~oz/hash.html "title") hash function，因為其使用 shift operation 取代乘法運算，在計算上希望可以得到好一點的效果。 ```clike= unsigned int DJB2HASH(char *str) { long long int hash=0; do { hash = (hash << 5) + (*str++); } while(*str); return hash % TABLE_SIZE; } ``` * 執行 `$ ./phonebook_opt_hash` 的效能如下 ``` size of entry : 32 bytes execution time of append() : 0.041744 sec execution time of findName() : 0.000000 sec ``` * 執行 `$ make cache-test` 的結果 * cache-misses 從85%降為 26% ``` Performance counter stats for './phonebook_opt_hash' (100 runs): 90,855 cache-misses # 26.736 % of all cache refs 339,825 cache-references 238,085,920 instructions # 1.51 insn per cycle 157,819,651 cycles 0.047382079 seconds time elapsed ``` 使用 hash function 之後，findName 的確大幅下降到一瞬間就可以做完了，但因建立 hash table 時需花費許多對於 hash value 的運算，因此 append 的時間是目前為止最長的，把 append 和 findName 加起來看，hash function 還跟未優化版本幾乎一樣，那 hash 是否就是不好的方法？ 打開 main.c 後可以看到，此程式只找一個名字，但若需要執行多次 findName 的話，可以快速搜尋的 hash function 絕對是一個不錯的選擇。 * Perfomance comparison ![](https://i.imgur.com/dCLknAz.png) ## 資料之探討 __本次資料有代表性嗎？跟真實英文姓氏差異大嗎？__ 本次的測試資料存放在 words.txt 中，打開後可以發現本次資料與真實英文姓名差別很大，幾乎可以說是 35 萬筆亂數英文。 真實英文姓氏，字母間會有一些較有規則的排序，至少不會有人姓名是 zzzzzzz，而這筆資料較為平均分佈，雖然不能完全的當作代表，但也會有一定的參考價值。 * word.txt 中其中一小段 ``` zyoba zyrian zyskin zythia zythum zyudin zywiel zyxel zyxels zyzomys zyzop zyzzogeton zzzz zzzzz zzzzzz zzzzzzz zzzzzzzz ``` __資料難道「數大就是美」嗎？__ 不是，越接近真實資料的測試資料越好，若今天要做一本女性電話簿，而測試資料全都是男性姓名，那實際使用時的效率可能會與預期有很大的落差。 __如果我們要建立符合真實電話簿情境的輸入，該怎麼作？__ 在生成測試資料時，對於不同情況給予不同機率，例如名字為 10 個字母以上的產生次數要減少，而名字不可出現 20 個以上的字母、或是不能出現連續 3 母音相連、降低相鄰字母重複出現的次數。 ## 參考資料 [Hw1作業區](https://hackmd.io/MYJjEYGZITgWgOwCMAmw4BYYwAxyQQKxwBmwGOkAHMDeEgGxA===# "title") [Phonebook題目](https://hackmd.io/s/rJYD4UPKe# "title") 與 [video](https://www.youtube.com/watch?v=ZICRLKf_bVw "title") [作業範例](https://hackmd.io/s/BJRMImUPg# "title") [程式碼](https://github.com/king1224/phonebook "title") [Perf](https://hackmd.io/s/B11109rdg# "title") [gnuplot](https://hackmd.io/s/Skwp-alOg# "title") [hash](https://hackmd.io/s/HJln3jU_e# "title")