版本 23dba54fa0f99c0a2d235b6c9968c51ac66aa4c9
Changes from 23dba54fa0f99c0a2d235b6c9968c51ac66aa4c9 to 7491df77f4cd97c6debf381ad10d4a7752b785a3
---
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
```
* 關於 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 語言和資料結構。以前大家只是「背誦心法」，從來就不會去理解個別資料結構對整體的衝擊。
看到 `[sudo] password for ` 字樣時，輸入自己的 Linux 使用帳號密碼
作業要求
-------
* 在 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://embedded2015.hackpad.com/2015q3-Homework-2-y6EF1Im4GEr)」，增添開發紀錄和 GitHub 連結
- 至少要列出效能分析，以及充份說明你如何改善效能
* 務必使用 astyle 排版，詳細使用方式見 [README.md](https://github.com/embedded2015/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)
