Try   HackMD

2017q3 Homework2 (prefix-search)

contributed by <HMKRL>

Reviewed by jcyztw

  • 最近一次 commit 2d47e0b，如同老師在你 GitHub 的留言，有空可以針對 commit message 的內文做修改。看完你的 commit message，我只看到你改了哪些檔案，但是你此次 commit 做了什麼事並沒有寫出來；因為我還沒仔細看你的 code，無法很迅速得知你這次 commit 到底做了什麼，覺得有點美中不足。(P.S. How to Write a Git Commit Message 中文翻譯在這裡，供你參考)
  • 請問你的開發環境為何？是單核心或是多核心的 CPU？我會問這個問題，主要是因為看到你在做 test_cpy 和 test_ref 的效能分析時，用了 RDTSC 指令來幫你達成目的。但是根據以前修課同學的共筆及其相關影片，RDTSC 指令在多核心 CPU 的環境上作量測會有問題。所以你才會使用 chrt 和 taskset 兩個 command 來解決 RDTSC 不能在多核心 CPU 量測的限制嗎？

Reviewed by amikai

  • 建議先提及理論, 在對應到自己的 code, 報告會更有完整性

  • 我找到一個函式 sched_setaffinity(), 可以試試看

  • tst_traverse_fn 這邊建議可以在介紹的詳細一點，因為這是很有用的函式, 並且可以舉個
    實例

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

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

:notes: jserv

實作 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;
}

REF 模式應該將字串另外儲存，理想情況應該直接採用原始資料儲存的位置，但在這個例子中原始資料是讀檔取得，因此無法直接使用

  1. 可考慮引入 mmap，詳見 B07: phonebook-concurrent
  2. 承上，引入 mmap 時，需要一併將 Stream I/O (如 fopen, fread, fclose) 替換為低階 I/O (如 open, read, close)
  3. 不要忽略檔案操作在整體時間的影響
    :notes: jserv

針對這個問題和 HTYISABUG 討論，我們想到可以將原始資料儲存起來，但若同樣採用 malloc 個別分配記憶體空間，則與 CPY 版本沒有差異，因此我們決定採用 mempool 儲存原始資料

詳見 commit d3eb39c

實作 mempool 後發現無法正常完成 delete 操作，經 gdb 檢查找到問題在 tst.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);
    }

但檢視輸出檔後發現由於搜尋所花時間太短，無法有效測量

為何不透過統計模型來分析呢？
"jserv"

此處消耗時間已低於本計時函式精確度，因此數據無法使用
"HMKRL

因此引入作業1中曾出現過的方法，利用 RDTSC 計算所消耗的 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 從頭到尾沒變啊
HTYISABUG

結果：

重新設定範圍消除過高資料後（來源應為作業系統其他背景工作）：

搭配使用 chrt，將排程策略變更為 real-time FIFO，以及用 taskset 限定在某個/某些處理器上運作程式
"jserv"

使用 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

從隨機事件的觀點，用 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 傳入，即可用於除錯/觀察資料結構/效能量測等用途

Last changed by 
 
はみ
0
839
Published on HackMD