# 2017q1 Homework1 (phonebook)
contributed by < `etc276` >
###### tags: `etc276`
## Reviewed by `yanang`
* 在 append() 中，當發生相同 hash value ，以 linked list 串連心增加的 data ，若考慮將資料重最前端插入，則可以減少尋找尾端的時間。
```c=
entry *pHead = (entry *) malloc (sizeof(entry));
pHead->pNext = e[hash];
e[hash] = pHead;
strcpy(pHead->lastName,lastName);
```
* 不同的 hash function 和不同的 table size 都會影響實驗結果，可以參考 [how to choose size of hash table](http://stackoverflow.com/questions/22741966/how-to-choose-size-of-hash-table)
* 針對你的實驗結果，就我的實驗結果和各位同學的共筆展示，使用 hash table 來搜尋資料應是非常迅速。
* time of finName() = 0.002348 是完全不符合預期的，是否在繪圖時使用了錯誤的資料來源?
## 開發環境
- Ubuntu 16.10 (64bit)
```
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 61
Model name: Intel(R) Core(TM) i7-5500U CPU @ 2.40GHz
Stepping: 4
CPU MHz: 2400.878
CPU max MHz: 3000.0000
CPU min MHz: 500.0000
BogoMIPS: 4788.90
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 4096K
NUMA node0 CPU(s): 0-3
```
## 相關連結
- [2017 年春季作業說明](https://hackmd.io/s/Bk-1zqIte#)
- [2017q1 Homework1 (作業區)](https://hackmd.io/MYJjEYGZITgWgOwCMAmw4BYYwAxyQQKxwBmwGOkAHMDeEgGxA===?view)
- [B01: phonebook作業要求](https://hackmd.io/s/rJYD4UPKe#b01-phonebook)
- [phonebook Github連結 ( etc276 ) ](https://github.com/????????)
- [作業解說 video](https://www.youtube.com/watch?v=ZICRLKf_bVw)
- [課程進度與開放資源 Wiki](http://wiki.csie.ncku.edu.tw/sysprog/schedule)
## 開發紀錄
### Original
```c==
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;
```
* 自 GitHub 取得作業程式碼 (先要 fork 到自己帳號在 clone )
```
$ git clone https://github.com/etc276
$ cd phonebook
```
* 執行程式，並用 perf 檢查效能，可以發現 cache miss 高達 81.73%
```clike
Performance counter stats for './phonebook_orig' (100 runs):
3,430,005 cache-misses # 81.729 % of all cache refs ( +- 0.03% )
4,196,826 cache-references ( +- 0.19% )
261,712,845 instructions # 1.34 insn per cycle ( +- 0.02% )
194,998,572 cycles ( +- 0.26% )
0.066929775 seconds time elapsed ( +- 0.31% )
```
* 透過 gnuplot 建立執行時間的圖表
### Optimization 1 (By struct)
```c==
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
struct __PHONE_BOOK_ENTRY *pNext;
struct __PHONE_BOOK_DETAIL *pDetail;
} entry;
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;
```
目前我對 cache miss 對效能影響的理解為，由於記憶體使用上並不連續，造成 latency 變長。所以先從 struct 下手，讓會用到的資料盡量連續，而方法為將 lastname 以外的資料存在別的地方，減少單一 entry 的大小。
如下方所示，cache miss下降到 69.64%，執行時間也稍有下降。
```c
Performance counter stats for './phonebook_opt' (100 runs):
1,210,125 cache-misses # 69.643 % of all cache refs ( +- 0.19% )
1,737,624 cache-references ( +- 0.58% )
243,060,991 instructions # 1.75 insn per cycle ( +- 0.02% )
139,089,184 cycles ( +- 0.78% )
0.048515702 seconds time elapsed ( +- 0.93% )
```
### Optimization 2 (By hash)
```c==
entry *findName(char lastName[], entry *e[])
{
int hash = BKDRHash(lastName)%TABLE_SIZE;
entry *tmp = e[hash];
while (tmp) {
if (!strcasecmp(lastName, tmp->lastName))
return tmp;
tmp = tmp->pNext;
}
return NULL;
}
void append(char lastName[], entry *e[])
{
int hash = BKDRHash(lastName)%TABLE_SIZE;
entry *tmp = e[hash];
while (tmp->pNext) {
tmp = tmp->pNext;
}
entry *node = (entry *) malloc(sizeof(entry));
tmp->pNext = node;
strcpy(node->lastName, lastName);
}
```
減少 cache miss 之後，下一步想辦法從演算法減少時間。 original 的版本就是從頭到尾跑一遍查詢，這在資料量龐大時效能會有明顯影響，所以就想用 O(1) 的 hash 去實現。而在參考完 [Section 8 哈希表（Hash Table）](http://pisces.ck.tp.edu.tw/~peng/index.php?action=showfile&file=f3443505c4cd3d8598eee689618327ef8af0f8af7)，決定使用 BKDR 加上"拉鍊法"處理 hash 和碰撞的問題。
而實際上 coding 才想到自己其實不知道要怎麼選 table size，參考完 [为什么hash table的大小最好取一个不接近2^p的素数](http://thuhak.blog.51cto.com/2891595/1352903) 還是不知道要選用什麼數量級的質數，再繼續看其他人的開發紀錄，發現有人[實驗](https://hackmd.io/s/Hyr9PhFYx)過，最後決定選用 20k 附近且有在[這篇](https://hackmd.io/s/HkO2ZpIYe)中出現的 21911 作為 table size.
cache miss 下降到 36.93%
```clike
Performance counter stats for './phonebook_opt' (100 runs):
15,649 cache-misses # 36.930 % of all cache refs ( +- 1.25% )
42,374 cache-references ( +- 0.61% )
691,447 instructions # 0.59 insn per cycle ( +- 0.20% )
1,169,857 cycles ( +- 1.09% )
0.121802201 seconds time elapsed ( +- 1.69% )
```
:::danger
所以你還是沒搞懂，快去「找教科書」(不要茫茫網海亂找) 來讀，我等你的報告 --jserv
:::
### 問題思考
* 有代表性嗎？跟真實英文姓氏差異大嗎？
* 我們先查看各字母使用的頻率，可以發現差異相當大
圖片來源 : https://zh.wikipedia.org/wiki/%E5%AD%97%E6%AF%8D%E9%A2%91%E7%8E%87
* 然後再查看英文單詞中，首字母的頻率
* 再查看 work.txt 以及 [illusion030 的共筆]("https://hackmd.io/s/S1mqcITtl#")可得知此 dataset 的 真實姓名不多
>> words.txt 中有大量沒有意義的單字(ex.aaaaa)，寫一個比較的程式發現，words.txt 裡總共 349900 筆資料，但是只有 7426 筆資料有在 all-names.txt 裡出現，所以 words.txt 對 phonebook 來說代表性很低。
* 而且真實情況中， lastName 一定會發生重複的情況
```
首字母 單詞頻率
t 16.671%
a 11.602%
s 7.755%
h 7.232%
w 6.753%
i 6.286%
o 6.264%
b 4.702%
m 4.374%
f 3.779%
c 3.511%
l 2.705%
d 2.670%
p 2.545%
n 2.365%
e 2.007%
g 1.950%
r 1.653%
y 1.620%
u 1.487%
v 0.649%
j 0.597%
k 0.590%
q 0.173%
x 0.037%
z 0.034%
```
* 資料難道「數大就是美」嗎？
寫程式是要給其他人使用的，所以數據的選擇也要盡量真實。以此 dataset 為例，就算增加 work.txt 裡的 "偽" 數據，也無法"美"。例如 Michael 在英文名字中出現的頻率遠比 Zuzzolo 高，如果我們單純地用 lastName 去做 hash 處理，會發現前者的 link list 過長，而後者就只有一個 entry 的情況出現。
* 如果我們要建立符合真實電話簿情境的輸入，該怎麼作？
要先確定這本電話簿的使用情況，如年代、地區等等，然後去戶政事務所或是相關網站找出一部份的姓名，並試圖增加重複性或抽樣等方法當作母群體，去實際執行並抓出 95% 的信賴區間，以符合真實情況。
## 相關知識
### cache
目前電腦的架構為處理器(CPU)+記憶體(RAM)，但由於近 40 年來兩者的速度差異越來越大，所以就利用 cache 去減少效能上的差異。
cache 是 CPU 外層的記憶體，其容量相當小，藉由將 RAM 的一部分資料先放在上面，減少兩者溝通的時間。而因為 cache 的容量遠小於 RAM，所以如果 CPU 要用到的下一個資料不在 cache 上，就會發生 **cahe miss**，反之則為 **cache hit**。
cache 的原理為：「實務上會使用到的記憶體常為連續性的」。所以才有辦法藉由這種結構去彌補兩者之間的速度差(可以先把資料放上 cache )，因此第一個優化方法就是先盡量將資料連續化。
###### 參考資料
### perf
perf 是一種效能分析工具。他會幫你計算 cache miss, instructions 等等，去分析程式的效能瓶頸。相關資料請參閱 [perf 原理和實務 ](https://hackmd.io/s/B11109rdg)
### gunplot
* gunplot 是一種繪圖工具，可以批次提供圖表。
* gnuplot 啟動後，需要做一些必要設定，例如設定圖片名稱，XY 軸的資訊等等:
```c
> 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 [Script]
* 查看圖片 $ eog [jpg/png...]
* 更多使用方法請點 [這裡](https://hackmd.io/s/Skwp-alOg)
### astyle
使用相同的 coding style 有助於多人開發(commit style也是)，而這次的規範為：
```
$ astyle --style=kr --indent=spaces=4 --indent-switches --suffix=none *.[ch]
```
- ```--style=kr``` 用 K&R 的風格進行編程
- ```--indent=spaces=4``` 四個空格
- ```--indent-switches``` 關於 Case 的縮排
> Indent 'switch' blocks, so that the inner 'case XXX:'
headers are indented in relation to the switch block.
- ```--suffix=none``` 不保存原始文件
- ``` *.[ch]``` 所有的.c或.h檔
## 進度與小結
:::danger
「預計」就不要寫出來，Show me the code!
HackMD 會幫你記錄每筆紀錄的變更和具體時間，把時間省下來發現並解決問題 --jserv
:::
<s>
* 2/27 以前在安裝 ubuntu 和閱讀相關資烙
* 2/28 開始寫開發紀綠(一些自己的認知和 original 的測試結果)
* 3/01 第一次 commit (Opt by struct)
* 3/02 (預計) 完成 Opt by hash
</s>
## 心得
在寫 hash 的時候，產生一堆 bug ，時間詭異，圖也沒有出現。後來才知道是 main.c 錯太多東西，導致像 orig.txt 等文件並沒有產生成功，索性刪掉重新 clone 。之後先仔細閱讀 Makefile 裡各 source code 的相依性，才知道要先從 opt.h 修改起，像是我修改 function 的 prototye，這時 main.c 就需要去利用 #ifdef OPT 做修改，最後才是 opt.c 的小 bug .
Sign in with Wallet
Connect another wallet