# 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` 定義：

#define BENCH_TEST_FILE "bench_ref.txt"

並且呼叫 `bench.c` 中的函式產生

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 機制效能

        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` 較高，符合第一段討論的結果。