分享到plurk 分享到twitter 分享到facebook

版本 054960e05bbb97f101acce23634f3efc2132a44e

2016q1 Homework #1

預期目標

  • 準備 GNU/Linux 開發工具
  • 學習使用 Git 與 GitHub
  • 學習效能分析工具
  • 研究軟體最佳化

標注須知

下方只要是 $ 開頭,就表示在 GNU/Linux 的終端機裡面輸入的指令,比方說 $ sudo apt-get update,就表示要輸入 sudo apt-get update

預先準備動作

  • 安裝 GNU/Linux,建議安裝 Lubuntu 15.10 (64-bit)
    • 注意: 不要透過虛擬機器,而是用多重開機直接裝在硬碟中,記得先切割好硬碟
  • 安裝相關開發工具
$ 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

Linux 效能分析工具: Perf

  • Perf 全名是 Performance Event,是在 Linux 2.6.31 以後內建的系統效能分析工具,它隨著核心一併釋出。藉由 perf,應用程式可以利用 PMU (Performance Monitoring Unit), tracepoint 和核心內部的特殊計數器 (counter) 來進行統計,另外還能同時分析運行中的核心程式碼,從而更全面了解應用程式中的效能瓶頸
  • 詳細閱讀 Linux 效能分析工具: Perf 並在自己的 Linux 開發環境實驗

作業要求

  • 詳細閱讀 Week #3 課程的 案例分析: Phone Book,研究降低 cache miss 的方法
  • 在 GitHub 上 fork phonebook,然後適度修改 phonebook_opt.cphonebook_opt.h 兩個檔案,使得這兩者執行時期的 cache miss 降低。請用 perf 驗證,而且改進的過程中,不能有功能方面的減損。
    • phonebook_orig.[ch] 不需要修改,我們關注的是 phonebook_opt.[ch],當然要修改 main.c 也是允許的
    • findName() 的時間必須比 Week #3 課程 列出的數據,來得更快
    • append() 的時間可以比原始版本稍久,但不應該增加太多
    • main.c 應該只有一份,不要建立新的 main(),善用 Makefile 定義對應的 CFLAGS
    • 在執行程式(phonebook_origphonebook_opt) 前,先清空 cache:
    $ echo 1 | sudo tee /proc/sys/vm/drop_caches
  • 除了修改程式,也要編輯 Hackpad 下方「作業區」,增添開發紀錄和 GitHub 連結
    • 至少要列出效能分析,以及充份說明你如何改善效能。請使用 gnuplot 建立圖表
  • 務必使用 astyle 排版,詳細使用方式見 README.md
  • 可能的效能改進方向:
    • 改寫 struct __PHONE_BOOK_ENTRY 的成員,搬動到新的結構中
    • 使用 hash function 來加速查詢
    • 既然 first name, last name, address 都是合法的英文 (可假設成立),使用字串壓縮的演算法,降低資料表示的成本
    • 使用 binary search tree 改寫演算法
  • 截止日期:
    • Oct 12, 2015 (含) 之前
    • 越早在 GitHub 上有動態、越早接受 code review,評分越高

挑戰題

  • 除了降低 findName() 的 cache miss 與執行成本,append() 也該想辦法縮減時間
    • 建立 phone book 時,既然 lastName 是索引值,可以優先建立搜尋表格,其他資料可稍後再補上
    • 用 PThread 建立 manager/worker thread model
  • 支援 fuzzy search,允許搜尋 lastName 時,不用精準打出正確的寫法
    • 比方說電話簿有一筆資料是 McDonald,但若使用者輸入 MacDonaldMcDonalds,也一併檢索出來
  • 改善電話簿的效能分析,透過大量的重複執行,找出 95% 信賴區間,而且允許動態新增資料 (較符合現實) 和查詢
  • gnuplot 繪製效能分析圖表,藉此得知 Fibonacci 數列對於效能的影響

參考資料