版本 2866d29b6d80aa69c2c83c1fd4afb644c4d5f8d1
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- 關於 GNU/Linux 指令，請參閱 鳥哥的 Linux 私房菜
- 本系列課程全程使用 GNU/Linux，全世界有十幾億台裝置內建 Linux 系統，學習 Linux 是相當划算的投資！
- 熟悉 Git 和 GitHub 操作
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.c和phonebook_opt.h兩個檔案，使得這兩者執行時期的 cache miss 降低。請用 perf 驗證，而且改進的過程中，不能有功能方面的減損。phonebook_orig.[ch]不需要修改，我們關注的是phonebook_opt.[ch]，當然要修改main.c也是允許的findName()的時間必須比 Week #3 課程 列出的數據，來得更快append()的時間可以比原始版本稍久，但不應該增加太多main.c應該只有一份，不要建立新的main()，善用 Makefile 定義對應的CFLAGS- 在執行程式(
phonebook_orig和phonebook_opt) 前，先清空 cache:
- 除了修改程式，也要編輯 Hackpad 下方「作業區」，增添開發紀錄和 GitHub 連結
- 至少要列出效能分析，以及充份說明你如何改善效能。請使用 gnuplot 建立圖表
- 務必使用 astyle 排版，詳細使用方式見 README.md
- 可能的效能改進方向：
- 改寫
struct __PHONE_BOOK_ENTRY的成員，搬動到新的結構中 - 使用 hash function 來加速查詢
- 既然 first name, last name, address 都是合法的英文 (可假設成立)，使用字串壓縮的演算法，降低資料表示的成本
- 使用 binary search tree 改寫演算法
- 改寫
- 截止日期：
- Mar 6, 2016 (含) 之前
- 越早在 GitHub 上有動態、越早接受 code review，評分越高
挑戰題
- 除了降低
findName()的 cache miss 與執行成本，append()也該想辦法縮減時間- 建立 phone book 時，既然 lastName 是索引值，可以優先建立搜尋表格，其他資料可稍後再補上
- 用 PThread 建立 manager/worker thread model
- 支援 fuzzy search，允許搜尋 lastName 時，不用精準打出正確的寫法
- 比方說電話簿有一筆資料是
McDonald，但若使用者輸入MacDonald或McDonalds，也一併檢索出來
- 比方說電話簿有一筆資料是
- 改善電話簿的效能分析，透過大量的重複執行，找出 95% 信賴區間，而且允許動態新增資料 (較符合現實) 和查詢
- 以 gnuplot 繪製效能分析圖表
