2016q3 Homework1 (phonebook)

contributed by <Jing Zhou>

Reviewed by `ChenYi`

github上的code有問題
- phonebook_opt.c 裡的apend funciton中的tmp沒有被宣告
commit訊息只有add file via upload，可以考慮寫詳細點

開發環境

ubuntu 16.04

將磁碟分割出80G空間後，使用live usb安裝
開機選單只出現單系統，解決方法：
Windows與Ubuntu雙系統，開機時偵測不到彼此的解決方法

準備過程

安裝相關開發工具

$ 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

$ sudo apt-get install linux-tools-4.4.0-31-generic

測試Perf

# 測試成功
$ sudo perf list
$ sudo perf top

# 測試失敗(解決)
# 必須在 ./example 執行結束前輸入以下指令才可偵測
$ sudo perf top -p $pid

Github及Git操作

Github加入本機ssh

# 本機產生ssh
$ ssh-keygen -t rsa -C "[email]"
$ ssh-agent -s
$ ssh-add ~/.ssh/id_rsa

# 複製id_rsa.pub內容到Github加入ssh
$ cd ~/.ssh
$ cat id_rsa.pub

# 檢查
$ ssh -T git@github.com

顯示底下表示成功

Hi [username]! You've successfully authenticated,
but GitHub does not provide shell access.

Git遠端同步操作

# 安裝
$ sudo apt-get install git
			
# 從Github fork專案
# 下載到本機
$ git clone https://github.com/judy66jo/phonebook

# 進入 ./phonebook  底下有已有 .git/
# 跳過 $ git init
			
# 設定參數
$ git config --global user.email "you@example.com"
$ git config --global user.name "Your Name"
$ git config --global push.default matching

# 上傳前先清乾淨不必要的檔案
$ make clean

# 修改檔案後
$ git add .
$ git commit -m "..."
$ git push

參考資料
Linux 效能分析工具: Perf
GitHub - 參與一個專案
 GitHub Trianing
C 語言中的編譯時期函數

phonebook優化

未優化版本

執行時間

$ ./phonebook_orig 
size of entry : 136 bytes
execution time of append() : 0.035779 sec
execution time of findName() : 0.004830 sec

cache-misses 90.670%

$make cache-test
...
 Performance counter stats for './phonebook_orig' (100 runs):

		  446,2693      cache-misses              #   90.670 % of all cache refs      ( +-  0.18% )
		  492,1906      cache-references                                              ( +-  0.12% )
	   2,6067,0515      instructions              #    1.42  insns per cycle          ( +-  0.02% )
	   1,8331,1704      cycles                                                        ( +-  0.15% )

	   0.050803658 seconds time elapsed                                          ( +-  1.20% )

執行前清空caches

$ echo 1 | sudo tee /proc/sys/vm/drop_caches

用perf找熱點，findName佔了26.83%

$ ./phonebook_orig & sudo perf top -p $!

縮減欄位

將沒有用到的資料欄位建立新的struct，entry中只保留lastname，其它和維持orig版一樣，結果顯示cache-misses下降

phonebook_opt.h

typedef struct __PHONE_BOOK_DETAIL {
char firstName[16];
char email[16];
char phone[10];
char cell[10];
char addr1[16];
char addr2[16];
char city[16];
char state[2];
char zip[5];
} detail;

typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
detail *pDetail;
struct __PHONE_BOOK_ENTRY *pNext;
} entry;

執行時間

$ ./phonebook_opt
size of entry : 32 bytes
execution time of append() : 0.029268 sec
execution time of findName() : 0.001594 sec

cache-misses 65.434 %

$make cache-test
...
 Performance counter stats for './phonebook_opt' (100 runs):

      143,7633      cache-misses              #   65.434 % of all cache refs      ( +-  0.63% )
      219,7071      cache-references                                              ( +-  0.17% )
   2,4388,5560      instructions              #    2.03  insns per cycle          ( +-  0.02% )
   1,2025,0834      cycles                                                        ( +-  0.16% )

   0.032420169 seconds time elapsed                                          ( +-  0.16% )