# 2018q1 Homework1 (phonebook)
contributed by <`afcidk`>
### Reviewed by `ryanpatiency`
* Could you explain under which condition trie will be faster than hash ?
### Reviewed by `LinYunWen`
* 後面的 commit message 寫得很不錯，甚至還有畫些圖，不過有兩個 commit message 的 title 一樣，雖然內文不同，但是會有點奇怪 ([commit 29f0572](https://github.com/afcidk/phonebook/commit/29f0572097f0fc84e38b5bd62a601ad4284faf97)、[commit ebca2de](https://github.com/afcidk/phonebook/commit/ebca2be088e6041ef6fced91eb454772ca7f9f2e))
* 最後的 trie 可以多說明一些 cache miss 上的比較或解釋，多偏向只有時間上的看法
>對應的程式碼修改應一併傳到 github 上
>[color=red][name=課程助教]
## 開發環境
```
afcidk@Lubuntu1:~$ lscpu
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: 1
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 94
Model name: Intel(R) Core(TM) i5-6400 CPU @ 2.70GHz
Stepping: 3
CPU MHz: 2700.000
CPU max MHz: 3300.0000
CPU min MHz: 800.0000
BogoMIPS: 5424.00
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 6144K
NUMA node0 CPU(s): 0-3
```
## 目標
* 理解 cache 是什麼
* 優化程式碼
* [減少 entry size](#減少-entry-size)
* [hash function](#嘗試3-使用hash-function)
* [trie](#嘗試4-使用-trie-資料結構)
* fuzzy search
>中英文字間請記得以空白隔開
>[color=red][name=課程助教]
## TODO
* binary search
* fuzzy search
* memory pool
## 理解 cache 是什麼
因為 CPU 的速度太快了，而主記憶體( DRAM )和 CPU 的速度也不是只有差一點點。<s>為了避免整體速度被拖延到，產生了 cache 的技術。</s> cache 的存在就是為了解決 DRAM 和 CPU 的處理速度差距而產生的瓶頸。為什麼這樣說呢？
CPU 處理的速度很快，但是因為 DRAM 速度比較慢，所以會讓 CPU 有空閒的時間。想要讓 CPU 忙一點，我們勢必要讓輸入趕上處理速度，在硬體的部份就產生了快一點的 cache( SRAM ) 來當中介。可是又有新問題了，cache 裡面的資料要放什麼呢？
cache 裡面的資料遵守 *Locality of Reference*
*Locality of Reference* 代表的是 cache 在儲存資料時會選擇
* 頻繁被要求的資料 ( temporal locality )
* 現在使用中的資料附近的資料 ( spatial locality )
這讓 CPU 在處理的時候可以優先從 cache 裡面選擇這些**比較有可能**會用到的資料，進而提昇效能
:::danger
上面這句話不精確，請翻閱計算機組織的教材，重新用自己的認知表達過。
:notes: jserv
:::
> 已重新表達！
cache( SRAM ) 比主記憶體( DRAM )還要快，可以用來銜接 CPU 和 DRAM 之間的訊息傳輸。SRAM 是由電晶體構成，DRAM 是由電容構成，充放電的速度導致在讀寫速度上 SRAM > DRAM。
:::danger
memory 一般翻譯為「記憶體」，是通用詞彙，而 cache 是一種 memory，你在表達時，應該區分 cache 和 DRAM 一類的「主記憶體」
:notes: jserv
:::
> 已更改敘述！
在[关于CPU Cache -- 程序猿需要知道的那些事](http://cenalulu.github.io/linux/all-about-cpu-cache/)介紹完什麼是 cache line 後，他有提出兩段相差不大的C語言程式碼，但是執行速度卻有很大的落差。
```clike
//比較快
int num = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
//code
arr[i][j] = num++;
}
}
```
```clike
//比較慢
int num = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
//code
arr[j][i] = num++;
}
}
```
<s>根據自己對於 cache line 的理解</s>，第二份程式碼比較慢的原因是因為它每次要被assign的位置都不是相鄰的，有比較大的機會讓需要操作到的記憶體空間不在 cache 上，導致 cache miss 比較大
:::warning
「根據自己對於 ... 的理解」這種話就不需要在共筆提及，這裡本來就是你的理解。你應該要精確地描述 locality 的影響。
:notes: jserv
:::
>關鍵字：row major, column major
>[color=red][name=課程助教]
在 C 語言中，陣列的儲存方式採用 row major 的方式，再回頭看看上述的例子
假設陣列大小( n )是 3 x 3
第一個版本儲存的資料按照順序會是 0 1 2 3 4 5 6 7 8
```=
0 _ _ _ _ _ _ _ _
0 1 _ _ _ _ _ _ _
0 1 2 _ _ _ _ _ _
0 1 2 3 _ _ _ _ _
0 1 2 3 4 _ _ _ _
0 1 2 3 4 5 _ _ _
0 1 2 3 4 5 6 _ _
0 1 2 3 4 5 6 7 _
0 1 2 3 4 5 6 7 8
```
第二個版本儲存的資料按照順序會是 0 3 6 1 4 7 2 5 8
```=
0 _ _ _ _ _ _ _ _
0 _ _ 1 _ _ _ _ _
0 _ _ 1 _ _ 2 _ _
0 3 _ 1 _ _ 2 _ _
0 3 _ 1 4 _ 2 _ _
0 3 _ 1 4 _ 2 5 _
0 3 6 1 4 _ 2 5 _
0 3 6 1 4 7 2 5 _
0 3 6 1 4 7 2 5 8
```
可以發現第一個版本的數字是一個一個放上去的，而第二個版本的數字是跳著放上去的
（從 0 依序放到 8 ）
實際執行看看 cache 的變化大不大 (使用 n = 3 )
理論上比較快的程式碼
```
793 cache-misses # 2.302 % of all cache refs ( +- 16.37% )
34,459 cache-references ( +- 0.46% )
```
理論上比較慢的程式碼
```
819 cache-misses # 2.387 % of all cache refs ( +- 15.70% )
34,307 cache-references ( +- 0.53% )
```
在陣列大小不大時影響似乎看不太出來，因為 cache 都還放得下，但是如果數據量大一點呢？
可以使用指令`lshw`( list hardware )查看電腦的 cache 大小
```
*-cache:0
description: L1 cache
physical id: 3e
slot: L1 Cache
size: 128KiB
capacity: 128KiB
capabilities: synchronous internal write-back data
configuration: level=1
```
$128*2^{10} = 2^{17}$
$2^{17}/2^2 = 2^{15} = 32768$
這次讓 n = 3000，再比對一次 cache 的變化
> 為什麼選 3000 的原因是要讓 cache 小於陣列的大小
> $3000*3000>32768$
```
751,144 cache-misses # 87.156 % of all cache refs ( +- 0.07% )
861,836 cache-references ( +- 0.06% )
```
```
1,700,256 cache-misses # 5.942 % of all cache refs ( +- 0.13% )
28,616,391 cache-references ( +- 0.21% )
```
這次 cache-miss 就增加了兩倍以上，cache-reference 也跟著增加到三倍以上
## 原本 performance
entry size 為 136 bytes
```
Performance counter stats for './phonebook_orig' (100 runs):
453,7987 cache-misses # 92.087 % of all cache refs ( +- 0.07% )
492,7930 cache-references ( +- 0.05% )
2,7522,5199 instructions # 1.41 insn per cycle ( +- 0.02% )
1,9559,6852 cycles ( +- 0.07% )
0.062733108 seconds time elapsed ( +- 0.48% )
```
## 減少 entry size
要減少 cache miss 的其中一個方法是讓 entry size 小一點，這樣 cache 裡面可以放的資料就比較多
原本的 entry size 是 136 bytes，也許可以<del>試著讓裡面的資料壓縮一點</del>，或是把某部份只是用來紀錄的資料搬到別的地方
:::danger
用語要==精確==！搬動資料不算「壓縮」，理工人如果連說話都不精確，要怎麼說服他人呢？
:notes: jserv
:::
> 謝謝老師的提醒！其實我最初的想法是要陳述可以壓縮空間或是搬動資料兩件事的，但是後來覺得我不應該在這方面要求 phonebook 的其他資料大小一定要壓縮成怎樣。
> 已更改敘述方式！ [name=afcidk][color=blue]
### 嘗試1 只留 lastname
觀察`main.c`後發現 append 和 findName 這兩個函式都只有用到 lastname，先把`__PHONE_BOOK_ENTRY `其他的變數都拿掉試試看
編譯完後執行：`$ make cache-test`
修改後的 entry size 為 24 bytes
```
Performance counter stats for './phonebook_opt' (100 runs):
100,8296 cache-misses # 62.527 % of all cache refs ( +- 0.42% )
161,2565 cache-references ( +- 0.12% )
2,5082,2518 instructions # 2.06 insn per cycle ( +- 0.02% )
1,2185,8684 cycles ( +- 0.10% )
0.039152981 seconds time elapsed ( +- 0.14% )
```
發現 cache-miss 和原本的差了 4 倍左右，時間也差了快一倍。但是 phone book 顯然不會只有 lastname 而已，其他的資料應該也要放上去，查詢到正確的 lastname 時才可以顯示
### 嘗試2 entry 多加一個 pointer 指向其他資料存放位置
增加了一個 structure ，因為不會參與到查詢，所以把它額外放在別的地方，並用一個指標存取記憶體位址
```clike
//size of entry: 32 bytes
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
struct __PHONE_BOOK_ENTRY *pNext;
struct __OTHER_PHONE_BOOK_DATA *pData;
} entry;
```
```clike
typedef struct __OTHER_PHONE_BOOK_DATA {
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];
} phonebookData;
```
編譯完後執行：`make cache-test`
```
Performance counter stats for './phonebook_opt' (100 runs):
148,4340 cache-misses # 66.452 % of all cache refs ( +- 0.39% )
223,3716 cache-references ( +- 0.14% )
2,5438,6330 instructions # 1.97 insn per cycle ( +- 0.02% )
1,2896,4063 cycles ( +- 0.09% )
0.042576904 seconds time elapsed ( +- 0.28% )
```
發現效能雖然比只留 lastname 差了一點，但是和優化前比較 entry size 仍然大幅度降低，所以整體的效能還是有提高，cache-miss 也有減少
後來發現忘記在 append 時 malloc 空間給`pData`，加上去後發現效能大幅度的降低了，甚至比沒優化前還要低
看起來應該是 malloc 惹的禍，可是更改`append()`竟然也會影響到`findName()`
為什麼會這樣要再想一下
:::danger
你需要證明上述推論，請試著撰寫更多程式來釐清 `malloc()` 的影響
:notes: jserv
:::
> 原本以為是`malloc()`花費太多時間，沒想到是 cache-miss 導致效能變差
首先，比對程式碼的 cache-miss 狀況
分別是刪除`e->pData = (phonebookData *) malloc(sizeof(phonebookData));`和沒有刪除的版本
刪除的版本 (沒有配置空間)
```
1,528,953 cache-misses # 68.037 % of all cache refs ( +- 0.29% )
2,247,223 cache-references ( +- 0.21% )
260,220,582 instructions # 1.97 insn per cycle ( +- 0.02% )
131,995,699 cycles ( +- 0.08% )
0.049236369 seconds time elapsed ( +- 0.49% )
```
沒刪除的版本 (有配置空間)
```
5,855,719 cache-misses # 95.576 % of all cache refs ( +- 0.09% )
6,126,743 cache-references ( +- 0.08% )
371,742,089 instructions # 1.37 insn per cycle ( +- 0.01% )
271,899,335 cycles ( +- 0.21% )
0.090920051 seconds time elapsed ( +- 0.49% )
```
發現 cache-miss 差了將近四倍，再用`perf top`計算出哪個地方耗費的時間最多
```
26.40% phonebook_opt [.] main
14.22% libc-2.26.so [.] _int_malloc
9.03% libc-2.26.so [.] __strcasecmp_l_avx
8.83% libc-2.26.so [.] _IO_fgets
```
```
24.60% libc-2.26.so [.] __strcasecmp_l_avx
14.54% phonebook_opt [.] main
11.19% libc-2.26.so [.] _int_malloc
4.14% phonebook_opt [.] findName
```
變化最大的是`strcasecmp()`，代表有沒有配置空間對`strcasecmp()`有很大的影響
因此，就算把不是查詢用的資料移到別的地方，在每次配置空間時仍會讓 cache-miss 提高，再加上每次呼叫`malloc()`的時間，整體效能會比沒有搬動資料還要差。
但是如果不需要事先配置好位置給額外的資料，而是需要填入資料時再配置空間，仍然可以提昇部份效能。
## 嘗試3 使用hash function
使用類似 Rabin-Karp algorithm 的 rolling hash 方法，因為每個字串的每個字元都會計算到，所以在`append()`花費的時間比較多。使用質數 40009 作為 hashTable
一開始 hashTable 想要建到 150000 附近，但是因為`main.c`是共用的， hashTable 太大會讓原本的`phonebook_orig`無法執行。
後來參考[陳冠廷同學](https://hackmd.io/s/r1qMdqji-#fn1)的筆記，發現以數據量為 300000 來說，假設資料平均分佈， 300000/150000 = 2 ，而 300000/40000 = 7.5 ，花費在`findName()`的時間只有極微小的差距。
:::warning
不要寫「這位同學」，人家有名字 (至少有 GitHub 帳號)，你應該清楚提及
:notes: jserv
:::
> 已補上！
雖然說查詢一個 lastName 的時間已經降到 1e-6 以下，但是查詢量低的時候其實沒有什麼差別，反倒是`append()`和原本的`phonebook_orig`相比，效能相差了 4 倍以上，後面應該要找一些 hash function 來比對看看
:::warning
用 perf top/stat 找出效能瓶頸再來分析
:notes: jserv
:::
> 又腦補了...QQ 直覺就認為是 hash function 的問題，要看數據說話！
使用`perf top`查看效能瓶頸，得到以下結果
```
48.68% libc-2.26.so [.] __strncmp_sse42
33.80% phonebook_hash [.] hashFunc
4.48% phonebook_hash [.] main
3.65% phonebook_hash [.] append
1.91% libc-2.26.so [.] _int_malloc
1.53% libc-2.26.so [.] _IO_fgets
1.48% libc-2.26.so [.] __strncpy_sse2_unaligned
1.29% libc-2.26.so [.] malloc
```
發現`append()`裡面處理 hash collision 的字串比對佔用最多的時間，其次是產生 hash value
> 後來又看了一下程式碼發現當初想錯了，處理 hash collision 不用比對字串，直接把新的資料放到 linked list 的尾端就好了
更正後又跑了一次`perf top`
```
61.06% phonebook_hash [.] hashFunc
8.73% phonebook_hash [.] append
6.06% phonebook_hash [.] main
4.56% libc-2.26.so [.] _int_malloc
3.39% libc-2.26.so [.] __strlen_avx2
```
發現先前錯誤的程式碼中，`append()`裡的`strcmp()`幾乎佔據了總時間的一半。改善過後效能提高了，瓶頸也如同預期的一樣卡在生成 hashValue
再來我參考[這篇文章](https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed)使用 djb2 作為 hash function，其餘程式碼沒有變動，執行`make plot`後產生的效能比對圖如下
可以發現`append()`的效能提昇了不少，雖然和未優化前的版本相比仍然降低一些，但是透過 hash function 讓查詢資料時的時間大幅縮短
使用`perf top`指令查看，發現 hash function 佔用的時間縮短許多
```
24.82% phonebook_hash [.] append
19.83% phonebook_hash [.] main
13.92% phonebook_hash [.] hashFunc
8.33% libc-2.26.so [.] _int_malloc
```
這讓我想到一些問題：
* 原本使用 rolling hash 當 hash function ，效能低落是不是因為`hashFunc()`沒有寫好？
* 這個版本我一樣把不會用來查詢的資料搬到另外一個 structure 以減少 entry size ，但是沒有事先給予這些資料空間來儲存。如果和上面的作法一樣事先配置空間給這些資料，`findName()`會不會像`phonebook_opt`實做時一樣效能降低？也許可以從這裡發現什麼東西
對於第二個問題，我做了兩個變動來比對效能
* 讓 entry size 恢復成 136 bytes
* 每次執行`append()`時順便配置空間給未用來查詢的資料
### 使用 dbj2 hash function，維持 entry size 為 136 bytes
```
Performance counter stats for './phonebook_hash' (100 runs):
4,068,228 cache-misses # 69.258 % of all cache refs ( +- 0.06% )
5,874,013 cache-references ( +- 0.06% )
300,915,071 instructions # 1.16 insn per cycle ( +- 0.03% )
259,404,732 cycles ( +- 0.05% )
```
```
28.00% phonebook_hash [.] append
13.01% phonebook_hash [.] hashFunc
12.86% phonebook_hash [.] main
5.29% libc-2.26.so [.] _int_malloc
```
發現`append()`時間變長了
### 使用 dbj2 hash function，每次 append 時配置空間給未用來查詢的資料
```
Performance counter stats for './phonebook_hash' (100 runs):
3,954,543 cache-misses # 66.471 % of all cache refs ( +- 0.19% )
5,949,307 cache-references ( +- 0.17% )
384,800,899 instructions # 1.43 insn per cycle ( +- 0.02% )
268,910,185 cycles ( +- 0.08% )
```
```
24.67% phonebook_hash [.] append
13.83% phonebook_hash [.] main
9.63% libc-2.26.so [.] _int_malloc
8.22% phonebook_hash [.] hashFunc
```
比對兩張圖的 hash 部份，雖然花費的時間相差不大，但是由`perf stat/top`可以看出這應該是 cache-miss 和 malloc 花費的時間剛好互相彌補而已，兩個應該沒有直接關係。
## 嘗試4 使用 trie 資料結構
實做前預想可能得到的結果是
* entry size 大幅度增加 -> cache-miss 提高 -> `append()`花費時間較多
* `findName()` 時間大幅度縮短，在找 lastName 時複雜度為 O(n)，n 是 lastName 的字元個數
* 因為想到可能比較不出來 hash 和 trie 在`findName()`的表現，所以會提昇查詢次數
假設 lastName 只有大小寫英文字母，如果有非英文字母以外字元出現會略過
```ctype
typedef struct __PHONE_BOOK_ENTRY {
struct __PHONE_BOOK_ENTRY *nch[52]; //A-Z a-z 共52字母
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];
} entry;
```
這代表這個方式只適用在英文上，中文可能不行（字太多）。不過如果替換成注音符號或是羅馬拼音應該是可行的
`append()`和`findName()`很相似，就是把要查詢/加入的字串一個字元一個字元找下去
節錄`append()`部份程式碼
```cytpe
while (c = *lastName++) {
int ind;
if (islower(c)) ind = c-'a'+26;
else if (isupper(c)) ind = c-'A';
else printf("invalid name");
if (iter->nch[ind] == NULL) {
iter->nch[ind] = (entry *) malloc(sizeof(entry));
}
iter = iter->nch[ind];
}
```
這個方法 entry size 為 528 bytes，效能比對如下
發現在查詢量大的時候 hash 和 trie 佔了很大的優勢，畢竟`append()`只要做一次，而`findName()`會依使用次數而增加
* 缺點
太佔空間，無法負荷太多資料
`append()`會花費較多時間
* 優點
速度快，<s>**某些情況下會比 hash 快**</s>
> 後來發現並不是會比 hash 還要快，而是查詢的速度會浮動，為什麼會造成這種結果還要再找找看
## 參考資料
* [作業解說影片](https://www.youtube.com/watch?v=ZICRLKf_bVw)
* [dram、flash貴到炸，你還搞不懂記憶體的差異嗎？](https://hellolynn.hpd.io/2017/05/06/dram%E3%80%81flash%E8%B2%B4%E5%88%B0%E7%82%B8%EF%BC%8C%E4%BD%A0%E9%82%84%E6%90%9E%E4%B8%8D%E6%87%82%E8%A8%98%E6%86%B6%E9%AB%94%E7%9A%84%E5%B7%AE%E7%95%B0%E5%97%8E%EF%BC%9F/)
* [Which hashing algorithm is best for uniqueness and speed?](https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed)
## [心得與啟發](https://hackmd.io/s/HkP3eEzFG#)<因為自動飲料機而延畢的那一年>
Sign in with Wallet
Connect another wallet