2018q1 Homework1 (phonebook)
===
contributed by <`raygoah`>
### Reviewed by `afcidk`
* 把 lastName 以外的資料移至另一 struct 後，並沒有配置空間給那些資料。做了會不會對效能有影響？
* hash function 和 binary search tree 在 `findName()` 看不太出來效能的差別，是否有嘗試過查詢不同名字或是多次查詢來進行比較？
* 應該要將 output_all.txt 的產生方式也放上去，而不是放一個檔案讓每次 plot 出來的圖片都一樣
* hash 實做補上後應該把原本程式碼裡面的 **TODO** 拿掉
### Reviewed by `LinYunWen`
* 有做很多不同 hash function 的實作，很不錯，不過可以多加一些說明在，為什麼要選取那幾種 hash function 來實作而不是別種
* 而且雖然實作了這麼多種 hash function ，但是為什麼最後跟 BST 做比較時，不是所有比較或是平均值比較，反而只取用 ELF hash function，這裡也可以多做些解釋
* 另外 hash function 不只如何運算 hash value 重要，其 hash table size 也是一個重要的議題，可以說明一下，為什麼 ```HASH_TABLE_LENGTH = 1024 ```
* 可以嘗試其他 data set 來做搜尋
* 我有點好奇為什麼你會有兩個一樣操作但是不同的 commit 點 ([commit 30cd405](https://github.com/raygoah/phonebook/commit/30cd405aabd8bdfe53e4c26bd12c3474df262ccb)、[commit 1143131](https://github.com/raygoah/phonebook/commit/114313110a8461108c758ebc82288f0292d3e02c))
### Reviewed by `rwe0214`
* 根據使用的演算法將 linked-list 轉成 BST 時間複雜度應為 `O(n)`，而不是 `O(nlogn)`，如果是 `O(nlogn)` 時間應該不只這樣><
>這裡對應的程式碼修改應一併傳到 GitHub 上
>commit message 的撰寫請參閱[【譯】如何撰寫Git提交訊息](https://xiwan.io/archive/how-to-write-a-git-commit-message.html)
>[color=red][name=vvn]
>> 好的，謝謝提醒 [name=raygoah]
## 系統環境
```shell
$ uname -a
Linux raygoah-X450JN 4.13.0-32-generic #35~16.04.1-Ubuntu SMP Thu Jan 25 10:13:43 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 60
Model name: Intel(R) Core(TM) i7-4700HQ CPU @ 2.40GHz
Stepping: 3
CPU MHz: 2394.560
CPU max MHz: 3400.0000
CPU min MHz: 800.0000
BogoMIPS: 4789.12
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 6144K
NUMA node0 CPU(s): 0-7
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt aes xsave avx f16c rdrand lahf_lm abm cpuid_fault epb invpcid_single pti tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt dtherm ida arat pln pts
```
## 認識 cache
* cache 可看做專屬於 cpu 的記憶體
* cpu 若在 cache 中找到所要的資料，則不必存取 main memory ，加快速度
* 閱讀資料: [cache 原理和實驗](https://hackmd.io/s/S14L26-_l#)
* 閱讀資料: [關於CPU Cache -- 程序猿需要知道的那些事](http://cenalulu.github.io/linux/all-about-cpu-cache/)
## phonebook 原始版本
* 先觀察一開始 fork 的檔案 cache miss 的情形
>中英文字間記得空白喔！[color=red][name=vvn]
>>感謝提醒[color=blue][name=raygoah]
* 清空cache
```shell
$ echo 1 | sudo tee /proc/sys/vm/drop_caches
```
* 觀察最原始版本的效能
```shell
$ make cache-test
```
* entry size 為 136 bytes下的部份輸出結果
```
size of entry : 136 bytes
execution time of append() : 0.046198 sec
execution time of findName() : 0.005292 sec
Performance counter stats for './phonebook_orig' (100 runs):
96,4703 cache-misses # 81.865 % of all cache refs ( +- 0.32% )
117,8403 cache-references ( +- 0.34% )
2,6322,4320 instructions # 1.29 insn per cycle ( +- 0.02% )
2,0401,7147 cycles ( +- 0.63% )
0.065028560 seconds time elapsed ( +- 1.07% )
```
* 利用 gnuplot 繪製圖形
* 切換成 root :
```shell
$ sudo su
```
* 繪製圖形
```shell
$ make plot
```
* 若要切換回 user
```shell
$ exit
```
* 在 user 用戶下使用 gnuplot 需要在前面加上 sudo
```shell
$ sudo make plot
```
>不需要使用 sudo XD [color=red][name=vvn]
>>之前沒有切換到 root ，現在學會了，已補上[color=blue][name=raygoah]
## 減少 entry size
* 想法：
* 觀察 `main.c` 後可以發現到，在 struct 中，實際會被使用到的其實只有 `lastName` ，推測將 struct 縮小，會降低 cache miss 的發生
* 作業解說影片中有提到，建議可先嘗試縮小 struct ，決定先從這部份下手。
* 測試減少 entry size 是否有用：
* 先試著將 struct 中除了 `lastName` 以外的所有程式碼註解
```clike=
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;
```
* 觀察縮小 struct 後，entry size 為 24 bytes 的情況下， cache miss 的情形：
```shell
$ make cache-test
```
```shell
Performance counter stats for './phonebook_opt' (100 runs):
4,0009 cache-misses # 50.970 % of all cache refs ( +- 0.27% )
7,8496 cache-references ( +- 0.33% )
9230,1160 instructions # 1.70 insn per cycle ( +- 0.00% )
5416,4353 cycles ( +- 0.32% )
0.121720307 seconds time elapsed ( +- 10.95% )
```
* 可以發現到，縮小 struct 後， cache miss 發生的情形確實有改善。但因為前面使用的方法是將程式碼註解，此方法可能會影響到程式的功能，因此接著嘗試在不影響程式功能的前提下，減少 entry size
* 減少 entry size:
* 將除了 lastName 以外的資料移至另一個 struct 中，分開儲存後，利用指標進行存取，在保存所有資料的同時，也減少了 `__PHONE_BOOK_ENTRY` 的大小，entry size 從原本的 136 bytes 減少為 32 bytes。
```clike=
typedef struct __PHONE_OTHER_ENTRY {
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];
} otherEntry;
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
struct __PHONE_BOOK_ENTRY *pNext;
otherEntry *other;
} entry;
```
* 在 entry size 為 32 bytes 的情況下，觀察 cache-miss 的情形：
```shell
$ make cache-test
```
```shell
Performance counter stats for './phonebook_opt' (100 runs):
16,1974 cache-misses # 47.797 % of all cache refs ( +- 1.18% )
33,8879 cache-references ( +- 1.04% )
2,4497,2241 instructions # 1.82 insn per cycle ( +- 0.02% )
1,3488,8711 cycles ( +- 0.48% )
0.043308698 seconds time elapsed ( +- 0.61% )
```
* 接著利用 gnuplot 繪製出圖形
```shell
$ make plot
```
* 從以上的結果可以看到，此方法在不影響到原始功能的情況下，減少了 entry size ，並且確實降低了 cache-miss 的發生。
## hash function
* 閱讀
* [hash function 觀念和實務](https://hackmd.io/s/HJln3jU_e#)
* [hash 函數比較](https://www.byvoid.com/zhs/blog/string-hash-compare)
* [BKDR hash](http://www.cnblogs.com/liuliuliu/p/3966851.html)
* [BKDR 算法解析及擴展](http://blog.csdn.net/wanglx_/article/details/40400693)
* 在實做前遇到的插曲：
* 更改完程式碼後，在 vscode 的 terminal 中 make ,程式碼確實有更動的情況，但 make 卻沒有反應
```shell
$ make
```
```shell
make: Nothing to be done for 'all'.
```
* 可能要先 `$ make clean` 再 `$ make`
* 之後每次先 `$ make clean` 再 `$ make` 後，就沒再發生過了
> 先把這個情況紀錄下來，要是還有出現，再來看看是哪邊出問題 [name=raygoah]
* 實作 hash function
依照 [hash 函數比較](https://www.byvoid.com/zhs/blog/string-hash-compare) 中介紹的各種不同的 hash function ，使用在此次作業中，並比較不同的 hash function 所得到的結果差異
1. 實作 BKDR hash
```clike=
unsigned int BKDRHash(char *str) {
unsigned int seed = 131;
unsigned int hash = 0;
while (*str) {
hash = hash * seed + (*str++);
}
return (hash % HASH_TABLE_LENGTH);
}
```
* 在這裡 seed 的值取 131，參考[此篇](https://www.zhihu.com/question/20507188)，而實際將 seed 改成 13 或 267 跑跑看，結果幾乎沒差，於是選擇 131 作為 seed 值
* 接著觀察使用了 BKDR hash 後，cache miss 的情形
```shell
Performance counter stats for './phonebook_hash_opt' (100 runs):
8,0568 cache-misses # 38.554 % of all cache refs ( +- 0.72% )
20,8977 cache-references ( +- 1.39% )
2,3603,5839 instructions # 1.83 insn per cycle ( +- 0.02% )
1,2924,6177 cycles ( +- 0.35% )
0.043926812 seconds time elapsed ( +- 0.88% )
```
* 由上圖可以看到，cache miss 發生的比率，從之前的 47.791% 下降到 38.554%, 因此實作 BKDR hash 是有助於減少 cache miss 的發生
* 利用 gnuplot 繪製出圖形，觀察使用 hash 後，`findName()` 和 `append()` 所需時間有無改變，可以看到在建立了 hash table 的版本中，`append()` 所花的時間是有些微增加的，但在 `findName()` 中所花費的時間，卻是大幅的減少，在圖中甚至已經看不太到了
2. 實作 AP hash
* 接著實作不同的 hash ，在這裡實作 AP Hash
```clike=
unsigned int APHash(char *str)
{
unsigned int hash = 0;
for (int i=0; *str; ++i) {
if ((i & 1) == 0) {
hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
} else {
hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));
}
}
return ((hash & 0x7FFFFFFF) % HASH_TABLE_LENGTH);
}
```
* 可以看到 cache-miss 的發生情形和 BKDR Hash 所產生的結果差不多，測試幾次的結果都落在 37% - 40%
```shell
Performance counter stats for './phonebook_hash_opt' (100 runs):
9,0705 cache-misses # 37.806 % of all cache refs ( +- 0.98% )
23,9924 cache-references ( +- 1.84% )
2,6462,1363 instructions # 1.97 insn per cycle ( +- 0.02% )
1,3420,8036 cycles ( +- 0.26% )
0.053116284 seconds time elapsed ( +- 0.88% )
```
* 而在 AP Hash 中，和 BKDR Hash 的結果類似，`append()` 所花的時間也是些微增加，在 `findName()` 中所花費的時間，也是大幅的減少
3. 實作 DJB Hash
```clike
unsigned int DJBHash(char *str)
{
unsigned int hash = 5381; // magic number
while (*str)
{
hash += (hash << 5) + (*str++);
}
return ((hash & 0x7FFFFFFF) % HASH_TABLE_LENGTH);
}
```
```shell
Performance counter stats for './phonebook_hash_opt' (100 runs):
8,3311 cache-misses # 37.684 % of all cache refs ( +- 0.41% )
22,1080 cache-references ( +- 2.15% )
2,3564,6536 instructions # 1.82 insn per cycle ( +- 0.02% )
1,2920,6859 cycles ( +- 0.38% )
0.040968937 seconds time elapsed ( +- 0.42% )
```
4. 實作 SDBMHash
* 接著實作看看在 [hash 函數比較](https://www.byvoid.com/zhs/blog/string-hash-compare) 中，平均得分比較低的 hash ，觀察得到的結果是否會如預期般有明顯落差
```clike
unsigned int SDBMHash(char *str)
{
unsigned int hash = 0;
while (*str) {
hash = hash * 65599 + (*str++);
}
return ((hash & 0x7FFFFFFF) % HASH_TABLE_LENGTH);
}
```
* 關於 cache-miss 的部份，平均 40.157% 比起上述幾種不同 hash 所得到的 cache-miss rate 來說，確實是有比較高，嘗試了幾次後，得到的結果也都落在 39% - 41% 附近
```shell
Performance counter stats for './phonebook_hash_opt' (100 runs):
9,9660 cache-misses # 40.157 % of all cache refs ( +- 0.87% )
24,8174 cache-references ( +- 1.89% )
2,3289,3548 instructions # 1.74 insn per cycle ( +- 0.02% )
1,3368,8164 cycles ( +- 0.55% )
0.042705223 seconds time elapsed ( +- 0.56% )
```
5. 實作 ELFHash
```clike
unsigned int ELFHash(char *str)
{
unsigned int hash = 0;
unsigned int x = 0;
while (*str) {
hash = (hash << 4) + (*str++);
if ((x = hash & 0xF0000000L) != 0) {// 28-31 is 1 others are 0
hash ^= (x >> 24);
hash &= ~x;
}
}
return ((hash & 0x7FFFFFFF) % HASH_TABLE_LENGTH);
}
```
* 可以看到 cache-miss 的部份，發生的比率也是比較高的，嘗試了幾次後，得到的結果大致落在 39% - 42% 附近, cache-miss rate 是以上幾種 hash 中較高的
```shell
Performance counter stats for './phonebook_hash_opt' (100 runs):
8,3888 cache-misses # 40.979 % of all cache refs ( +- 1.16% )
20,4710 cache-references ( +- 0.99% )
2,5497,9203 instructions # 1.84 insn per cycle ( +- 0.02% )
1,3870,1759 cycles ( +- 0.18% )
0.044650160 seconds time elapsed ( +- 0.30% )
```
* 至於在 `findName()` 和 `append()` 所需時間方面，和之前幾種 hash 相比沒什麼顯著的差異
### 比較結果：
* 在以上幾種不同的 hash function 中，可以看到在 `append()` 的部份，所需花費的時間比起沒有使用 hash 的版本都有些許的增加，但在 `findName()` 的部份，可以很明顯的看到花費的時間大幅的減少
* 使用不同的 hash function，對於 cache-miss 的發生會有一點影響，在[hash 函數比較](https://www.byvoid.com/zhs/blog/string-hash-compare) 中排名較高的 hash，發生 cache-miss 的次數也有比較少的現象，但整體而言有使用 hash 比起沒有使用的版本，cache-miss rate 都是比較低的
## Binary Search Tree
* 閱讀
- [ryanwang522](https://hackmd.io/s/Sk-qaWiYl)
- [Sorted Linked List to Balanced BST](https://www.geeksforgeeks.org/sorted-linked-list-to-balanced-bst/)
- [演算法筆記](http://www.csie.ntnu.edu.tw/~u91029/Order.html)
* 實作
* 由 `ryanwang522` 的紀錄，以及 [Sorted Linked List to Balanced BST](https://www.geeksforgeeks.org/sorted-linked-list-to-balanced-bst/)，閱讀後實作 BST
```clike
BSTNode *BST(entry **tmp_head, int length)
{
if (length <= 0)
return NULL;
BSTNode *left = BST(tmp_head, length/2);
BSTNode *root = (BSTNode *) malloc(sizeof(BSTNode));
root->entry = *tmp_head;
root->left = left;
*tmp_head = (*tmp_head)->pNext;
root->right = BST(tmp_head, length - (length / 2 + 1));
return root;
}
```
* 可以看到 cache-miss 的部份，發生的比率比起使用 hash function 的結果來的高，同時整體所花費的時間也比較多，原因在於需要將 link list 轉成 BST，因此增加了整體運行的時間
```shell
Performance counter stats for './phonebook_bst_opt' (100 runs):
19,0481 cache-misses # 55.459 % of all cache refs ( +- 1.04% )
34,3462 cache-references ( +- 1.15% )
2,8595,9142 instructions # 1.76 insn per cycle ( +- 0.02% )
1,6207,7716 cycles ( +- 0.62% )
0.169329355 seconds time elapsed ( +- 8.87% )
```
* 雖說整體運行時間是增加的，但從繪製的比較圖中可以看到，BST 版本中 `findName()` 和 `append()` 所需時間比起使用 hash 的版本是比較低的，如下圖所示
* 由於 `append()` 的部份是直接將 dataset 中的名字串接成 link list，所以花費的時間和縮小 struct 的 `optimized` 版本會是相同的，但若是把建立 BST 所需的時間加入的話，所需時間應該是會上升的，如下圖所示
* 而重點是在於 `findName()` 的部份，證實了利用 BST 在搜尋方面，時間複雜度最佳為 `O(logn)` 最差為 `O(n)` 的特性，是可以有效降低 `findName()` 的所需時間，但因為建立 BST 為 `O(nlogn)` ，所以在整體運行上所需要的時間會是變多的
## 問題討論
* 回答以下問題：本例選用的 dataset (也就是輸入電話簿的姓名) 是否存在問題？
1. 有代表性嗎？跟真實英文姓氏差異大嗎？
* 從 `dictionary/words.txt` 中可以看到有人的姓名入下所示：
```
aaaa
aaaaa
aaaaaa
aaaaaaa
aaaaaaaa
aaaaaaaah
aaaaaaauugh
aaaaaagh
aaaaaahhhhh
aaaaaaugh
aaaaagh
aaaaah
```
* 很明顯的，正常來說，不會有這種由一個字母重複出現的取名方式，就算他父母很想讓他在學校永遠都當一號，而取了 `aaaa` 這樣的名字，但我想這也是不太可能的事情，因此我認為 dataset 中許多筆資料的和真實狀況是相差許多的，但如果這些資料是取自於網路上的 id 或是帳號暱稱，那麼就相對的就比較合理
* 再來是關於每筆資料都不同這點，光是一個 50 人的班級中，都很有可能出現兩個或以上名字一樣的人了，在這麼多筆資料中，每筆資料卻是不重複的，這種情況應該不太可能，當然因為 phonebook 的作業是老師經過簡化過後的情況，所以才會如此，不然一般來說必定會有重複的姓名出現，而且重複的情況應該會不少
2. 資料難道「數大就是美」嗎？
* 我認為不是，資料量多的時候，勢必需要花費更多資源去處理，但如本此作業的 dataset 所示，資料量雖大，但卻不符合實際情形，那麼還不如資料量較少，但每筆資料卻是符合真實狀況，是具有可信度的資料來的實際，因此我認為數大就是美的概念，是要在達成資料是有用的條件下，才會成立
4. 如果我們要建立符合真實電話簿情境的輸入，該怎麼作？
* 可以從外國的網站參考，如：
- [babycenter](https://www.babycenter.com/top-baby-names-2017.htm) : 有統計美國一年新生兒姓名的排行，以及常見的外國取名，可以作為參考
- [Data.gov](https://catalog.data.gov/dataset?tags=baby-names) : 可以從美國的政府資料開放平台中取得歷年新生兒姓名的資料，而且資料量滿龐大的
* 自己蒐集：
- 利用 facebook 舉辦抽獎，須填表單以及真實姓名才有資格抽獎，相信以 facebook 用戶愛抽獎的特性，一定可以蒐集到許多資料，但可能要加註聲明表示會利用蒐集的資料做研究，不然可能有法律上的問題，不過一般人看到使用者規約通常都會不在意的拉到最下方案我同意，所以應該不至於影響提供資料參加抽獎的意願
## 參考資料
* [phonebook 作業解說影片](https://www.youtube.com/watch?v=ZICRLKf_bVw)
* [ryanpatiency: 給初學者/無頭緒的建議](https://hackmd.io/EYEwzALATAhgpmAtMMMCciIEYDsGYAMBAHIgKzYwBscAZlMbRMEA?view)
* [ryanwang522](https://hackmd.io/s/Sk-qaWiYl)
* [演算法筆記](http://www.csie.ntnu.edu.tw/~u91029/Order.html)
## 因為自動飲料機而延畢的那一年
* [讀後心得及啟發](https://hackmd.io/YXnTlwD1Ty2rHv4WcZDHzw)
Sign in with Wallet
Connect another wallet