# prefix-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。
:::info
一開始，trie tree 起始於一個空的root - ◎
:::
```
◎
```
:::info
若今插入一個字串 and
1. 首先將 and 拆解成 a, n ,d
2. 因為 a 第一次出現，所以在 root 建立一個新children node ,value= a
3. 接下來從node "a" 出發，剩下 n,d
4. n 也是第一次出現,因此在 a 建立一個新 children node ,value= n
5. d 比照 4 作法。
:::
```
◎
/
a
/
n
/
d
```
:::info
若此時插入一個字串 ant
1. ant 拆解成 a , n , t，從 root 出發
2. node "a" 已經存在，因此不再在 root 創造新的 children
3. 再來看 n , node "a" 往 children 看發現 node "n"已存在，因此也不創造 children
4. 再來看 t 發現 n 的 children 中沒有此 node，因此創造新 children "t"
:::
```
◎
/
a
/
n
/ \
d t
```
:::info
如此再插入 bear ,bea 就會產生像這樣子的 tree
1. 有 value 的就是有 string 存在的 node
2. 因此 search "ant" 會 return 值 0 ，表示 trie 內有此string
3. 而 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 個)
### Ternary search tree (TST)
因此用此 Ternary search tree ，就能解決上面的問題。這種樹的每個節點最多只會有3個 children，分別代表小於，等於，大於。以下範例解釋 Ternary search tree 。
:::info
插入一個字串 and
1. 與 trie 概念相同，但是在root 是直接擺 "a" 而不需要一個null 。
:::
```
a
|
n
|
d
```
:::info
接著插入單字ant
1. 我們先比對 a ，發現 a 和 root 的字母相同（a=a）
2. 因此 pointer 往下，來到 n 節點，發現 n 節點和 ant 的第二個字母相同（n=n）
3. 因此 pointer 再往下，來到 d 節點，發現 d 節點和 ant 的第三個字母不同，而且 **t>d**
4. 因此 d 節點的 right child 成為 t ，成功將 ant 放入原本的 TST 中
:::
```
a
|
n-
| |
d t
```
:::info
接著插入單字age
1. 我們先比對 a ，發現 a 和 root 的字母相同（a=a)
2. 因此 pointer 往下，來到 n 節點，發現 n 節點和 age 的第二個字母不同，而且 **g<n**
3. 因此 n 節點的 left child 成為 g ，成功將 age 放入原本的 TST 中
:::
```
a
|
-n
| |
g d-
| |
e t
```
[ Ternary Search Tree ](https://www.cs.usfca.edu/~galles/visualization/TST.html) 此網址提供了用動畫表示的方式，可以清楚看到如何加入與刪除 string 的流程。
從 Ternary Search Tree 中，我們可以發現幾種特性。
1. 解決 trie tree 中大量佔用記憶體的情況，因為 TST 中，每個 node 最多只會有3個 child
2. 但尋找時間在有些 case 中 ， 會比 trie 慢 ，而這是因為 TST 插入的順序會影響比較的次數。例如以下兩張圖，上圖是用 `aa->ac->ae->af->ag->ah` 的次序插入，而下圖是 `af->ae->ac->aa->ag->ah`的順序。試想今天要尋找 ah ，則上圖要比較6次，下圖則是只要比較3次。而若是建立 trie ，只需要2次。
## 程式碼分析
### 修改 test_ref.c
參考[ tina0405 ](https://hackmd.io/s/SkEFpwh2-#)。
找尋 test_ref.c 中的註解fixme，因為我們是希望比較兩種方式 (copy/reference) 的效能，所以應該做以下更動
```clike
- 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 ，因此都是指向同一塊記憶體空間。
```clike=
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 ](https://hackmd.io/s/SkEFpwh2-#)，
* 新增一新的二元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 』嗎？[name=洪培軒]
```clike=
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);
```
如此一來，程式就能執行正確。但又遇上另外兩個問題，
1. quit 時印出錯誤訊息`free(): invalid pointer: 0x00007fff194808b0` ，然後就會 core dumped 。
2. 此外當我 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。
```clike=
-tst_free_all(root);
+tst_free(root)
```
解決2：這次發現問題出在 tst_ins_del() 中，`return tst_del_word(root, curr, &stk, 1);`這行，發現最後一個 argument 是 1 , 將它改成cpy，發現程式可正常 delete ，解決問題2。
```clike=
-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)
```
因為原本的程式必須要透過使用者手動輸入才能運作下去，但這對於效能分析需要多次的執行十分的不方便，因此我想到可以有三種寫法。
1. 透過寫腳本的方式讓程式可以自動輸入，餵給 scanf。
2. 修改程式架構，讓原本要用 scanf 輸入的參數能以 argument command line 的方式傳入。
3. 修改程式架構，在程式一開始偵測若是 benchmarking 模式，就進入自己宣告的 function 先做一些初始化，擴充度較高，因為若是日後想要做 a~z 開頭的 prefix 都搜尋一次，就在程式內呼叫這個 function 改變輸入的資料即可。
在查詢1.解法的時候，網路上查找關鍵字`script`大部份是 shell script 的資料，不知道能不能適用在此處的自動輸入 scanf ，因此決定先用2. 的解法。
> 可以用 `<` 以 file 作為 stdin, 關鍵字: bash redirect
> 也可以改用 fscanf 將 stdin 改為 file pointer
> [name=ryanpatiency][color=green]
>>好的，感謝指教。
>>[name=rex662624][color=#662624]
程式碼修改為，只要有 --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](http://man7.org/linux/man-pages/man3/strdup.3.html)，而這個指令隱含著 malloc 的動作。而 ref 的版本是一塊連續的記憶體，因為我用二維陣列去宣告它。而因為 cache 的 spatial locality 特性，會將許多目前不需要 access 到的 data 一起更新到 cache ，因此造成 cache miss rate 較高。
再者，用固定大小去宣告 array ， 會有 memory fragmentation 的問題，因為不一定每個 city 都會把分配到的空間使用完全。
### 引入 memory pool
#### memorypool 實作 1
在上個作業，我已經有把 memory pool 引入，因此參考[自己](https://github.com/rex662624/phonebook)，引入 memory pool 的功能。
memory pool 的概念是先要一塊夠大的記憶體，爾後就不用再跟系統要，直接從這塊記憶體切一小塊下來用就好。
```clike=
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
```clike=
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 ](https://hackmd.io/s/ByeocUhnZ#)，實做出 memorypool ，與上面的版本不同之處在於，上面的版本是做成一個個的 function 去呼叫，而這個版本只有簡單的兩個指標，一個指向 memorypool 整體，一個 Top 指向目前要分配出去的記憶體位置。
```clike=
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 ](https://hackmd.io/mI8HxMMJRqy_I2BmDzZWAQ#)[(github)](https://github.com/tina0405/prefix-search)的實驗，因為這位同學實做 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 看看為什麼效能能如此卓越。
```clike=
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();
```
這裡卻發現了兩個錯誤。
1. 第三行用 sizeof(word) ，那跟宣告固定大小的陣列是無異的。我們 word 的宣告是用 `char word[WRDMAX]`，這樣 sizeof(word) 每次都是跟 pool 要 WRDMAX (= 256) byte，失去動態宣告的意義。應該改為 strlen(word) 。
2. 這位同學用`fscanf(fp, "%s", word)`把字串存進 word 裡面，在下面用指標 p 指向 pool 切下來的那塊 memory，然後就把 &p 傳進去了，這樣資料就丟失了。fscanf 進來的資料沒有被 insert 進 tree 中，我想這就是 cycle 數如此低的原因，因為資料沒存進去 tree 中 ，所以完全不需要走訪，不管怎麼 search 都不會找到資料。因此需要再多一道 `strcpy(p,word);` ，而我在 memory pool 實做1已經做過並提出效能不足的地方。
也有可能只是這位同學沒有上傳正確的 code ，或是我搞錯了什麼也不一定。因此決定還是先回到自己的實驗照實分析自己的數據。
#### search 效能分析
參考[ kevin550029 ](https://hackmd.io/s/HJwsLH16Z#)，在這裡我把測試資料設為取出所有 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 {\pm} z \cdot\dfrac{s}{\sqrt{n}}$==
- **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 ](https://en.wikipedia.org/wiki/Callback_(computer_programming))， 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 是使用者自訂的函式。因此應用可以為
1. debug用，透過印出每個 node 資訊，知道每個 node 詳細狀況。
2. 觀察資料結構，可以知道整個 tree 是怎麼排列的。
3. 效能量測，例如可以量測 CPY 還有 REF 版本走訪整棵 tree 的時間比較。
## reference
* [twngbm 的 Hackmd ](https://hackmd.io/s/rJKkryGpb#Ternary-search-tree-%E4%BB%8B%E7%B4%B9)
* [Ternary Search Tree](https://www.cs.usfca.edu/~galles/visualization/TST.html)
* [演算法筆記](http://www.csie.ntnu.edu.tw/~u91029/String.html#6)
* [ChiuYiTang 的 Hackmd ](https://hackmd.io/s/ByeocUhnZ#)
* [kevin550029](https://hackmd.io/s/HJwsLH16Z#)
Sign in with Wallet
Connect another wallet