G08: dict

主講人: jserv / 課程討論區: 2019 年系統軟體課程

返回「進階電腦系統理論與實作」課程進度表

預期目標

• 學習 ternary search tree 作為 auto-complete 和 prefix search 的實作機制
• 學習 Bloom filter / Quotient filter 和 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 分析程式效能 和 簡介 perf_events 與 Call Graph 這兩份中文介紹
• 在自己的 Linux 開發環境實際操作
  • 再次提醒：你的 GNU/Linux「不能」也「不該」透過虛擬機器 (如 VMware, VirtualBox, QEMU 等等) 安裝
  • 請務必依據 GNU/Linux 開發工具共筆 指示，將 Linux 安裝於實體硬碟並設定好多重開機

作業要求

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

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

繳交方式

• 編輯 Homework 5 作業區共筆，將你的觀察、上述要求的解說、應用場合探討，以及各式效能改善過程，善用 gnuplot 製圖，紀錄於新建立的共筆

截止日期

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