# 2016q3 Homework1 (phonebook) contributed by <`petermouse`> ### Reviewed by <`jkrvivian`> * 可以嘗試引入不同的hash function 進行效能比較 * 還有其他的方法可以實驗，如：字串壓縮法 * 還未引進符合現實狀況的 data set實驗 * 改良版本v2貼上的每段程式碼，加入說明會比較清楚 * 參考[How to Write a Git Commit Message](http://chris.beams.io/posts/git-commit/)，Title以大寫開頭 * [8dc5a4f](https://github.com/petermouse/phonebook/commit/8dc5a4f76df6be71b1aa8d6e1f4522d829436246)從標題看不出在哪裡做了甚麼修改 ## 開發環境 * OS:Lubuntu 16.04 LTS * Memory: 8 GB * CPU: * Name: * Intel(R) Core(TM) i5-4200H CPU @ 2.80GHz * Cache: * L1d Cache： 32K * L1i Cache： 32K * L2 Cache： 256K * L3 Cache： 3072K * Frequency: * CPU max MHz: 3400 * CPU min MHz: 800 測試時governor皆設定為performance `$ cpupower frequency-set -g performance` (需root權限) Frequency: > 2.8 GHz ## Perf測試 根據[Linux 效能分析工具: Perf](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial) `perf_top_example.c`做測試 ``` Samples: 1K of event 'cycles:pp', Event count (approx.): 951215754 Overhead Shared O Symbol 99.40% test [.] compute_pi_baseline 0.41% [kernel] [k] _nv014159rm 0.06% [kernel] [k] _nv014096rm 0.06% [kernel] [k] pci_conf1_read 0.06% [kernel] [k] __internal_add_timer 0.01% [kernel] [k] entry_SYSCALL_64_fastpath 0.00% [kernel] [k] native_write_msr_safe ``` >「程式輸出的文字訊息」請勿使用圖片表示，請改由文字貼上[name=課程助教] >不好意思，已更正[name=petermouse] 大部分的執行時間都花在了`compute_pi_baseline`上 ## Makefile ing... --- ## Phone Book ### 原始版本 不修改code，執行`make cache-test`看cache miss rate 結果: ``` Performance counter stats for './phonebook_orig' (100 runs): 1,024,374 cache-misses # 85.793 % of all cache refs ( +- 0.26% ) 1,194,011 cache-references ( +- 0.30% ) 260,843,909 instructions # 1.38 insns per cycle ( +- 0.02% ) 188,829,353 cycles ( +- 0.51% ) 0.057309105 seconds time elapsed ( +- 0.92% ) ``` 100次平均時間 ``` append() 0.037041 findName() 0.005024 ``` ### 改良版本v1 在原始版本中，因為struct太大，導致cache中最多能夠存的資料量極少，cache miss機率高，影響到效能，因此最直接的作法是改良struct的大小。 將`phonebook_opt.h`資料結構改變。 ```clike= typedef struct __PHONE_BOOK_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]; }data; typedef struct __PHONE_BOOK_ENTRY { char lastName[MAX_LAST_NAME_SIZE]; struct __PHONE_BOOK_DATA *pData; // a pointer to other data struct __PHONE_BOOK_ENTRY *pNext; } entry; ``` 而`phonebook_opt.c`與`phonebook_orig.c`大致相等。 結果 ``` Performance counter stats for './phonebook_opt' (100 runs): 139,238 cache-misses # 46.657 % of all cache refs ( +- 0.35% ) 298,427 cache-references ( +- 0.45% ) 244,614,107 instructions # 1.93 insns per cycle ( +- 0.02% ) 126,809,543 cycles ( +- 0.40% ) 0.038456267 seconds time elapsed ( +- 0.51% ) ``` 100次平均時間 ``` append() 0.030186 findName() 0.001915 ``` 長條圖 ![](https://i.imgur.com/TKbwS1o.png) Cache miss 大幅降低，但仍有45% 而append()與findName()時間都減少了 我並沒有分配空間給其他資料，所以還不能存取 ### 改良版本v2 因為資料多達35萬筆，且採用linked list結構，萬一資料在linked list尾端，每次重頭搜尋會花太多時間。 解決辦法：引入hash(使用djb2)，pHead也改為陣列。 以下為幾個程式碼片段(main.c) ```clike= #define PRIME_NUM 42737 ``` ```clike= unsigned int Hash(char *str) //djb2 { unsigned long hash = 5381; int c; while ((c = *str++)) hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ return hash%PRIME_NUM; } ``` ```clike= pHead = (entry *) malloc(sizeof(entry)*PRIME_NUM); ``` ```clike= e=pHead+Hash(line); e=append(line, e); ``` 結果： ![runtime_comp3.png](https://i.imgur.com/hnUHyI1.png) 可以發現append會比較花時間，而findName幾乎瞬間完成，原因是append需要經過hash才能append，findName反而透過hash使得總體要找的linked list資料變少，幾乎瞬間完成。 因為測資只有一筆資料(zyxel)，如果有多筆資料的查詢，findName會節省更多時間，將會比前兩組有更好的效能 ### 改良版本v3 待續 ## 參考資料 [課程video](https://www.youtube.com/watch?v=ZICRLKf_bVw) [Linux 效能分析工具: Perf](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial) [使用gnuplot科學作圖](http://www.phy.fju.edu.tw/~ph116j/gnuplot_tutorial.pdf)