# 2017q3 Homework2 (prefix-search)
###### tags: `sysprog2017` `dev_record`
contributed by <`HTYISABUG`>
### Reviewed by `amikai`
- [91a32d](https://github.com/HTYISABUG/prefix-search/commit/91a32dcc4cb79012b268772488add231e73acc3e) 這個 commit 裡的
```
test._ref.c:
Add a mempool to store data
tst.c:
Don't free the data in leaf
```
建議用陳述的方式講一下前因後果, 其實大概懂 Don't free the data in leaf, 但是要去追 code 才知道再做什麼, 應該在 commit message 多給一點資訊.
- 可以將 cache line 的大小去調整資料結構
<s>以上是小弟淺見, 如有冒犯請見諒</s>
:::danger
1. 凡事都要怕冒犯,就不要去做了
2. 只要能提升其他同學程度的事,就大膽作
3. 指出他人的弱點,大家才能一同成長
:notes: jserv
:::
---
<!--
## 預期目標
* [x] 學習 ternary search tree 作為 auto-complete 和 prefix search 的實作機制
* [ ] 延續 phonebook 的基礎工作,引入 ternary search tree 讓電話簿程式得以更符合人性
* [ ] 配合 Week3 進度,思考針對現代處理器特性的高效能程式設計議題
* [x] 設計效能評比 (benchmark) 的程式框架
* [x] 學習 GNU make 的進階技巧
* [ ] 學習物件導向程式開發思維
-->
---
## 下載並測試
下載並測試程式碼, 經確認後程式可執行且輸出正常
程式共有兩版, `test_cpy.c` & `test_ref.c`
Diff 兩版只有註解差異
---
## 修改 test_ref.c
嘗試照註解修改程式碼, 先查詢 `tst.h` 註解
先簡單的把程式中的 `CPY` 替換成 `REF`
----
### 執行結果
```shell
suggest[0] : Tain
suggest[1] : Tain
suggest[2] : Tain
suggest[3] : Tain
suggest[4] : Tain
*** Error in `./test_ref':double free or corruption (out): 0x00007fff16197340 ***
```
Search 時只搜的到輸入的字串本身
Quit 時會回報 error message
>> 調整用語,儘量清楚明暸。「噴出」錯誤的用法不明確
>> [name="jserv"][color=red]
----
### 解決方案
先觀察了 `test_ref.c` 中負責釋放記憶體的部份, 發現是呼叫了 `tst.h` 中的 `tst_free_all`
這個函式在註解中有注明是 data storage **internal**, 推斷為 `CPY` 使用
另外有 `tst_free` 在同一份 header 中, 注明 data storage **external**, 應該就是 `REF` 使用
將 `tst_free_all` 更換為 `tst_free` 後, 在 quit 時就正常結束了
```c=
case 'q':
/*tst_free_all(root);*/
tst_free(root);
return 0;
break;
```
再來要解決 search 出錯的問題
:::info
在閱讀程式碼的途中, 發現 ternary tree 的末端明明 type 是 (tst_node *)
實際上儲存的東西是一個字串, 之前還真沒想過可以這樣安插字串進 tree 之中!
:::
> 善用 GDB 觀察記憶體,你會感受到更多資料結構和底層機制的關聯
> [name="jserv"][color=red]
找了一兩個小時, 終於在使用的時候找到了 search 的錯誤
```shell=
(gdb) p sgl
$1 = {0x7fffffffdac0 "Tain" <repeats 12 times>, 0x0 <repeats 1012 times>}
```
這些輸出的字串, 通通是指向同一個位置, 這說明那些 leaf 的末端都是指向同一個位址......?
Sgl 內的字串全是以指標形式在 `tst_suggest` 裡賦值的
如果這些末端都指向同一位址, 那說明在 insert 階段應該已經出錯了
終於找到確切的錯誤位置了
```c=
/* 這是 tst_ins_del 中將字串存進 leaf 的 code */
curr->eqkid = (tst_node *) *s;
/* 這是 main 中呼叫 tst_ins_del 的部份 */
char word[WRDMAX] = "";
/* 省略 */
switch (...) {
char *p = word;
tst_ins_del(&root, &p, INS, REF)
}
```
從這幾行 code 可以看出 s 是一個指向 p 的指標, 而 p 又是指向 word 的指標
在 `tst_ins_del` 中 s 完全沒有被更改, 也就是說最後被存起來的全部都是指向 **word** 的指標
在輸入 search 時是最後更改 word 的時間點, 所以最終輸出會全部都是輸入的字串!
現在多了一個問題, `CPY` 版本會 allocated 一塊記憶體用於儲存資料
而 `REF` 版本看起來是想只藉由指標導向資料已經存在的空間
但如果不分配一塊空間儲存, 新資料進來一定會洗掉原本的資料
這又跟 `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;
}
```
> 也可變更 tst.[ch] 的介面/實作,調整記憶體處理模型。
> 程式碼給你是讓你實驗用的
> [name="jserv"][color=red]
針對這問題跟 [HMKRL](https://github.com/HMKRL/) 討論
我們看完程式碼後得到的結論是
讀取自文件中的資料在被洗掉以前完全沒有被儲存起來
既然沒有被儲存起來那就不可能被讀取, 因此必然需要分配記憶體用於儲存
考慮到多次 allocate 會導致記憶體破碎, cache-misses 大量產生
應用之前在 phonebook 曾經用過的 **mempool** 技巧使資料連續儲存
然後 leaf 儲存的指標將會指向 pool 中的某個位址
因應資料儲存方式的變動, tst.c 也隨之改變
程式更動請見 [91a32d](https://github.com/HTYISABUG/prefix-search/commit/91a32dcc4cb79012b268772488add231e73acc3e)
> 不要濫用 `:::info` 一類的標注,你應該清楚闡述前因後果,把技術文件寫好
> [name="jserv"][color=red]
> 呃, 我不太懂老師的意思
> 我想說能用色塊強調問題點跟解決方法就用了
> [name="HTYISABUG]
> 技術文件強調「結構」,認真想這件事,我們要寫出專業的文件,不是流水帳。
> [name="jserv"][color=red]
:::info
* 修正 `tst.c` 的 `tst_del_word`
* 沒注意到參數就有 `freeword` 而直接將釋放記憶體的步驟清除了, 這樣將會導致 memory leak
* 同時將 `tst_ins_del` 中呼叫 `tst_del_word` 時的參數修正
* 在 [HMKRL](https://github.com/HMKRL/) 提醒後修正
* 程式更動請見 [1a4d3b](https://github.com/HTYISABUG/prefix-search/commit/1a4d3b29bf95aabd915a9e0fc70975366d2266e6)
:::
---
## Benchmark
為了接受 `--bench` 參數, 加入 `getopt_long`
為了更精確的時間數值, 引入 `clz-test` 的組語計算 cycles
----
### REF
#### Insert
將每筆資料的 insert 時間印出
![](https://i.imgur.com/wsVXufA.png)
為了確認資料長度對 insert 的影響, 先確認資料長度的分佈
> 下圖標題與內容不匹配,應修正
> [name="jserv"][color=red]
![](https://i.imgur.com/IfUTyBD.png)
可見資料大多集中在 10 字以下
定義長度 10+ 為長字串, 以不同顏色在時間圖中標出
參考老師在 [HMKRL 筆記](https://hackmd.io/s/BkdddNs3-)中所留有關排程與限定處理器的建議重新執行
![](https://i.imgur.com/kPSDK7l.png)
> 「其他人」在哪?為何不列出訊息的源頭呢?養成好習慣,日後才能追蹤和反思
> [name="jserv"][color=red]
從圖中可知資料的長度跟 insert 時間並無太大關係
大部份資料都 分佈在 20000 cycles 以下
將 20000+ cycles 的資料取出觀察分佈
![](https://i.imgur.com/gCg40by.png)
分佈的趨勢跟整體的分佈趨勢大致相符
說明不論資料長度如何, 都有可能出現高耗時的情況
這樣看來, 這些高耗時的的情況可以視為 jitter
```shell=
average cycles: 1086.009093 cycles
standard deviation: 1695.082006
confidence interval (95%): (1079.482252, 1092.535933)
```
----
#### Prefix Search
將每筆資料 prefix search 的時間印出
![](https://i.imgur.com/cBtuT0W.png)
700000+ 次搜索太多, 結果什麼都看不清楚
換個角度, 從被搜到的資料量跟時間的關係觀察
![](https://i.imgur.com/y7f0If6.png)
雖然還是很雜亂, 但已經隱約可以看出時間分佈是照所搜到的資料量呈區段分佈的
以每 50 為一區段計算平均時間
![](https://i.imgur.com/HNpBsnC.png)
可確認搜索時間跟搜得資料量成正比
```shell=
average cycles: 77646.828332 cycles
standard deviation: 180620.276540
confidence interval (95%): (77227.247323, 78066.409341)
```
----
### CPY
採用跟 `REF` 同樣的方法分析
#### Insert
```shell=
average cycles: 1105.770331 cycles
standard deviation: 1520.471492
confidence interval (95%): (1099.915820, 1111.624841)
```
----
#### Prefix Search
```shell=
average cycles: 65042.560313 cycles
standard deviation: 149953.627612
confidence interval (95%): (64694.217948, 65390.902679)
```
----
### 結果比較
![](https://i.imgur.com/Nyv2dZm.png)
| |ref |cpy |
|-------------------------|-------------|--------------|
|average cycles |1086.009093 |1105.770331 |
|confidence interval (95%)|$\pm 6.52684$|$\pm 5.854511$|
Insert 的部份, `REF` 跟 `CPY` 差異的時間其實不太大, 也才幾十 cycles 的程度
![](https://i.imgur.com/qWYNIrf.png)
但 `REF` 在大部份資料長度區段出現高耗時的次數都比 `CPY` 多
![](https://i.imgur.com/EI6qrJE.png)
在 prefix search 的部份, 原本預期兩者時間會差不多的, 畢竟 search 的程式碼幾乎都沒有改動
但看起來似乎不是這樣, 詳細原因還要再找找
用 perf 收集執行 100 次的 cache-misses 資料
||CPY|REF|
|-|-|-|
|cache-miss rates|70.981 %|69.267 %|
結果 cache-misses 好像也沒好多少, 到底是哪裡出問題了......
> perf 有 raw-counter 可觀察更細緻的表現,像是 branch predictor 的資訊。
> [name="jserv"][color=red]
----
再做了幾次測試取結果, 因為重複做 100 次太耗時, 因此改為 50 次
並且測試時將電腦上所有多餘的程式全部關掉, 總算得到較為符合預期的結果
```shell=
CPY insert
average cycles: 947.251744 cycles
standard deviation: 918.691873
confidence interval (95%): (943.714361, 950.789128)
```
```shell=
REF insert
average cycles: 874.937502 cycles
standard deviation: 923.376178
confidence interval (95%): (871.382081, 878.492922)
```
`CPY` 在 insert 上是應該要比 `REF` 慢的, 這中間差異的時間就是分配記憶體的時間
```shell=
CPY prefix search
average cycles: 61632.745353 cycles
standard deviation: 140002.927347
confidence interval (95%): (61307.518470, 61957.972236)
```
```shell=
REF prefix search
average cycles: 67237.457684 cycles
standard deviation: 156323.729683
confidence interval (95%): (66874.317568, 67600.597800)
```
`REF` prefix search 的時間雖然已經相近, 但仍然比 `CPY` 長, 結果還是找不到原因
:::danger
1. 接著繼續思考 page fault 的影響
2. alignment 和 memory pool 相關議題
3. 試著用 perf 和 gprof 找出效能 hotpsot
:notes: jserv
:::
||cache misses|branch misses|
|-|-|-|
|`CPY`|52.681 %|2.74%|
|`REF`|53.303 %|2.76%|
在 cache misses 及 branch misses 方面兩者也是相差僅有可以忽略的數字
綜合下來看, 除了 insert 的效能因為省去了 allocated 的時間, 兩版幾乎可說是毫無差別
---
## tst 的優點 & 電話簿或戶政管理系統
tst 的優點是能用 prefix 當作關鍵字進行搜尋, 在要求不詳細的情況下也能快速得到需要的結果
這種特性我們平常在寫程式使用 auto complete 等輔助工具時就已經體會到了它的方便之處
但是對於電話簿或許還堪用, 戶政管理系統恐怕就無法使用了
這次所使用的約 260k 筆資料, 以台灣的戶政管理系統來說需要處理 23m 人的資料
其中幾乎所有人能當作關鍵字的資料長度都不超過個位數
也就是 prefix search 會為了生出範圍不夠小的建議群而花上極長的時間
更別提還要處理同名等問題, 這明顯不符成本的情況使戶政管理系統不太適用 tst
---
## Forward Declaration
Forward Declaration 是指將 **definition** 可以跟 **declaration** 分離這種特性加以應用的技巧
在 C/C++ 裡 definition 是可以跟 declaration 分開的, 所以才會有 .h/.c 這種結構
如果 header 中只有 definition, 那麼之後就算在 .c 檔中的 declaration 被修改了
因為引用 header 的檔案跟 .c 並沒有 dependency, 所以可以重新連結, 省去編譯時間
這種用法的使用限制是, 只能應用在不需知道 declaration 才能提供的資訊
如所需記憶體大小之類的情況
應用在 phonebook 就是將 mempool 跟 entry 的 declaration 放到 .c 檔裡去
但是因為在 main 中有用到 sizeof(entry), 所以無法使用這種方法
:::danger
1. 用物件導向和模組化的觀點去陳述
2. 試著舉出更多實例
:notes: jserv
:::
---
## tst_traverse_fn
只看這 function 本身就只是一個跑完整個 tst 的程式
特別之處在於它能有限制的根據傳入的 function 對 tst 中每個節點做各種各樣的事
在提供的程式碼中, 只要是 prototype 符合 (const void *, void *) 的 function 都能作為參數傳入
---
## 參考資料
* [When can I use a forward declaration? (stackoverflow)](https://stackoverflow.com/questions/553682/when-can-i-use-a-forward-declaration)
* [forward declaration](http://ascii-iicsa.blogspot.tw/2010/12/forward-declaration.html)
---
<!--
## 作業要求
* [x] 在 GitHub 上 fork prefix-search,並修改 Makefile 以允許 $ make bench 時,可對 ternary search tree 的實作做出效能評比,涵蓋建立 tst 和 prefix search 的時間,應比照 clz 透過統計模型,取出 95% 信賴區間
* [x] 測試程式碼應該接受 --bench 的執行參數,得以在沒有使用者輸入的前題下,對 tst 程式碼進行效能分析,應涵蓋 cpy 和 ref 兩種途徑 (詳情參閱 tst.h 的程式碼註解)
* [x] 解釋 tst 的優點和引入 tst 到電話簿或戶政管理系統的適用性
* [x] 修改 test_ref.c,參照裡頭標註 TODO 的部分,替換成真正有效的 API 和對應的程式碼,這裡要求你學習分析現有的程式碼並得以擴充
* [ ] 分析 test_cpy 和 test_ref 兩種方式 (copy/reference) 的效能,並且針對現代處理器架構,提出效能改善機制
* [ ] 指出目前實作中,針對各國城市的 prefix search 有無缺陷呢?比方說無法區分城市和國家,並提出具體程式碼的修正
* [ ] 引入 phonebook 的基礎工作,透過 ternary search tree 讓電話簿程式得以更符合人性,當使用者新增資料時,可以在居住地透過 prefix search 找出最接近的城市並避免輸入錯誤
* [x] 詳細觀察 tst.h 和 tst.c 為何要 forward declaration 呢?分離介面和實作有何好處呢?這樣的思維又該如何運用於 phonebook 呢?提出想法並且實作
* [x] 研究程式碼的 tst_traverse_fn 函式,並思考如何運用這個實作,注意到 callback function 的程式開發技巧/模式
* [x] 將你的觀察、上述要求的解說、應用場合探討,以及各式效能改善過程,善用 gnuplot 製圖,紀錄於「作業區」
-->