# 2017q3 Homework2 (prefix-search)
contributed by <`ZixinYang`>
### Reviewed by `zhanyangch`
* 在 [Modify makefile and test_ref.c](https://github.com/ZixinYang/prefix-search/commit/2d9b35f83b604d500deb85e3377d974240760d64) 中實際上加入了 bench 與 gnuplot 的相關功能，但在 commit message 中沒有寫出，若要新增多個功能可以考慮分次 commit，此外 runtime.png bench_cpy.txt 等效能測試的結果不用上傳，可以藉由[修改.gitignore](https://zlargon.gitbooks.io/git-tutorial/content/file/ignore.html) 來忽略這些檔案。
* 有解說 branch prediction，但沒有實際分析 branch prediction 對此程式的影響。
* 有找到逗號對於搜尋功能的影響，應該在多加觀察 cities.txt 的資料格式，找到分辨城市與國家的方法。
## Trie 的介紹
又稱做 prefix tree, 特性是每個節點所有的 child 都有相同的 prefix, 可用來儲存大量字串。
* Standard Trie: 每個節點有 26 個 pointers, 指向 a~z, 每個單字結尾的節點會儲存一個值做為單字的編號。
如下圖:
圖中每個 `end` 的位置皆儲存單字編號
* Ternary Search Tree: 結合 standard trie 與 binary search tree 的特性。 每個節點有3個pointers, 左 child 儲存較小的值, 中間的 child 儲存相同的值, 右 child 儲存較大的值。
如下圖:
## Ternary Search Tree 原理
* 取得 [prefix-search](https://github.com/sysprog21/prefix-search) 程式碼，編譯並測試
```
Commands:
a add word to the tree
f find word in tree
s search words matching prefix
d delete word from the tree
q quit, freeing all data
```
接著 trace code 並討論每個 operation 的執行方法以及複雜度
### Insertion Operation
trace tst_ins_del 函式, 每次增加一個字串, 從 root 開始搜索, 依字串大小往左中右 trace, 若已有重複的字串在 TST 當中, 則 refcnt 加一, 否則需增加新的節點來計錄新的值。 複雜度和 BST 相似, Best-case: O(log n), Worst-case: O(n)
### Find Operation
trace tst_search 函式, 從 root 開始搜索, 直到找到值相等, 且都是 NULL 的時候即找到。
### Search Prefix Operation
trace tst_search_prefix 函式, 從 root 開始搜尋, 每次找齊了 prefix 就呼叫 tst_suggest 把剩下的 child 都走遍, 並都存在一個指標陣列中, 直到搜尋到 NULL 。
### Delete Operation
trace tst_ins_del 函式, 用 insertion operation 搜尋插入點的方式找到目標字串的位置, 並呼叫 tst_del_word, 刪除目標之前會檢查 refcnt 是否為 0, 為 0 就可以刪除, 非 0 則 recnt 繼續保留在 buffer, 同時保留節點。
### Complexity
| |Average-case|Worst-case|
|:-------:|:----------:|:--------:|
|Insertion|O(log n)|O(n)|
|Search|O(log n)|O(n)|
|Delete|O(log n)|O(n)|
若是插入或搜尋一個相對短的字串或是有存在共同 prefix 的字串,時間上會得到好處, 最差的情況是插入或搜尋一個特殊的字串。
## 修改 Makefile
參考 [簡單學 makefile](http://mropengate.blogspot.tw/2015/06/makefile-makefile.html), [跟我一起寫 makefile](http://wiki.ubuntu.org.cn/index.php?title=%E8%B7%9F%E6%88%91%E4%B8%80%E8%B5%B7%E5%86%99Makefile:MakeFile%E4%BB%8B%E7%BB%8D&variant=zh-hant), 以及 [st9007a](https://hackmd.io/s/SkeKQEq3Z#) 同學的共筆
這裡的作業要求是`測試程式碼應該接受 --bench 的執行參數，得以在沒有使用者輸入的前題下，對 tst 程式碼進行效能分析，應涵蓋 cpy 和 ref 兩種途徑 (詳情參閱 tst.h 的程式碼註解)`
所以需要把 --bench 執行參數的判斷寫在 test_cpy.c 及 test_ref.c 當中, 一旦判斷式成立就進行效能評估, 並在 makefile 裡面增加 `bench` 要觸發的指令, 如下：
```
BIN = \
test_cpy \
test_ref
bench: $(BIN)
@for test in $(BIN); do\
./$$test --bench; \
done
```
## 修改 test_ref.c
FIXME 需修改的地方將 CPY 改為傳入 REF, 則 tst_ins_del 接收到 CPY = 0, 直接測試程式。
* quit 程式的時候會發生 `free(): invalid pointer` 的錯誤, 搜尋了一下這個錯誤的原因, 是因為該變數存的記憶體是 stack memory, 不可以 free(), 也就是因為 cpy 版本的會利用 strdup() 重新分配記憶體給 *s, 但 ref 版本是直接存取 *s 到 TST。 在 tst.c 中有一個 tst_free_all 和 tst_free, 推測 tst_free 函式才是 ref 版本的釋放記憶體的方式, 所以更改了以下程式碼:
```clike=
case 'q':
tst_free(root);
return 0;
break;
```
quit 便可以成功執行了。
* search prefix 結果錯誤如下:
```
choice: s
find words matching prefix (at least 1 char): Tai
Tai - searched prefix in 0.000524 sec
suggest[0] : Tai
suggest[1] : Tai
suggest[2] : Tai
suggest[3] : Tai
suggest[4] : Tai
suggest[5] : Tai
suggest[6] : Tai
suggest[7] : Tai
suggest[8] : Tai
suggest[9] : Tai
suggest[10] : Tai
```
重新檢視 tst_ins_del 函式
```clike= if (*p++ == 0) {
void *tst_ins_del(tst_node **root, char *const *s, const int del, const int cpy)
{
...
for (;;) {
...
if (*p++ == 0) {
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;
}
}
pcurr = &(curr->eqkid);
}
}
```
cpy 版本會 strdup() 重新分配記憶體給 *s, 但 ref 版本每個節點會直接指向 word 的起始記憶體位址, 所以最直覺的方法就是 strdup(), 再重新配置記憶體給 p, 如下：
```clike=
p = strdup(word);
tst_ins_del(&root, &p, DEL, REF);
```
更改後 search prefix 結果正常
## search-prefix 的效能評估
y 軸為搜尋時間
x 軸為第幾筆搜尋關鍵字 (15000~20000)
把區間縮小到 15000~16000, 但依然看不出 cpy 與 ref 的效能優劣
> 問題不在「效能優劣」，而是你現在仍沒有做出「實際上不需要 copy 而用 reference 手段降低資料存取的機制」，需要想辦法進一步改善
> [name="jserv"][color=red]
用 `perf stat` 測試效能
```
Performance counter stats for './test_cpy --bench' (100 runs):
2427,5349 branch-misses ( +- 0.01% )
1,4563,3386 cache-misses # 54.203 % of all cache refs ( +- 0.60% )
2,6868,1670 cache-references ( +- 0.03% )
47,1267,5761 instructions # 0.94 insn per cycle ( +- 0.00% )
49,8968,8599 cycles ( +- 0.31% )
1.522736177 seconds time elapsed ( +- 0.37% )
```
```
Performance counter stats for './test_ref --bench' (100 runs):
2518,0124 branch-misses ( +- 0.01% )
2,0967,7296 cache-misses # 62.078 % of all cache refs ( +- 0.33% )
3,3776,6486 cache-references ( +- 0.04% )
55,1926,9877 instructions # 0.81 insn per cycle ( +- 0.00% ) ( +- 0.22% )
67,8715,6960 cycles
2.069019844 seconds time elapsed ( +- 0.27% )
```
* branch-misses: `branch prediction` 是利用歷史資訊, 預測下一個指令會走哪一個分支, 參考以下兩篇思考可能造成預測錯誤的原因。 推測是因為利用 strdup() 重新配置記憶體, 造成 branch predictor 缺乏有跡可循的歷史紀錄去預測未來分支走向。
* [Measuring Branch Prediction Accuracy Using Linux Perf Tools](http://www.bnikolic.co.uk/blog/hpc-perf-branchprediction.html)
* [Fast and slow if-statements: branch prediction in modern processors](http://igoro.com/archive/fast-and-slow-if-statements-branch-prediction-in-modern-processors/)
* cache-misses: 因為每次新增字串, 都用了 strdup() 重新配置記憶體, 這對 cache spatial locality 的特性有很大的影響。
:::danger
1. 用現代處理器的行為解釋上述效能落差
2. 用 `perf` 的進階選項，如 instruction count 和 branch prediction 去分析程式運作
3. 設計更長期涵蓋更多的測試方法
:notes: jserv
:::
> 謝謝老師建議, 已嘗試用 branch prediction 分析
> [name=ZixinYang]
## 針對各國城市 search prefix 的缺陷
* 建 TST 的過程中, 是整個字串輸入, 包含逗號, 所以會出現以下情況
```
choice: f
find word in tree: Shanghai
Shanghai not found.
```
```
choice: f
find word in tree: Shanghai,
found Shanghai, in 0.000000 sec.
```
所以我在讀檔的地方增加一行程式碼, 慮掉逗號
```clike=
if ( word[strlen(word)-1] == ',') word[strlen(word)-1] = '\0';
```
更改後正確
```
choice: f
find word in tree: Shanghai
found Shanghai in 0.000000 sec.
```
* 無法辨別 TST 中的單字是指城市還是國家, 且城市與國家的關係應整合在一起, 擴增搜尋功能。
## 詳細觀察 tst.h 和 tst.c 為何要 forward declaration, 分離介面和實作有何好處, 如何運用在 phonebook
參考 [Function Pointer](https://openhome.cc/Gossip/CppGossip/FunctionPointer.html), [Forward Declaration](http://ascii-iicsa.blogspot.tw/2010/12/forward-declaration.html)
```
/* forward declaration of ternary search tree */
typedef struct tst_node tst_node;
```
將 tst_node 的定義寫在 tst.c, 而另外在 tst.h 當中做 forward declaration, 這樣的好處是, 當修改 tst_node 的結構時，其他 include tst.h 的檔案不需要重新編譯， 可以節省編譯時間。
應用在 `phonebook` 當中, 一樣可以將 ENTRY 各自定義在 orig.c 和 opt.c 當中, 然後建立一個共用的 phonebook.h 檔, 在其中 forward declaration entry。
## 研究程式碼的 tst_traverse_fn 及 callback function 的程式開發技巧/模式
參考 [Callback](https://en.wikipedia.org/wiki/Callback_(computer_programming))
callback 的概念就是傳回某函式的指標, 呼叫者就可以透過該指標執行函式
以程式碼中的 tst_trverse_fn 為例, 可以利用這個函式來 debug, 像是印出每個節點的存的資料。
```clike=
void print_word(const void *node, void *data) {
printf("%s\n", tst_get_string(node));
}
void tst_traverse_fn(const tst_node *p,
void(fn)(const void *, void *),
void *data)
{
if (!p)
return;
tst_traverse_fn(p->lokid, fn, data);
if (p->key)
tst_traverse_fn(p->eqkid, fn, data);
else
fn(p, data);
tst_traverse_fn(p->hikid, fn, data);
}
```
然後我們在主程式呼叫 tst_traverse_fn
```clike=
tst_traverse_fn(root, print_word, word);
```
就可以走遍每個節點並印出如下的資料:
> 這動作不叫 "trace"，請查詢 English-English dictionary，以理解具體意義
> [name="jserv"][color=red]
> 好的, 已修正。
> trace: to follow the path or line of sth.
> [name=ZixinYang]
```
Trooz
Tropea
Trophy
Trosa
Troskami
Trosly-Breuil
Trosna
Trossin
Trossingen
Trostberg
```
## 參考資料
* [Ternary Search Tree](http://www.geeksforgeeks.org/ternary-search-tree/)
* [Prefix trees: Comparison between Trie, Ternary Search Tree and Radix Tree](https://oscarforner.com/2016/02/26/Prefix_trees__Comparison_between_Trie__Ternary_Search_Tree_and_Radix_Tree)
* [free(): invalid pointer](https://stackoverflow.com/questions/20297524/c-free-invalid-pointer)
* [malloc() & free()](https://stackoverflow.com/questions/2688377/why-exactly-should-i-not-call-free-on-variables-not-allocated-by-malloc)
Sign in with Wallet
Connect another wallet