2016q1 Homework 1 (phonebook)

# 2016q1 Homework 1 (phonebook) contributed by <`HuangWenChen`> ### Reviewed by `shelly4132` - 可以利用字串壓縮法降低資料表現的成本 - 可利用binary search改寫演算法 ## 開發環境 * Description : Ubuntu 16.04.1 LTS * linux kernel version : 4.4.0-38-generic * CPU : AMD A6-4455M APU with Radeon(tm) HD Graphics * Cache : * L1d cache : 16K * L1i cache : 64K * L2 cache : 2048K 可使用`$ lscpu` and `$ cat /etc/os-release` 查看規格 ## 預期目標 * 準備 GNU/Linux 開發工具 * 學習使用 Git 與 GitHub * 學習效能分析工具 * 研究軟體最佳化 ## Cache 相關知識 * 參考閱讀 * [Shared Level-1 instruction-cache performance on AMD family 15h CPUs](http://amd-dev.wpengine.netdna-cdn.com/wordpress/media/2012/10/SharedL1InstructionCacheonAMD15hCPU.pdf) * [How L1 and L2 CPU caches work](http://www.extremetech.com/extreme/188776-how-l1-and-l2-cpu-caches-work-and-why-theyre-an-essential-part-of-modern-chips) * [Basic Performance Measurements](http://amd-dev.wpengine.netdna-cdn.com/wordpress/media/2012/10/Basic_Performance_Measurements.pdf) There are three categories of cache misses: 1. Compulsory misses - occur on first reference to a data item. 2. Capacity misses - occur when the working set exceeds the cache capacity. 3. Conflict misses - occur when a data item is referenced after the cache line containing the item was evicted. ## Git * 參考閱讀 * [Git 情境劇]( http://blog.gogojimmy.net/2012/02/29/git-scenario/) 將常用的指令先大概看過一遍，上機操做看看。 `git init` 開始一個新的 Git repo. `git status` 確認現在所有檔案的狀況 `git clone` 複製一個專案 `git add` 將想要的檔案加入 Stage `git add .` 將所有編修過的檔案加入 Stage `git commit` 將 Stage 狀態的檔案做 Commit 動作 `git pull remote名稱 branch名稱` 下載一個遠端的 branch 並合併 ==pull = fetch + merge== `git push` 將本地端的 branch 上傳到遠端。 ## 效能分析工具 Perf：Phonebook * 參考閱讀 * [Linux 效能分析工具: Perf](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial) * [kptr_restrict for hiding kernel pointers]( https://lwn.net/Articles/420403/) 完成前置準備安裝如果要檢測 cache miss event ，需要先取消 kernel pointer 的禁用。 `$ sudo sh -c " echo 0 > /proc/sys/kernel/kptr_restrict"` 從 [kptr_restrict for hiding kernel pointers]( https://lwn.net/Articles/420403/) 文章裡看到 "If kptr_restrict is set to 0, no deviation from the standard %p behavior occurs." kptr_restrict 設為零可以%p行為發生沒有偏差 ### 未優化版本 `$ make` `$ make run` ``` size of entry : 136 bytes execution time of append() : 0.117969 sec execution time of findName() : 0.009333 sec ``` `$ perf stat -r 100 -e cache-misses,cache-references,instructions,cycles ./phonebook_orig` 當執行要觀看未優化版本的 cache-misses rate 時，發生了奇怪的事情，預期執行後應該會落在 9x％-8x% 之間，但執行之後沒有看到預期的結果，竟然只有 0.530 %，目前尚未了解原因。 `dmidecode` 是可以解析 CPU 型號、主機板型號與記憶體相關的型號等等資訊。 `$ dmidecode -t cache` ``` Handle 0x0029, DMI type 7, 19 bytes Cache Information Socket Designation: L1 CACHE Configuration: Enabled, Not Socketed, Level 1 Operational Mode: Write Back Location: Internal Installed Size: 96 kB Maximum Size: 96 kB Supported SRAM Types: Pipeline Burst Installed SRAM Type: Pipeline Burst Speed: 1 ns Error Correction Type: Multi-bit ECC System Type: Unified Associativity: 2-way Set-associative ``` 發現顯示 L1-cache 是 96kbytes 觀查到 cache-references 非常的大。 ``` size of entry : 136 bytes execution time of append() : 0.103768 sec execution time of findName() : 0.009330 sec Performance counter stats for './phonebook_orig' (100 runs): 368,925 cache-misses # 0.530 % of all cacherefs ( +- 0.80% ) (74.39%) 69,551,729 cache-references ( +- 0.11% ) (51.84%) 262,353,690 instructions # 0.95 insns per cycl ( +- 0.03% ) (76.04%) 276,827,399 cycles ( +- 0.08% ) (74.63%) 0.134035292 seconds time elapsed ( +- 0.10% ) ``` ### 優化版本 * 參考閱讀 [Programming Small](https://hackmd.io/s/S1rbwmZ6) #### 減少entry空間從參考資料中，了解到在搜尋的過程只需要搜尋 lastName，其他資料內容尚未使用到，所以可以設計一個 struct 只儲存 lastName 使原本的 struct 大小從 136 bytes → 32 bytes ，讓 L1 cache 多放更多資料。從約30筆entry到約128筆entry ```c= typedef struct __PHONE_BOOK_DETAIL { 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_DETAIL *pNext; } entry_detail; typedef struct __PHONE_BOOK_ENTRY{ char lastName[MAX_LAST_NAME_SIZE]; entry_datail *datail; struct __PHONE_BOOK_ENTRY *pNext; }entry; ``` 將修改完的程式再編譯一次 `$ make` `$ perf stat -r 100 -e cache-misses,cache-references,instructions,cycles ./phonebook_opt` cache-misses rate 問題依舊尚未了解，從時間上與 cache-misses rate 是有改善。但從 cache-misses rate 看沒有很大的變化。 * cache-misses 下降0.2% ``` size of entry : 32 bytes execution time of append() : 0.078245 sec execution time of findName() : 0.009389 sec Performance counter stats for './phonebook_opt' (100 runs): 211,003 cache-misses # 0.330 % of all cache refs ( +- 0.67% ) (73.75%) 63,978,495 cache-references ( +- 0.22% ) (51.55%) 242,944,615 instructions # 1.10 insns per cycle ( +- 0.08% ) (77.21%) 221,482,539 cycles ( +- 0.12% ) (75.64%) 0.107024164 seconds time elapsed ( +- 0.14% ) ``` ![](https://i.imgur.com/xZUT8Sw.png) `$ ./phonebook_hash_opt & sudo perf top -p $!` 將空間減少後時間都花在比對上面 ![](https://i.imgur.com/eEAopUT.png) #### 使用hash function方式 * 參考資料 * [Programming Small](https://hackmd.io/s/S1rbwmZ6) * [各種字符串Hash函數比較](https://www.byvoid.com/zht/blog/string-hash-compare) * [HASHING](https://www.csie.ntu.edu.tw/~hsinmu/courses/_media/dsa_12spring/hashing.pdf) * [Hash table lengths and prime numbers](http://srinvis.blogspot.tw/2006/07/hash-table-lengths-and-prime-numbers.html) * [phonebook code](https://github.com/charles620016/embedded-summer2015/tree/master/phonebook) hash 的方法是將資料透過某種公式(hash function)轉換成 key值，再去bucket中尋找資料。當沒有overflow的時候，計算hash function的時間: O(1) 而設定 hash table 大小通常會找較大質數，可以讓取出的餘數平均分佈在表中。這裡參考 [Programming Small](https://hackmd.io/s/S1rbwmZ6) 設定 42373 大小。從 [各種字符串Hash函數比較](https://www.byvoid.com/zht/blog/string-hash-compare) 發現 BKDRHash function 效果最好，所以採用此 hash function。在處理 static hashing Overflow Handling 有兩種最受歡迎的方式: 1. Open Addressing 2. Chaining 此方法使用 Chaining ```c= unsigned int BKDRHash(char *str) { unsigned int seed = 131; // 31 131 1313 13131 131313 etc.. unsigned int hash = 0; while (*str) { hash = hash * seed + (*str++); } return (hash & TABLE_SIZE); } ``` 再寫 hash 方式，因為對C不熟再 code 方面研究了很久，看很多 code 慢慢去改寫原本的 code 。經過 BKDRhash function 優化後 : * append() 時間明顯得上升 * findName() 時間明顯下降為0 * cache-misses 下降 1.7 % `$ make` `$ perf stat -r 100 -e cache-misses,cache-references,instructions,cycles ./phonebook_hash_opt` ``` size of entry : 32 bytes execution time of append() : 0.104041 sec execution time of findName() : 0.000000 sec Performance counter stats for './phonebook_hash_opt' (100 runs): 236,819 cache-misses # 0.360 % of all cache refs ( +- 0.36% ) (73.68%) 65,704,977 cache-references ( +- 0.17% ) (51.50%) 235,583,333 instructions # 1.07 insns per cycle ( +- 0.04% ) (77.26%) 220,478,824 cycles ( +- 0.05% ) (75.60%) 0.106951672 seconds time elapsed ( +- 0.21% ) ``` ![](https://i.imgur.com/oIsOxZj.png) `$ ./phonebook_hash_opt & sudo perf top -p $!` 從下圖可以發現時間幾乎花在 BKDRHash function 上面。 ![](https://i.imgur.com/IMwsgKe.png) 使用第二種 hash function 做比較，選用 Programming Small 提到的 djb2 `$ make` `$ perf stat -r 100 -e cache-misses,cache-references,instructions,cycles ./phonebook_hash2_opt` ``` size of entry : 32 bytes execution time of append() : 0.101210 sec execution time of findName() : 0.000000 sec Performance counter stats for './phonebook_hash2_opt' (100 runs): 207,652 cache-misses # 0.326 % of all cache refs ( +- 0.82% ) (73.63%) 63,632,029 cache-references ( +- 0.13% ) (52.49%) 235,883,099 instructions # 1.10 insns per cycle ( +- 0.05% ) (76.70%) 215,110,824 cycles ( +- 0.37% ) (74.88%) 0.104529298 seconds time elapsed ( +- 0.42% ) ``` 經過 djb2hash function 優化後 : * append() 時間明顯得上升 * findName() 時間明顯下降為0 * cache-misses 下降 2.04% 發現 djb2 cache-misses 下降較多。 ![](https://i.imgur.com/WVcGtpg.png)