2017q3 Homework2 (prefix-search)

contributed by<zhanyangch>

執行環境

$ lscpu
Architecture:          x86_64
CPU 作業模式：    32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
每核心執行緒數：2
每通訊端核心數：2
Socket(s):             1
NUMA 節點：         1
供應商識別號：  GenuineIntel
CPU 家族：          6
型號：              42
Model name:            Intel(R) Core(TM) i7-2640M CPU @ 2.80GHz
製程：              7
CPU MHz：             855.421
CPU max MHz:           3500.0000
CPU min MHz:           800.0000
BogoMIPS:              5587.06
虛擬：              VT-x
L1d 快取：          32K
L1i 快取：          32K
L2 快取：           256K
L3 快取：           4096K
NUMA node0 CPU(s):     0-3

tst_suggest 修正

用 prefix search 搜尋 'A' 時會產生 Segmentation fault
用 gdb 查看錯誤資訊

choice: s
find words matching prefix (at least 1 char): A

Program received signal SIGSEGV, Segmentation fault.
0x0000000000401f8b in tst_suggest (p=0xd72680, c=65 'A', nchr=1, 
    a=0x7fffffffbd50, n=0x7fffffffbd0c, max=1024) at tst.c:330
330	        a[(*n)++] = (char *) p->eqkid;

tst_suggest() 的原始程式碼，找到符合的節點會將字串放入 a[]中，但對於 n 的檢查 *n == max，因　tst_suggest 會多次呼叫自己，可能出現 n>=max 的情形，此時會導致程式嘗試去寫入不合法的記憶體。
if (!p || *n == max) 修正為 if (!p || *n >= max) 即可。
修正後搜尋'A'只會找到前 1025 筆資料，應為1024筆，改為在記憶體寫入前再做一次檢查

void tst_suggest(const tst_node *p,
                 const char c,
                 const size_t nchr,
                 char **a,
                 int *n,
                 const int max)
{
    if (!p || *n >= max)
        return;
    tst_suggest(p->lokid, c, nchr, a, n, max);
    if (p->key)
        tst_suggest(p->eqkid, c, nchr, a, n, max);
    else if (*(((char *) p->eqkid) + nchr - 1) == c && *n < max)
        a[(*n)++] = (char *) p->eqkid;
    tst_suggest(p->hikid, c, nchr, a, n, max);
}

1. 目前 Git commit Fix memory access out of bounds 描述太不清楚，請參照 Memory access out of bounds error when using _malloc on WASM compiled code 的分析和隨後的程式碼修正方式，改善你的 Git commit messages
2. 善用 git commit --amend 和 git push --force，讓程式碼的變革更清楚且易於維護

jserv

REF 實做

此部份參考st9007a的共筆

void *tst_ins_del(tst_node **root, char *const *s, const int del, const int cpy)
{
    /* ....*/
        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;
            }
        }
   /* ....*/
}

原本使用 CPY 時會利用 strdup 分配一塊記憶體放置複製的字串，若改用 REF 必需先為該字串分配記憶體。
宣告一個二維陣列來存放所有要放入 TST 的字串。

char (*cities)[WRDMAX] = malloc(sizeof (*cities) * CITYMAX);

1. 上述對應的 Git commit Implement ref version 描述太不清楚，請改善 commit message!
2. 不要濫用 "version" 這詞彙，在你學習軟體工程後，應該更謹慎
3. Repalce argument CPY with REF in test_ref.c => 這說明了什麼？你要做高階的描述，說明你的修改動機、目的，還有方法。不用特別說在哪個檔案，Git 會自動追蹤
4. Modify parameter of tst_del_word invoked by tst_ins_del => 同上，不要做低層次的描述，Git commit messages 是給合作者和「未來的你」看的。

jserv

測試過程:

