Try   HackMD

B01: phonebook

tags: sysprog2017

作業解說 video，請對照觀看

主講人: jserv / 課程討論區: 2017 年系統軟體課程
:mega: 返回「嵌入式作業系統設計與實作」課程進度表

預期目標

  • 準備 GNU/Linux 開發工具
  • 學習使用 Git 與 GitHub
  • 學習效能分析工具
  • 研究軟體最佳化
  • 技術報告寫作練習

Linux 效能分析工具: Perf

  • Perf 全名是 Performance Event，是在 Linux 2.6.31 以後內建的系統效能分析工具，它隨著核心一併釋出。藉由 perf，應用程式可以利用 PMU (Performance Monitoring Unit), tracepoint 和核心內部的特殊計數器 (counter) 來進行統計，另外還能同時分析運行中的核心程式碼，從而更全面了解應用程式中的效能瓶頸
  • 請詳讀 perf 原理和實務 並在自己的 Linux 開發環境實際操作
    • 再次提醒：你的 GNU/Linux「不能」也「不該」透過虛擬機器 (如 VMware, VirtualBox, QEMU 等等) 安裝，請務必依據 2017 年春季作業說明 指示，將 Linux 安裝於實體硬碟並設定好多重開機

案例探討：電話簿搜尋

  • 詳細閱讀 Programming Small 裡頭的電話簿程式，研究降低 cache miss 的方法
  • 雖然這是探討 cache miss 和效能議題，其實是帶著同學重新複習 C 語言和資料結構。以前大家只是「背誦心法」，從來就不會去理解個別資料結構對整體的衝擊。
  • 自 GitHub 取得作業程式碼 (基礎)
$ git clone https://github.com/sysprog21/phonebook/
$ cd phonebook
  • 編譯
$ make
  • 測試。當看到 [sudo] password for 字樣時，輸入自己的 Linux 使用帳號密碼
$ make run
  • 參考輸出： (按下 Ctrl-C 可以離開畫面)
size of entry : 136 bytes
execution time of append() : 0.043859 sec
execution time of findName() : 0.004776 sec
  • 透過 gnuplot 建立執行時間的圖表 (保持耐心等待，中間過程不要切換視窗)
$ make plot
  • 正確執行後，目錄裡頭會有個名為 runtime.png，可用 eog runtime.png 命令來觀看

善用 gnuplot 來製圖

  • 從今天起忘記 Microsoft Excel，因為 gnuplot 可以給你更專業的圖表，而且能夠批次產生
  • 先啟動 gnuplot:
$ gnuplot
  • gnuplot 啟動後，需要做一些必要設定，例如設定圖片名稱，XY軸的資訊等等:
> set title 'my plot'           ＠ 設定圖片名稱
> set xlabel 'x axis'           ＠ 設定XY軸座標名稱
> set ylabel 'y axis'
> set terminal png              ＠ 設定輸出格式為 .png
> set output 'output_plot.png'  ＠ 設定輸出檔名
> plot [1:10][0:1] sin(x)       ＠ 畫出 sin(x) 函式
                                @ x軸座標範圍 1-10
                                @ y軸座標範圍 0-1
  • 可以將這些設定另外存成一個檔案，作為 gnuplot 的腳本。假設上述指令存在一個名為 plot 的檔案裡面，以後只要輸入 gnuplot plot 即可畫出我們想要的圖表。
  • 參考圖表: 
  • 請繼續閱讀 gnuplot 語法解說和示範

使用 astyle + Git 實做自動程式碼排版檢查

  • 使用一致的 coding style 很重要，我們可透過 astyle 這個工具來協助。調整作業程式要求的風格為以下:
$ astyle --style=kr --indent=spaces=4 --indent-switches --suffix=none *.[ch]
  • 你可以想像 Apple 和 Google 的工程師隨便安置程式碼，然後不用管合作的議題嗎？
    • 即便一個人寫作業，其實是三人的參與：過去的你、現在的你，以及未來的你
  • 當首次執行 make 後，Git pre-commit hook 將自動安裝到現行的工作區 (workspace)，之後每次執行 git commit 時，Git hook 會檢查 C/C++ 原始程式碼的風格是否一致:
    • 我們介紹 Git hooks 是為了日後銜接 Continuous integration (CI)，專業程式設計必備的準備工作
    • 任何人都可以寫出機器看得懂的程式碼 (在檔案總管裡面對 EXE 檔複製貼上即可)，但我們之所以到資訊工程系接受訓練，為了寫出人看得懂、可持續維護和改進的程式
  • 下圖展示 Git pre-commit hook 偵測到開發者的修改並未遵守一致的 coding style，主動回報並提醒開發者: 

