# 2020q3 Homework3 (dict)
contributed by < `RainbowEye0486` >
## 視覺化 ternary search tree + bloom filter 的效能表現
當執行完
```
$ ./test_common --bench CPY
```
以及
```
$ ./test_common --bench CPY
```
後，我們可以發現檔案底下產生出一個 `bench_ref.txt` 檔案，這個檔案是由 `test_common.c` 定義：
```cpp=20
#define BENCH_TEST_FILE "bench_ref.txt"
```
並且呼叫 `bench.c` 中的函式產生
```cpp=103
if (argc == 3 && strcmp(argv[1], "--bench") == 0) {
int stat = bench_test(root, BENCH_TEST_FILE, LMAX);
tst_free(root);
free(pool);
return stat;
}
```
接下來，我們要比較 `CPY` 和 `REF` 之間的差異，發現其實整體看下來，效能以 `CPY` 較佳，而且`CPY` 的方式整體來說穩定的多，大部分數值都落在0.7以下，原因老師也有提到，在 `tst.c` 中可以發現在 insert 的時候，字串會直接 `malloc` ，記錄下來，因此搜尋的時候有很大的機會會在 `catch` 裡面找到，反而是 `REF` 的機制，將地名放在 `memory pool` 裡面，所以每次尋找的時候都有可能還需要去記憶體裡面 load `memory pool` 的某個部份進來，所以效能表現較差，這個部份和講義上面的一樣。
至於為什麼在 `REF` 機制中有些點出現比周圍大很多的值呢？（這邊為了版面一致所以 y 軸取一樣的級距，但是 `REF` 機制出現零碎的極大值情形較 `CPY` 機制頻繁）根據上面的 `cache miss rate` 去推測，很有可能就是當 `cache miss` 的時候，必須去 memory 裡面抓取資料所增加的 `latency`
- `CPY` 對於 prefix search 機制效能
- `REF` 對於 prefix search 機制效能
```cpp=239
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;
}
}
```
分析 `tst.c` 關於 insert 的敘述，當 `CPY` 時會 malloc 保存字串，增加額外的記憶體空間，
接著，比較完 prefix 搜尋之後，我們設計實驗觀察 `REF` `CPY` 兩種機制下，加上 `bloom filter` 前後，幾種字串輸入的效能分析。
**實驗一：字典內部隨機選取**
這個實驗是將九萬筆城市資料進行隨機取樣，然後進行搜尋，得到的結果如下圖所示，對於有加 `bloom filter` 與沒加 `bloom filter` 的情況，有加 `bloom filter` 低於0.002秒的圖形底層其實比較稀疏一點，代表平均起來搜尋結果高於0.002秒的點較常出現，整體搜尋時間來說，沒有 `bloom filter` 的搜尋會稍微快一些（圖片上面較不明顯），原因是因為有加 `bloom filter` 的情形在搜尋開始之前的時候會先重新將字串透過 `hash function` 轉換一次，進行 `hash table` 對 `hash key` 的確認後才會進入真正的 `tst` 搜尋，在這個情形中，由於我們所有的輸入字串都是從字典內部取得，所以比較均為成功，多出的 hash mapping 計算反而增加效能的負擔。
| \ | 有 bloom filter | 沒有 bloom filter |
| --- | --- | --- |
| **CPY** |||
| **REF** || |
經過比較之後，我們發現對於搜尋來說，其實 `REF` 機制和 `CPY` 機制並沒有相差很大，推測其中一個原因是因為平均秒數過小，搜尋時間受環境或是因素影響較大，所以 `cache miss` 造成的 `latency` 影響沒有顯現出來。
**實驗二：隨機字串(固定開頭大寫之後小寫)**
實驗二內容是隨機給定一個字串，只有開頭是大寫，其他都是小寫，字串的長度為6個字元，進行搜尋之後，呈現下圖的結果。實驗的預期原本猜測是有 `bloom filter` 的情形搜尋時間會大幅降低，因為對於一個隨機字串，透過 `hash function` 轉換之後應該很快就可以知道此字串是否屬於 `cities.txt` ，而且由於我們的字串是隨機的，所以應該不在`cities.txt` 的機率比較高才對（猴子打字機原理），但是結果出來效能並沒有提昇，反而朝向一個奇怪的方式分佈：
| \ | 有 bloom filter | 沒有 bloom filter |
| --- | --- | --- |
| **CPY** |||
| **REF** |||
思考一下這樣的結果，發現一個有趣的現象，由於字串的隨機性，當我們從 `tst` 的 root 開始比對下來時，也有很高的機率直接 return 不存在。
:::success
舉例來說：
搜尋 `Be` 當作 prefix 得到 2609 個可能的城市
搜尋 `Bl` 當作 prefix 得到 376 個可能的城市
搜尋 `Bg` 、 `Bk` 、 `Bt` 當作 prefix 均得到 No result
:::
這是根據文化、語法、發音等等原因，所以開頭高度集中於某些特定的字首，在第二個字元開始分散就極度不均等的情況下，到第二個字元回傳不存在的機率因此大幅上升，同時也降低了整體的搜尋時間。
:::info
TODO:研究為何在有 `bloom filter` 的情形搜尋時間分佈會呈現兩個區段分佈
:::
## 以 perf 分析 TST 程式碼的執行時期行為並且充分解讀
用 perf 分析，輸入
```
$ sudo perf stat ./test_common --bench CPY
```
```
$ sudo perf stat ./test_common --bench REF
```
得到以下結果：
```
CPY mechanism
ternary_tree, loaded 206849 words in 0.174244 sec
Performance counter stats for './test_common --bench CPY':
16,104.35 msec task-clock # 0.986 CPUs utilized
67 context-switches # 0.004 K/sec
0 cpu-migrations # 0.000 K/sec
7,348 page-faults # 0.456 K/sec
51,966,296,466 cycles # 3.227 GHz
50,435,658,306 instructions # 0.97 insn per cycle
7,538,992,738 branches # 468.134 M/sec
224,385,189 branch-misses # 2.98% of all branches
16.329711541 seconds time elapsed
16.025359000 seconds user
0.079986000 seconds sys
```
```
REF mechanism
ternary_tree, loaded 206849 words in 0.120071 sec
Performance counter stats for './test_common --bench REF':
18,852.90 msec task-clock # 0.999 CPUs utilized
79 context-switches # 0.004 K/sec
1 cpu-migrations # 0.000 K/sec
7,170 page-faults # 0.380 K/sec
55,456,300,927 cycles # 2.942 GHz
50,414,057,902 instructions # 0.91 insn per cycle
7,534,475,849 branches # 399.645 M/sec
224,267,391 branch-misses # 2.98% of all branches
18.867488778 seconds time elapsed
18.821164000 seconds user
0.032001000 seconds sys
```
觀察到，載入時間 `REF` 效能較高，因為不需要額外的 `malloc` 時間。
讀取 `cache` 內部，得到：
```
CPY mechanism
ternary_tree, loaded 206849 words in 0.171644 sec
Performance counter stats for './test_common --bench CPY':
1,677,730,516 cache-misses # 59.616 % of all cache refs
2,814,241,920 cache-references
50,431,936,426 instructions # 1.00 insn per cycle
50,604,876,868 cycles
14.978900109 seconds time elapsed
14.887244000 seconds user
0.044009000 seconds sys
```
```
REF mechanism
ternary_tree, loaded 206849 words in 0.166995 sec
Performance counter stats for './test_common --bench REF':
1,844,243,164 cache-misses # 59.582 % of all cache refs
3,095,309,932 cache-references
50,410,105,265 instructions # 0.92 insn per cycle
55,018,747,093 cycles
18.346063654 seconds time elapsed
18.244198000 seconds user
0.060013000 seconds sys
```
相較之下， `REF` 的 `cache miss` 較高，符合第一段討論的結果。
Sign in with Wallet
Connect another wallet