Try   HackMD

2016q3 Homework1 (phonebook)

Reviewed TotallyWrong

其實光是說明影片中就有很多線索可以把這個程式改善，例如利用 Hash 或是利用順序關係是可以省下很多搜尋時間。記憶體除了大小外位置也是很重要的，可以了解一下順序。

開發環境

  • 作業系統：Kubuntu 16.04.01 LTS (64bit)
  • 硬體
    • 查看硬體資訊：$ lscpu 
      ​​​​​​​​Architecture:          x86_64
​​​​​​​​CPU 作業模式：    32-bit, 64-bit
​​​​​​​​Byte Order:            Little Endian
​​​​​​​​CPU(s):                8
​​​​​​​​On-line CPU(s) list:   0-7
​​​​​​​​每核心執行緒數：2
​​​​​​​​每通訊端核心數：4
​​​​​​​​Socket(s):             1
​​​​​​​​NUMA 節點：         1
​​​​​​​​供應商識別號：  GenuineIntel
​​​​​​​​CPU 家族：          6
​​​​​​​​型號：              94
​​​​​​​​Model name:            Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz
​​​​​​​​製程：              3
​​​​​​​​CPU MHz：             808.429
​​​​​​​​CPU max MHz:           4000.0000
​​​​​​​​CPU min MHz:           800.0000
​​​​​​​​BogoMIPS:              6816.61
​​​​​​​​虛擬：              VT-x
​​​​​​​​L1d 快取：          32K
​​​​​​​​L1i 快取：          32K
​​​​​​​​L2 快取：           256K
​​​​​​​​L3 快取：           8192K
​​​​​​​​NUMA node0 CPU(s):     0-7

學習 Git 與 Github

上傳流程

  • 在 GitHub 上 fork phonebook
  • Clone 專案到本地端 
    ​$ git clone git@github.com:GoblinBear/repository.git
  • 修改專案
  • 將新增的檔案加入到 Git 版本控管 
    ​$ git add .
  • 提交變更到本地端 
    ​$ git commit -m "my commit"
  • 加入一個遠端儲存庫 
    ​$ git remote add origin http://github.com/GoblinBear/repository.git
  • 上傳到 GitHub 上的遠端儲存庫 
    ​$ git push origin master

指令

  • $ git reset：重設工作目錄的索引狀態
  • $ git log：查詢版本的歷史紀錄
  • $ git status：查詢當前工作目錄的詳細狀態

學習 Gnuplot

  • 用老師的 script 當範例 
    ​reset
​set ylabel 'time(sec)'
​set style fill solid
​set title 'perfomance comparison'
​set term png enhanced font 'Verdana,10'
​set output 'runtime.png'

​plot [:][:0.150]'output.txt' using 2:xtic(1) with histogram title 'original', \
​'' using ($0-0.06):($2+0.001):2 with labels title ' ', \
​'' using 3:xtic(1) with histogram title 'optimized'  , \
​'' using ($0+0.3):($3+0.0015):3 with labels title ' '
    • set ylabel 'time(sec)' 設定 y 座標軸名稱
    • set title 'perfomance comparison' 設定圖上的標題
    • [:][:0.150] X 座標軸，Y 座標軸從 0 到 0.150
    • xtic(1) X 軸的 label 是取自第1個 column
    • using 2:xtic(1) with histogram title 'original' 取第2個 column 的數據產生柱狀圖
    • ($0-0.06) label 的 X 軸座標
    • ($2+0.001) label 的 Y 軸座標

案例分析 phonebook

可能的效能改進方向

  • 改寫struct __PHONE_BOOK_ENTRY的成員，搬動到新的結構中
  • 使用 hash function 來加速查詢
  • 既然 first name, last name, address 都是合法的英文 (可假設成立)，使用字串壓縮的演算法，降低資料表示的成本
  • 使用 binary search tree 改寫演算法

