---
tags: 進階電腦系統理論與實作, NCKU Linux Kernel Internals, 作業系統
---

# [2020q3 Homework3](https://hackmd.io/@sysprog/2020-homework3) (dict)
contributed by <`RusselCK` >

###### tags: `RusselCK`

> [dict](https://hackmd.io/@sysprog/2020-dict#-Trie-%E5%92%8C-Ternary-search-tree)

## 視覺化 [ternary search tree](hhttps://hackmd.io/nnYME5GkRS2JEfY1WD28FA?view#-ternary-search-tree-%E7%9A%84%E5%AF%A6%E4%BD%9C%E7%A8%8B%E5%BC%8F%E7%A2%BC) + bloom filter 的效能表現並分析
* 允許不同的字串輸入並探討 TST 回應的統計分佈
>* 要考慮到 prefix search 的特性還有詞彙的涵蓋率
>* 限用 [gnuplot](https://hackmd.io/@sysprog/Skwp-alOg?type=view) 來製圖

## 以 [perf 分析](https://hackmd.io/nnYME5GkRS2JEfY1WD28FA?view#%E4%BD%BF%E7%94%A8-perf-%E5%88%86%E6%9E%90%E7%A8%8B%E5%BC%8F%E6%95%88%E8%83%BD) 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](https://github.com/FastFilter/xor_singleheader)，引入 dict 程式碼中
* 論文：[Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters](https://arxiv.org/abs/1912.08258)

#### 比較原有的 bloom filter 和 xor filter 在錯誤率及記憶體開銷
> 善用 Valgrind 和 [Massif](https://valgrind.org/docs/manual/ms-manual.html)，使用方式參見 [I01: lab0](https://hackmd.io/@sysprog/2020-lab0)

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

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