# 2016q3 Homework1 (phonebook) contributed by <`Jing Zhou`> ## Reviewed by `ChenYi` 1. github上的code有問題 * phonebook_opt.c 裡的apend funciton中的tmp沒有被宣告 2. commit訊息只有add file via upload，可以考慮寫詳細點 ## 開發環境 ubuntu 16.04 ![](https://i.imgur.com/CXutnYD.png) ![](https://i.imgur.com/vajf5ZC.png) 將磁碟分割出80G空間後，使用live usb安裝 開機選單只出現單系統，解決方法： [Windows與Ubuntu雙系統，開機時偵測不到彼此的解決方法](http://ericsilverblade.blogspot.tw/2015/05/windowsubuntu.html) ## 準備過程 ### 安裝相關開發工具 ```shell $ 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 $ sudo apt-get install linux-tools-4.4.0-31-generic ``` ### 測試Perf ```shell # 測試成功 $ sudo perf list $ sudo perf top # 測試失敗(解決) # 必須在 ./example 執行結束前輸入以下指令才可偵測 $ sudo perf top -p $pid ``` ![](https://i.imgur.com/tSLDX8k.png) ## Github及Git操作 * Github加入本機ssh ```shell # 本機產生ssh $ ssh-keygen -t rsa -C "[email]" $ ssh-agent -s $ ssh-add ~/.ssh/id_rsa # 複製id_rsa.pub內容到Github加入ssh $ cd ~/.ssh $ cat id_rsa.pub # 檢查 $ ssh -T git@github.com ``` 顯示底下表示成功 > Hi [username]! You've successfully authenticated, > but GitHub does not provide shell access. * Git遠端同步操作 ```shell # 安裝 $ sudo apt-get install git # 從Github fork專案 # 下載到本機 $ git clone https://github.com/judy66jo/phonebook # 進入 ./phonebook 底下有已有 .git/ # 跳過 $ git init # 設定參數 $ git config --global user.email "you@example.com" $ git config --global user.name "Your Name" $ git config --global push.default matching # 上傳前先清乾淨不必要的檔案 $ make clean # 修改檔案後 $ git add . $ git commit -m "..." $ git push ``` * 參考資料 [Linux 效能分析工具: Perf](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial) [GitHub - 參與一個專案](https://git-scm.com/book/zh-tw/v2/GitHub-%E5%8F%83%E8%88%87%E4%B8%80%E5%80%8B%E5%B0%88%E6%A1%88) [GitHub Trianing](https://services.github.com/kit/downloads/cn/github-git-cheat-sheet.html) [C 語言中的編譯時期函數](http://ccckmit.wikidot.com/cp:macrofunc) ## phonebook優化 ### 未優化版本 * 執行時間 ```shell $ ./phonebook_orig size of entry : 136 bytes execution time of append() : 0.035779 sec execution time of findName() : 0.004830 sec ``` cache-misses 90.670% ```shell $make cache-test ... Performance counter stats for './phonebook_orig' (100 runs): 446,2693 cache-misses # 90.670 % of all cache refs ( +- 0.18% ) 492,1906 cache-references ( +- 0.12% ) 2,6067,0515 instructions # 1.42 insns per cycle ( +- 0.02% ) 1,8331,1704 cycles ( +- 0.15% ) 0.050803658 seconds time elapsed ( +- 1.20% ) ``` * 執行前清空caches $ echo 1 | sudo tee /proc/sys/vm/drop_caches * 用perf找熱點，findName佔了26.83% $ ./phonebook_orig & sudo perf top -p $! ![](https://i.imgur.com/9UKzJjD.png) ### 縮減欄位 將沒有用到的資料欄位建立新的struct，entry中只保留lastname，其它和維持orig版一樣，結果顯示cache-misses下降 * phonebook_opt.h ```shell typedef struct __PHONE_BOOK_DETAIL { 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]; } detail; typedef struct __PHONE_BOOK_ENTRY { char lastName[MAX_LAST_NAME_SIZE]; detail *pDetail; struct __PHONE_BOOK_ENTRY *pNext; } entry; ``` * 執行時間 ```shell $ ./phonebook_opt size of entry : 32 bytes execution time of append() : 0.029268 sec execution time of findName() : 0.001594 sec ``` * cache-misses 65.434 % ```shell $make cache-test ... Performance counter stats for './phonebook_opt' (100 runs): 143,7633 cache-misses # 65.434 % of all cache refs ( +- 0.63% ) 219,7071 cache-references ( +- 0.17% ) 2,4388,5560 instructions # 2.03 insns per cycle ( +- 0.02% ) 1,2025,0834 cycles ( +- 0.16% ) 0.032420169 seconds time elapsed ( +- 0.16% ) ``` * 用perf找熱點，findName佔了5.02%，大幅下降 $ ./phonebook_opt & sudo perf top -p $! ![](https://i.imgur.com/Jsfq4lz.png) * 比較圖 $ make plot ![](https://i.imgur.com/mXnhmTn.png) ### 加上hash 使用效率較優的BKDRHash function https://www.byvoid.com/zht/blog/string-hash-compare 切分SIZE設3571(取質數) 結果如下 ![](https://i.imgur.com/Sq5zVj4.png) SIZE=5107 ![](https://i.imgur.com/atEdx0V.png) SIZE=257 ![](https://i.imgur.com/1Yy0Zqx.png) SIZE過大或過小可能都會增加append()的時間，甚至有時造成程式記憶體區段錯誤 findName()時間則無明顯變化