# G08: dict

:::info
主講人: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) / 課程討論區: [2019 年系統軟體課程](https://www.facebook.com/groups/system.software2019/)
:mega: 返回「[進階電腦系統理論與實作](http://wiki.csie.ncku.edu.tw/sysprog/schedule)」課程進度表
:::

## 預期目標

* 學習 [ternary search tree](https://en.wikipedia.org/wiki/Ternary_search_tree) 作為 [auto-complete](https://en.wikipedia.org/wiki/Autocomplete) 和 prefix search 的實作機制
* 學習 [Bloom filter](https://en.wikipedia.org/wiki/Bloom_filter) / [Quotient filter](https://en.wikipedia.org/wiki/Quotient_filter) 和 [ternary search tree](https://en.wikipedia.org/wiki/Ternary_search_tree) 的整合議題
* bit-wise operation 的實踐
* 設計效能評比 (benchmark) 的程式框架
* 學習 GNU make 和 `Makefile` 撰寫
* 複習機率統計和對應的數學基礎

## Linux 效能分析工具: Perf

* Perf 全名是 Performance Event，是在 Linux 2.6.31 以後內建的系統效能分析工具，它隨著核心一併釋出。藉由 perf，應用程式可以利用 PMU (Performance Monitoring Unit), tracepoint 和核心內部的特殊計數器 (counter) 來進行統計，另外還能同時分析運行中的核心程式碼，從而更全面了解應用程式中的效能瓶頸
* 參考 [使用 perf_events 分析程式效能](https://zh-blog.logan.tw/2019/07/10/analyze-program-performance-with-perf-events/) 和 [簡介 perf_events 與 Call Graph](https://zh-blog.logan.tw/2019/10/06/intro-to-perf-events-and-call-graph/) 這兩份中文介紹
* ==在自己的 Linux 開發環境實際操作==
* 再次提醒：你的 GNU/Linux「==不能==」也「==不該==」透過虛擬機器 (如 VMware, VirtualBox, QEMU 等等) 安裝
* 請務必依據 [GNU/Linux 開發工具共筆](https://hackmd.io/c/rJKbX1pFZ) 指示，將 Linux 安裝於實體硬碟並設定好多重開機

## 作業要求

* 詳細閱讀 [隱藏在字典裡的數學](https://hackmd.io/@sysprog/BkE3uSvdN)，並在自己的電腦環境重現裡頭的實驗，應該充分記錄所見所聞
* 在 GitHub 上 fork [dict](https://github.com/sysprog21/dict)，研讀並修改 `Makefile` 以允許 `$ make plot` 時，視覺化 ternary search tree + bloom filter 的效能表現。注意，需要設計實驗，允許不同的字串輸入並探討 TST 回應的統計分佈
* 要考慮到 prefix search 的特性還有詞彙的涵蓋率
* 限用 gnuplot 來製圖
* 參閱 [Hash Table Benchmarks](http://incise.org/hash-table-benchmarks.html)
* 以 perf 分析 TST 程式碼的執行時期行為並且充分解讀
* 考慮到 CPY 和 REF 這兩種實作機制，思考效能落差的緣故，並且提出後續效能改善機制
* 充分量化並以現代處理器架構的行為解讀
* 實作 [Quotient filter](https://en.wikipedia.org/wiki/Quotient_filter) 並整合進 [dict](https://github.com/sysprog21/dict) 程式碼中，需要比較兩者在錯誤率及記憶體開銷
* 研讀 [dict 改善 & 效能探討](https://hackmd.io/@j4ywJU0OTzS2BlwpJo6THA/r1ZdcbFpm)，改善現有程式碼;
* 依據下方程式碼檢查事項，逐一修正和分析;

## [dict](https://github.com/sysprog21/dict) 程式碼檢查事項
1. Bloom filter 空間浪費: 整個 table 都把 byte 當 bit 來用，浪費 7/8 的 table 空間

    void bloom_add(bloom_t filter, const void *item) {
        struct bloom_hash *h = filter->func;
        uint8_t *bits = filter->bits;
        while (h) {
            unsigned int hash = h->func(item);
            hash %= filter->size;
            bits[hash] = 1; // 每個 uint8_t 不是 1 就是 0
            h = h->next;
        }
    }

2. `test_cpy.c` 和 `test_ref.c` 兩個檔案有許多部分重複，是否能引入 `test-common.c` 來統合呢？
3. 城市名後面跟着逗號: 應該區分城市名和國家名。另外，記錄城市名時不應該把逗號也存下來
4. memory leaks 的偵測及修正
5. 如何縮減頻繁 malloc 帶來的效能衝擊呢？提示: [memory pool](https://en.wikipedia.org/wiki/Memory_pool)

## 繳交方式
* 編輯 [Homework 5 作業區共筆](https://hackmd.io/@sysprog/rkw3RV0YS)，將你的觀察、上述要求的解說、應用場合探討，以及各式效能改善過程，善用 gnuplot 製圖，紀錄於新建立的共筆

## 截止日期
* Nov 6, 2019 (含) 之前進行，不該截止日前一天才動手
* 越早在 GitHub 上有動態、越早接受 code review，評分越高