Try   HackMD

2017q3 Homework2 (prefix-search)

tags: sysprog2017 dev_record

contributed by <HTYISABUG>

Reviewed by amikai

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 的大小去調整資料結構

以上是小弟淺見, 如有冒犯請見諒

  1. 凡事都要怕冒犯，就不要去做了
  2. 只要能提升其他同學程度的事，就大膽作
  3. 指出他人的弱點，大家才能一同成長

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
jserv

下載並測試

下載並測試程式碼, 經確認後程式可執行且輸出正常
程式共有兩版, test_cpy.c & test_ref.c
Diff 兩版只有註解差異

修改 test＿ref.c

嘗試照註解修改程式碼, 先查詢 tst.h 註解
先簡單的把程式中的 CPY 替換成 REF

執行結果

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

調整用語，儘量清楚明暸。「噴出」錯誤的用法不明確
"jserv"

解決方案

先觀察了 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 時就正常結束了






case 'q':
    /*tst_free_all(root);*/
    tst_free(root);
    return 0;
    break;

再來要解決 search 出錯的問題

在閱讀程式碼的途中, 發現 ternary tree 的末端明明 type 是 (tst_node *)
實際上儲存的東西是一個字串, 之前還真沒想過可以這樣安插字串進 tree 之中!

善用 GDB 觀察記憶體，你會感受到更多資料結構和底層機制的關聯
"jserv"

找了一兩個小時, 終於在使用的時候找到了 search 的錯誤



(gdb) p sgl
$1 = {0x7fffffffdac0 "Tain" <repeats 12 times>, 0x0 <repeats 1012 times>}

這些輸出的字串, 通通是指向同一個位置, 這說明那些 leaf 的末端都是指向同一個位址…?
Sgl 內的字串全是以指標形式在 tst_suggest 裡賦值的
如果這些末端都指向同一位址, 那說明在 insert 階段應該已經出錯了

終於找到確切的錯誤位置了











