# 2020q3 Homework3 (dict)
contributed by < [stonelin](https://github.com/StoneLin0708) >

###### tags: `sysprog2020`

---

* [ ] 在 GitHub 上 fork dict，視覺化 ternary search tree + bloom filter 的效能表現並分析。注意，需要設計實驗，允許不同的字串輸入並探討 TST 回應的統計分佈
* 要考慮到 prefix search 的特性還有詞彙的涵蓋率
* 限用 gnuplot 來製圖
* [ ] 以 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 的專案，並解析其導入的考量