2017q3 Homework2 (prefix-search)

# 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 ::: ---  --- ## 下載並測試下載並測試程式碼, 經確認後程式可執行且輸出正常程式共有兩版, `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) ---