# 2020q3 Homework3 (dict)
contributed by < `johnnycck` >
###### tags: `sysprog2020`
---
## :penguin: 作業要求
> [dict 題目連結](https://hackmd.io/@sysprog/2020-dict)
- [ ] 在 GitHub 上 fork [dict](https://github.com/sysprog21/dict)，視覺化 ternary search tree + bloom filter 的效能表現並分析。注意，需要設計實驗，允許不同的字串輸入並探討 TST 回應的統計分佈
- [x] :warning: 若你的 GitHub 帳號在 2020 年 9 月 24 日已自 [dict](https://github.com/sysprog21/dict) fork，請在 GitHub 上重新 fork
- [ ] 要考慮到 prefix search 的特性還有詞彙的涵蓋率
- [ ] 限用 gnuplot 來製圖
- [ ] 以 perf 分析 TST 程式碼的執行時期行為並且充分解讀
- [ ] 考慮到 CPY 和 REF 這兩種實作機制，思考效能落差的緣故，並且提出後續效能改善機制
- [ ] 充分量化並以現代處理器架構的行為解讀
- [ ] 如何兼顧執行時間和空間運用效率？
- [ ] 研讀 [Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters](https://arxiv.org/abs/1912.08258) 論文並參閱對應程式碼實作 [xor_singleheader](https://github.com/FastFilter/xor_singleheader)，引入上述 [dict](https://github.com/sysprog21/dict) 程式碼中，需要比較原有的 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 的專案，並解析其導入的考量

---