# 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 空間 ```cpp 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,評分越高