choice: q
*** Error in `./test_ref': free(): invalid pointer: 0x00007f1a6f8bef10 ***

在執行 quit 時發現 free() 到不合法的指標，將 tst_free_all(root) 改為 tst_free(root)，兩者差異主要在於 tst_free_all 會 free 儲存字串的　tst_node ，tst_free 則不會。

void tst_free_all(tst_node *p)
{
    if (!p)
        return;
    tst_free_all(p->lokid);
    if (p->key)
        tst_free_all(p->eqkid);
    tst_free_all(p->hikid);
    if (!p->key)
        free(p->eqkid);
    free(p);
}

/** free the ternary search tree rooted at p, data storage external. */
void tst_free(tst_node *p)
{
    if (!p)
        return;
    tst_free(p->lokid);
    if (p->key)
        tst_free(p->eqkid);
    tst_free(p->hikid);
    free(p);
}

delete 的部份與 quit 相同，將 tst_ins_del 的 return tst_del_word(root, curr, &stk, 1) 改為 return tst_del_word(root, curr, &stk, cpy)
在 REF 時 freeword 為0，不會 free 字串的記憶體。

static void *tst_del_word(tst_node **root,
                          tst_node *node,
                          tst_stack *stk,
                          const int freeword)
{
     tst_node *victim = node;          /* begin deletion w/victim */
    tst_node *parent = tst_stack_pop(stk); /* parent to victim */

    if (!victim->refcnt) {            /* if last occurrence */
        if (!victim->key && freeword) /* check key is nul   */
            free(victim->eqkid);      /* free string (data) */
    /*...*/
}

應該一併開發可以自動測試程式的機制，這樣才能交叉比對 CPY 和 REF 兩種實作的結果，而不用每次都透過人工輸入

jserv

效能比較

接受 --bench 的執行參數，將 TST 的建立時間儲存在檔案中，並且在 bench 函式中測試 search A-Z 、 a-z 所需的時間。

    if(argc==2 && strcmp(argv[1], "--bench") == 0){
        fp = fopen (TST_BENCH,"a+");
        if (!fp) {
            fprintf(stderr, "error: file open failed '%s'.\n", TST_BENCH);
            return 1;
        }
        fprintf(fp, "%.6f\n",t2 - t1);
        fclose(fp);
        fp = fopen (SEARCH_BENCH,"a+");
        if (!fp) {
            fprintf(stderr, "error: file open failed '%s'.\n", SEARCH_BENCH);
            return 1;
        }
        fprintf(fp, "%.6f\n",bench(root, sgl, &sidx, LMAX));
        fclose(fp);
        return 0;
    }

double bench(const tst_node *root,
             char **a,
             int *n,
             const int max)
{
    double t1, t2, totaltime;
    char word[]="A";
    totaltime = 0;
    for (int i=0 ; i<25 ; i++) {
        t1 = tvgetf();
        tst_search_prefix(root, word, a, n, max);
        t2 = tvgetf();
        word[0]++;
        totaltime += t2 - t1;
    }
    word[0] = 'a';
    for (int i=0 ; i<25 ; i++) {
        t1 = tvgetf();
        tst_search_prefix(root, word, a, n, max);
        t2 = tvgetf();
        word[0]++;
        totaltime += t2 - t1;
    }
    return totaltime;
}

輸入 make bench 時會執行 perf 測試效能

bench:
	echo 3 | sudo tee /proc/sys/vm/drop_caches
	perf stat --repeat 100 \
                -e cache-misses,cache-references,instructions,cycles \
                sudo chrt -f 99 taskset -c 0 ./test_cpy --bench
	echo 3 | sudo tee /proc/sys/vm/drop_caches
	perf stat --repeat 100 \
                -e cache-misses,cache-references,instructions,cycles \
                sudo chrt -f 99 taskset -c 0 ./test_ref --bench

測試結果：CPY 的 cache miss 較多，但執行時間較短。

  Performance counter stats for 'sudo chrt -f 99 taskset -c 0 ./test_cpy --bench' (100 runs):

               577      cache-misses              #   29.304 % of all cache refs      ( +-  1.17% )
             1,970      cache-references                                              ( +-  1.07% )
            37,668      instructions              #    0.33  insns per cycle          ( +-  0.51% )
           114,387      cycles                                                        ( +-  0.82% )

       0.177266445 seconds time elapsed                                          ( +-  0.57% )
 Performance counter stats for 'sudo chrt -f 99 taskset -c 0 ./test_ref --bench' (100 runs):

               563      cache-misses              #   28.153 % of all cache refs      ( +-  0.72% )
             2,001      cache-references                                              ( +-  1.29% )
            37,615      instructions              #    0.33  insns per cycle          ( +-  0.67% )
           113,579      cycles                                                        ( +-  1.25% )

       0.199392490 seconds time elapsed                                          ( +-  0.28% )

建立 TST 的時間
利用 gnuplot 的 stat 指令可以獲得統計數據

stat 'tst-cpy-bench.txt' using 1 name 'CPY'

CPY:
  Mean:               0.1280
  Std Dev:            0.0071
REF:
  Mean:               0.1411
  Std Dev:            0.0039

搜尋時間

CPY:
  Mean:               0.0421
  Std Dev:            0.0007
REF:
  Mean:               0.0505
  Std Dev:            0.0005

原因探討

• 建立 TST 時 REF 使用的記憶體空間固定，CPY 則是依據輸入字串的長度，且 REF 要將每一筆資料儲存在不同的記憶體位置，這個記憶體位置需要計算。
• 搜尋的差異只在於葉節點的字串儲存位置不同，將 CPY 的葉節點(儲存字串)和上一個節點(儲存 key)的記憶體位置印出，可以發現位置是相鄰的。

address of node:   0x3c59000
address of string: 0x3c59030

*　改善 REF 的方向：先配置一塊記憶體，將節點與字串依序存放。

forward declaration

在 tst.h 中 並沒有定義 tst_node 的成員，並且所有函式都是對 tst_node 的指標作運算，這樣的作法好處是減少重新編譯的時間，且可以由不同的 .c 檔案實做 struct 的內容，缺點是不能直接對 struct 作操作，要改用 get、set 等函式。

typedef struct tst_node tst_node

tst_traverse_fn

走訪每一個節點，順序是 lokid、eqkid、hikid、parent，且對於葉節點呼叫 fn
fn 在此為 callback function ，在符合條件時會自動被呼叫，可以藉由傳入不同的函數來實現不同功能，例如 tst_get_refcnt 可以取得字串出現的次數、tst_get_string 取得字串等。

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);
}

callback function 也常被用於使用者界面，例如 OpenCV 的 setMouseCallback 當收到使用者的滑鼠事件，會呼叫 onMouse 函數進行處理，範例。

void setMouseCallback(const string& winname, MouseCallback onMouse, void* userdata=0 )

程式碼列表太少，需要提及如何「運用」，也就是最小可執行的示範
"jserv"

修正資料分隔符號

原本讀取檔案的方式為 fscanf(fp, "%s", word) 但 cities.txt內的格式為 city, country，fscnaf 讀取字串時遇到空格字元會停止讀取，例如：Buenos Aires, Argentina 會認為是三個字串 "Buenos"、"Aires,"、"Argentina"，但這筆資料的意義應該是"Buenos Aires"、"Argentina"，所以需要修改讀取的格式。

    while ((rtn = fscanf(fp, "%[^,\n]", word)) != EOF) {
        char tmp = fgetc(fp);
        if (tmp == ',') {
            tmp = fgetc(fp);
            strcat(word, ",");
            }
        /*...*/                                                      }                                     

%[^,\n] 為讀取字串直到遇到 [^] 內的字元，這裡以',' '\n'分隔不同筆資料，當遇到','時忽略後面一個字元(在資料中','後面必定有一空白)，並且為了辨識是 city 還是 country ，再把','補上。
測試結果：可以正確找到含有空格的字串

choice: s   
find words matching prefix (at least 1 char): Buenos
  Buenos - searched prefix in 0.000005 sec

suggest[0] : Buenos Aires,

參考資料

st9007a的共筆
stats_(Statistical_Summary) - Gnuplot: An Interactive Plotting Program
OpenCV documentation