HackMD
2016q3 Homework1 (phonebook)
contributed by <linachiu>
Reviewed by <snoopy831002>
- 建議可以加上perf觀察orig版本與opt版本的效能差異
- commit e05558 message “I hate gugu”超怪xd 這樣應該會忘記這個本的更新原因吧!
預期目標
- 準備 GNU/Linux 開發工具
- 在筆電上灌了 Ubuntu 16.04 LTS
- 學習使用 Git 與 GitHub
- 綁訂機器的 SSH key
- 安裝相關開發工具 (還不知道作業怎麼寫之前就先消極的sudo apt-get install 相關工具八)
- 基本編譯器
- 效能分析工具 (perf)
- astyle
- colordiff
- gnuplot
$ 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
- 研究軟體最佳化
研究軟體最佳化 (案例分析：Phone Book)
優化前
執行程式前先清空cache
$ echo 1 | sudo tee /proc/sys/vm/drop_caches
1
執行結果
$ ./phonebook_orig
size of entry : 136 bytes
execution time of append() : 0.096668 sec
execution time of findName() : 0.005940 sec
看看 cache-misses
$ make cache-test
發現 cache-misses 超高
size of entry : 136 bytes
execution time of append() : 0.054454 sec
execution time of findName() : 0.006213 sec
Performance counter stats for './phonebook_orig' (100 runs):
201,0310 cache-misses # 93.881 % of all cache refs ( +- 0.51% )
214,1343 cache-references ( +- 0.44% )
2,6080,7284 instructions # 1.32 insns per cycle ( +- 0.02% )
1,9743,3320 cycles ( +- 0.79% )
0.079924222 seconds time elapsed ( +- 1.12% )
優化方法
- 更改 struct 結構
typedef struct __LAST_NAME_ENTRY{
char lastName[MAX_LAST_NAME_SIZE];
detail *detail;
struct __LAST_NAME_ENTRY *pNext;
} entry;
優化後
來看看結果
$ ./phonebook_opt
size of entry : 32 bytes
execution time of append() : 0.035469 sec
execution time of findName() : 0.002437 sec
cache-misses 從原本的93.8% 變成 67.7%
$ make cache-test
Performance counter stats for './phonebook_opt' (100 runs):
39,5587 cache-misses # 67.738 % of all cache refs ( +- 0.22% )
58,3992 cache-references ( +- 0.87% )
2,4400,9857 instructions # 1.65 insns per cycle ( +- 0.02% )
1,4827,5161 cycles ( +- 1.02% )
0.050210939 seconds time elapsed ( +- 1.06% )
透過 gnuplot 建立執行時間比較圖表
$ make plot
結果分析
- 查看電腦 cache 大小
$ lscpu | grep cache