/* 這是 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 版本的目的衝突, 這到底該如何解決?











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] 的介面/實作，調整記憶體處理模型。
程式碼給你是讓你實驗用的
"jserv"

針對這問題跟 HMKRL 討論
我們看完程式碼後得到的結論是
讀取自文件中的資料在被洗掉以前完全沒有被儲存起來
既然沒有被儲存起來那就不可能被讀取, 因此必然需要分配記憶體用於儲存

考慮到多次 allocate 會導致記憶體破碎, cache-misses 大量產生
應用之前在 phonebook 曾經用過的 mempool 技巧使資料連續儲存
然後 leaf 儲存的指標將會指向 pool 中的某個位址
因應資料儲存方式的變動, tst.c 也隨之改變

程式更動請見 91a32d

不要濫用 :::info 一類的標注，你應該清楚闡述前因後果，把技術文件寫好
"jserv"

呃, 我不太懂老師的意思
我想說能用色塊強調問題點跟解決方法就用了
"HTYISABUG

技術文件強調「結構」，認真想這件事，我們要寫出專業的文件，不是流水帳。
"jserv"

  • 修正 tst.c 的 tst_del_word
    • 沒注意到參數就有 freeword 而直接將釋放記憶體的步驟清除了, 這樣將會導致 memory leak
    • 同時將 tst_ins_del 中呼叫 tst_del_word 時的參數修正
    • 在 HMKRL 提醒後修正
    • 程式更動請見 1a4d3b

Benchmark

為了接受 --bench 參數, 加入 getopt_long
為了更精確的時間數值, 引入 clz-test 的組語計算 cycles

REF

Insert

將每筆資料的 insert 時間印出

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

為了確認資料長度對 insert 的影響, 先確認資料長度的分佈

下圖標題與內容不匹配，應修正
"jserv"

可見資料大多集中在 10 字以下
定義長度 10+ 為長字串, 以不同顏色在時間圖中標出

參考老師在 HMKRL 筆記中所留有關排程與限定處理器的建議重新執行

「其他人」在哪？為何不列出訊息的源頭呢？養成好習慣，日後才能追蹤和反思
"jserv"

從圖中可知資料的長度跟 insert 時間並無太大關係
大部份資料都 分佈在 20000 cycles 以下
將 20000+ cycles 的資料取出觀察分佈

分佈的趨勢跟整體的分佈趨勢大致相符
說明不論資料長度如何, 都有可能出現高耗時的情況
這樣看來, 這些高耗時的的情況可以視為 jitter




average cycles: 1086.009093 cycles
standard deviation: 1695.082006
confidence interval (95%): (1079.482252, 1092.535933)

將每筆資料 prefix search 的時間印出

700000+ 次搜索太多, 結果什麼都看不清楚
換個角度, 從被搜到的資料量跟時間的關係觀察

雖然還是很雜亂, 但已經隱約可以看出時間分佈是照所搜到的資料量呈區段分佈的
以每 50 為一區段計算平均時間

可確認搜索時間跟搜得資料量成正比




average cycles: 77646.828332 cycles
standard deviation: 180620.276540
confidence interval (95%): (77227.247323, 78066.409341)

CPY

採用跟 REF 同樣的方法分析

Insert




average cycles: 1105.770331 cycles
standard deviation: 1520.471492
confidence interval (95%): (1099.915820, 1111.624841)

Prefix Search




average cycles: 65042.560313 cycles
standard deviation: 149953.627612
confidence interval (95%): (64694.217948, 65390.902679)

結果比較

ref cpy
average cycles 1086.009093 1105.770331
confidence interval (95%)
±6.52684
±5.854511

Insert 的部份, REF 跟 CPY 差異的時間其實不太大, 也才幾十 cycles 的程度

但 REF 在大部份資料長度區段出現高耗時的次數都比 CPY 多

在 prefix search 的部份, 原本預期兩者時間會差不多的, 畢竟 search 的程式碼幾乎都沒有改動
但看起來似乎不是這樣， 詳細原因還要再找找

用 perf 收集執行 100 次的 cache-misses 資料

CPY REF
cache-miss rates 70.981 % 69.267 %

結果 cache-misses 好像也沒好多少, 到底是哪裡出問題了…

perf 有 raw-counter 可觀察更細緻的表現，像是 branch predictor 的資訊。
"jserv"

再做了幾次測試取結果, 因為重複做 100 次太耗時, 因此改為 50 次
並且測試時將電腦上所有多餘的程式全部關掉, 總算得到較為符合預期的結果





CPY insert
average cycles: 947.251744 cycles
standard deviation: 918.691873
confidence interval (95%): (943.714361, 950.789128)





REF insert
average cycles: 874.937502 cycles
standard deviation: 923.376178
confidence interval (95%): (871.382081, 878.492922)

CPY 在 insert 上是應該要比 REF 慢的, 這中間差異的時間就是分配記憶體的時間





CPY prefix search
average cycles: 61632.745353 cycles
standard deviation: 140002.927347
confidence interval (95%): (61307.518470, 61957.972236)





REF prefix search
average cycles: 67237.457684 cycles
standard deviation: 156323.729683
confidence interval (95%): (66874.317568, 67600.597800)

REF prefix search 的時間雖然已經相近, 但仍然比 CPY 長, 結果還是找不到原因

  1. 接著繼續思考 page fault 的影響
  2. alignment 和 memory pool 相關議題
  3. 試著用 perf 和 gprof 找出效能 hotpsot

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
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), 所以無法使用這種方法

  1. 用物件導向和模組化的觀點去陳述
  2. 試著舉出更多實例

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
jserv

tst_traverse_fn

只看這 function 本身就只是一個跑完整個 tst 的程式
特別之處在於它能有限制的根據傳入的 function 對 tst 中每個節點做各種各樣的事

在提供的程式碼中, 只要是 prototype 符合 (const void *, void *) 的 function 都能作為參數傳入

參考資料

Last changed by 
 
TSUNGYU HSIEH
0
510
Published on HackMD