原版

  • 編譯 
    ​$ make
  • 測試 
    ​$ make run
  • 輸出 
    ​size of entry : 136 bytes
​execution time of append() : 0.034903 sec
​execution time of findName() : 0.004713 sec
    (按下 Ctrl-C 可以離開畫面)
  • 清空 cache: 
    ​$ echo 1 | sudo tee /proc/sys/vm/drop_caches
  • 透過 gnuplot 建立執行時間的圖表 
    ​$ make plot
    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →

優化版 - 改寫資料結構

  • 減少entry空間
    只會用到lastName，所以將其他用不到的結構成員隱藏在detail中，因此entry的空間由 136 byte 降到 32 byte

    
















    ​typedef struct __PHONE_BOOK_DETAIL {
​	char firstName[16];
​	char email[16];
​	char phone[10];
​	char cell[10];
​	char addr1[16];
​	char addr2[16];
​	char city[16];
​	char state[2];
​	char zip[5];
​} detail;

​typedef struct __PHONE_BOOK_ENTRY {
​	char lastName[MAX_LAST_NAME_SIZE];
​	detail *d;
​	struct __PHONE_BOOK_ENTRY *pNext;
​} entry;

  • Cache miss 比較

    • 原版
    ​Performance counter stats for './phonebook_orig' (100 runs):

​​​​     4,487,968      cache-misses              #   90.803 % of all cache refs      ( +-  0.13% )
​​​​     4,942,555      cache-references                                              ( +-  0.08% )
​​​​   261,554,655      instructions              #    1.44  insns per cycle          ( +-  0.02% )
​​​​   181,260,699      cycles                                                        ( +-  0.18% )

​​​​   0.049006945 seconds time elapsed                                          ( +-  0.22% )
    • 優化版
    ​Performance counter stats for './phonebook_opt' (100 runs):

​​​​     1,376,895      cache-misses              #   61.605 % of all cache refs      ( +-  0.53% )
​​​​     2,235,047      cache-references                                             ( +-  0.16% )
​​​​   244,216,012      instructions              #    2.07  insns per cycle         ( +-  0.02% )
​​​​   117,889,769      cycles                                                       ( +-  0.47% )

​​​​   0.032283080 seconds time elapsed                                          (+-  0.52% )

  • 執行時間比較

    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →

  • 效能分析
    L1d cache = 32K，entry資料變少，cache 可以存更多筆entry，因此 cache miss 降低

優化版 - 資料大小為 Cache line 的倍數

優化版 - Hash function 加速查詢

資料閱讀

作法

  • Hash function：djb2
  • Table size = 42737，有約35萬個英文單字，為了減少碰撞機會，挑了一了蠻大的質數
  • 精度：優化後findName()執行時間小於10-6秒，所以我把fprintf()的參數%lf改成%.9lf

優化版 - 字串壓縮演算法

資料閱讀

壓縮演算法

  • Huffman Compression
  • Arithmetic Compression
    • 壓縮效果最好，達到了理論極限
    • 壓縮速度最快

算術編碼問題

  • 用算術編碼壓縮字串，若字串為zzzzzzzzzz，使用long double精度仍會不夠
[ 0] 0.994815802925586024 1.000000000000000000
[ 1] 0.999973124100693638 1.000000000000000000
[ 2] 0.999999860670041444 1.000000000000000000
[ 3] 0.999999999277686036 1.000000000000000000
[ 4] 0.999999999996255382 1.000000000000000000
[ 5] 0.999999999999980587 1.000000000000000000
[ 6] 0.999999999999999899 1.000000000000000000
[ 7] 0.999999999999999999 1.000000000000000000
[ 8] 1.000000000000000000 1.000000000000000000
[ 9] 1.000000000000000000 1.000000000000000000
tag = 1.000000000000000000
  • 除不盡的小數會造成解碼沒有盡頭，不知道什麼時候要停止，不知道中止條件
Last changed by 
 
GoblinBear
0
332
Published on HackMD