2020q3 Homework3 (dict)

contributed by <RusselCK >

tags: RusselCK

dict

視覺化 ternary search tree + bloom filter 的效能表現並分析

• 允許不同的字串輸入並探討 TST 回應的統計分佈

• 要考慮到 prefix search 的特性還有詞彙的涵蓋率
• 限用 gnuplot 來製圖

以 perf 分析 TST 程式碼的執行時期行為並且充分解讀

• CPY 機制

$ sudo perf stat ./test_common --bench CPY
CPY mechanism
ternary_tree, loaded 206849 words in 0.108725 sec

 Performance counter stats for './test_common --bench CPY':

         13,760.11 msec task-clock                #    0.999 CPUs utilized          
                67      context-switches          #    0.005 K/sec                  
                 0      cpu-migrations            #    0.000 K/sec                  
             7,352      page-faults               #    0.534 K/sec                  
    46,180,340,963      cycles                    #    3.356 GHz                    
    52,118,242,060      instructions              #    1.13  insn per cycle         
     7,539,335,793      branches                  #  547.913 M/sec                  
       218,537,018      branch-misses             #    2.90% of all branches        

      13.770924690 seconds time elapsed

      13.740414000 seconds user
       0.020000000 seconds sys

• REF 機制

$ sudo perf stat ./test_common --bench REF
REF mechanism
ternary_tree, loaded 206849 words in 0.109187 sec

 Performance counter stats for './test_common --bench REF':

         19,406.16 msec task-clock                #    0.999 CPUs utilized          
                81      context-switches          #    0.004 K/sec                  
                 0      cpu-migrations            #    0.000 K/sec                  
             7,172      page-faults               #    0.370 K/sec                  
    54,332,178,006      cycles                    #    2.800 GHz                    
    52,101,462,485      instructions              #    0.96  insn per cycle         
     7,535,813,034      branches                  #  388.321 M/sec                  
       219,356,372      branch-misses             #    2.91% of all branches        

      19.422496812 seconds time elapsed

      19.350347000 seconds user
       0.055983000 seconds sys

考慮到 CPY 和 REF 這兩種實作機制，思考效能落差的緣故

• 充分量化並以現代處理器架構的行為解讀

如何兼顧執行時間和空間運用效率？

後續效能改善機制

研讀論文並參閱對應程式碼實作 xor_singleheader，引入 dict 程式碼中

• 論文：Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters

比較原有的 bloom filter 和 xor filter 在錯誤率及記憶體開銷

善用 Valgrind 和 Massif，使用方式參見 I01: lab0

如何縮減頻繁 malloc 帶來的效能衝擊呢？

提示: memory pool

• 儲存字串用的 memory pool 在 REF 版本中已實作，但在 tst_ins_del() 當中頻繁以 calloc() 配置節點空間造成的效能衝擊，應許以改進。
• REF 版本中的 pool 只會一直增添新的資料，並沒有從中移除資料的操作發生，因此可以用更進階的手段來管理
• tst 則會有移除節點的操作，我們無法確定要被刪除的節點他使用的記憶體落在 memory pool 的哪個地方，如何管理 memory pool， 使之不會有記憶體碎片產生，是這個問題的關鍵。

在現有的開放原始碼專案中，找出使用 bloom filter 的專案，並解析其導入的考量