# 2017q1 Homework1(phonebook)
contributed by < `baimao8437` >
## Reviewed by `xdennisx`
- 使用字串開頭的字母作為分類依據無法符合真實名字的分布量，應該要在找尋適合的 hsah function 做為分類依據
- commit [30978966cd6f9f7f236aa3a5f39485080a7c820f](https://github.com/baimao8437/phonebook/commit/30978966cd6f9f7f236aa3a5f39485080a7c820f)，應該說明實作後有什麼影響
- 第二個優化方式 (建立字首表) 的效能應該要獨立長條圖，比較能一眼能看出效能差異
### 花費時間 ~2/22~ ~-~ ~2/25~
* 環境建制：1 hr
* 讀書：8 hr
* 文件：5 hr
* coding: 3 hr
* ~~看著發呆：4 hr~~
## 目標設定
* 習慣 linux 系統基本操作
* 熟練 git 基本版本控管操作
* 效能分析 & 繪圖工具練習
* HackMD 學習報告寫作練習
* 減少發呆時間...
## 前置作業
1. 雙系統安裝： Ubuntu 16.10
2. git 安裝
3. perf 安裝
* 查看是否啟用 perf
```
＄ cat "/boot/config-`uname -r`" | grep "PERF_EVENT"
```
* output:
```
CONFIG_HAVE_PERF_EVENTS=y
CONFIG_PERF_EVENTS=y
CONFIG_HAVE_PERF_EVENTS_NMI=y
CONFIG_PERF_EVENTS_INTEL_UNCORE=y
CONFIG_PERF_EVENTS_INTEL_RAPL=m
CONFIG_PERF_EVENTS_INTEL_CSTATE=m
# CONFIG_PERF_EVENTS_AMD_POWER is not set
CONFIG_SECURITY_PERF_EVENTS_RESTRICT=y
```
3. Sublime package 安裝
* *c improved*
* *git*
* *SublimeAStyleFormatter*
>好物阿 設定k&r風格 tab = 4 space... 按下ctrl+alt+f就會自動 format
* ...
## 開發環境
```
baimao@baimao-Aspire-V5-573G:~$ lscpu
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
型號： 69
Model name: Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz
製程： 1
CPU MHz： 1711.242
CPU max MHz: 2600.0000
CPU min MHz: 800.0000
BogoMIPS: 4589.38
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 3072K
NUMA node0 CPU(s): 0-3
```
## 效能分析
* 先把 cache drop 掉 ```echo 1 | $ sudo tee /proc/sys/vm/drop_caches```
* 原始效能: ```$ make``` ```$./phonebook_orig```
```
size of entry : 136 bytes
execution time of append() : 0.080590 sec
execution time of findName() : 0.006082 sec
```
* 嘗試使用 perf 找尋熱點: ```$ ./phonebook_orig & sudo perf top -p $!```
不知道為何常常會出現錯誤
回頭參考[文件](https://hackmd.io/s/B11109rdg)
輸入```$ cat /proc/sys/kernel/perf_event_paranoid```
結果回傳 3 看來我發現第五種權限
無法理解 只好重新安裝 ```sudo apt-get install linux-tools-4.8.0-39-generic linux-cloud-tools-4.8.0-39-generic```
結果還是一樣...
只有某一次貌似有成功
>其實一開始權限未開時, default=3 是沒錯的。[name=課程助教][color=#08cccc]
```
Samples: 9 of event 'cycles:ppp', Event count (approx.): 608768382360
Overhead Shared Object Symbol
100.00% phonebook_orig [.] findName
0.00% libc-2.24.so [.] __strcasecmp_l_avx
0.00% [kernel] [k] __perf_event_enable
0.00% [kernel] [k] native_write_msr
```
* ~~*沒意義的*~~ *plot 練習*: ```$ sudo make plot```
* cache misses: ```$ sudo make cache-test```
```
Performance counter stats for './phonebook_orig' (100 runs):
706,754 cache-misses # 70.053 % of all cache refs ( +- 0.75% )
1,008,891 cache-references ( +- 0.62% )
261,532,481 instructions # 1.11 insn per cycle ( +- 0.02% )
234,628,975 cycles ( +- 1.18% )
0.098893317 seconds time elapsed
```
奇怪 cache misses 只有70.053% 怎麼比想像中的小 drop cache 後再試一次
```
Performance counter stats for './phonebook_orig' (100 runs):
696,272 cache-misses # 69.420 % of all cache refs ( +- 0.94% )
1,002,985 cache-references ( +- 0.60% )
261,616,187 instructions # 1.09 insn per cycle ( +- 0.02% )
239,799,933 cycles ( +- 0.86% )
0.101390978 seconds time elapsed
```
恩... miss 更少了... 是運氣好 吧 嗎？！
不管了直接~~先睡~~進行下一步開始優化~
## 效能提升
### 改寫 structure 成員 搬動到新的結構中
1. 改變 ```struct __PHONE_BOOK_ENTRY``` 的成員：
```clike=
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
struct __PHONE_BOOK_ENTRY *pNext;
} entry;
```
由於 append & findName 都只有用到 lastName 所以只留下 lastName 來做搜尋
#### 結果：
* size of entry 由原本 136 減少至 24 byte
```
size of entry : 24 bytes
execution time of append() : 0.041032 sec
execution time of findName() : 0.002848 sec
```
* cache misses 也從原本 69.087% 降至 **41.109%**
```
Performance counter stats for './phonebook_opt' (100 runs):
89,422 cache-misses # 41.109 % of all cache refs ( +- 0.80% )
217,523 cache-references ( +- 0.65% )
239,413,785 instructions # 1.89 insn per cycle ( +- 0.02% )
126,844,067 cycles ( +- 0.23% )
0.051042882 seconds time elapsed
```
* plot
!!! 為什麼感覺沒有變! 肯定是我忘了什麼了
原來是我眼殘沒看到 ```phonebook_opt.h``` 的 TODO
要把 ```// #define OPT 1``` 註解拿掉阿 可惡的柱姐!
成功 plot 看出差異
**執行第一次 commit** ```Minify tht struct only lastName stay```
>後來使用 ```git commit --amend``` 修改最近一次 commit message 成 ```Minify the structure only lastName stay```
commit 後熊熊發現 沒有格式化程式碼風格
趕緊安裝 git hook ```$ ln -sf ../../scripts/pre-commit.hook .git/hooks/pre-commit```
接著 ```astyle --style=kr --indent=spaces=4 --indent-switches --suffix=none *.[ch]```
還好沒有檔案需要格式化 下次提交前也會自動檢查符不符合格式了
2. 搬動到新的結構中：
>這邊參考了去年作業的開發紀錄 因為只有 lastName 的電話簿就不是電話簿了
>再顧及 structure 大小和資料的完整性
>把其他的資料移至另一個新的 structure
```clike=
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];
struct __PHONE_BOOK_DETAIL *details;
struct __PHONE_BOOK_ENTRY *pNext;
} entry;
```
將除了 lastName 以外的資料 都放進 detail 中
主要的搜尋還是由 entry 來執行
#### 結果：
* size of entry 由原本(opt) 24 增加至 32 byte
```
size of entry : 32 bytes
execution time of append() : 0.050103 sec
execution time of findName() : 0.003956 sec
```
* cache misses 也從原本(opt) 41.109% 降至 **28.988%**
```
Performance counter stats for './phonebook_opt' (100 runs):
133,845 cache-misses # 28.988 % of all cache refs ( +- 0.93% )
461,732 cache-references ( +- 0.54% )
243,501,920 instructions # 1.63 insn per cycle ( +- 0.09% )
149,249,905 cycles ( +- 0.59% )
0.063046039 seconds time elapsed
```
* plot
???? 怎麼好像似曾相識的數值 WHY~ 畫出來的圖跟上面一模一樣
怒 ```$ make clean``` ```$ sudo make plot``` 就正常了@@
合理的結果 兩個 function 的時間都比上次還要長
因為 entry size 變大了
**執行第二次 commit**```Move other detail into a new structure```
### 建立字首表 決定開頭
想法：在建 list 時用一 array 將每個名單的每種字母開頭的第一個 entry 紀錄下來
```clike=
entry *table[26];
int index = 0;
char lastAlph;
while (fgets(line, sizeof(line), fp)) {
while (line[i] != '\0')
i++;
line[i - 1] = '\0';
i = 0;
e = append(line, e);
if (line[0]!=lastAlph){
table[index++]=e;
lastAlph = line[0];
}
}
```
findName 前先決定開頭位置
```c=
e = table[input[0]-'a'];
assert(findName(input, e) &&
"Did you implement findName() in " IMPL "?");
```
#### 結果：
* cache misses 提高了不少@@
```
Performance counter stats for './phonebook_opt' (100 runs):
80,153 cache-misses # 49.690 % of all cache refs ( +- 0.87% )
161,306 cache-references ( +- 1.16% )
184,687,859 instructions # 1.61 insn per cycle ( +- 0.03% )
114,998,558 cycles ( +- 0.36% )
0.046735902 seconds time elapsed
```
* 但是 findname 的執行時間確實有減少蠻多的感覺
**第三次 commit**```Create a array of leading alphabet to set entry```
結果一個沒注意 有兩三個地方不符合 coding style 被提醒說要修改
**第四次 commit**
```
Fix the incorrect code and ensure the coding style
First, the coding style won't always warn by git hook, like space
beside assignment(=), should format code by sublime etc.
Second, don't leave a dead code in source code, there are complete
history in github, so no need to comment code to see what we changed.
Final, the warning of no newline at end of file, each line of source
code should have a character symbolizes the end, that is newline.
```
詳閱了 [How to Write a Git Commit Message](https://chris.beams.io/posts/git-commit/)
commit 了第一次包含正文的 message
## 本例選用的 dataset (也就是輸入電話簿的姓名) 是否存在問題？
* Q: 有代表性嗎？跟真實英文姓氏差異大嗎？
A: word.txt 中存在很多沒有意義的字，甚至不能稱為 word，而只是依些隨機的字母排列，跟真實的姓氏其實差異很大, 來看分析數據:
其中將 word 與另一個字典檔 all-names 做比較，其中 all-names 裏面還有重複的資料，word 則無
將 all-names 全部共 16747 筆資料，在 word 中檢視存不存在:
```
result:total:16747,found:14538(repeat:48),unfound:2209
```
這就表示，並不是全部該有的名子都包含在 word 中，另一方面也表示，word 中其實只有 14538 - 48 = 14490 筆是有用的名子，word 的資料量卻有 34990 筆，有超過一半的資料是無用的字，以 word 來作為 phonebook 的代表性很低
* Q: 資料難道「數大就是美」嗎？
A: 資料量大固然代表相對齊全，但搜尋的花費也相對較多，而不必要的資料就會產生不必要的花費，所以資料應該重點是精準,而不在多
* Q: 如果我們要建立符合真實電話簿情境的輸入，該怎麼作？
A: 既然是人名，在建立電話簿時的單字就應該要是合法的英文，把不可能出現的單字都刪掉 e.g.三字母以上連續 (aaaaaagh...)
然後在搜尋時，為了做有效的輸入，可以在輸入一個字母時立即判斷並列出可能選項，減少輸入錯誤
## 參考資料：
* [vivian 的共筆](https://hackmd.io/s/SyOQgOQa#)
* [Jserv's blog: "no newline at end of file"](http://blog.linux.org.tw/~jserv/archives/001933.html)
Sign in with Wallet
Connect another wallet