# 2017q3 Homework2 (prefix-search)
contributed by <`HMKRL`>
### Reviewed by `jcyztw`
* 最近一次 [commit 2d47e0b](https://github.com/HMKRL/prefix-search/commit/2d47e0b35c4ff1392292709502f974101eba6c09)，如同老師在你 GitHub 的留言，有空可以針對 commit message 的內文做修改。看完你的 commit message，我只看到你改了哪些檔案，但是你此次 commit 做了什麼事並沒有寫出來；因為我還沒仔細看你的 code，無法很迅速得知你這次 commit 到底做了什麼，覺得有點美中不足。(P.S. [How to Write a Git Commit Message 中文翻譯在這裡](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)，供你參考)
* 請問你的開發環境為何？是單核心或是多核心的 CPU？我會問這個問題，主要是因為看到你在做 `test_cpy` 和 `test_ref` 的效能分析時，用了 `RDTSC` 指令來幫你達成目的。但是根據以前修課同學的[共筆](https://hackmd.io/s/BJBZn6Q6)及其[相關影片](https://youtu.be/DRkXFjLfaVg)，`RDTSC` 指令在多核心 CPU 的環境上作量測會有問題。所以你才會使用 `chrt` 和 `taskset` 兩個 command 來解決 `RDTSC` 不能在多核心 CPU 量測的限制嗎？
### Reviewed by `amikai`
- 建議先提及理論, 在對應到自己的 code, 報告會更有完整性
- 我找到一個函式 sched_setaffinity(), 可以試試看
- tst_traverse_fn 這邊建議可以在介紹的詳細一點，因為這是很有用的函式, 並且可以舉個
實例
<s>以上是小弟淺見, 如有冒犯請見諒</s>
:::danger
1. 凡事都要怕冒犯，就不要去做了
2. 只要能提升其他同學程度的事，就大膽作
3. 指出他人的弱點，大家才能一同成長
:notes: jserv
:::
## 實作 `REF` 模式
根據程式碼註解：
```c
if (cpy) { /* allocate storage for 's' */
const char *eqdata = strdup(*s);
if (!eqdata)
return NULL;
curr->eqkid = (tst_node *) eqdata;
return (void *) eqdata;
} else { /* save pointer to 's' (allocated elsewhere) */
curr->eqkid = (tst_node *) *s;
return (void *) *s;
}
```
`REF` 模式應該將字串另外儲存，理想情況應該直接採用原始資料儲存的位置，但在這個例子中原始資料是讀檔取得，因此無法直接使用
:::danger
1. 可考慮引入 mmap，詳見 [B07: phonebook-concurrent](https://hackmd.io/s/rkOExTOoe)
2. 承上，引入 mmap 時，需要一併將 Stream I/O (如 `fopen`, `fread`, `fclose`) 替換為低階 I/O (如 `open`, `read`, `close`)
3. 不要忽略檔案操作在整體時間的影響
:notes: jserv
:::
針對這個問題和 [HTYISABUG](https://github.com/HTYISABUG) 討論，我們想到可以將原始資料儲存起來，但若同樣採用 `malloc` 個別分配記憶體空間，則與 `CPY` 版本沒有差異，因此我們決定採用 mempool 儲存原始資料
詳見 [commit d3eb39c](https://github.com/HMKRL/prefix-search/commit/d3eb39c93f66c5a128c5a3e0506017607d60da6f)
實作 mempool 後發現無法正常完成 delete 操作，經 gdb 檢查找到問題在 `tst.c` 中：
```c
if (del) { /* delete instead of insert */
(curr->refcnt)--; /* decrement reference count */
/* chk refcnt, del 's', return NULL on successful del */
- return tst_del_word(root, curr, &stk, 1);
+ return tst_del_word(root, curr, &stk, cpy);
}
```
這裡直接使用1傳入造成 delete word 時錯誤對 mempool 進行 free , 修改為傳入正確的模式變數 `cpy` 即可正常運作
## 效能測試
首先，為兩個不同的 test 檔加入讀取 `--bench` 選項的部份：
```
/* process --bench flag */
int bench_flag = 0;
struct option long_opt[] = {
{"bench", no_argument, &bench_flag, 1},
{0, 0, 0, 0}
};
getopt_long(argc, argv, "", long_opt, NULL);
```
並加入以下計時用程式碼，嘗試計算 `tst_search_prefix` 所需時間
```
for (int i = 0; i < SEARCH_TIMES; ++i) {
fscanf(infp, "%3s", prefix);
t1 = tvgetf();
tst_search_prefix(root, word, sgl, &sidx, LMAX);
t2 = tvgetf();
fprintf(outfp, "%d %.6lf\n", i, t2 - t1);
}
```
但檢視輸出檔後發現由於搜尋所花時間太短，無法有效測量
>> 為何不透過統計模型來分析呢？
>> [name="jserv"][color=red]
>> 此處消耗時間已低於本計時函式精確度，因此數據無法使用
>> [name="HMKRL]
因此引入作業1中曾出現過的方法，利用 [RDTSC](http://x86.renejeschke.de/html/file_module_x86_id_278.html) 計算所消耗的 cpu cycle
```
for (int i = 0; i < SEARCH_TIMES; ++i) {
fscanf(infp, "%3s", prefix);
get_cycles(&timec_high1, &timec_low1);
tst_search_prefix(root, word, sgl, &sidx, LMAX);
get_cycles_end(&timec_high2, &timec_low2);
timec = diff_in_cycles(timec_high1, timec_low1, timec_high2, timec_low2);
fprintf(outfp, "%d %ld\n", i, timec);
}
```
> 你輸入 search 的 prefix 從頭到尾沒變啊
> [name=HTYISABUG][color=black]
結果：
重新設定範圍消除過高資料後（來源應為作業系統其他背景工作）：
>> 搭配使用 [chrt](http://man7.org/linux/man-pages/man1/chrt.1.html)，將排程策略變更為 real-time FIFO，以及用 [taskset](https://linux.die.net/man/1/taskset) 限定在某個/某些處理器上運作程式
>> [name="jserv"][color=red]
>>
使用 `sudo chrt -f 99 taskset -c 0 ./test_cpy --bench` 進行測試
並修改 gnuplot script 改用長條顯示使結果更明顯，得到以下結果：
計算標準差及95%信賴區間
```
CPY:
AVG = 1032.330220
SIGMA = 2273.788154
95%: 1023.575096 - 1041.085344
```
```
REF:
AVG = 998.183646
SIGMA = 1967.461852
95%: 990.608019 - 1005.759274
```
計算標準差及95%信賴區間
```
CPY:
AVG = 34.966300
SIGMA = 2.620935
95%: 34.914930 - 35.017670
```
```
REF:
AVG = 32.950000
SIGMA = 3.629959
95%: 32.878853 - 33.021147
```
其中 `CPY` 模式的 cache-miss 為 24.305%
`REF` 模式則為 19.859%
可見採用連續記憶體空間可以有效降低 cache-miss
:::danger
從隨機事件的觀點，用 poisson distribution 解釋 REF 和 CPY 實作
:notes: jserv
:::
## 觀察 tst.h 和 tst.c
此處對 `tst_node` 進行 forward declaration:
```
/* forward declaration of ternary search tree */
typedef struct tst_node tst_node;
```
這樣做可以帶來的優點：
1. 通過 `typedef` 讓後續程式碼可讀性增加(省略 `struct`)
2. 若修改 `tst_node` 中的實作時，其他使用到 `tst.h` 的原始碼檔案不需要重新編譯，當專案規模增加時能節省許多編譯時間
但使用上有條件限制：若程式碼中需要得知 `sizeof(tst_node)` 即無法使用(例如用到 `malloc` 或將 `tst_node` 用於其他 struct 中)
在 phonebook 中，也能以同樣的方法將 entry 做 forward declaration ，在 opt 和 origin 中在詳細定義，即可共用 `phonebook.c`
## 觀察 tst_traverse_fn
本 function 提供了一個 debug 介面，使用者可以使用自己的函式作為 function pointer 傳入，即可用於除錯/觀察資料結構/效能量測等用途
Sign in with Wallet
Connect another wallet