HackMDprefix-search
contributed by < rex662624 >
系統環境
$lscpu
Architecture: x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
每核心執行緒數： 1
每通訊端核心數： 4
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 94
Model name: Intel(R) Core(TM) i5-6300HQ CPU @ 2.30GHz
製程： 3
CPU MHz： 2300.000
CPU max MHz: 3200.0000
CPU min MHz: 800.0000
BogoMIPS: 4608.00
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 6144K
NUMA node0 CPU(s): 0-3
何謂 Ternary search tree
Ternary search tree 是一種字典樹（trie），以下將先介紹何謂 trie 。
trie
trie 與 binary search tree 不同在於，不是把整個字串包在同一個node 中 ，而是根據 node 的位置決定代表的字串為何。也就是一個看結果( 最終 node )，一個看過程(經過的node)。因此利用 trie，可以快速的找出有相同 prefix 的字串。以下將舉例示範 trie 如何儲存 data。
一開始，trie tree 起始於一個空的root - ◎
◎
若今插入一個字串 and
- 首先將 and 拆解成 a, n ,d
- 因為 a 第一次出現，所以在 root 建立一個新children node ,value= a
- 接下來從node "a" 出發，剩下 n,d
- n 也是第一次出現,因此在 a 建立一個新 children node ,value= n
- d 比照 4 作法。
◎
/
a
/
n
/
d
若此時插入一個字串 ant
- ant 拆解成 a , n , t，從 root 出發
- node "a" 已經存在，因此不再在 root 創造新的 children
- 再來看 n , node "a" 往 children 看發現 node "n"已存在，因此也不創造 children
- 再來看 t 發現 n 的 children 中沒有此 node，因此創造新 children "t"
◎
/
a
/
n
/ \
d t
如此再插入 bear ,bea 就會產生像這樣子的 tree
- 有 value 的就是有 string 存在的 node
- 因此 search "ant" 會 return 值 0 ，表示 trie 內有此string
- 而 search "be" 會 retrun NULL ， 因為並沒有值在 node "e"。
◎
/ \
a b
/ \
n e
/ \ \
d t a (3)
(0) (1) \
r (2)
以上，我們注意到 Trie 中，若有儲存的字串有許多相同的 prefix ，那麼 trie 可以節省大量儲存空間，因為 Trie 中每個字串都是經由 character by character 方法進行儲存，所以具有相同 prefix 的部份都會有共同的 node 。
相對的，若是資料非常大量，而且幾乎沒有相同的 prefix 將會非常浪費儲存空間。因為 trie 在 memory 的 儲存方式其實是像下圖這樣，每個 node 建立時，都必須同時創造26個值為NULL的子節點。(下圖的 universal set ={a,b,c,d,e}5所以只創造了 5 個)
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Ternary search tree (TST)
因此用此 Ternary search tree ，就能解決上面的問題。這種樹的每個節點最多只會有3個 children，分別代表小於，等於，大於。以下範例解釋 Ternary search tree 。
插入一個字串 and
- 與 trie 概念相同，但是在root 是直接擺 "a" 而不需要一個null 。
a
|
n
|
d
接著插入單字ant
- 我們先比對 a ，發現 a 和 root 的字母相同（a=a）
- 因此 pointer 往下，來到 n 節點，發現 n 節點和 ant 的第二個字母相同（n=n）
- 因此 pointer 再往下，來到 d 節點，發現 d 節點和 ant 的第三個字母不同，而且 t>d
- 因此 d 節點的 right child 成為 t ，成功將 ant 放入原本的 TST 中
a
|
n-
| |
d t
接著插入單字age
- 我們先比對 a ，發現 a 和 root 的字母相同（a=a)
- 因此 pointer 往下，來到 n 節點，發現 n 節點和 age 的第二個字母不同，而且 g<n
- 因此 n 節點的 left child 成為 g ，成功將 age 放入原本的 TST 中
a
|
-n
| |
g d-
| |
e t
Ternary Search Tree 此網址提供了用動畫表示的方式，可以清楚看到如何加入與刪除 string 的流程。
從 Ternary Search Tree 中，我們可以發現幾種特性。
- 解決 trie tree 中大量佔用記憶體的情況，因為 TST 中，每個 node 最多只會有3個 child
- 但尋找時間在有些 case 中 ， 會比 trie 慢 ，而這是因為 TST 插入的順序會影響比較的次數。例如以下兩張圖，上圖是用
aa->ac->ae->af->ag->ah的次序插入，而下圖是af->ae->ac->aa->ag->ah的順序。試想今天要尋找 ah ，則上圖要比較6次，下圖則是只要比較3次。而若是建立 trie ，只需要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
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
程式碼分析
修改 test_ref.c
參考 tina0405 。
找尋 test_ref.c 中的註解fixme，因為我們是希望比較兩種方式 (copy/reference) 的效能，所以應該做以下更動
- tst_ins_del(&root, &p, INS, CPY)
+ tst_ins_del(&root, &p, INS, REF)
然而 compile 後再 run 一次，發現答案是錯誤的。
choice: s
find words matching prefix (at least 1 char): Tain
Tain - searched prefix in 0.000008 sec
suggest[0] : Tain
suggest[1] : Tain
suggest[2] : Tain
suggest[3] : Tain
suggest[4] : Tain
suggest[5] : Tain
suggest[6] : Tain
suggest[7] : Tain
suggest[8] : Tain
suggest[9] : Tain
suggest[10] : Tain
suggest[11] : Tain
因此來到呼叫的 tst_ins_del() 內觀察，在這裡注意我們改變了最後一個參數，從 CPY 改成 REF ，我們用 enum 與 marco 分別把 REF 與 CPY 宣告為0和1，因此傳入這裡的最後一個 argument 等同是 1 。觀察註解，看到了這行 if 'cpy' is non-zero allocate storage for 's', otherwise save pointer to 's'. 這裡的 parameter "s" 是要插入 tree 的 string ，觀察以下code發現，若是傳入的是 REF 會進入 else ，然而else 是直接指向 *s ，因此都是指向同一塊記憶體空間。
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;
}
}
因此決定參考 tina0405 ，
- 新增一新的二元array，來儲存所有產生的節點
- 原本的程式有259111個城市，若宣告成
word2[259111][WRDMAX]一執行就會 core dumped ，因此決定縮減 cities.txt 裡面成前5000行，總共12703個 cities 。我覺得 core dumped 的講法怪怪的，core dump 指的是系統產生 core dump file 這件事。你想要敘述的應該是程式發生的錯誤，但是 core dump 應該不算錯誤吧？如果有時候 core dump file 因為權限或是空間限制之類的問題而沒有被生成，依然要說是『會 core dumped 』嗎？洪培軒
int count=0 ;
char word2[20000][WRDMAX];
while ((rtn = fscanf(fp, "%s", word2[count])) != EOF) {
char *p = word2[count++];
/* FIXME: insert reference to each string */
if (!tst_ins_del(&root, &p, INS, REF)) {
fprintf(stderr, "error: memory exhausted, tst_insert.\n");
fclose(fp);
return 1;
}
idx++;
}
t2 = tvgetf();
printf("total city:%d\n",count-1);
fclose(fp);
printf("ternary_tree, loaded %d words in %.6f sec\n", idx, t2 - t1);
如此一來，程式就能執行正確。但又遇上另外兩個問題，
- quit 時印出錯誤訊息
free(): invalid pointer: 0x00007fff194808b0，然後就會 core dumped 。 - 此外當我 delete "Austria" 時，第一次會印出
Austria (refcnt: 4) not removed.然後印出Austria (refcnt: 3) not removed.…直到 refcnt 應該將變為0，就會 core dumped。這表示若把某 string 從 tree 中完全抹除就會產生此狀況。
解決1： 用 gdb 觀察發現問題出在tst_free_all(root); 因此進一步看看此函式裡面做了什麼。發現它會做free(p->eqkid)，free 到儲存字串的位置，發現下面剛好有個tst_free(tst_node *p)沒有做這件事，因此改呼叫此函式。發現結果能正常 quit ，解決問題1。
-tst_free_all(root);
+tst_free(root)
解決2：這次發現問題出在 tst_ins_del() 中，return tst_del_word(root, curr, &stk, 1);這行，發現最後一個 argument 是 1 , 將它改成cpy，發現程式可正常 delete ，解決問題2。
-tst_del_word(root, curr, &stk, 1);
+tst_del_word(root, curr, &stk, cpy);
至此，已經完成基本修改，因此先做效能比較。
修改 Makefile 與程式架構以做效能比較
首先，因為要透過 perf 分析效能，所以必須修改 Makefile ， 而上一個 phonebook 作業的 Makefile 也已有此功能，因此修改一下就能用。
TESTS = test_cpy test_ref
TEST_DATA = s Tai
test: $(TESTS)
echo 3 | sudo tee /proc/sys/vm/drop_caches;
perf stat --repeat 100 \
-e cache-misses,cache-references,instructions,cycles \
./test_ref --bench $(TEST_DATA)
perf stat --repeat 100 \
-e cache-misses,cache-references,instructions,cycles \
./test_cpy --bench $(TEST_DATA)
因為原本的程式必須要透過使用者手動輸入才能運作下去，但這對於效能分析需要多次的執行十分的不方便，因此我想到可以有三種寫法。
- 透過寫腳本的方式讓程式可以自動輸入，餵給 scanf。
- 修改程式架構，讓原本要用 scanf 輸入的參數能以 argument command line 的方式傳入。
- 修改程式架構，在程式一開始偵測若是 benchmarking 模式，就進入自己宣告的 function 先做一些初始化，擴充度較高，因為若是日後想要做 a~z 開頭的 prefix 都搜尋一次，就在程式內呼叫這個 function 改變輸入的資料即可。
在查詢1.解法的時候，網路上查找關鍵字script大部份是 shell script 的資料，不知道能不能適用在此處的自動輸入 scanf ，因此決定先用2. 的解法。
可以用
<以 file 作為 stdin, 關鍵字: bash redirect
也可以改用 fscanf 將 stdin 改為 file pointer
ryanpatiency好的，感謝指教。
rex662624
程式碼修改為，只要有 –bench 選項就會偵測後面的兩個 argument並執行完，例如鍵入./test_cpy --bench s Tai則表示 "以benchmarking 模式" 執行 "search" 以 "Tai" 為prefix 的所有城市，這裡的程式碼是strcmp(argv[1],"--bench")==0。
而只加了這個功能還不夠，因為整個程式是用 for(;;) 包住，執行完一個功能後會再問使用者再來要執行哪個選項，因此必須有一個機制讓第一次搜尋完之後就能跳到 quit ，這裡我是用 label的方式做解，在執行完 search 後若是benchmarking模式，就直接跳到 case q 執行而不要 break 。
以下是各執行1000次的結果
Performance counter stats for './test_cpy -a s Tai' (1000 runs):
27,714 cache-misses # 7.159 % of all cache refs ( +- 1.61% )
387,131 cache-references ( +- 0.06% )
31,125,263 instructions # 1.69 insn per cycle ( +- 0.00% )
18,461,756 cycles ( +- 0.05% )
0.006802493 seconds time elapsed ( +- 0.37% )
Performance counter stats for './test_ref -a s Tai' (1000 runs):
114,547 cache-misses # 22.465 % of all cache refs ( +- 0.41% )
509,896 cache-references ( +- 0.05% )
31,007,880 instructions # 1.47 insn per cycle ( +- 0.00% )
21,086,508 cycles ( +- 0.05% )
0.007814856 seconds time elapsed ( +- 0.28% )
以上可以看出 cpy 版本較 ref 版本 ，cache miss rate 低上許多。
這是因為 cpy 版本用到的是 strdup，而這個指令隱含著 malloc 的動作。而 ref 的版本是一塊連續的記憶體，因為我用二維陣列去宣告它。而因為 cache 的 spatial locality 特性，會將許多目前不需要 access 到的 data 一起更新到 cache ，因此造成 cache miss rate 較高。
再者，用固定大小去宣告 array ， 會有 memory fragmentation 的問題，因為不一定每個 city 都會把分配到的空間使用完全。
引入 memory pool
memorypool 實作 1
在上個作業，我已經有把 memory pool 引入，因此參考自己，引入 memory pool 的功能。
memory pool 的概念是先要一塊夠大的記憶體，爾後就不用再跟系統要，直接從這塊記憶體切一小塊下來用就好。
pool = pool_init(poolsize);//要一塊大空間
while ((rtn = fscanf(fp, "%s",word)) != EOF) {
char *p = pool_alloc(pool,strlen(word)+1);//切一塊word長度的空間
strcpy(p,word);
/* FIXME: insert reference to each string */
if (!tst_ins_del(&root, &p, INS, REF)) {
fprintf(stderr, "error: memory exhausted, tst_insert.\n");
fclose(fp);
return 1;
}
idx++;
}
以上是 code ，以下做 perf 比較：(同樣用 cities5000.txt ，cities.txt 裡面的前5000行)
Performance counter stats for './test_ref --bench s Tai' (100 runs):
26,430 cache-misses # 6.793 % of all cache refs ( +- 4.54% )
389,072 cache-references ( +- 0.19% )
29,954,352 instructions # 1.63 insn per cycle ( +- 0.01% )
18,421,456 cycles ( +- 0.09% )
0.007204022 seconds time elapsed ( +- 3.91% )
發現的確比原本用二維陣列宣告做出的 test_ref 效能要高，而跟 test_cpy (7.159 %)比起來0.3 % 好像不算太顯著的提昇，但 memory pool 的優勢應該是在不需要每次和記憶體要空間，所以接下來應該做的效能比較是觀察兩者的插入資料時間，這裡預測應該 ref 就會遠優於 cpy版本。
另外在做實驗時，我本來加入了把插入資料的時間儲存在檔案中的 code
FILE *output;
output = fopen("ref.txt", "a");
if(output!=NULL)
{
fprintf(output, "%.6f\n",t2-t1);
fclose(output);
}
else
printf("open file error\n");
但發現執行後 cache miss 上升為16.125 % ，幾乎是本來的實驗數據的3倍，後來註解掉就下降為正常數據，因此做任何 code 更動時都要想一下是否會對效能展生影響。
以下是觀察兩者的插入資料時間的比較，我的預測是 ref 會遠優於 cpy 版本。
結果卻與我預測的不同，兩者插入資料的時間是差不多的，甚至 ref 還高一點。而我推測是因為strcpy(p,word);這個指令花掉的時間，讓整體速度與 cpy 版本差不多，因此思考不需多這一個 copy 動作，而是直接就存進 p 當中的辦法。因此有了下面的實做2。
memorypool 實做 2
參考 ChiuYiTang 的 Hackmd ，實做出 memorypool ，與上面的版本不同之處在於，上面的版本是做成一個個的 function 去呼叫，而這個版本只有簡單的兩個指標，一個指向 memorypool 整體，一個 Top 指向目前要分配出去的記憶體位置。
char *pool = (char malloc(poolsize * sizeof(char));
char *Top = pool;
while ((rtn = fscanf(fp, "%s",Top)) != EOF) {
t1 = tvgetf();
char *p = Top;
/* FIXME: insert reference to each string */
if (!tst_ins_del(&root, &p, INS, REF)) {
fprintf(stderr, "error: memory exhausted, tst_insert.\n");
fclose(fp);
return 1;
}
idx++;
Top += (strlen(Top) + 1);
t2 = tvgetf();
total+=(t2-t1);
}
// t2 = tvgetf();
fclose(fp);
printf("ternary_tree, loaded %d words in %.6f sec\n", idx,total);
效能分析的部份把t1 = tvgetf(); ,t2 = tvgetf();包在 insert 動作之外就好，不要連 fscanf 的 i/o 時間都算進來，最後印出total，發現這次 ref 的時間小於 cpy 的時間。
ref 和 cpy 兩者做 search 的效能分析
重現實驗
在做這個部份時，我一直想重現 tina0405 (github)的實驗，因為這位同學實做 memory pool 的效能遠超於我的，他的實驗中 ref 版本 cycle 數也十分的低，但我在測試我做的兩個版本的 memory pool 卻都不如這位同學的效能，因此想看看其中的差異到底在哪。
在 clone 他的專案到我的 local 端後，首先跑 make 發現他的 #define POOL_SIZE 後面沒宣告數字，再來 testbench.c 中要用的 cities_new.txt 也不在 github 上。但我相信只是這位同學沒把正確的 code commit ，或是後來又再改動。因為這樣是連 run 都不能 run ，何況是作效能比較。改正#define POOL_SIZE 2560000 與把 cities_new.txt 改為 cities_3000.txt 後 make bench 會輸出兩個檔案 out_ref.txt 和 out_cpy.txt。果然發現 ref的 cycle 數遠小於 cpy 版本。
於是進到他的 code 看看為什麼效能能如此卓越。
t1 = tvgetf();
while ((rtn = fscanf(fp, "%s", word)) != EOF) {
char *p = pool_access( poolmemory , sizeof(word));
// printf("%ld\n",sizeof(word));
/* FIXME: insert reference to each string */
if (!tst_ins_del(&root, &p, INS, REF)) {
fprintf(stderr, "error: memory exhausted, tst_insert.\n");
fclose(fp);
return 1;
}
idx++;
}
t2 = tvgetf();
這裡卻發現了兩個錯誤。
- 第三行用 sizeof(word) ，那跟宣告固定大小的陣列是無異的。我們 word 的宣告是用
char word[WRDMAX]，這樣 sizeof(word) 每次都是跟 pool 要 WRDMAX (= 256) byte，失去動態宣告的意義。應該改為 strlen(word) 。 - 這位同學用
fscanf(fp, "%s", word)把字串存進 word 裡面，在下面用指標 p 指向 pool 切下來的那塊 memory，然後就把 &p 傳進去了，這樣資料就丟失了。fscanf 進來的資料沒有被 insert 進 tree 中，我想這就是 cycle 數如此低的原因，因為資料沒存進去 tree 中 ，所以完全不需要走訪，不管怎麼 search 都不會找到資料。因此需要再多一道strcpy(p,word);，而我在 memory pool 實做1已經做過並提出效能不足的地方。
也有可能只是這位同學沒有上傳正確的 code ，或是我搞錯了什麼也不一定。因此決定還是先回到自己的實驗照實分析自己的數據。
search 效能分析
參考 kevin550029 ，在這裡我把測試資料設為取出所有 input 檔中城市的前三個字元(若城市名稱本來就小於 3 就先不取)，並用這三個字元作為 prefix 加以 search ，最後測量執行時間。
以下為效能分析圖，因為兩個版本資料混在一起較難以觀察，故做成 gif 形式以觀察。
橫軸為測試資料的編號，縱軸為執行的時間，單位為秒數。可以大致看到 ref 版本資料較分散，而 cpy 版本則是對絕大多數的資料都保持著 350 sec 以下的搜尋時間。此外也可大致看出 ref 版本的搜尋時間大於 cpy 版本。
以下用 gnuplot 內建的分析指令做進一步分析。
$gnuplot
$stats "bench_ref.txt" using 2
$stats "bench_cpy.txt" using 2
cpy版本(單位：sec) ref版本(單位：sec)
Mean: 77.7579 88.1680
Std Dev: 85.7190 97.7437
Sample StdDev: 85.7225 97.7477
Skewness: 2.2209 2.3286
Kurtosis: 9.9791 10.9175
Avg Dev: 63.0210 71.0939
Sum: 947712.8982 1.07459e+06
Sum Sq.: 1.63246e+08 2.11187e+08
Mean Err.: 0.7764 0.8854
Std Dev Err.: 0.5490 0.6260
Skewness Err.: 0.0222 0.0222
Kurtosis Err.: 0.0444 0.0444
Minimum: 0.2384 [10152] 0.4768 [ 1127]
Maximum: 660.1810 [ 8375] 792.5034 [ 3932]
Quartile: 20.0272 22.4113
Median: 45.0611 52.2137
Quartile: 113.7257 127.0771
The Confidence Interval formula is
- X is the mean
- Z : 95% 時 z = 1.960
- s is the standard deviation
- n is the number of samples (我的 sample 數總共12188)
由以上推導出 :
CPY版本 95% 信賴區間: 77.7579 ± 1.5 (sec)
REF版本 95% 信賴區間: 88.1680 ± 1.7 (sec)
因此觀察到，REF 版本的 MEAN (平均數) 、 兩個 Quartile (第1四分位數與第3四分位數)都比 CPY 來得高。同時標準差也比較大，表示 REF 版本的分散程度較大，漲跌較劇烈。
因此總結效能比較， insert 的效率因為使用 memory pool 的原因，REF的效能較好。而 cache miss 則有微幅下降的情況。 search 的效能 ，則是有微幅下降的狀況。
tst_traverse_fn
根據維基百科定義 callback function ， callback is any executable code that is passed as an argument to other code 。例如一個 function 透過 function pointer 的方式，作為 argument 傳入另一個 function ，就為此類範疇。
而程式中的 tst_teaverse_fn ，就利用到 callback 的機制。此函式會走訪每個 tree上的 node ，並把走訪 node 傳進 fn 裡面，這個 fn 是使用者自訂的函式。因此應用可以為
- debug用，透過印出每個 node 資訊，知道每個 node 詳細狀況。
- 觀察資料結構，可以知道整個 tree 是怎麼排列的。
- 效能量測，例如可以量測 CPY 還有 REF 版本走訪整棵 tree 的時間比較。
