# 2018q3 Homework3 (dict)
###### tags: `C語言`
contributed by < `asd757817` >
```
實驗環境
作業系統： Ubuntu 16.04 x64
kernel： 4.15.0-34-generic
gcc 版本： gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.10)
CPU：Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
```
## 原專案功能介紹&測試
### 原專案提供的 --bench 搜尋效率檢查
原專案預設的 --bench 這個參數協助測試，輸入：
```shell
$ make && ./test_cpy --bench
```
這一份測試會逐行讀取 cities.txt 的內容，以","分隔字串並以輸入字串的前三個字元進行 prefix search，紀錄 prefix search 所耗費的時間最後輸出到 bench_cpy.txt 內。
- tst_search_prefix 函式：
比對傳入的字串(傳入的字串是要搜尋字串的 prefix，如： china 會傳 chi 給 tst_search_prefix)，若能找到 chi 分別對應的節點則以 i 的結點作為 root，呼叫 tst_suggest。
- tst_suggest 函式：
以傳入的節點做為 root，走訪之下的所有分支並紀錄到 array 中。
參考< Jyun-Neng >同學的共筆得知可以使用原專案的 script 作圖
```shell
$ gnuplot scripts/runtime3.gp
$ eog runtime3.png
```
圖中顯示時間單位為"秒"，但一般而言搜尋的時間不應該耗費上百秒，因此查看程式碼 bench.c
```C
double tvgetf()
{
struct timespec ts;
double sec;
clock_gettime(CLOCK_REALTIME, &ts);
sec = ts.tv_nsec;
sec /= 1e9;
sec += ts.tv_sec;
return sec;
}
```
bench_cpy.txt 的內容是根據下列程式
```C
t1 = tvgetf();
t2 = tvgetf();
fprintf(fp, "%d %f sec\n", idx, (t2 - t1) * 1000000);
```
t1、t2 透過 tvgetf() 獲得數值，單位為"秒"，故 （ t1 - t2 ) 的單位也為秒，乘以 \*1000000 得到的應該是"奈秒"，修改 runtime3.gp 的 y 軸單位；此外原先圖形 x 軸只顯示到 12500，但輸入的資料約有25000筆，順手修改做圖時 x 軸的範圍。
修改後輸出圖形如下：
## FIXED
### 新增 ./test_ref --bench 測試程式
以 ./test_cpy --bench 能產生 bench_cpy.txt 的測試文件，但執行 ./test_ref 卻會出現錯誤，查看 test_ref.c 發現並沒有加入 --bench 功能。
```
$ ./test_ref --bench
CC test_ref.o
LD test_ref
ternary_tree, loaded 259112 words in 0.264681 sec
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
[1] 8203 segmentation fault (core dumped) ./test_ref --bench
```
參考 test_cpy.c 程式碼，修改 test_ref.c 的內容，在載入字典檔後判斷是否輸入 --bench
```C
...以上略...
t2 = tvgetf();
fclose(fp);
printf("ternary_tree, loaded %d words in %.6f sec\n", idx, t2 - t1);
if (argc==2 && strcmp(argv[1],"--bench")==0){
int stat = bench_test(root,BENCH_TEST_FILE,LMAX);
tst_free(root);
return stat;
}
...以下略...
```
檢查功能是否正常
```shell
$ make && ./test_ref --bench
CC test_ref.o
LD test_ref
ternary_tree, loaded 259112 words in 0.262914 sec
$ cat bench_ref.txt
0 236.034393 nsec
1 613.689423 nsec
2 281.333923 nsec
3 41.484833 nsec
4 248.670578 nsec
5 165.700912 nsec
6 82.969666 nsec
7 310.182571 nsec
8 90.122223 nsec
9 130.414963 nsec
10 95.605850 nsec
11 219.106674 nsec
12 438.928604 nsec
13 436.544418 nsec
14 12.397766 nsec
15 133.514404 nsec
16 176.191330 nsec
17 61.750412 nsec
18 919.580460 nsec
19 36.001205 nsec
20 545.978546 nsec
21 99.658966 nsec
22 27.179718 nsec
23 630.617142 nsec
24 263.929367 nsec
25 228.881836 nsec
26 271.558762 nsec
27 72.002411 nsec
28 294.685364 nsec
29 331.401825 nsec
30 382.900238 nsec
31 165.462494 nsec
32 162.601471 nsec
33 63.657761 nsec
34 214.576721 nsec
35 59.843063 nsec
36 46.253204 nsec
......
```
在 Makefile 新增 plot，繪製 cpy、ref 輸入 --bench 的搜尋時間圖
```
plot: bench_cpy.txt test_cpy test_ref
./test_cpy --bench
./test_ref --bench
gnuplot scripts/runtime3.gp
eog runtime3.png
```
修改 runtime3.gp，同時輸出 cpy、ref runtime 的時間圖
```
reset
set xlabel 'prefix'
set ylabel 'time(nsec)'
set title 'perfomance comparison'
set term png enhanced font 'Verdana,10'
set output 'runtime3.png'
set format x "%10.0f"
set xtic 1200
set xtics rotate by 45 right
plot [:25000][:1000]'bench_cpy.txt' with points,'bench_ref.txt' with points \
```
測試結果
```shell
$ make plot
./test_cpy --bench
ternary_tree, loaded 259112 words in 0.209411 sec
./test_ref --bench
ternary_tree, loaded 259112 words in 0.267564 sec
gnuplot scripts/runtime3.gp
eog runtime3.png
```
從這樣的圖形無法進行比較，因此將數據以搜尋時間為 x 軸、x 軸區間50奈秒、y 軸統計次數重新做圖。
新增 test.gp
```
clear
reset
set xlabel 'search time(nsec)'
set ylabel 'count'
set title 'perfomance comparison'
set term png enhanced font 'Verdana,10'
set output 'test.png'
stats 'bench_cpy.txt' using 2 name 'cpy'
stats 'bench_ref.txt' using 2 name 'ref'
set arrow 1 from cpy_mean,graph 0.5 to cpy_mean,graph 0
set label 1 at cpy_mean, graph 0.5 "mean cpy" center offset 3,1
set arrow 2 from ref_mean,graph 0.5 to ref_mean,graph 0
set label 2 at ref_mean, graph 0.5 "mean ref" center offset 4,-1
set boxwidth 1.0 absolute
#set style fill solid 1.0 noborder
bin_width = 1;
bin_number(x) = floor(x/bin_width)
rounded(x) = bin_width * ( bin_number(x) + 0.5 )
plot [0:2][0:]'bench_cpy.txt' using (rounded($2)):(1) smooth freq with boxes title 'cpy',\
'bench_ref.txt' using (rounded($2)):(1) smooth freq with boxes title 'ref',\
```
```shell
$ gnuplot scripts/test.gp && eog test.png
```
修改 Makef
```
plot: bench_cpy.txt test_cpy test_ref
./test_cpy --bench
./test_ref --bench
gnuplot scripts/test.gp
eog test.png
```
CPY、REF 兩者的差別在於 REF 引入 bloom filter，在搜尋之前先透過 bloom filter 預測輸入的字串是否在字典中，預測在字典中才進入 tree 中搜尋。
從圖中發現在當前的測試樣本 ref 搜尋的時間會略大於 cpy，這是因為搜尋的樣本使用的也是 cities.txt，全部搜尋的字串都在字典檔裡，ref 因為多了 bloom filter 判斷才開始搜索，會多耗費 bloom filter 的判斷時間，後續搜尋的時間與 cpy 一致，因此平均的搜尋時間會略大於 cpy。
### 修改測試的內容
原測試程式以 tst_search_prefix 函式進行搜尋，搜尋只管前三個字元，不管實際輸入的字串是否真的在字典檔內，為了使 bloom filter 效果更加明顯，改以 tst_search
Bloom filter 最理想的情境為：輸入字串的長度為 n，前 n-1 個字元都能夠在 tree 中找到對應的節點，直到最後一個字元才發現輸入字串不在 tree 裡，而透過 bloom filter 可以預設出此字串不在 tree 中
當輸入的搜尋字串不在字典檔內的比例夠高時，bloom filter 的效用還能夠體現，因此修改複製一份 cities.txt，將裡面的部份文字以其他文字取代，使得輸入字串與原本有差異，比較 bloom filter 效益。
**bench.c 修改**
- 引用 bloom.h、新測試文件 t.txt
```C
#include "bloom.h"
#define DICT_FILE "t.txt"
```
- 加入 tst_search 的搜尋時間測量
```C
int bench_test(const tst_node *root, char *out_file, const int max)
{
char word[WORDMAX] = "";
FILE *fp = fopen(out_file, "w");
FILE *dict = fopen(DICT_FILE, "r");
int idx = 0;
double t1, t2;
if (!fp || !dict) {
if (fp) {
fprintf(stderr, "error: file open failed in '%s'.\n", DICT_FILE);
fclose(fp);
}
if (dict) {
fprintf(stderr, "error: file open failed in '%s'.\n", out_file);
fclose(dict);
}
return 1;
}
while (fscanf(dict, "%s", word) != EOF) {
t1 = tvgetf();
tst_search(root,word);
t2 = tvgetf();
fprintf(fp, "%d %f nsec\n", idx, (t2 - t1) * 1000000);
idx++;
}
fclose(fp);
fclose(dict);
return 0;
}
```
- bench.c 加入測試有 bloom filter 時的 tst_search 執行時間
```C
int bench_test_bloom(const tst_node *root, char *out_file, const int max,bloom_t bloom)
{
char word[WORDMAX] = "";
FILE *fp = fopen(out_file, "w");
FILE *dict = fopen(DICT_FILE, "r");
int idx = 0;
double t1, t2;
if (!fp || !dict) {
if (fp) {
fprintf(stderr, "error: file open failed in '%s'.\n", DICT_FILE);
fclose(fp);
}
if (dict) {
fprintf(stderr, "error: file open failed in '%s'.\n", out_file);
fclose(dict);
}
return 1;
}
while (fscanf(dict, "%s", word) != EOF) {
t1 = tvgetf();
if (bloom_test(bloom, word) == 1) {
tst_search(root, word);
t2 = tvgetf();
}
else
t2 = tvgetf();
fprintf(fp, "%d %f nsec\n", idx, (t2 - t1) * 1000000);
idx++;
}
fclose(fp);
fclose(dict);
return 0;
}
```
- python 程式將 cities.txt 內的字串最後一個字元以 rot13 轉換(shift 13位)，輸出為 t.txt
```python
import os
import string
rot13 = string.maketrans(
"ABCDEFGHIJKLMabcdefghijklmNOPQRSTUVWXYZnopqrstuvwxyz",
"NOPQRSTUVWXYZnopqrstuvwxyzABCDEFGHIJKLMabcdefghijklm")
fi = open("cities.txt",'r')
fo = open("t.txt",'w')
for l in fi.readlines():
w_line = ""
for x in l.split(','):
x = x.strip()
i=x[-1:]
x=x[:-1]+string.translate(i,rot13)
w_line += ','+x
fo.write(w_line.strip(',')+'\n')
```
t.txt 內容如下
```
Shanghnv,Chian
Buenos Airrf,Argentian
Mumbnv,Indvn
Mexico Cigl,Distrito Federny,Mexipb
Karacuv,Pakistna
İstanbhy,Turkrl
Deluv,Indvn
Maniyn,Philippinrf
Moscbj,Russvn
Dhaxn,Bangladefu
Seohy,South Korrn
São Pauyb,Brazvy
Lagbf,Nigervn
Jakargn,Indonesvn
Toklb,Japna
Zhumadina,Chian
```
假設 bloom filter 能夠直接指出 shift 後的字串不在 tree 中，而未加 bloom filter 時會搜索到最後一個節點才發現搜尋的字串不在 tree中，推 bloom filter 的搜尋方式在這個測試中平均搜尋時間較短，實際測試結果：
```
cpy
Mean: 0.3788
Std Dev: 0.3103
================================
ref
Mean: 0.2236
Std Dev: 0.3078
```
測試結果符合預期，bloom filter 在此時充份發揮功效。
## Perf
### perf 操作練習：檢查程式在執行過程中各函式佔用 CPU 的時間(cycle)比例
```shell
$ make
$ perf record -e branch-misses:u,branch-instructions:u ./test_cpy --bench
$ perf report perf.data | sed '/^#/ d' | sed '/^$/d' >> perf.txt
$ cat perf.txt
# To display the perf.data header info, please use --header/--header-only options.
#
#
# Total Lost Samples: 0
#
# Samples: 104K of event 'branch-misses:u'
# Event count (approx.): 211066590
#
# Overhead Command Shared Object Symbol
# ........ ....... ............. ......
#
# Samples: 104K of event 'branch-instructions:u'
# Event count (approx.): 7059830582
#
# Overhead Command Shared Object Symbol
# ........ ........ ................ ................................
#
95.52% test_cpy test_cpy [.] tst_suggest
0.73% test_cpy libc-2.23.so [.] _IO_vfscanf
0.70% test_cpy libc-2.23.so [.] __GI___printf_fp_l
0.51% test_cpy libc-2.23.so [.] __mpn_divrem
0.47% test_cpy test_cpy [.] tst_ins_del
0.42% test_cpy libc-2.23.so [.] vfprintf
0.15% test_cpy libc-2.23.so [.] _int_malloc
0.15% test_cpy test_cpy [.] tst_search_prefix
0.13% test_cpy test_cpy [.] tst_free_all
0.11% test_cpy libc-2.23.so [.] __isoc99_fscanf
0.10% test_cpy libc-2.23.so [.] _int_free
```
Sign in with Wallet
Connect another wallet