# 2020q3 Homework3 (dict)
contributed by < `WeiCheng14159` >
###### tags: `sysprog2020`
[dict](https://hackmd.io/@sysprog/2020-dict#-%E4%BD%9C%E6%A5%AD%E8%A6%81%E6%B1%82)
### 運作原理

比較 TST 的兩種查找模式：
* `tst_search` 用來查找一組字串是否存在 TST 中
* 可以使用 bloom filter 加速，在容許的錯誤範圍內更快給出結果
* `tst_search_prefix` 在 TST 中查找所有與輸入字串有相同前綴的字串
* 當然 `tst_search_prefix` 也可以用來當作 `tst_search` 使用

### 視覺化 ternary search tree + bloom filter 的效能表現並分析
在 `tst_search` 模式之下比較 `CPY` 和 `REF` 的效能

## 以 perf 分析 TST 程式碼的執行時期行為
## 考慮到 CPY 和 REF 這兩種實作機制，思考效能落差的緣故，並且提出後續效能改善機制
### 充分量化並以現代處理器架構的行為解讀
### 如何兼顧執行時間和空間運用效率？
## 研讀 Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters 論文並參閱對應程式碼實作 xor_singleheader，引入上述 dict 程式碼中，需要比較原有的 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 的專案，並解析其導入的考量