--- title: 2016q1 Homework #1 toc: no ... 預期目標 ------------ - 準備 GNU/Linux 開發工具 - 學習使用 Git 與 GitHub - 學習效能分析工具 - 研究軟體最佳化 標注須知 ------- 下方只要是 `$ ` 開頭,就表示在 GNU/Linux 的終端機裡面輸入的指令,比方說 `$ sudo apt-get update`,就表示要輸入 `sudo apt-get update`。 預先準備動作 ------------------- * 安裝 GNU/Linux,建議安裝 [Lubuntu](http://lubuntu.net/) 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 gnuplot ``` * 關於 GNU/Linux 指令,請參閱 [鳥哥的 Linux 私房菜](http://linux.vbird.org/) - 本系列課程全程使用 GNU/Linux,全世界有十幾億台裝置內建 Linux 系統,學習 Linux 是相當划算的投資! * [熟悉 Git 和 GitHub 操作](/github) - [30 天精通 Git 版本控管](https://github.com/doggy8088/Learn-Git-in-30-days) Linux 效能分析工具: Perf ----------------------- * Perf 全名是 Performance Event,是在 Linux 2.6.31 以後內建的系統效能分析工具,它隨著核心一併釋出。藉由 perf,應用程式可以利用 PMU (Performance Monitoring Unit), tracepoint 和核心內部的特殊計數器 (counter) 來進行統計,另外還能同時分析運行中的核心程式碼,從而更全面了解應用程式中的效能瓶頸 * 詳細閱讀 [Linux 效能分析工具: Perf](/embedded/perf-tutorial) 並在自己的 Linux 開發環境實驗 案例探討:電話簿搜尋 ----------------- * 詳細閱讀 [案例分析: Phone Book](https://embedded2016.hackpad.com/ep/pad/static/1vvUk25C0fI),研究降低 cache miss 的方法 * 雖然這是探討 cache miss 和效能議題,其實是帶著同學重新複習 C 語言和資料結構。以前大家只是「背誦心法」,從來就不會去理解個別資料結構對整體的衝擊。 * 抓取和測試程式 - 自 GitHub 取得作業程式碼 (基礎) ``` $ git clone https://github.com/embedded2016/phonebook $ cd phonebook ``` - 編譯 ``` $ make ``` - 測試。當看到 `[sudo] password for ` 字樣時,輸入自己的 Linux 使用帳號密碼 ``` $ make run ``` - 參考輸出: (按下 `Ctrl`-`C` 可以離開畫面) ``` size of entry : 136 bytes execution time of append() : 0.043859 sec execution time of findName() : 0.004776 sec ``` * 透過 gnuplot 建立執行時間的圖表 (保持耐心等待,中間過程不要切換視窗) ``` $ make plot ``` - 正確執行後,目錄裡頭會有個名為 `runtime.png`,可用 `eog runtime.png` 命令來觀看 善用 gnuplot 來製圖 ================== * 忘記 Microsoft Excel,gnuplot 可以給你更專業的圖表,而且能夠批次產生 * 先啟動 gnuplot: ``` $ gnuplot ``` * gnuplot 啟動後,需要做一些必要設定,例如設定圖片名稱,XY軸的資訊等等: ``` > set title 'my plot' @設定圖片名稱 > set xlabel 'x axis' @設定XY軸座標名稱 > set ylabel 'y axis' > set terminal png @設定輸出格式為 .png > set output 'output_plot.png' @設定輸出檔名 > plot [1:10][0:1] sin(x) @畫出 sin(x) 函式,x軸座標範圍1 ~ 10, y軸座標範圍0 ~ 1 ``` * 可以將這些設定另外存成一個檔案,作為 gnuplot 的腳本。假設上述指令存在一個名為 plot 的檔案裡面,以後只要輸入 `gnuplot plot` 即可畫出我們想要的圖表。 作業要求 ------- * 在 GitHub 上 fork [phonebook](https://github.com/embedded2016/phonebook),然後適度修改 `phonebook_opt.c` 和 `phonebook_opt.h` 兩個檔案,使得這兩者執行時期的 cache miss 降低。請用 perf 驗證,而且改進的過程中,不能有功能方面的減損。 - `phonebook_orig.[ch]` 不需要修改,我們關注的是 `phonebook_opt.[ch]`,當然要修改 `main.c` 也是允許的 - `findName()` 的時間必須原本的時間更短 - `append()` 的時間可以比原始版本稍久,但不應該增加太多 - `main.c` 應該只有一份,不要建立新的 `main()`,善用 Makefile 定義對應的 `CFLAGS` - 在執行程式(`phonebook_orig` 和 `phonebook_opt`) 前,先清空 cache: ```sh $ echo 1 | sudo tee /proc/sys/vm/drop_caches ``` * 除了修改程式,也要編輯 Hackpad 下方「[作業區](https://embedded2016.hackpad.com/2016q1-Homework-1-tiduo3FfIQD)」,增添開發紀錄和 GitHub 連結 - 至少要列出效能分析,以及充份說明你如何改善效能 * 更新 Hackpad 後,**還要寄信通知授課教師和助教** - 寄件到 - 標題: “[NCKU/embedded]” 開頭,後面加學號與姓名 - 內容:(回答以下問題) - GitHub 帳號, wiki 帳號 (註冊本站) - 關於 fork 出來的 repository 修改描述 - 附上一份自我介紹和對課程的期許 * 務必使用 astyle 排版,詳細使用方式見 [README.md](https://github.com/embedded2016/phonebook/blob/master/README.md) * 可能的效能改進方向: - 改寫 `struct __PHONE_BOOK_ENTRY` 的成員,搬動到新的結構中 - 使用 hash function 來加速查詢 - 既然 first name, last name, address 都是合法的英文 (可假設成立),使用[字串壓縮的演算法](http://stackoverflow.com/questions/1138345/best-compression-algorithm-for-short-text-strings),降低資料表示的成本 - 使用 binary search tree 改寫演算法 * 截止日期: - Mar 6, 2016 (含) 之前 - 越早在 GitHub 上有動態、越早接受 code review,評分越高 挑戰題 ---------- * 除了降低 `findName()` 的 cache miss 與執行成本,`append()` 也該想辦法縮減時間 - 建立 phone book 時,既然 lastName 是索引值,可以優先建立搜尋表格,其他資料可稍後再補上 - 用 PThread 建立 [manager/worker thread model](http://stackoverflow.com/questions/12282393/how-to-synchronize-manager-worker-pthreads-without-a-join) * 支援 [fuzzy search](http://www.informit.com/articles/article.aspx?p=1848528),允許搜尋 lastName 時,不用精準打出正確的寫法 - 比方說電話簿有一筆資料是 `McDonald`,但若使用者輸入 `MacDonald` 或 `McDonalds`,也一併檢索出來 - 延伸閱讀: [Levenshtein Distance (編輯距離)](https://charles620016.hackpad.com/ep/pad/static/Japi4qFyAzt) * 改善電話簿的效能分析,透過大量的重複執行,找出 95% 信賴區間,而且允許動態新增資料 (較符合現實) 和查詢 * 以 [gnuplot](http://www.gnuplot.info/) 繪製效能分析圖表 參考資料 ------- * [Makefile 語法簡介](http://tetralet.luna.com.tw/?op=ViewArticle&articleId=185) * [Gnuplot 純畫圖](http://user.frdm.info/ckhung/b/ma/gnuplot.php)