# 2018q1 Homework2 (prefix-search)
contributed by <`t5i0m7`>
## 開發環境
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
供應商識別號： AuthenticAMD
CPU 家族： 21
型號： 16
Model name: AMD A10-5800K APU with Radeon(tm) HD Graphics
製程： 1
CPU MHz： 1400.000
CPU max MHz: 3800.0000
CPU min MHz: 1400.0000
BogoMIPS: 7599.92
虛擬： AMD-V
L1d 快取： 16K
L1i 快取： 64K
L2 快取： 2048K
NUMA node0 CPU(s): 0-3
```
## Ternary search tree
這次的重點放在ternary search tree這個資料結構該怎麼做insert、delete、search等行為，並透過了解其演算法修改prefix-search裡的code，並比較裡面code兩種不同資料儲存分配方法的效能。
* Ternary search tree 視覺化
透過共筆上提供的線上[視覺化工具](https://www.cs.usfca.edu/~galles/visualization/TST.html)和網路上的一些資料像是[維基百科](https://en.wikipedia.org/wiki/Ternary_search_tree)可以了解到這個資料結構是怎麼做insert和search的動作。
```
o
|-c
|-0
------------+------------
|lokid |eqkid |hikid
o o o
|-a
|-0
----+----
| | | note: any of the lokid or hikid nodes
o can also have pointers to nodes
|-t for words that "cat" or "ca" is
|-0 a partial prefix to.
----+----
| | |
o
|-0
|-1 <== the refcnt is only relevant to the final node
----+----
| | |
NULL o NULL
"cat"
```
上述圖是由prefix-search裡的readme提供，當要搜尋一串字串時，字母由第一個字進入root node並與node裡的key進行比較，相等、大於、小於會去進入對應的node，噹當有相等的情形發生，將會比對字串下一個字，直到結尾字元。如果直到結尾字元都有直表示此字串在這個ternary search tree裡是存在的，並在eqkid的指標填入字串位置。
* TST node 結構
以這次prefix search tree一個Ternary search tree node裡的element包含四個東西，key、refcnt、hikid、lokid、edkid。
:::info
key -> 每個node裡都會存一個character當作key來搜尋
refcnt -> 當final word時就會為1
lokid -> 比目前node key level還低的key的node
hikid -> 比目前node key level還高的key的node
eqkid -> 當符合Key下一個接的node
:::
:::warning
在insert的function裡這段code不太符合insert的方法，在readme有提到refcnt為1的情況是此node的key為結尾字元
```clike
curr = *pcurr;
curr->key = *p;
curr->refcnt = 1;
curr->lokid = curr->hikid = curr->eqkid = NULL;
```
由上code可看出在每次新增節點時都會令refcnt為1，不過基本上不影響code的運行，因為在判斷字串結尾時已經不是用refcnt來進行判斷，從search function可以知道判斷結尾已改成判斷自尾相減為0且字尾字元為結尾字元
:::
## test_ref裡的BUG
首先要更改存在test_ref裡Fix me的地方，看到tst\_ins\_del(&root, &p, INS, CPY);可以想到跟傳進去的參數CPY有關，畢竟這個程式的命名就跟REF有關於是我直接改成tst\_ins\_del(&root, &p, INS, CPY)
```
choice: s
find words matching prefix (at least 1 char): Tain
Tain - searched prefix in 0.000011 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
```
很悲劇的，程式能用但結果跟test_cpy差異很大，於是再細看tst\_ins\_del這條function裡寫了啥，有可能是REF這個參數的變化改變了哪些條件，於是找到下方的code，這是tst\_ins\_del裡的一段
```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;
}
}
```
這段code指的是當字串要插入最後一個結尾字元發生的事，可以看出用CPY可以決定eqkid接的完整字串複製方式。當使用CPY參數時，是直接allocate一段空間來塞入字串，而使用REF參數值是將讀到的字串首位reference到eqkid，但這個讀進來的字串fscanf存入的變數位置的是一樣的，導致每個有結尾字串node的eqkid的reference都相同,這也影響到prefix-search的function。
* 解決方法
在test_ref讀入程式資料時使用static array來儲存資料，reference到的資料都有一塊空間能使用，為了方便之後比較我使用，我將字串word改為二維矩陣char word\[CITY_NUM\]\[WRDMAX\]，其中最大字串大小為128、城市資料大小為30000筆，這樣就能解局Fix Me區域內的Bug，實際運作為下
```
choice: s
find words matching prefix (at least 1 char): Ame
Ame - searched prefix in 0.000015 sec
suggest[0] : Ameca,
suggest[1] : Americana,
suggest[2] : Amersfoort,
suggest[3] : Ames,
```
當用先宣告一個二為矩陣用來去存之後會存入的字串資料，要delete資料時矩陣裡會發生fragmentation，後來想想這相當於是寫一個Memory pool，不過這種我也是之後才知道這叫Memory pool，用這種寫法要再寫處理fragmentation的function，而這部份我打算使用一條linked list來儲存被刪掉資料的位置，並在改寫insert function，當這條linked list不為empty則優先選linked list底下的位置填入。
## 資料讀入格式問題
* 用於test_ref的prefix search function
```
choice: s
find words matching prefix (at least 1 char): Ame
Ame - searched prefix in 0.000015 sec
suggest[0] : Ameca,
suggest[1] : Americana,
suggest[2] : Amersfoort,
suggest[3] : Ames,
```
整個test_ref裡寫的功能都不能用，裡面的資料都是亂的甚麼都找不到
:::info
這跟資料讀入有關，忘了後面還有未處理的標點符號問題，所以我再重新看raw data，發現有幾個如果用原本的程式會發生的問題
* 城市與國家沒分清楚
* 空格影響到城市
:::
各國的城市有分層級，而會有從國家->州區/省區->城市，所以我這裡測試一慮使用最小分層的城市，也就是第一個逗號以前的字串為城市的資料。
* 修改code讓讀入的城市不因空格與國家字串干擾
```clike
for ( ; (rtn = fgets(word[idx], WRDMAX , fp) != NULL ); idx++) {
rmcrlf(word[idx]);
rmcomma(word[idx]);
char *p = word[idx];
/* 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;
}
// city num too big checj
if(idx > 30000)
break;
}
```
* 更改後結果
```
choice: s
find words matching prefix (at least 1 char): Ame
Ame - searched prefix in 0.000042 sec
suggest[0] : Ameca
suggest[1] : Amecameca de Juárez
suggest[2] : Amelia
suggest[3] : American Canyon
suggest[4] : American Fork
suggest[5] : Americana
suggest[6] : Americus
suggest[7] : Amersfoort
suggest[8] : Amersham
suggest[9] : Amersham on the Hill
suggest[10] : Ames
suggest[11] : Amesbury
suggest[12] : Amet
suggest[13] : Amethi
```
從結果可以看出prefix search的結果更加正確，尾端部會有逗號，也不會因為空格跑出一些奇怪的結果或是該有的城市跑不出來。
## Ternary search tree eqkid覆蓋問題
```c
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;
}
}
```
:::warning
上述這段code取至 tst_ins_def 函式裡，依照上面寫的，在找到字串有結尾字元之後，在其node的eqkid接上原始字串，但假如ABC與AB這兩個字串來講AB不會洗掉要接到C的eqkid嗎?
如下圖表示，ABC接下的eqkid會被之後AB的eqkid所覆蓋
:::
<img width="200" height="200" align="left" src="https://i.imgur.com/cdrokFj.png" >
<img width="180" height="180" align="right" src="https://i.imgur.com/LA5t5pl.png" >
:::info
在之後我了解到結尾字元也要算在Ternary search tree裡面，當時只想到字串比較沒想到還缺比較結尾字元，而真實情況應該如下圖(O代表結尾字元)
:::
<img width="180" height="180" align="right" src="https://i.imgur.com/P5pS2Pz.png" >
<img width="180" height="180" align="right" src="https://i.imgur.com/NSNPRB8.png" >
## REF CPY效能比較
我的測試方式是重複做一百次測試，並將每次create tst的時間跟search tst的時間都記錄並分別計入在個別的檔案，而底下兩個是perf統計的狀況。
* test_cpy repeat 100 times
```
146,358 cache-misses # 9.906 % of all cache refs ( +- 0.67% ) (75.83%)
1,477,486 cache-references ( +- 0.55% ) (53.62%)
99,146,525 instructions # 0.82 insn per cycle ( +- 0.19% ) (76.90%)
120,918,081 cycles ( +- 0.48% ) (75.05%)
0.035312134 seconds time elapsed ( +- 1.01% )
```
* test_ref repeat 100 times
```
229,856 cache-misses # 12.994 % of all cache refs ( +- 0.67% ) (72.74%)
1,768,879 cache-references ( +- 0.54% ) (55.81%)
96,545,321 instructions # 0.70 insn per cycle ( +- 0.33% ) (79.31%)
138,133,805 cycles ( +- 0.23% ) (74.77%)
0.040373533 seconds time elapsed ( +- 1.10% )
```
Sign in with Wallet
Connect another wallet