2020q3 Homework3 (dict)

--- tags: 進階電腦系統理論與實作 --- # 2020q3 Homework3 (dict) contributed by < `RinHizakura` > > [I04: dict](https://hackmd.io/@sysprog/2020-dict) > [GitHub](https://github.com/RinHizakura/dict) ## 程式原理 ### CPY 與 REF 機制在原始程式的實作中，程式可以分成 CPY 和 REF 兩種模式。使用何種模式會在程式中根據輸入的參數來判斷，並對變數去做對應的處理。 ```cpp if (!strcmp(argv[1], "CPY") || (argc > 2 && !strcmp(argv[2], "CPY"))) { CPYmask = 0; REF = DEL; printf("CPY mechanism\n"); } else printf("REF mechanism\n"); ``` 原始的 `Top` 總空間為 WRDMAX = 256 個 char。如果在 REF 模式下，`CPYmask` = -1，因此會進入下面的 if 中，改成配置一個大的 heap 空間給 `Top`。 ```cpp char word[WRDMAX] = ""; char *Top = word; ... if (CPYmask) { /* memory pool */ pool = (char *) malloc(poolsize * sizeof(char)); Top = pool; } ``` `Top` 的大小和兩個模式的關聯性為何呢？從下面的迴圈可以看出端倪: ```cpp while (fgets(buf, WORDMAX, fp)) { int offset = 0; for (int i = 0, j = 0; buf[i + offset]; i++) { Top[i] = (buf[i + j] == ',' || buf[i + j] == '\n') ? '\0' : buf[i + j]; j += (buf[i + j] == ','); } while (*Top) { if (!tst_ins_del(&root, Top, INS, REF)) { ... } Top -= offset & ~CPYmask; memset(Top, '\0', WORDMAX); } ``` * 首先檔案中的字串會被逐行讀出，並根據 `,` 和 `\n` 去做分割 * 透過 `tst_ins_del` 去插入 ternary search tree 的節點，如果是在 CPY 模式下，會透過 `strdup` 隱性的去呼叫 malloc，配置新的空間擺放字串;如果是在 REF 模式下，因為事先已經配置了一個很大的記憶體空間 `Top` 來擺放所有的待搜尋字串，因此只要 refererence 過去即可 * 如果是 CPY 模式，需要透過 `Top -= offset & ~CPYmask` 會讓 Top 回到 `word` 的起始位置，REF 模式則 `~CPYmask` 為 0 因此 `Top` 的位址會維持不變 :::info 也許是因為考慮分支的成本，所以程式才透過 CPYmask 去區隔 CPY 和 REF 的實作。否則的話其實我偏好換成同等的 statement `if(!CPYmask) Top = word`，因為對我來說可讀性比較好XD 其他使用 `CPYmask` 的地方其實也是相似概念，其實都可以用 if 敘述改寫成比較容易讀的版本 > 路見不平，拿 pull request 來補強，等你 > :notes: jserv > :ok_hand: 原本的實作可以減少 branch 所以效能其實會相對更好 :D 只是個人喜好覺得這裡可以在效能和可讀性間做一點 trade off，會再想想有沒有可以兼顧兩者的作法~ ::: 所以我們可以明顯的看出兩個機制的差別在於從檔案中讀入的字串是否需要另外複製一份。 ### `tst_ins_del` `tst_ins_del(tst_node **root, const char *s, const int del, const int cpy)` 會插入或者移除(根據 del)字串 `s`。程式的執行邏輯如下: ```cpp int diff; const char *p = s; tst_stack stk = {.data = {NULL}, .idx = 0}; tst_node *curr, **pcurr; if (!root || !s) return NULL; if (strlen(s) + 1 > STKMAX / 2) return NULL; ``` * `p` 指向字串的開頭，並透過 struct literal 初始化 `tst_stack` * 檢查錯誤的操作(`**rool` 或者 `*s` 為 NULL)，包含字串的長度不能超過 `STKMAX / 2` ```cpp pcurr = root; while ((curr = *pcurr)) { diff = *p - curr->key; if (diff == 0) { if (*p++ == 0) { if (del) { (curr->refcnt)--; return tst_del_word(root, curr, &stk, cpy); } else curr->refcnt++; return (void *) curr->eqkid; } pcurr = &(curr->eqkid); } else if (diff < 0) { pcurr = &(curr->lokid); } else { pcurr = &(curr->hikid); } if (del) tst_stack_push(&stk, curr); } ``` * 從 root 開始搜尋，根據目前走訪的節點字元與字串目前的字元去決定下一個走訪的節點 * 在 delete 模式下，`tst_stack` 會去儲存如何走訪，以便在 `tst_del_word` 時去做對應的處理 * `if (*p++ == 0)` 下的 statement 表示已經走到字串的 `\0`，此時去判斷是否此字串已經被放在 TST 中，如果已經存在 * 在 delete 模式下，`refcnt` 減 1，並透過 `tst_del_word` 做刪除對應的處理 * 在 insert 模式下，則直接回傳該字串 ```cpp for (;;) { if (!(*pcurr = calloc(1, sizeof **pcurr))) { fprintf(stderr, "error: tst_insert(), memory exhausted.\n"); return NULL; } curr = *pcurr; curr->key = *p; curr->refcnt = 1; curr->lokid = curr->hikid = curr->eqkid = NULL; if (!*root) /* handle assignment to root if no root */ *root = *pcurr; 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; } } pcurr = &(curr->eqkid); } ``` * 在 insert 模式下，如果遍歷 TST 的途中發現字串尚不在 TST 上，則需配置新空間給新節點並調整節點的相關資訊，將剩餘的節點補足 * `if (*p++ == 0)` 下將 `curr->eqkid` 指向字串的真正內容，根據 CPY 或 REF 會有不同的處理 * `pcurr = &(curr->eqkid)` 更新 `pcurr` 指向下一個新節點的位置 ### `tst_del_word` 透過 `tst_del_word` 將 TST 上的字串進行刪除。 ```cpp tst_node *victim = node; tst_node *parent = tst_stack_pop(stk); if (!victim->refcnt) { if (!victim->key && freeword) free(victim->eqkid); while (!parent->lokid && !parent->hikid && !victim->lokid && !victim->hikid) { ... } ``` * `victim` 會從等待被刪除的字串本身開始，`parent` 即是 `victim` 的母節點，也是下一個該被處理的節點 * 如果該 `refcnt` > 0，表示尚有 reference 存在，則不需刪除 * `if (!victim->key && freeword) free(victim->eqkid)`，判斷是否為 CPY 模式，若是，則首先釋放字串本身 * while 迴圈中，如果待移除的 `victim` 和其 `parent` 沒有其他 child，則可以直接釋放 ```cpp if (victim->lokid && victim->hikid) { /* victim has both lokid/hikid */ if (!victim->lokid->hikid) { /* check for hikid in lo tree */ ... } else if (!victim->hikid->lokid) { /* check for lokid in hi tree */ ... } else /* can't rotate, return, leaving victim->eqkid NULL */ return NULL; } else if (victim->lokid) { /* only lokid, replace victim with lokid */ ... } else if (victim->hikid) { /* only hikid, replace victim with hikid */ ... } else { /* victim - no children, but parent has other children */ ... ``` :bell: :bell: :bell: * 在該移除的候選節點 `victim` 同時具有 low child 和 high child 的情形下 * `if (!victim->lokid->hikid)`: 如果 `victim` 的 low child 沒有 high child，則把 `victim` 的 high child 接到 `victim` low child 的 high child，並將其此 low child 取代 `victim` 的位置，然後釋放掉 `victim` * `else if (!victim->hikid->lokid)` 則與上述概念相似 * 如果以上情形皆非，則 `victim` 不釋放並會指向 NULL 字串，維持 TST 原貌 * 如果 `victim` 僅有 low child，則把 `victim` 的位置替換成其 low child 並釋放 `victim` * 如果 `victim` 僅有 high child，則把 `victim` 的位置替換成其 high child 並釋放 `victim` * 如果 `victim` 沒有 child 的話，原本 `parent` 指向 `victim` 的路徑就不能用 `victim` 的 child 去更新，因此需要後續的處理 ```cpp if (victim == parent->lokid) { /* if parent->lokid - trim */ ... } else if (victim == parent->hikid) { /* if parent->hikid - trim */ ... } ``` * 如果 `victim` 是 `parent` 的 low child，則需把 `parent->lokid` 指向 NULL 並且釋放 `victim` * 同理，如果 `victim` 是 `parent` 的 high child，則需把 `parent->hikid` 指向 NULL 並且釋放 `victim` ```cpp else { /* victim was parent->eqkid, but parent->lo/hikid exists */ parent->eqkid = NULL; /* set eqkid NULL */ free(victim); /* free current victim */ victim = parent; /* set parent = victim */ parent = tst_stack_pop(stk); /* get new parent */ /* if both victim hi/lokid are present */ if (victim->lokid && victim->hikid) { ... } else if (!victim->hikid->lokid) { ... } else return NULL; } /* if only lokid, rewire to parent */ else if (victim->lokid) { ... } /* if only hikid, rewire to parent */ else if (victim->hikid) { ... } } ``` * 如果 `victim` 是 `parent->eqkid`，首先也先將 `parent->eqkid` 指向 NULL 並且釋放 `victim` * 與前面不同的是，此時需對 `parent` 的 `parent` 進行處理，因為此時的 `parent` 很可能已經是不再被需要的節點了 * 因此首先對變數進行更新，此時的 `victim` 實際上是原始 `victim` 的 parent，而 `parent` 則是原始 `parent` 的 parent * 接著的步驟就類似於前面標註 :bell::bell::bell: 處，去對 TST 結構做對應的更新 :::info `tst_del_word` 函式的程式量比較龐大，為保持一定的版面整潔因此省略部份程式，詳細請追溯原始程式碼~ ::: ## Ternary search tree + bloom filter 的效能表現仿效原作業說明的內容，嘗試比較 bloom filter 的使用對於效能提升的效益。為了方便進行實驗，在原始程式碼中額外安插一段程式類似如下： ```cpp if (argc == 3 && strcmp(argv[1], "--bench") == 0) { ... else if (argc == 3 && strcmp(argv[1], "--perf") == 0) { /* 測試用的程式 */ } ``` :::warning :warning: 原本的程式碼寫得很醜 (對不起，我督導不周)，你可嘗試用 [getopt](https://www.gnu.org/software/libc/manual/html_node/Getopt.html) 改寫，預期將大幅縮減程式碼長度且更容易擴充。 :notes: jserv ::: 藉此，我們只要透過類似 `./test_common --perf CPY` 的命令，就可以根據撰寫的程式使用搜尋等相關 function，設計對應的實驗並計算運行的時間。為了減少實驗誤差，改變 config 使電腦上的第 6 核空下(不工作)，並透過 taskset 鎖定在上面執行。對於每個實驗，進行總共 100 次的實驗，得到如下的各種結果。 :::warning :warning: 最好搭配 Linux 核心啟動參數 `isolcpus` 使用，詳見: https://www.suse.com/support/kb/doc/?id=000017747 :notes: jserv > :ok_hand: 這裡說「不工作」的意思，的確就是透過更動 grub 的 isoplus 參數使 taskset 指定外的任務不會排程到我的第 6 核，是我用詞不夠精確，不好意思 ::: ### 實驗 `1`：使用 cities.txt 做為搜尋字串 ![](https://i.imgur.com/kfEdynY.png) 由於 ternary search tree 就是根據 cities.txt 建立的，而 bloom filter 的價值是在於事先預測不存在字典檔的字串，減少真正搜尋 TST 的 overhead。因此可以從圖看到整體的表現上，bloom filter 的使用反而只會增加額外的 overhead，導致運行的時間更長。 ### 實驗 `2`：使用隨機字串做為搜尋字串這裡的**隨機字串**，實際上是用了有點投機的方法產生的。為了保證搜尋的量與實驗 `1` 的一致性，實驗中會先將 cities.txt 中的字串讀出，再根據一個機率去隨機變動其中的字元，使得搜尋的字串不在字典檔中。 ![](https://i.imgur.com/FHXkg92.png) 根據統計，上圖的實驗中共有 0.997 - 0.998 的字串是由 bloom filter 判讀不在字典檔中的。在此狀態下，可以看到不意外的使用 bloom filter 後可以得到較短的搜尋時間。 ![](https://i.imgur.com/wRomTNY.png) 調整隨機字串產生的機率後，根據統計上圖的實驗中則有大約 0.535 的字串可以由 bloom filter 判讀不在字典檔中，剩下的約 0.465 部份則需額外的加上 TST 本身的搜尋。在此情境下，可以看到 bloom filter 仍可以發揮其效用，整體擁有較佳的搜尋時間。 ### 實驗 `3`：使用 prefix 接近的隨機字串做為搜尋字串由於 TST 是 prefix based 的樹狀結構，因此對於不在字典檔的字串，是否提早發先 mismatch 會導致不同的時間成本。下面我們使隨機字串與字典檔中的字串僅在最後一個字元有差異並進行觀察。 ![](https://i.imgur.com/eGtlehB.png) 可以看到使用 bloom filter 與否產生的時間差異更為明顯。如前所述，一直搜尋到最後才發現字串不在字典檔中的成本是很高的，而由於 bloom filter 是 hash based 的預測字串是否存在字典檔中，就可以一定程度減少搜尋 TST 造成的開銷。 ## CPY 和 REF 的效能差異在前面的圖部份，REF 和 CPY 在時間上的差異很難被很好的看出來，因此我將練習使用 perf，試圖分析 CPY 和 REF 兩種機制的 trade-off。 ``` $ sync $ sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches' $ sudo perf stat --repeat 100 -e cache-misses:u,cache-references:u \ ./test_common --bench CPY s Taiwan > /dev/null Performance counter stats for './test_common --bench CPY s Taiwan' (100 runs): 3,561,972 cache-misses:u # 42.040 % of all cache refs ( +- 1.52% ) 8,472,724 cache-references:u ( +- 0.19% ) 0.16881 +- 0.00333 seconds time elapsed ( +- 1.97% ) $ sync $ sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches' $ sudo perf stat --repeat 100 -e cache-misses:u,cache-references:u \ ./test_common --bench REF s Taiwan > /dev/null Performance counter stats for './test_common --bench REF s Taiwan' (100 runs): 3,467,701 cache-misses:u # 41.160 % of all cache refs ( +- 1.28% ) 8,424,852 cache-references:u ( +- 0.20% ) 0.17402 +- 0.00307 seconds time elapsed ( +- 1.76% ) ``` 嘗試透過上面的指令來觀察 CPY 和 REF 的 cache miss 是否確實有顯著的差距。為了減少實驗的誤差干擾，首先使用 `sync` 避免資料的遺失，再使用 `sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches'` 去清除 cache 上的資料。根據原作業的敘述，原本我預期因為 CPY 版本的 `strdup` 出來的字串和 TST 節點的位置比較相近，所以應該會有比較少的 cache-miss ，然而實驗的結果兩個機制似乎沒有太大的 cache-miss 差異。由於這裡的 `perf stat` 是對整個程式的執行做分析，而我們比較在乎的其實是在 `search` 的差異，因此我轉為使用 `perf record` 以取樣的方式來觀察 cache-miss 的比例，得到以下結果。以 CPY 下的分析結果為例: ``` Samples: 396 of event 'cache-misses:u', Event count (approx.): 3061235 Overhead Command Shared Object Symbol 48.85% test_common test_common [.] tst_free_all 23.36% test_common test_common [.] tst_ins_del 12.71% test_common libc-2.31.so [.] _int_free ``` 可以看到造成 cache miss 最多的比例是在釋放 TST 時，顯然不是我們想要關注的部份。為此，我認為應當需要調整實驗的 benchmark，讓 TST search 的操作足夠頻繁而成為 cache-miss 的瓶頸，才能更好的證實我們的猜測。因此，我設計一個迴圈不斷的進行 search，希望可以藉此讓其成為瓶頸，根據此實驗設計的結果如下: * CPY 的結果 ``` Samples: 3K of event 'cache-misses:u', Event count (approx.): 18776657 Overhead Command Shared Object Symbol 60.32% test_common test_common [.] tst_search 9.10% test_common test_common [.] tvgetf ``` * REF 的結果 ``` Samples: 3K of event 'cache-misses:u', Event count (approx.): 17551249 Overhead Command Shared Object Symbol 60.15% test_common test_common [.] tst_search 8.25% test_common test_common [.] tvgetf ``` 結果來看，雖然我們已經讓 tst_search 成為 cache-miss 的密集點，然而兩者的 cache miss 似乎仍沒有顯著的差距... :::danger 需要仔細思考自己的 benchmark 設計是否有甚麼問題 :cry: ::: ## malloc 的效能調整為了可以更有效率的管理記憶體，我們可以設計客製化的 memory pool，更有效的管理記憶體的配置。 ### 撰寫量身打造的 memory pool 初步先參考了 [jobtalle/pool](https://github.com/jobtalle/pool) 來實作 general used 的 memory pool，目前的實作程式碼請參考 [pool.c](https://github.com/RinHizakura/dict/blob/master/pool.c) 和 [pool.h](https://github.com/RinHizakura/dict/blob/master/pool.h)。未來則可以思考能不能更進一步為此程式去做特化，更佳的減少 malloc 帶來的效能衝擊。大致的使用方法為： * 宣告一個 `pool_t` 的物件 * `pool_init`: 初始化 `pool_t` 物件 `p`，其中 `element_size` 是該物件的大小，而 `page_size` 則是每次 malloc 時的實際單位 * 也就是說，memory pool 的 allocate 會以 `page_size` 為單位配置，並且將其切成 `page_size / element_size` 個單位 * 則恰當的設定 `page_size` 可以平衡時間和空間的成本 * 如果讓 `page_size` 符合系統 page table 中的 page 大小的話，說不定可以有效的管理記憶體減少 page fault?(待思考及實驗) * `pool_alloc`: 配置一個物件大小的記憶體空間，內部會去管理實際配置的記憶體夠不夠，其中有兩處是真正的使用 system call 配置空間的 * 如果是可使用的 page 數量不足，則呼叫 realloc 增加可以紀錄 page pointer 的空間 * 如果是實際上要配置的 page 不足，則透過 malloc 去配置新的空間 * 否則的話，檢查 `free_list` 是否有之前被釋放的節點可以配置，或者只是將現有的空間切出物件大小的部份分派出去 * `pool_free`: `pool_free` 不會真正的釋放 malloc 來的記憶體，而是把其掛在一個 linked-list 上，則下次需要再次 allocate 時，可以直接將這個位址回傳回去即可 * `pool_free_all`: 將整個 memory pool 配置的空間真正的釋放掉從目前的實作我們也可以思考其相對較佳的使用情境，應該是程式的執行時間內有大量的配置，並且搭配少量的釋放。在此情境下，程式可以受益於 memory pool 一次 allocate 更多的記憶體，減少 malloc 的呼叫，且對少量的釋放也可以不必直接呼叫 free，將記憶體暫時保留並且再利用。此外，為了同時也保留原本的實作以進行實驗，會透過編譯時期的參數決定是否使用 memory pool 配置 TST 節點。 ### 在 dict 中使用 memory pool 為整併 memory pool 的使用到原始程式中，做下列對應的修改： * 在 `tst.h` 新增物件的變數 `tst_node_pool`，並且在程式執行初期呼叫 `pool_init(&tst_node_pool, sizeof(tst_node), 0x1000)` 去初始化(`page_size` 設為 0x1000 並非最佳，需要再根據實驗去調整) * 將 `tst_ins_del` 中的 ```cpp if (!(*pcurr = calloc(1, sizeof **pcurr))) { fprintf(stderr, "error: tst_insert(), memory exhausted.\n"); return NULL; } ``` 替換成 ```cpp if (!(*pcurr = pool_alloc(&tst_node_pool))) { fprintf(stderr, "error: tst_insert(), memory exhausted.\n"); return NULL; } memset(*pcurr, 0, sizeof(**pcurr)); ``` * `tst_del_word` 中與節點相關的 `free` 都要更換的 `pool_free` * 釋放整個 TST 的 `tst_free_all`(CPY 下)，與 `tst_free`(REF 下) 也需進行對應調整: * 由於實際的字串和節點是透過不同的方式配置而來，因此需要做不同的處理。目前的作法是採走遍整個樹並釋放字串部份，最後再呼叫 `pool_free_all(&tst_node_pool)` 釋放所有配置的節點 * 對於 `tst_free` 的處理相對簡單，由於字串的部份已經透過 `test_common.c` 中的 `free(pool)` 釋放了，因此我們只要呼叫 `pool_free_all(&tst_node_pool)` 釋放整個 memory pool 即可，這個作法也間接使得 REF 版本的釋放不需要走過整個 TST 來一一釋放節點初步運行並使用沒有發現問題，透過 valgrind 來檢查 `tst_free` 和 `tst_free_all` 也沒有 memory leak，之後會再檢查是否有粗心遺漏的地方。 ### memory pool 的效益 memory pool 的使用如果搭配 REF 機制(也用另一個 memory pool 儲存字典檔中的字串)，則最大的效益可以體現在整釋放整個 TST 時。因為在釋放所有節點時，如果遍歷整個 TST，會因為節點記憶體空間的分散導致 cache-miss 嚴重。然而在使用 memory pool 搭配 REF 的機制下，由於只要各自釋放兩個 pool 本身即可，而不必重新搜尋整個 TST，可以大幅的降低 cache miss。 * 原始程式版本: ``` Performance counter stats for './test_common REF --cmd sTai' (100 runs): 2,879,100 cache-misses:u # 34.876 % of all cache refs ( +- 1.54% ) 8,255,177 cache-references:u ( +- 0.35% ) 0.13305 +- 0.00261 seconds time elapsed ( +- 1.96% ) ``` * 使用 memory pool 版本 ``` Performance counter stats for './test_common REF --cmd sTai' (100 runs): 970,211 cache-misses:u # 18.670 % of all cache refs ( +- 5.08% ) 5,196,748 cache-references:u ( +- 0.55% ) 0.11235 +- 0.00259 seconds time elapsed ( +- 2.31% ) ``` 不過比起釋放整個 TST，我們應該會更在意在新增、搜尋、刪除的表現上呢，下面設計不同的實驗來觀察此差距(都是在 REF 模式下測試)。首先實驗了 100000 筆隨機的新增或刪除操作的統計分佈結果(會確保新增的是隨機生成的字串，而刪除的是在字典檔中的字串，使得有真正對節點的操作)，並只累計新增和刪除操作的時間，重複 300 次後，所需時間的分佈結果。在下圖中也嘗試比較了 pre-allocate 不同大小記憶體的時間差異比較從時間來看，不同大小的 pre-allocate 在時間上的影響比較沒有太大的差異，但都相對於直接 malloc 有更好的時間優勢。 ![](https://i.imgur.com/lII3eNv.png) 在另一個實驗中，則測試搜尋這個操作的時間成本，使用字典檔中的 prefix 進行 1000 次的搜尋，並重複 300 次，得到的時間分佈則如下圖， ![](https://i.imgur.com/H85BEEp.png) 可以看到時間上的差異新增與刪除操作呈現的結果大致相同，memory pool 都有比較好的表現。 :::info :bell: 這裡的實驗是透過前面有提到的 isoplus + taskset 所做的，值得一提的是，在我使用此方法前，得到的結果相當不穩定。原本我認為進行足夠多次的實驗(例如上面的 300 次)然後排除 outlier 之後，得到的結果也應該不會太差，不過看起來在此系列實驗中並非如此。 ::: 追究其原因，我認為有可能是因為無論是新增、刪除、搜尋的操作，都需要走訪 TST 的節點，因此節點的 locality 就變得相當重要，而我觀察分配記憶體的地址，發現 malloc 每次分配的地址大致是 0x30 一數(即連續 malloc 的兩個節點地址差距最小是 0x30，而某些時候也可能會再更大一些)，然而實際上 `sizeof(tst_node)` 佔的空間是 0x20。這代表使用 malloc 分配出的節點與節點是有空隙的，導致每次進入 cache line 中的節點數量沒有最大化。需要做相應的實驗來驗證我的假設。 ## 改進程式碼 :::warning "optimize code" 翻譯為「改進程式碼」，而非「優化原始程式碼」，僅有原始程式碼有改進的必要，而非輸出的二進位檔案。 :notes: jserv ::: ### 讀取測試檔案在原始的程式碼中，可以看到一些原始的程式撰寫者為了進行實驗而置入的程式碼(包含某些寫檔、`--bench` 參數的使用等)。雖然我們也可以仿效這個作法，直接改寫程式內容來設計實驗，但是我更希望有一個可以輕鬆使用的介面，可以只是撰寫各種測試的檔案，就可以更方便的進行實驗。因此首先根據老師的建議使用 [getopt](https://www.gnu.org/software/libc/manual/html_node/Getopt.html)(實際上是用 `getopt_long` 因此可以保留長參數的使用) 改寫，可以接受兩個參數 * `--bench`、`-b`: 呼叫原本程式中的 `bench_test`。這個函式的功能是搜尋 `cities.txt` 的內容並且把執行時間寫檔，如果想要改寫程式來設計實驗，則可以直接去修改 `bench_test` 內的程式碼 * `--cmd`、`-c`: 這個參數是用來取代原本可以透過類似 `./test_common --bench CPY s Tai` 這樣的命令來做單次的 TST 操作，避免不同的功能對參數的混用造成混亂。更動後改成 `./test_common CPY --cmd sTai` 可以以達到同樣的效果 * 因為 `getopt` 本身的限制，及為了減少對輸入參數的混亂，`--cmd` 後的參數格式為: 第一個字元是對 TST 的操作(a、f、s 等)並直接接續參數字串(如果需要) * `--file`、`-f`: 後面加上檔案名稱作為參數，則可以 parsing 一個檔案並對 TST 進行相應操作，因此我們就可以單指令的進行一系列的操作實驗，再透過 perf 工具來檢視這些操作的影響 * 目前還沒有做防呆，所以必須依照指定格式撰寫實驗檔(逐行的字元位置 0 會是操作方式，字元位置 2 以後則是相應的字串(如果需要)) * 檔案的格式大致為： ``` s Tai f Taiwan a Wasteland f Wasteland q ``` ### :bug: BUG? 有了 `--file` 之後，我們就可以撰寫 python scirpt 產生隨機的測資來進行實驗了(可以參考 [randstrGenerator.py](https://github.com/RinHizakura/dict/blob/master/scripts/randstrGenerator.py))，然而我在測試的時候發現，進行多個單字串刪除的命令後(`d <name>`)，再呼叫 `tst_free_all` 或 `tst_free` 會出現 segmentation fault。經過測資的檢查之後，再回到原始版本的程式碼上測試，確定是原本的實作有問題: * 如果先 `d Gondal` 再 `d Guder` 再 `q` ，會出現 `Segmentation fault` * 如果是先 `d Guder` 再 `q`，會出現 `free(): double free detected in tcache 2` 目前認為錯誤的發生應該有兩種可能性: * 建立整個 TST 時就發生錯誤 * 在堆疊 tst_stack 時發生錯誤進一步透過 gdb 檢查後，發現了程式邏輯上的明顯錯誤： ```cpp if (victim->lokid && victim->hikid) { /* victim has both lokid/hikid */ ... } else if (victim->lokid) { /* only lokid, replace victim with lokid */ parent->eqkid = victim->lokid; free_node(victim); victim = NULL; } else if (victim->hikid) { /* only hikid, replace victim with hikid */ parent->eqkid = victim->hikid; free_node(victim); victim = NULL; } ``` 在 `tst_del_word` 階段，可以見到如上的程式已經假設了 victim 是 parent 的 eqkid，然後事實上卻並非如此，以我測試的測資來說，字典中僅有三筆資料 *註: 這裡的 `free_node` 是根據編譯時期參數去決定呼叫 `free` 還是 `pool_free` 來釋放節點的封裝* ``` Guderm Guder Guderhandviertel ``` 建立出的 TST 結構大致如下: ```graphviz digraph g{ splines=false; node[shape=record] G [label=" | G | "] u [label=" | u | "]; d [label=" | d | "]; e [label=" | e | "]; r [label=" | r | "]; m [label="<f0> | m | <f1>"]; h [label="<f0> | h | <f1>"]; a [label="<f0> | a | <f1>"]; NULL[label=" <f0>| <f1> \\0 | <f2>"]; NULL2[label=" | \\0 | "]; dot[label="...",shape=plaintext]; invis1[style=invisible]; invis2[style=invisible]; Guder[label="Guder"] Guderm[label="Guderm"] G->u->d->e->r->m->NULL2 m:f0->NULL:n m:f1->invis1:n NULL:f1->Guder NULL2->Guderm NULL:f0->invis2 NULL:f2->h->a a->dot } ``` 在刪除 Guder 時，其 `parent->eqkid` 並非自己，而是 `parent->lokid` 才是，可以對照下面的 gdb 訊息 ``` (gdb) p parent $55 = (tst_node *) 0x55555555da10 (gdb) p victim $56 = (tst_node *) 0x55555555da90 (gdb) p parent->eqkid $57 = (struct tst_node *) 0x55555555da40 (gdb) p parent->lokid $58 = (struct tst_node *) 0x55555555da90 ``` 因此，我將原始程式的此部份去做修正，對該 victim 實際上是 parent 的哪一個 kid 去做檢查，將該段落修正為: ```cpp #define del_node(parent, victim, root, kid) \ do { \ if (!parent) { \ *root = kid; \ } else { \ if (victim == parent->lokid) \ parent->lokid = kid; \ else if (victim == parent->hikid) \ parent->hikid = kid; \ else \ parent->eqkid = kid; \ } \ free_node(victim); \ victim = NULL; \ } while (0) ... if (victim->lokid && victim->hikid) { /* victim has both lokid/hikid */ ... } else if (victim->lokid) { /* only lokid, replace victim with lokid */ del_node(parent, victim, root, victim->lokid); } else if (victim->hikid) { /* only hikid, replace victim with hikid */ del_node(parent, victim, root, victim->hikid); } ``` 原始的程式碼其實在其他的 branch 都有做相應的檢查，而這兩個 else if 可能是不小心忽略了，也因為這個檢查在刪除的過程中被頻繁的使用，為避免產生太多重複的程式碼，並且根據老師的建議考慮到程式的可讀性，因此這裡我用一個如上述 macro 來包裝。