# 2018q3 Homework3 (dict)
contributed by < `ofAlpaca` >
###### tags: `CSIE5006` `HW`
## 實驗環境
```
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 60
Model name: Intel(R) Xeon(R) CPU E3-1231 v3 @ 3.40GHz
Stepping: 3
CPU MHz: 3548.766
CPU max MHz: 3800.0000
CPU min MHz: 800.0000
BogoMIPS: 6799.62
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 8192K
NUMA node0 CPU(s): 0-7
```
## Makefile 解析
* 先從變數開始看 :
* `TESTS` 指的是 repo 中的 `test_cpy.c` 與 `test_ref.c`
* `TEST_DATA` 為在執行 `test_cpy` 與 `test_ref` 時 `--bench` 的參數
* `CFLAGS` 為 gcc 的參數
```clike=
TESTS = test_cpy test_ref
TEST_DATA = s Tai
CFLAGS = -O0 -Wall -Werror -g
```
* 此處使用 `.PHONY` 來指定了 `all` 與 `clean` 為 fake 項目，因為他們並非是檔案但卻又需要執行，如此一來 make 就不會去檢查是否存這兩個檔案而直接執行。
* `all` target 需要 `$(TESTS)` 的 dependency ，也就是 `test_cpy` 與 `test_ref` 這兩個檔案。
```clike=
.PHONY: all clean
all: $(GIT_HOOKS) $(TESTS)
```
* 因為 `all` 的 `($TESTS)` dependency ，會跑到 target `test_%` 來檢查 dependency ，會發現需要四個 `.o` 檔，分別是 `test_cpy.o` 、 `test_ref.o` 、 `tst.o` 、 `bloom.o` ，接著再跑到 target `%.o` 檢查 dependency 後執行命令 (第一次 make 沒有 `.o` 檔)。
* target `%.o` 下的命令有兩道 :
* `$(VECHO) " CC\t$@\n"` 是用於印出訊息，如 `CC test_cpy.o` 。
* `$(Q)$(CC) -o $@ $(CFLAGS) -c -MMD -MF .$@.d $<` 需要一一分析 :
* `$(Q)` 變數是 `@` ，不顯示所執行的指令
* `-o $@` 意思是 output ， `$@` 即是工作目標檔名，如 : `test_cpy.o`
* `-MMD -MF .$@.d` 意思是令 gcc 自動產生相依性文件 ，如 : `.test_cpy.o.d`
* `-c` 是使 compile source code
* dependency file 就是其他的 Makefile 檔
```
$ cat .test_cpy.o.d
test_cpy.o: test_cpy.c bench.c bench.h tst.h
```
* 可以透過 `include` 來引入其他 Makefile ，加 `-` 意思是是不報錯誤訊息，繼續執行。
* object 檔出來後，接著會回去執行 target `test_%` 。
* `$(Q)$(CC) $(LDFLAGS) -o $@ $^ -lm` 主要目的是連結各個 object 檔並產生執行檔， `-l` 是代表連結 static library ， `-lm` 表示是連結 libm.a 這個 library ，其效果與 `/usr/lib/libm.a` 是一樣的。libm.a 是 math 的 library 。 ([source](http://www.network-theory.co.uk/docs/gccintro/gccintro_17.html))
* 最後產生 `test_cpy` 與 `test_ref` 兩個執行檔。
* `CC` 、 `LDFLAGS` 、 `CFLAGS` 、 `RM` 都是 GNU make 的 predefined variables 。 ([source](https://www.gnu.org/software/make/manual/html_node/Implicit-Variables.html))
```clike=
OBJS_LIB = \
tst.o bloom.o
OBJS := \
$(OBJS_LIB) \
test_cpy.o \
test_ref.o
deps := $(OBJS:%.o=.%.o.d)
test_%: test_%.o $(OBJS_LIB)
$(VECHO) " LD\t$@\n"
$(Q)$(CC) $(LDFLAGS) -o $@ $^ -lm
%.o: %.c
$(VECHO) " CC\t$@\n"
$(Q)$(CC) -o $@ $(CFLAGS) -c -MMD -MF .$@.d $<
-include $(deps)
```
---
## [Bloom filter](https://www.youtube.com/watch?v=bEmBh1HtYrw) TL;DR
Bloom filter 利用 hash function 不透過尋訪來**預測**字串是否存在於資料結構中。
因此時間複雜度是 $O(1)$ 而非傳統尋訪的 $O(n)$ 。
* n-bits 的 table
* k 個 hash fucntion ， h~1~ 、 h~1~ ... h~k~
* 每當要加入新字串 s 時，會將 s 透過這 k 個 hash function 各自轉換為 table index (範圍 : 0~n-1) ，所以有 k 個 hash function ，就該有 k 個 index ，然後將該 table[index] 上的 bit set
* 下次若要檢查該字串 s 是否存在時，只需要再跑一次那 k 個 hash function ，並檢查是否所有的 k 個 bit 都是 set 即可
但這樣做是會**存在錯誤率的**，例如原本沒有在資料結構中的字串 s1 經過 hash 轉換後得出的 bit 的位置和另一個存在於資料結構中的字串 s2 經過 hash 之後的結果相同，如此一來，原本不存在的 s1 便會被認為存在了，這就是 `false positive` 。
---
## Makefile 修改
* 透過 `scripts` 底下的 `.gp` 檔與 Makefile 可以看出應該要有哪些 output 檔，透過缺失的檔案來判斷該如何修補程式碼。
* 應該要有的 output 為 :
* `bench_cpy.txt` : 可以透過下 `$ ./test_cpy --bench` 取得。
* `cpy.txt` : 執行 `$ ./test_cpy` 時建制 ternary search tree 的時間。
* `output.txt` : 要透過編譯 `calculate.c` 並執行才會產生。
* `bench_ref.txt` 、 `ref.txt` : 都沒有辦法產生，所以需要修補。
* 基於以上問題，首先對 Makefile 進行了些許調整 :
* 新增了編譯 `calculate.c` 並產生執行檔。
* 將 target clean 最後一行命令的 `caculate` 改為 `calculate` ，這應該是錯字。
---
## Output 檔的意義
* `cpy.txt` 、 `ref.txt` : 是紀錄 `test_cpy` 與 `test_ref` 在載入 TST 時花費的時間，每次載入就會新增一筆時間，單位是**秒**。
* `bench_cpy.txt` 、 `bench_ref.txt` : 是紀錄 `bench_test` 中每次執行 `tst_search_prefix()` 函式所花費的時間。每次的 `prefix` 為 `cities.txt` 中各字串的前三字元。
* `cities.txt` 中的字串是以 whitespace 來區隔，所以 `Hisel, Germany` 視為兩個字串， `Hisel,` 與 `Germany` 。
* 檔案的單位應是**微秒**。
* `output.txt` 是 `calculate.c` 將 `cpy.txt` 與 `ref.txt` 裡的時間各別加總起來除以 100 的平均時間，也可以說是載入 TST 的平均時間，用於畫長條圖。
---
## `test_ref.c` 修改
* `test_ref.c` 無法產生 `ref.txt` 與 `bench_ref.txt` ，所以需要增加 `test_cpy.c` 中的部份程式碼。
* 但並非完全一樣，原本的 `tst_free_all()` 須改為 `test_free` 。
* 如此一來，執行 `$ ./test_ref` 即可產生 `ref.txt` ， 執行 `$./test_ref --bench` 即可產生 `bench_ref.txt` 。
```clike=
if (argc == 2 && strcmp(argv[1], "--bench") == 0) {
int stat = bench_test(root, BENCH_TEST_FILE, LMAX);
tst_free(root);
return stat;
}
FILE *output;
output = fopen("ref.txt", "a");
if (output != NULL) {
fprintf(output, "%.6f\n", t2 - t1);
fclose(output);
} else
printf("open file error\n");
```
---
## `test_cpy.c` 修改
* CPY 與 REF 還有個差別是前者有 Bloome filter ，後者沒有，為了能夠比較兩實作的差異，所以也需要替 CPY 加上 Bloom filter 的功能。
* 主要的修改部份是在載入 TST 時需要新增 Bloom filter table 。
* 下 `a` 或 `f` 指令時需要先使用 `bloom_test` 來偵測字串是否存在，但這可能會有錯誤的狀況發生 (false positives)。
* [詳細修改內容](https://github.com/ofAlpaca/dict/commit/66f3475eff21af27085cfe7709dd5f030064c542#diff-28acc58b9a966cc6418269e7116fd14c)
---
## `test_cpy.c` 與 `test_ref.c` 共同修改
* `test_cpy` 和 `test_ref` 的執行參數:
* `--bench` : 可以執行 `bench_test` 並產生 `bench_cpy` 或 `bench_ref`
* `--bench [as] <WORD>` : 可以執行 `a` 新增與 `s` search prefix ，使用 `f` 、 `d` 指令會有永遠卡在該指令的 bug 。
* 修補 : 在 `f` 、 `d` 指令也新增 `--bench` 判斷與 `goto quit` 。
* `bench_test` 也有 bug ，下方會解說。
* 由於 `cities.txt` 裡是以 `,` 區隔城市名稱與國家，因為國家大多重複，且重複載入沒意義，故乾脆只取城市名稱來載入至 TST :
* 將 `fscanf()` 的 regular expression 改為 `%256[^,], %256[^\n]\n` 。
* 分別取得**城市名稱**與**國家**。
* `test_cpy.c` 、 `test_ref.c` 、 `bench.c` 都需要修改。
* 改法如下 :
```clike
fscanf(dict, "%256[^,], %256[^\n]\n", word, nation)
```
---
## `bench.c` 修改
* 在 `bench_test` 中有個嚴重的 bug ，那就是 `char prefix[3]` 長度不夠。
* `strncpy(prefix, word, 3)` 的 `prefix` 長度不夠，導致複製了 `word` 的 3 個字元過去後會沒位置放 `\0` ，造成接下來的 `tst_search_prefix` 永遠找不到字串。
* 在 `tst_search_prefix` 中印出 `prefix` 可以發現如下的現象，但是 `prefix` 的 length 不是只有 3 嗎？怎除了前三字元後面還有重複的，那是因為在 `prefix` 範圍內並沒有 `\0` 所以導致在擷取字串時和 `word` 重疊，也就是說 `Ger` 是 `prefix` 而 `Germany` 是 `word` 。
* 可以透過將 `prefix` length 改為 4 ，就能解決這問題。
* 如果沒發現這問題，可能還會覺得怎麼 `bench_test` 速度這麼快，原來是根本沒找到。
```
...
BerBergewöhrden,
GerGermany
SomSomolinos,
SpaSpain
MerMerlscheid,
GerGermany
CasCasas
GarGarcimolina,
SpaSpain
...
```
* 出問題的程式碼
```clike=
char prefix[3] = ""; // make it to 4 bytes to hold '\0'
char word[WORDMAX] = "";
...
while (fscanf(dict, "%s", word) != EOF) {
if (strlen(word) < 4)
continue;
strncpy(prefix, word, 3);
t1 = tvgetf();
tst_search_prefix(root, prefix, sgl, &sidx, max);
t2 = tvgetf();
fprintf(fp, "%d %f sec\n", idx, (t2 - t1) * 1000000);
idx++;
}
```
* 觀察了 `bench_cpy.txt` 總覺的哪裡怪怪的，上面時間動輒幾百秒，但執行時不見得有這麼久。
* 後來看到是 `fprintf(fp, "%d %f sec\n", idx, (t2 - t1) * 1000000)` 有些不對勁， `t1` 、 `t2` 是由 `tvgetf()` 函式產生的，其時間單位是**秒**，那為什麼相減後乘上 10^6^ 還是**秒**呢？
* 所以單位應該是**微秒 (microsecond)** 才是。
---
## Make plot
* 新增 `make plot` 功能，此功能是要將 TST + Bloom filter 效能視覺化。
* target `load` 與 `output.txt` 是要比較 CPY 與 REF 載入 TST 時的效能比較。
* target `bench_%.txt` 則是執行 `bench_test` 來測試 prefix search 的統計分佈。
* `make plot` 後會產生 `runtime3.png` 與 `runtime2.png` ，前者是 CPY
```
load: $(TESTS)
perf stat --repeat 100 \
-e cache-misses,cache-references,instructions,cycles \
./test_cpy --bench q
perf stat --repeat 100 \
-e cache-misses,cache-references,instructions,cycles \
./test_ref --bench q
plot: bench_cpy.txt bench_ref.txt output.txt
$(Q)gnuplot scripts/runtime3.gp
$(Q)gnuplot scripts/runtimept.gp
$(Q)gnuplot scripts/runtime.gp
$(Q)eog plots/runtime3.png
bench_%.txt: test_%
$(VECHO) " benching...\t$@\n"
$(Q)./$< --bench
output.txt: calculate load
$(VECHO) " calculating...\t$@\n"
$(Q)./$<
```
* `runtimept.gp` 與 `runtime3.gp` 也做了些修改，將原本的範圍擴大與將產生的圖放 plots 目錄下。
```
reset
set xlabel 'prefix'
set ylabel 'time(sec)'
set title 'perfomance comparison'
set term png enhanced font 'Verdana,10'
set output 'plots/runtime2.png'
set format x "%10.0f"
set xtic 5000
set xtics rotate by 45 right
plot [:90000][:1000]'bench_cpy.txt' using 1:2 with points title 'cpy',\
'bench_ref.txt' using 1:2 with points title 'ref',\
```
* CPY 在 prefix search 時的統計分佈
* CPY 與 REF 的 prefix search 比較
* 就此來看 CPY 的分佈較為集中些， REF 的極端值較明顯。
---
## TST 對 prefix search 的影響
* 根據 TST 的特性可以得知，如果按照**字串大小順序加入**字串，比較會讓 TST 產生出來的樹歪斜。當在搜尋字串時會導致需要比對更多次。
* 原本認為隨機選擇的插入順序在操作 TST 時效能應該都會比較好，因為隨機插入所生成的 TST 較會是平衡樹，但是 prefix search 卻並非如此。
* 將 `cities.txt` 排序成 `cities_sorted.txt` 後下指令 `s Tai` 測試效能 ( 為了比對，都使用 CPY )
```
Performance counter stats for './test_cpy --bench s Tai' (100 runs):
270,092 cache-misses # 55.784 % of all cache refs ( +- 0.94% )
484,176 cache-references ( +- 0.21% )
559,474,006 instructions # 1.63 insn per cycle ( +- 0.01% )
343,459,668 cycles ( +- 0.14% )
0.093505691 seconds time elapsed ( +- 0.15% )
```
* 使用原本的 `cities.txt` 下指令 `s Tai` 測試效能
```
Performance counter stats for './test_cpy --bench s Tai' (100 runs):
1,101,592 cache-misses # 49.866 % of all cache refs ( +- 0.89% )
2,209,089 cache-references ( +- 0.24% )
503,962,290 instructions # 1.18 insn per cycle ( +- 0.01% )
428,791,962 cycles ( +- 0.29% )
0.117321684 seconds time elapsed ( +- 0.40% )
```
* 從以上兩種載入順序可以發現按照大小順序載入的 prefix search 竟然會比較快。實驗 TST 的插入順序是否影響 prefix search 效能 :
* 執行 `make plot` 來得到 prefix search 的統計分佈
* 排序後插入 TST 的 prefix search
* 沒排序插入 TST 的 prefix search
* 從上圖可以得知，使用排序後插入的 prefix search 速度大優於沒有排序的，結果出人意料。
* 為了調查原因，去觀察一下 `tst_search_predfix()` 的程式碼，會發現到當找到 prefix 最後字元所在的 node 後，會透過 `tst_suggest()` 遞迴進入 left child 、 mid child 、 right child 將符合 prefix 字串的 node 的指標都存入 `char **a` 裡。
```clike=
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);
}
```
* 使用 `$ perf record ./test_cpy --bench` 與 `$perf report` 來查看哪個函式是 hot spot 。
* 排序後 :
```
Overhead Command Shared Object Symbol
92.67% test_cpy test_cpy [.] tst_suggest
2.46% test_cpy test_cpy [.] tst_search_prefix
0.77% test_cpy libc-2.27.so [.] _IO_vfscanf
0.75% test_cpy test_cpy [.] tst_ins_del
...
```
* 非排序 :
```
Overhead Command Shared Object Symbol
95.60% test_cpy test_cpy [.] tst_suggest
0.56% test_cpy test_cpy [.] tst_ins_del
0.51% test_cpy test_cpy [.] tst_search_prefix
0.49% test_cpy libc-2.27.so [.] _IO_vfscanf
...
```
由此可見 `tst_suggest()` 函式的 Overhead 比例最高，可見其對於執行速度最具影響力。而排序與非排序也影響著 `tst_suggest()` 上的 Overhead ，所以說排序後插入的 TST 對於遞迴的效率較好，至於原因想不太出來。
參考 :
[Hackmd 共筆](https://hackmd.io/c/rJKbX1pFZ/https%3A%2F%2Fhackmd.io%2Fs%2FB11109rdg)
[Linux下的系統性能調優工具——Perf](https://hk.saowen.com/a/b6b4110cddc0a8d10a9a5a14a44e9ab3317f88324c133bca50d1fc0ce73afed5)
---
## CPY 與 REF 實作差異
* 兩者最大的差別在於 REF 使用了 memory pool 的機制來分配記憶體，而 CPY 則是正常的 `malloc()` 與 `free()` 。
* 從 `test_ref.c` 可以看到 memeory pool 的機制分配了一塊大記憶體 (`poolsize * sizeof(char)`) ，使用 `pool` 指標指向 memory pool 的開頭， `Top` 指標指向下一個要分配出的記憶體位址，以此來控制記憶體存取。
* REF 和 CPY 相比少了頻繁使用 `malloc` 。
```clike=
/* memory pool */
char *pool = (char *) malloc(poolsize * sizeof(char));
char *Top = pool;
while ((rtn = fscanf(fp, "%256[^,], %256[^\n]\n", Top, nation)) != EOF) {
char *p = Top;
...
```
* 可以在 `tst.c` 下的 `tst_ins_del()` 函式看到 CPY 是使用 `strdup` 來分配記憶體，而 REF 僅僅是回傳指標。 `cpy` 為 0 則為 CPY 呼叫此函式。
```clike=
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;
}
```
* `make plot` 後生成 TST 所花費的時間 ( 跑 100 次取平均 )，可看到 REF 略快於 CPY 。
* 可以看到 REF 的 cache-misses 較低， `./test_ref --bench q` 只做完載入動作後就離開程式。
```
Performance counter stats for './test_ref --bench q' (100 runs):
985,229 cache-misses # 44.418 % of all cache refs ( +- 0.48% )
2,218,064 cache-references ( +- 0.08% )
467,074,659 instructions # 1.16 insn per cycle ( +- 0.00% )
403,330,172 cycles ( +- 0.12% )
0.109016797 seconds time elapsed ( +- 0.15% )
...
Performance counter stats for './test_cpy --bench q' (100 runs):
1,010,358 cache-misses # 45.856 % of all cache refs ( +- 0.50% )
2,203,335 cache-references ( +- 0.15% )
503,410,105 instructions # 1.20 insn per cycle ( +- 0.01% )
419,903,519 cycles ( +- 0.13% )
0.113889864 seconds time elapsed ( +- 0.16% )
```
* 透過這篇 [CPU Cache 原理探討](https://hackmd.io/s/H1U6NgK3Z#) 可以得知，當 CPU 在 CPU cache 找不到需要的資料時就會產生 cache-misses 。
* 使用 memory pool 的 REF 一開始就分配大量記憶體，所以資料彼此是連續的，也就是有比較好的 Data locality ，因此 cache-misses 才會比 CPY 少，載入速度較快。
---
Sign in with Wallet
Connect another wallet