A Brief report on Prefix-Search
===
## 開發環境
列出CPU資訊
`$ lscpu`
```
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 60
Model name: Intel(R) Core(TM) i5-4200M CPU @ 2.50GHz
Stepping: 3
CPU MHz: 799.865
CPU max MHz: 3100.0000
CPU min MHz: 800.0000
BogoMIPS: 4988.06
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 3072K
NUMA node0 CPU(s): 0-3
```
列出系統相關資訊
`$ uname -a`
```
Linux michael-Lenovo-IdeaPad-Z510 4.10.0-35-generic #39-Ubuntu SMP Wed Sep 13 07:46:59 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux
```
清空 cache, 檢視一下資源 (只開 terminal 的情況)
`$ echo 1 | sudo tee /proc/sys/vm/drop_caches`
`$ free`
```
total used free shared buff/cache available
Mem: 8087436 281492 7619884 61484 186060 7543304
Swap: 10000380 0 10000380
```
---
## 測試 prefix-search 程式的功能
```
Commands:
a add word to the tree
f find word in tree
s search words matching prefix
d delete word from the tree
q quit, freeing all data
```
### 測試 search 功能
測試 search words matching prefix 的功能，依照，輸入 T 搜尋到 1024 筆資料
```
$ ./test_cpy
ternary_tree, loaded 259112 words in 0.080956 sec
...
choice: s
find words matching prefix (at least 1 char): T
T - searched prefix in 0.000217 sec
suggest[0] : Tàrrega,
suggest[1] : Tàu,
...
suggest[1023] : Tasquillo,
```
再輸入 B ，也搜尋到 1024 筆資料
```
find words matching prefix (at least 1 char): B
B - searched prefix in 0.001191 sec
suggest[0] : Bábolna,
suggest[1] : Bácsalmás,
...
suggest[1023] : Balcón
```
輸入一個開頭比較少見的 X ，獲得 175 筆資料，目前都是正常情況
```
find words matching prefix (at least 1 char): X
X - searched prefix in 0.000042 sec
suggest[0] : Xàtiva,
suggest[1] : Xánthi,
...
suggest[174] : Xylotymbou,
```
輸入 A ，發現程式記憶體區段錯誤
```
find words matching prefix (at least 1 char): A
程式記憶體區段錯誤 (core dumped)
```
輸入 Aa 看是不是 prefix 有 A 都有問題，結果程式執行正常
```
find words matching prefix (at least 1 char): Aa
Aa - searched prefix in 0.000007 sec
suggest[0] : Aabenraa,
suggest[1] : Aach,
...
suggest[24] : Aasiaat,
```
經過以上的測試，小小的結論是，searched prefix 會輸出最多 1024 筆資料，而目前在 prefix = A 時會發生錯誤。
### 測試 add, find, delete 的功能
找個字串來做測試，找找看 "jacky" 有沒有在裡面
```
choice: f
find word in tree: jacky
jacky not found.
```
沒找到，add jacky to the tris
```
choice: a
enter word to add: jacky
jacky - inserted in 0.000002 sec. (259113 words in tree)
```
添加後，測試是否可以找到
```
choice: f
find word in tree: jacky
found jacky in 0.000001 sec.
```
測試刪除功能，測試刪去的資料是否真的找不到了
```
choice: d
enter word to del: jacky
deleting jacky
deleted jacky in 0.000004 sec
...
choice: f
find word in tree: jacky
jacky not found.
```
目前功能都正常，想到之前測試的有些資料最後有逗號，想要知道 find 功能對其的支援為何，輸入在 search prefix T 時的資料 Tasquillo,
```
choice: f
find word in tree: Tasquillo,
found Tasquillo, in 0.000002 sec.
```
可以找到有逗號的，那沒有逗號是否可以搜尋到
```
choice: f
find word in tree: Tasquillo
Tasquillo not found.
```
輸入 "Tasquillo" 沒辦法搜尋到 "Tasquillo,"
### 觀察原始資料
原始資料為，city, country，發現有些原始資料城市是超過兩個單字的長度， e.g. New York, Mexico City，但在searched prefix 時會發現輸入 New 並不會出現 New York
```
Shanghai, China
Buenos Aires, Argentina
Mumbai, India
Mexico City, Distrito Federal, Mexico
Karachi, Pakistan
İstanbul, Turkey
Delhi, India
Manila, Philippines
Moscow, Russia
Dhaka, Bangladesh
Seoul, South Korea
São Paulo, Brazil
Lagos, Nigeria
Jakarta, Indonesia
Tokyo, Japan
Zhumadian, China
New York, New York, United States
Taipei, Taiwan
...
```
* 由上面` "New York"` 的例子可以發現程式是以空格 `" "` 切割字串,再觀察上面的 `"Tasquillo,"` 發現 `","` 並沒有被切除。
* 上述兩個問題會造成使用者搜尋時的困難，搜尋 `"New"` 找不出 `"New York"` ; 尋找 `"Tasquillo"` 卻要輸入 `"Tasquillo,"` 。
* 因此，我們修改程式碼的對檔案讀入後的字串切割方式，改以判斷 `","` 來切割。同時解決上述兩個問題。
```C
char *delim = ",\n";
while (fgets(word, WRDMAX, fp)) {
char *p = strtok(word, delim);
do {
if (p[0] == ' ') /* because input data is "city, country" or "city, state, country", remove the redundant space */
p++;
if (!tst_ins_del(&root, &p, INS, CPY)) {
fprintf(stderr, "error: memory exhausted, tst_insert.\n");
fclose(fp);
return 1;
}
idx++;
} while((p = strtok(NULL, delim)) != NULL);
```
---
## 尋找 search "A" 發生 Segfault 的原因
使用 gdb debug
```
$ gdb test_cpy
...
(gdb) run
...
choice: s
find words matching prefix (at least 1 char): A
Program received signal SIGSEGV, Segmentation fault.
0x0000000000401d81 in tst_suggest (p=0x8061c0, c=65 'A', nchr=1, a=0x7fffffffbb10, n=0x7fffffffbad0, max=1024)
at tst.c:330
330 a[(*n)++] = (char *) p->eqkid;
```
發現程式執行到 tst.c:330 行時會 crash
```C=317
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)
a[(*n)++] = (char *) p->eqkid;
tst_suggest(p->hikid, c, nchr, a, n, max);
}
```
程式發生 crash 的條件是在第 N 層時執行 326 行時 *n = 1023 ， 遞迴自己進入第 N+1 層， 再一次執行 326 行時 p->lokid = NULL，所以進入 test_suggest 第 N+2 層會在 324 行滿足條件 return，第 N+1 層繼續往下進行條件剛好進入到 330 行 (*n)++，此時 331 行 *n = 1024，所以進入第 N+2 層 test_suggest 也會在 324 行滿足條件 retrun，第 N+1 層也在此時結束，回到第 N 層進行到 330 行，程式已經不符合原先期待，會對 a[1024] 做存取，並且隨著程式持續執行， *n 持續增加，持續存取到不正確的記憶體。
## [Fix function tst_suggest to prevent segfault](https://github.com/jackyhobingo/prefix-search/commit/0061574307eec153aa673b57fa87aec3bf57fd9d)
會增加 *n 的也只有第 330 行，只需要在 329 行的進入條件多增加 *n != max 即可修復此 bug
else if ( *(((char *) p->eqkid) + nchr - 1) == c<font color="Green"> && *n != max</font>)
```C=317
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);
}
```
---
## Memory pool
參考 [ChiuYiTang](https://hackmd.io/s/ByeocUhnZ#)
* 引入 Memory pool ，指定一塊連續的記憶體空間，之後需要時再操作指標分配。比起每次需要配置時才使用 malloc()，減少記憶體配置與釋放的時間。
* [Implement memory pool for tst_ref](https://github.com/Jetudie/prefix-search/commit/2a2c7881980ba53d51774afd83501e1a515b759a)
---
## 效能評比
參考[zhanyangch](https://hackmd.io/s/Syc8yOhhW)同學
新增可讀取 `--bench` 指令的測試功能。將 `TST` 的建立時間記錄在文件中。
```C
#define TST_BENCH "tst_bench_cpy.txt"
#define SEARCH_BENCH "search_bench_cpy.txt"
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);
int status = bench(root,sgl,SEARCH_BENCH, &sidx, LMAX);
tst_free_all(root);
return status;
}
```
在 `bench` 函式中將搜尋 A-Z , a-z 的時間記錄在文件中。
```C
int bench(const tst_node *root,
char **a,
char *out_file,
int *n,
const int max)
{
FILE *fp = fopen(out_file, "a+");
if (!fp) {
fprintf(stderr, "error: file open failed '%s'.\n", SEARCH_BENCH);
return 1;
}
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;
}
fprintf(fp, "%.6f\n",totaltime);
fclose(fp);
return 0;
```
修改 `Makefile` 再輸入 `$ make bench` 時執行 100 次 `perf` 校能分析
```shell
BIN = \
test_cpy \
test_ref
bench: $(BIN)
@for test in $(BIN); do\
perf stat --repeat 100 \
-e cache-misses,cache-references,instructions,cycles \
./$$test --bench;\
done
```
---
## Search time analysis
```
Performance counter stats for './test_cpy --bench' (100 runs):
2,288,956 cache-misses # 65.579 % of all cache refs ( +- 0.44% )
3,490,361 cache-references ( +- 0.24% )
520,491,275 instructions # 0.95 insn per cycle ( +- 0.00% )
545,061,602 cycles ( +- 0.22% )
0.182315420 seconds time elapsed ( +- 0.20% )
```
```
Performance counter stats for './test_ref --bench' (100 runs):
1,771,851 cache-misses # 59.341 % of all cache refs ( +- 0.41% )
2,985,902 cache-references ( +- 0.10% )
420,097,637 instructions # 0.89 insn per cycle ( +- 0.01% )
474,336,014 cycles ( +- 0.18% )
0.158849467 seconds time elapsed ( +- 0.20% )
```
* TST build time
* TST search time
* 由於 REF 的記憶體被指派為固定的大小， CPY 則是依據字串長度來大小，配置在相鄰的位置，減少額外的計算。
## 作業要求
* [ ] 在 GitHub 上 fork [prefix-search](https://github.com/sysprog21/prefix-search)，並修改 `Makefile` 以允許 `$ make bench` 時，可對 ternary search tree 的實作做出效能評比，涵蓋建立 tst 和 prefix search 的時間，應比照 [clz](https://hackmd.io/s/Hyl9-PrjW) 透過統計模型，取出 95% 信賴區間
* [x] 測試程式碼應該接受 `--bench` 的執行參數，得以在沒有使用者輸入的前題下，對 tst 程式碼進行效能分析，應涵蓋 `cpy` 和 `ref` 兩種途徑 (詳情參閱 `tst.h` 的程式碼註解)
* [ ] 解釋 tst 的優點和引入 tst 到電話簿或戶政管理系統的適用性
* [ ]修改 [test＿ref.c](https://github.com/sysprog21/prefix-search/blob/master/test_ref.c)，參照裡頭標註 `TODO` 的部分，替換成真正有效的 API 和對應的程式碼，這裡要求你學習分析現有的程式碼並得以擴充
* [x]分析 `test_cpy` 和 `test_ref` 兩種方式 (copy/reference) 的效能，並且針對現代處理器架構，提出效能改善機制
* [x]指出目前實作中，針對各國城市的 prefix search 有無缺陷呢？比方說無法區分城市和國家，並提出具體程式碼的修正
* [ ]引入 [phonebook](https://hackmd.io/s/HJJUmdXsZ) 的基礎工作，透過 [ternary search tree](https://en.wikipedia.org/wiki/Ternary_search_tree) 讓電話簿程式得以更符合人性，當使用者新增資料時，可以在居住地透過 prefix search 找出最接近的城市並避免輸入錯誤
* [ ]詳細觀察 `tst.h` 和 `tst.c` 為何要 forward declaration 呢？分離介面和實作有何好處呢？這樣的思維又該如何運用於 [phonebook](https://hackmd.io/s/HJJUmdXsZ) 呢？提出想法並且實作
* [ ]研究程式碼的 `tst_traverse_fn` 函式，並思考如何運用這個實作，注意到 [callback function](https://en.wikipedia.org/wiki/Callback_(computer_programming)) 的程式開發技巧/模式
* [ ]將你的觀察、上述要求的解說、應用場合探討，以及各式效能改善過程，善用 gnuplot 製圖，紀錄於「[作業區](https://hackmd.io/s/HkVvxOD2-)」
---
+ [x] [Add bench mark](https://github.com/Jetudie/prefix-search/commit/58c35296f320d882611515f2dd1dd65ef00ae372)
+ [x] [Implement memory pool for tst_ref](https://github.com/Jetudie/prefix-search/commit/2a2c7881980ba53d51774afd83501e1a515b759a)
+ [x] [Fix function tst_suggest to prevent segfault](https://github.com/Jetudie/prefix-search/commit/3a383b6df837546c322d31d77d73c59aaee7e48b)
+ [x] [Use ", " to split input data rather than " " ](https://github.com/Jetudie/prefix-search/commit/715faaf2c0cf1ac22cd052ac54e4d29f3cb7e994)
---
## Reference
* [Memory pool](https://zh.wikipedia.org/wiki/%E8%A8%98%E6%86%B6%E6%B1%A0)
* [Forward Declaration](https://en.wikipedia.org/wiki/Forward_declaration)
* [ChiuYiTang](https://hackmd.io/s/ByeocUhnZ#)
* [zhanyangch](https://hackmd.io/s/Syc8yOhhW)
Sign in with Wallet
Connect another wallet