# 2017q1 Homework1 (phonebook)
contributed by < `wangchangchun` >
>進度嚴重落後，趕緊追上
>[name=課程助教][color=red]

### Reviewed by `bananahuang`
* 因為 PID 就是 process ID,當你在 process 結束後在新 terminal 再下 `$perf top -p $pid`已經不會顯示任何資訊,解決方法有兩個,其一就是把執行時間拉長,其二使用`$ ./ "執行檔案名稱" & sudo perf top -p $!`
* perf 可以讓你知道在執行哪些函式最耗效能,可以針對其做進一步優化
* line 會存入 lastname 訊息,再拿來建立電話簿
* 可以著手 hash function 用來改善 findname 查詢速度
## 開發環境
電腦規格，偷看了共筆範例才知道原來 "lscpu" 這個指令可以用來看 cpu 資訊...

Architecture:          x86_64
CPU 作業模式：    32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
每核心執行緒數：2
每通訊端核心數：2
Socket(s):             1
NUMA 節點：         1
供應商識別號：  GenuineIntel
CPU 家族：          6
型號：              60
Model name:            Intel(R) Core(TM) i5-4210M CPU @ 2.60GHz
製程：              3
CPU MHz：             3161.539
CPU max MHz:           3200.0000
CPU min MHz:           800.0000
BogoMIPS:              5187.92
虛擬：              VT-x
L1d 快取：          32K
L1i 快取：          32K
L2 快取：           256K
L3 快取：           3072K
NUMA node0 CPU(s):     0-3

--> 看完有看沒有懂，該複習了QAQ

## Git
由於不熟悉 git 的用法，再練習使用時不小心改到 master 分支QAQ
老師建議使用```git rebase -i```修正
### git rebase 資料
[參考資料](https://blog.yorkxin.org/2011/07/29/git-rebase)
在 git 中，每一個 commit 都可以長出 branch ，而 branch 的 base 就是它生長出來的 commit ，rebase 也就是把該 branch 所長出來的 commit 給改去另一個 commit 。

## Perf
* 試了很久才發現好像要執行檔執行期間同時下 perf top -p $pid 才會出現結果
* wiki 上說 " perf 可以分析出消耗 CPU 週期最多的部份 " ->拿來找可優化的部份？

### Perf list
印出 perf 可以觸發哪些 event

### Perf top
拿phonebook來試 ```perf top```

-->好像沒有 overhead 特別重的部份？？

>進度要加快，perf 練習的部份記得也要放上共筆，因為這不只是給別人看，更是給未來的自己看的歐。[name=亮谷][color=#039fff]

## 閱讀程式碼
* IMPL
*
### main.c
IMPL --> 不太懂
* ```diff_in_second``` : 計算時間，有較高精確度。如果 nsec < 0 跟 sec 借一秒 ——> nsec + 1000000000 , sec - 1
* ```assert``` 若後面的判斷式為 true 則繼續執行，false 的話則停止運作
* 小技巧：再 assert 後加 && 印出字串
* line 是輸入的 lastName ? -> 結尾去掉換行符號

### phonebook_orig.h
* 電話簿的structure

typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    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];
    struct __PHONE_BOOK_ENTRY *pNext;
} entry;

* 要記得把 phonebook_orig.h 裡的``` #define OPT 1 ```前的註解拿掉，不然不會產生```opt.txt``` ， output.txt 會只有 orig.txt 的資料

### phonebook_orig.c
* ```strcasecmp``` : 忽略大小寫 byte-by-byte 比較字串
* ```entry *findName(char lastName[], entry *pHead)``` : 輸入 lastname 及 電話簿 linklist 的 head, 一一比較字串是否相同
* ```entry *append(char lastName[], entry *e)``` : 加入新的 lastname 在電話簿的最尾端 --> 不用按照順序排嗎？？
* ```entry *e```是最後一筆資料

## 減少 entry 的 struct 大小
將 lastName 以外的資料移出 entry
>文字訊息(如:程式碼和輸出結果)直接貼上就好，避免使用圖片
>[name=課程助教][color=red]

時間縮短不少

cache miss 也從 83.672 % 降到 41.381 %
>下列結果也請直接複製貼上[name=課程助教][color=red]



## BKDRhash
[各種hash funtion比較](https://www.byvoid.com/zhs/blog/string-hash-compare)
看完上方網站決定以效能較好的BKDR實作

[為何seed要取131](https://www.zhihu.com/question/20507188)
###### tags: `hw1-1`