# 2017q3 Homework2 (prefix-search)
contributed by<`zhanyangch`>
## 執行環境
```
$ lscpu
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
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 42
Model name: Intel(R) Core(TM) i7-2640M CPU @ 2.80GHz
製程： 7
CPU MHz： 855.421
CPU max MHz: 3500.0000
CPU min MHz: 800.0000
BogoMIPS: 5587.06
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 4096K
NUMA node0 CPU(s): 0-3
```
## tst_suggest 修正
用 prefix search 搜尋 'A' 時會產生 Segmentation fault
用 gdb 查看錯誤資訊
```
choice: s
find words matching prefix (at least 1 char): A
Program received signal SIGSEGV, Segmentation fault.
0x0000000000401f8b in tst_suggest (p=0xd72680, c=65 'A', nchr=1,
a=0x7fffffffbd50, n=0x7fffffffbd0c, max=1024) at tst.c:330
330 a[(*n)++] = (char *) p->eqkid;
```
tst_suggest() 的原始程式碼，找到符合的節點會將字串放入 a[]中，但對於 n 的檢查 *n == max，因 tst_suggest 會多次呼叫自己，可能出現 n>=max 的情形，此時會導致程式嘗試去寫入不合法的記憶體。
`if (!p || *n == max)` 修正為 `if (!p || *n >= max)` 即可。
修正後搜尋'A'只會找到前 1025 筆資料，應為1024筆，改為在記憶體寫入前再做一次檢查
```
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);
}
```
:::danger
1. 目前 Git commit [Fix memory access out of bounds](https://github.com/zhanyangch/prefix-search/commit/1399c7cb3b674ac3dc256f265c14fd5089e70e1c) 描述太不清楚，請參照 [Memory access out of bounds error when using _malloc on WASM compiled code](https://github.com/kripken/emscripten/issues/5161) 的分析和隨後的程式碼修正方式，改善你的 Git commit messages
2. 善用 `git commit --amend` 和 `git push --force`，讓程式碼的變革更清楚且易於維護
:notes: jserv
:::
## REF 實做
此部份參考[st9007a的共筆](https://hackmd.io/s/SkeKQEq3Z#)
``` clike
void *tst_ins_del(tst_node **root, char *const *s, const int del, const int cpy)
{
/* ....*/
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;
}
}
/* ....*/
}
```
原本使用 CPY 時會利用 strdup 分配一塊記憶體放置複製的字串，若改用 REF 必需先為該字串分配記憶體。
宣告一個二維陣列來存放所有要放入 TST 的字串。
```clike
char (*cities)[WRDMAX] = malloc(sizeof (*cities) * CITYMAX);
```
:::danger
1. 上述對應的 Git commit [Implement ref version](https://github.com/zhanyangch/prefix-search/commit/b77f6a3743b009151f192cfb6ace54e548185685) 描述太不清楚，請改善 commit message!
2. 不要濫用 "version" 這詞彙，在你學習軟體工程後，應該更謹慎
3. `Repalce argument CPY with REF in test_ref.c` => 這說明了什麼？你要做高階的描述，說明你的修改動機、目的，還有方法。不用特別說在哪個檔案，Git 會自動追蹤
4. `Modify parameter of tst_del_word invoked by tst_ins_del` => 同上，不要做低層次的描述，Git commit messages 是給合作者和「未來的你」看的。
:notes: jserv
:::
測試過程:
```
choice: q
*** Error in `./test_ref': free(): invalid pointer: 0x00007f1a6f8bef10 ***
```
在執行 quit 時發現 free() 到不合法的指標，將 tst_free_all(root) 改為 tst_free(root)，兩者差異主要在於 tst_free_all 會 free 儲存字串的 tst_node ，tst_free 則不會。
```clike
void tst_free_all(tst_node *p)
{
if (!p)
return;
tst_free_all(p->lokid);
if (p->key)
tst_free_all(p->eqkid);
tst_free_all(p->hikid);
if (!p->key)
free(p->eqkid);
free(p);
}
/** free the ternary search tree rooted at p, data storage external. */
void tst_free(tst_node *p)
{
if (!p)
return;
tst_free(p->lokid);
if (p->key)
tst_free(p->eqkid);
tst_free(p->hikid);
free(p);
}
```
delete 的部份與 quit 相同，將 tst_ins_del 的 return tst_del_word(root, curr, &stk, 1) 改為 return tst_del_word(root, curr, &stk, cpy)
在 REF 時 freeword 為0，不會 free 字串的記憶體。
```clike
static void *tst_del_word(tst_node **root,
tst_node *node,
tst_stack *stk,
const int freeword)
{
tst_node *victim = node; /* begin deletion w/victim */
tst_node *parent = tst_stack_pop(stk); /* parent to victim */
if (!victim->refcnt) { /* if last occurrence */
if (!victim->key && freeword) /* check key is nul */
free(victim->eqkid); /* free string (data) */
/*...*/
}
```
:::danger
應該一併開發可以自動測試程式的機制，這樣才能交叉比對 CPY 和 REF 兩種實作的結果，而不用每次都透過人工輸入
:notes: jserv
:::
## 效能比較
接受 `--bench` 的執行參數，將 TST 的建立時間儲存在檔案中，並且在 bench 函式中測試 search A-Z 、 a-z 所需的時間。
```clike
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);
fp = fopen (SEARCH_BENCH,"a+");
if (!fp) {
fprintf(stderr, "error: file open failed '%s'.\n", SEARCH_BENCH);
return 1;
}
fprintf(fp, "%.6f\n",bench(root, sgl, &sidx, LMAX));
fclose(fp);
return 0;
}
```
```clike
double bench(const tst_node *root,
char **a,
int *n,
const int max)
{
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;
}
return totaltime;
}
```
輸入 make bench 時會執行 perf 測試效能
```
bench:
echo 3 | sudo tee /proc/sys/vm/drop_caches
perf stat --repeat 100 \
-e cache-misses,cache-references,instructions,cycles \
sudo chrt -f 99 taskset -c 0 ./test_cpy --bench
echo 3 | sudo tee /proc/sys/vm/drop_caches
perf stat --repeat 100 \
-e cache-misses,cache-references,instructions,cycles \
sudo chrt -f 99 taskset -c 0 ./test_ref --bench
```
測試結果：CPY 的 cache miss 較多，但執行時間較短。
```
Performance counter stats for 'sudo chrt -f 99 taskset -c 0 ./test_cpy --bench' (100 runs):
577 cache-misses # 29.304 % of all cache refs ( +- 1.17% )
1,970 cache-references ( +- 1.07% )
37,668 instructions # 0.33 insns per cycle ( +- 0.51% )
114,387 cycles ( +- 0.82% )
0.177266445 seconds time elapsed ( +- 0.57% )
Performance counter stats for 'sudo chrt -f 99 taskset -c 0 ./test_ref --bench' (100 runs):
563 cache-misses # 28.153 % of all cache refs ( +- 0.72% )
2,001 cache-references ( +- 1.29% )
37,615 instructions # 0.33 insns per cycle ( +- 0.67% )
113,579 cycles ( +- 1.25% )
0.199392490 seconds time elapsed ( +- 0.28% )
```
建立 TST 的時間
利用 gnuplot 的 stat 指令可以獲得統計數據
```
stat 'tst-cpy-bench.txt' using 1 name 'CPY'
```
```
CPY:
Mean: 0.1280
Std Dev: 0.0071
REF:
Mean: 0.1411
Std Dev: 0.0039
```
搜尋時間
```
CPY:
Mean: 0.0421
Std Dev: 0.0007
REF:
Mean: 0.0505
Std Dev: 0.0005
```
原因探討
* 建立 TST 時 REF 使用的記憶體空間固定，CPY 則是依據輸入字串的長度，且 REF 要將每一筆資料儲存在不同的記憶體位置，這個記憶體位置需要計算。
* 搜尋的差異只在於葉節點的字串儲存位置不同，將 CPY 的葉節點(儲存字串)和上一個節點(儲存 key)的記憶體位置印出，可以發現位置是相鄰的。
```
address of node: 0x3c59000
address of string: 0x3c59030
```
* 改善 REF 的方向：先配置一塊記憶體，將節點與字串依序存放。
## forward declaration
在 tst.h 中 並沒有定義 tst_node 的成員，並且所有函式都是對 tst_node 的指標作運算，這樣的作法好處是減少重新編譯的時間，且可以由不同的 .c 檔案實做 struct 的內容，缺點是不能直接對 struct 作操作，要改用 get、set 等函式。
```
typedef struct tst_node tst_node
```
## tst_traverse_fn
走訪每一個節點，順序是 lokid、eqkid、hikid、parent，且對於葉節點呼叫 fn
fn 在此為 callback function ，在符合條件時會自動被呼叫，可以藉由傳入不同的函數來實現不同功能，例如 tst_get_refcnt 可以取得字串出現的次數、tst_get_string 取得字串等。
```clike
void tst_traverse_fn(const tst_node *p,
void(fn)(const void *, void *),
void *data)
{
if (!p)
return;
tst_traverse_fn(p->lokid, fn, data);
if (p->key)
tst_traverse_fn(p->eqkid, fn, data);
else
fn(p, data);
tst_traverse_fn(p->hikid, fn, data);
}
```
callback function 也常被用於使用者界面，例如 OpenCV 的 setMouseCallback 當收到使用者的滑鼠事件，會呼叫 onMouse 函數進行處理，[範例](http://opencvexamples.blogspot.com/2014/01/detect-mouse-clicks-and-moves-on-image.html)。
```clike
void setMouseCallback(const string& winname, MouseCallback onMouse, void* userdata=0 )
```
> 程式碼列表太少，需要提及如何「運用」，也就是最小可執行的示範
> [name="jserv"][color=red]
## 修正資料分隔符號
原本讀取檔案的方式為 fscanf(fp, "%s", word) 但 cities.txt內的格式為 city, country，fscnaf 讀取字串時遇到空格字元會停止讀取，例如：Buenos Aires, Argentina 會認為是三個字串 "Buenos"、"Aires,"、"Argentina"，但這筆資料的意義應該是"Buenos Aires"、"Argentina"，所以需要修改讀取的格式。
```clike
while ((rtn = fscanf(fp, "%[^,\n]", word)) != EOF) {
char tmp = fgetc(fp);
if (tmp == ',') {
tmp = fgetc(fp);
strcat(word, ",");
}
/*...*/ }
```
%[^,\n] 為讀取字串直到遇到 [^] 內的字元，這裡以',' '\n'分隔不同筆資料，當遇到','時忽略後面一個字元(在資料中','後面必定有一空白)，並且為了辨識是 city 還是 country ，再把','補上。
測試結果：可以正確找到含有空格的字串
```
choice: s
find words matching prefix (at least 1 char): Buenos
Buenos - searched prefix in 0.000005 sec
suggest[0] : Buenos Aires,
```
## 參考資料
[st9007a的共筆](https://hackmd.io/s/SkeKQEq3Z#)
[stats_(Statistical_Summary) - Gnuplot: An Interactive Plotting Program](http://soc.if.usp.br/manual/gnuplot-doc/htmldocs/stats_005f_0028Statistical_005fSummary_0029.html)
[OpenCV documentation](https://docs.opencv.org/2.4/modules/highgui/doc/user_interface.html)
Sign in with Wallet
Connect another wallet