作業要求

  • 在 GitHub 上 fork phonebook (若你在 2017 年 2 月 20 日之前已經 fork phonebook，那應該重新 fork 過)，然後適度修改 phonebook_opt.c 和 phonebook_opt.h 兩個檔案，使得這兩者執行時期的 cache miss 降低。請用 perf 驗證，而且改進的過程中，不能有功能方面的減損。

    • phonebook_orig.[ch] 不需要修改，我們關注的是 phonebook_opt.[ch]，當然要修改 main.c 也是允許的
    • findName() 的時間必須原本的時間更短
    • append() 的時間可以比原始版本稍久，但不應該增加太多，請參照下方共筆選讀的方法，著手縮減 append() 的時間開銷
    • main.c 應該只有一份，不要建立新的 main()，善用 Makefile 定義對應的 CFLAGS
    • 過程中也會需要改動到 Makefile，請詳閱 Makefile 語法和示範
    • 在執行程式(phonebook_orig 和 phonebook_opt) 前，先清空 cache:
    ​$ echo 1 | sudo tee /proc/sys/vm/drop_caches

  • 除了修改程式，也要編輯「作業區」，增添開發紀錄和 GitHub 連結

    • 至少要列出效能分析，以及充份說明你如何改善效能
    • 以 gnuplot 繪製效能分析圖表

  • 務必使用 astyle 來對程式碼進行排版，詳細使用方式見 README.md

  • 回答以下問題：本例選用的 dataset (也就是輸入電話簿的姓名) 是否存在問題？

    • 有代表性嗎？跟真實英文姓氏差異大嗎？
    • 資料難道「數大就是美」嗎？
    • 如果我們要建立符合真實電話簿情境的輸入，該怎麼作？

  • 詳細閱讀 示範用的 Phonebook 作業，嘗試在自己的環境中重現裡頭的實驗，比照其中的寫作格式，第一段要提及「開發環境」，並且充分比較不同資料結構的影響

  • 可能的效能改進方向：

    • 使用 binary search tree 或其他資料結構改寫
    • 藉由 hash function 來加速查詢，請詳閱 hash function 觀念和實務
    • 既然 first name, last name, address 都是合法的英文 (可假設成立)，使用字串壓縮的演算法，降低資料表示的成本

  • 截止日期：

    • Mar 4, 2017 (含) 之前
    • 越早在 GitHub 上有動態、越早接受 code review，評分越高

挑戰題

  • 除了降低 findName() 的 cache miss 與執行成本，append() 也該想辦法縮減時間
    • 建立 phone book 時，既然 lastName 是索引值，可以優先建立搜尋表格，其他資料可稍後再補上
  • 支援 fuzzy search，允許搜尋 lastName 時，不用精準打出正確的寫法
  • 改善電話簿的效能分析，透過大量的重複執行，找出 95% 信賴區間，而且允許動態新增資料 (較符合現實) 和查詢

見賢思齊：共筆選讀

  • 0140454: 共筆
    • 觀察程式中所使用的 words.txt，他發現，輸入已照字典序排序好，接著他思考：「如果把資料打亂再測試一次的話，結果是否會有所不同？」
    • 他打亂後發現，未優化前與前兩種方式所受到的影響比較小。而，trie 和 red-black tree 的方式，均有明顯的不同。原因在於順序的不同，導致在維護樹的時候有所差異。
    • 下一步，應該尋找一個適當的lastname dataset來做測試，因為words.txt中包含了許多沒有名字意義的單字。
    • 考慮用詞彙庫代替phonebook，挑戰會高很多也實用多了，就隨機輸入一篇專業文章然後逐步搜尋字彙。詞彙庫可以用微軟的: https://www.microsoft.com/Language/zh-tw/Terminology.aspx
  • nekoneko: 共筆
    • 引入 hash function 來改寫電話簿的搜尋機制時，針對 h(x) = x mod M 形式的函數，用不同的 M 帶入，發現 hash value 分佈落差很大
    • 延伸閱讀: MIT 線上課程 10. Dictionaries (video)
    • 單純將字元直接相加就是 lose-lose hash function
    • 可參考這篇: Hash Functions
    • 另外 hash function 做 mod 出來如果呈現 uniform distribution 才是最好的，搜尋每一個 bucket 的 worst case 都差不多，而像 lose-lose 遇到 worst case 就糟糕了
  • jkrvivian: 共筆
    • 觀察修改 data representation 對於 cache miss 和整體執行時間的衝擊外，她嘗試引入字串壓縮演算法，想研究 SMAZ 一類的字串壓縮演算法，對於 cache 的影響。
    • 因為我們給定的字典檔跟現實落差太大，所以常見的字串壓縮演算法往往無法發揮作用，會得到比原本字串還長的輸出，導致反效果。不過，如果善用壓縮演算法，針對特定的情況，會有幫助。
    • 實驗的精神、方法，以及最後如何解讀並且提出新的假設再持續調整，非常重要
  • louielu: 共筆
    • 研究 perf 資料的同時，花了很多時間研究究竟如何精準測量執行時間 (再多核心系統中，這件事越來越困難)，他從 PMU 的原理開始研讀，交叉對照 Intel® 64 and IA-32 Architectures Developer’s Manual，知曉 perf event 背後的議題，他也著手翻譯了部份技術文件，相當難得。
    • __builtin___clear_cache 可清除指定範圍內的 instruction cache，實做在 GNU Toolchain 提供的 libgcc 中。呂同學還注意到給定的 linked list 實做上，透過 e = append(line, e) 這種方式來 append，可以降低一般 linked list append 需要 O(n) 的時間，可是必須要維護一個 list head，這是很重要的發現
  • dada
  • rnic
  • Yuron

參考資料

引用過往作業成果時，務必標註出處 (包含 GitHub 帳號或人名)，連帶相關的超連結

Last changed by 
 
Jim Huang
0
5167
Published on HackMD