# 2017q1 Homework1 (phonebook) contribute by <`illusion030`> --- **Reviewed by `csielee`** * 在 BST 實作的部份，並沒有把建立 BST 的時間納入 append() 的執行時間中，造成最後效能不真實 ![](https://i.imgur.com/ptta8Dd.png) >可以發現在原始跟 BST 的版本， append 時間幾乎相同 而縮減結構跟 combine 版本， append 也幾乎相同 就是因為沒有把建立 BST 的時間納入，因此產生這樣的時間 * 在建立 BST 的函數中，每次建立 root 都會呼叫 malloc ，不過在 append 的時候就有 malloc，可以在建立 BST 的時候重複利用 malloc 出來的空間 * 可以嘗試利用編譯時的 -D 選項，去定義特定變數，方便產生多種版本，也能避免要寫很多份差不多的 code > 例如 ``` gcc -Wall -std=gnu99 -O0 -DIMPL="\"phonebook_opt.h\"" -DBST=1 -o phonebook_bst main.c phonebook_opt.c ``` > 這樣要做出組合版本(主要是因為方法1、2不衝突) > 可以呼叫 -DBST=1 -DOPT=1 ```clike typedef struct __PHONE_BOOK_ENTRY { char lastName[MAX_LAST_NAME_SIZE]; #ifdef OPT details *detail; #else 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]; #endif struct __PHONE_BOOK_ENTRY *pNext; #ifdef BST struct __PHONE_BOOK_ENTRY *pRight; struct __PHONE_BOOK_ENTRY *pLeft; #endif } entry; ``` ### Reviewed by `Billy4195` * BST可以改成在main function的地方就建立,不要建成linked-list再做轉換,可以減少轉換的時間。 * BST轉換的function有點問題,是從最左下角的leaf開始建的（猜測是因為輸入資料是排序過的所以才這樣做的）,如果是不想造成歪斜樹(Skewed binary tree),可以考慮改用RB-tree做平衡。 * [commit 3f9a271](https://github.com/illusion030/phonebook/commit/3f9a2717740ebc6aacfe9455d2d2d57bbecce8bd)這個commit可以用rebase修改前面的commit,可以參考[此篇文章](https://blog.yorkxin.org/2011/07/29/git-rebase)。 --- ## 開發環境 ``` illusion030@illusion030-X550LD:~$ lscpu Architecture: x86_64 CPU 作業模式： 32-bit, 64-bit Byte Order: Little Endian CPU(s): 4 On-line CPU(s) list: 0-3 每核心執行緒數：2 每通訊端核心數：2 Socket(s): 1 NUMA 節點： 1 供應商識別號： GenuineIntel CPU 家族： 6 型號： 69 Model name: Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz 製程： 1 CPU MHz： 1665.197 CPU max MHz: 2600.0000 CPU min MHz: 800.0000 BogoMIPS: 4588.94 虛擬： VT-x L1d 快取： 32K L1i 快取： 32K L2 快取： 256K L3 快取： 3072K NUMA node0 CPU(s): 0-3 ``` --- ## 事前準備 * 參考教學影片 [輕鬆學會 Windows / Ubuntu 雙系統安裝](https://www.youtube.com/watch?v=rjpBTT6AmeU) 安裝 window/linux 雙系統 * 參考 [Wiki - vimrc設定教學](http://wiki.csie.ncku.edu.tw/vim/vimrc) [Vundle：Vim Plugin 自動下載、安裝、更新與管理工具（Vim Bundle）](https://blog.gtwang.org/linux/vundle-vim-bundle-plugin-manager/) 安裝 vundle1 並設定 .vimrc ```vim= set nocompatible filetype off set rtp+=~/.vim/bundle/vundle/ call vundle#rc() Plugin 'gmarik/vundle' Plugin 'scrooloose/nerdtree' Plugin 'octol/vim-cpp-enhanced-highlight' syntax on set number set cursorline colorscheme default set bg=dark set tabstop=4 set expandtab set shiftwidth=4 set ai set hlsearch set smartindent map <F4> : set nu!<BAR>set nonu?<CR> map <F5> : NERDTreeToggle<CR> let g:cpp_class_scope_hilight = 1 let g:cpp_member_variable_hilight = 1 let g:cpp_experimental_simple_template_highlight = 1 let g:cpp_experimental_template_highlight = 2 ``` * 參考[GitHub 設定指引](http://wiki.csie.ncku.edu.tw/github) 學習 GitHub 的基本使用方式 * 參考[perf 原理和實務](https://hackmd.io/s/B11109rdg#) 了解效能分析工具 perf * 參考[gnuplot 語法解說和示範](https://hackmd.io/s/Skwp-alOg#) 初步了解 gnuplot 繪圖工具並將[runtime.gp](https://github.com/illusion030/phonebook/blob/master/scripts/runtime.gp)看懂 --- ## 原始版本 先將 [phonebook](https://github.com/sysprog21/phonebook/) fork 至自己的 [GitHub](https://github.com/illusion030/phonebook) 中 從 [GitHub](https://github.com/illusion030/phonebook) 上 clone 至本地端 ``` $ git clone https://github.com/illusion030/phonebook ``` 觀察 cache ``` $ make $ echo 1 | sudo tee /proc/sys/vm/drop_caches $ sudo make cache-test ``` ``` Performance counter stats for './phonebook_orig' (100 runs): 964,747 cache-misses # 88.200 % of all cache refs ( +- 0.36% ) 1,093,818 cache-references ( +- 0.21% ) 262,073,087 instructions # 1.51 insn per cycle ( +- 0.02% ) 173,571,440 cycles ( +- 0.16% ) 0.069692125 seconds time elapsed ( +- 0.61% ) ``` cache-misses 高達 88.2% --- >中英文字間記得以空白隔開! >[name=課程助教][color=red] ## 方式1-減少 struct 大小 * 參考 [Programming Small](https://hackmd.io/s/HkO2ZpIYe#) * 查看 cache 大小 ``` illusion030@illusion030-X550LD:~/Desktop/2017sysprog/phonebook$ lscpu | grep 快取 L1d 快取： 32K L1i 快取： 32K L2 快取： 256K L3 快取： 3072K ``` * level1 cache 大小為 32kbit，entry 的大小為 136bytes，32 * 1024 / (136 * 8) = 30.12，level1 cache 最多只能放 30 個 entry，會產生大量的 cache miss。 * 因為 findname() 是尋找 lastname，所以將 entry 縮小為只剩 lastName[]、*pNext 再加上一個指向 details 的指標 *detail ```=vim #define MAX_LAST_NAME_SIZE 16 typedef struct __PHONE_BOOK_ENTRY_DETAILS{ 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]; }details; typedef struct __PHONE_BOOK_ENTRY { char lastName[MAX_LAST_NAME_SIZE]; details *detail; struct __PHONE_BOOK_ENTRY *pNext; } entry; ``` * 此時，新的 entry 只有 32byte，level1 cache 大小為 32kbit，32 * 1024 / (32 * 8) = 128，level1 cache 最多可以放到 128 個 entry，大幅增加 cache hit 的次數。 * 實際跑一次 ``` $ echo 1 | sudo tee /proc/sys/vm/drop_caches $ sudo make cache-test ``` ``` size of entry : 136 bytes execution time of append() : 0.049777 sec execution time of findName() : 0.005254 sec Performance counter stats for './phonebook_orig' (100 runs): 987,058 cache-misses # 87.740 % of all cache refs ( +- 0.16% ) 1,124,977 cache-references ( +- 0.28% ) 262,133,370 instructions # 1.48 insn per cycle ( +- 0.02% ) 177,595,755 cycles ( +- 0.41% ) 0.072567950 seconds time elapsed ( +- 0.95% ) size of entry : 32 bytes execution time of append() : 0.040664 sec execution time of findName() : 0.002458 sec Performance counter stats for './phonebook_opt' (100 runs): 109,817 cache-misses # 28.277 % of all cache refs ( +- 0.84% ) 388,364 cache-references ( +- 0.72% ) 244,550,148 instructions # 1.95 insn per cycle ( +- 0.02% ) 125,603,317 cycles ( +- 0.58% ) 0.051310265 seconds time elapsed ( +- 0.75% ) ``` * cache-misses 降低為 28.277%，總消耗時間減少了約 29.29% * 把比較圖畫出來 ``` $ sudo make plot ``` >> 製圖時，應該避免用 `sudo` [name="jserv"] ![plot result](https://i.imgur.com/MhG9C8q.png) * append() 減少約 18.01%、findName() 減少約 53.87%、兩者加起來減少約 21.57% --- ## 方式2-將linked list的結構改寫成binary search tree * 參考 [Sorted Linked List to Balanced BST](http://ppt.cc/9ihkO) * 因為資料是已經被排序好的 所以直接將 linked list 的資料結構轉成 binary search tree 可以增進 search 的效率 假設 binary search tree 的高度為 7 可以存 128 筆資料 而搜尋其中一個資料 7 最多只需要搜尋 7 次 但是如果是 linked list 的資料結構存了 128 筆資料 搜尋其中一個資料最多需要搜尋到 128 次 * 將 linked list 轉為 binary search tree 的 function ```=vim entry *LinkedlistToBSTRecur(int count, entry **root) { if (count <= 0) return NULL; entry *left = LinkedlistToBSTRecur(count/2, root); entry *bstroot = (entry *) malloc(sizeof(entry)); bstroot->pNext = NULL; bstroot->pRight = NULL; bstroot->pLeft = NULL; strcpy(bstroot->lastName, (*root)->lastName); bstroot->pLeft = left; (*root) = (*root)->pNext; bstroot->pRight = LinkedlistToBSTRecur(count - count/2 - 1, root); return bstroot; } ``` * 觀察 cache-misses 的改變 ``` Performance counter stats for './phonebook_orig' (100 runs): 967,438 cache-misses # 88.373 % of all cache refs ( +- 0.32% ) 1,094,726 cache-references ( +- 0.34% ) 262,050,804 instructions # 1.51 insn per cycle ( +- 0.02% ) 173,038,845 cycles ( +- 0.12% ) 0.069173688 seconds time elapsed ( +- 0.76% ) Performance counter stats for './phonebook_bst' (100 runs): 477,853 cache-misses # 72.653 % of all cache refs ( +- 1.02% ) 657,723 cache-references ( +- 1.61% ) 340,792,831 instructions # 1.38 insn per cycle ( +- 0.02% ) 246,767,569 cycles ( +- 0.87% ) 0.099517555 seconds time elapsed ( +- 1.19% ) ``` * cache-misses 減少為 72.653%，時間多消耗了 1.44%，也許是因為要把 linked list 轉成 binary search tree 消耗的時間過多。 * 畫出比較圖 ![](https://i.imgur.com/AwmirP2.png) * append() 的時間差不多，findName() 的時間大幅下降，兩者相加時間下降約 9.9% --- ## 方式3-將方式1、2結合 * 將資料結構轉成 binary search tree 並將 struct 大小減少 * struct 內容 ```=vim typedef struct __PHONE_BOOK_ENTRY { char lastName[MAX_LAST_NAME_SIZE]; details *detail; struct __PHONE_BOOK_ENTRY *pNext; struct __PHONE_BOOK_ENTRY *pRight; struct __PHONE_BOOK_ENTRY *pLeft; } entry; ``` * 觀察 cache-misses ``` Performance counter stats for './phonebook_orig' (100 runs): 980,278 cache-misses # 88.622 % of all cache refs ( +- 0.21% ) 1,106,137 cache-references ( +- 0.16% ) 262,074,958 instructions # 1.51 insn per cycle ( +- 0.02% ) 173,583,429 cycles ( +- 0.12% ) 0.069245691 seconds time elapsed ( +- 0.22% ) Performance counter stats for './phonebook_opt' (100 runs): 111,577 cache-misses # 29.504 % of all cache refs ( +- 0.65% ) 378,174 cache-references ( +- 0.45% ) 244,507,593 instructions # 1.98 insn per cycle ( +- 0.02% ) 123,278,614 cycles ( +- 0.15% ) 0.049298250 seconds time elapsed ( +- 0.18% ) Performance counter stats for './phonebook_bst' (100 runs): 468,251 cache-misses # 73.256 % of all cache refs ( +- 0.11% ) 639,198 cache-references ( +- 0.27% ) 340,552,947 instructions # 1.42 insn per cycle ( +- 0.02% ) 239,774,681 cycles ( +- 0.14% ) 0.094940757 seconds time elapsed ( +- 0.16% ) Performance counter stats for './phonebook_combine' (100 runs): 204,236 cache-misses # 66.136 % of all cache refs ( +- 0.63% ) 308,813 cache-references ( +- 0.52% ) 305,335,087 instructions # 1.70 insn per cycle ( +- 0.01% ) 179,356,268 cycles ( +- 0.22% ) 0.071891923 seconds time elapsed ( +- 0.35% ) ``` * cache-misses 減少為 66.136%，時間相較於原始版本還是增加了 1.04% * 畫出比較圖 ![](https://i.imgur.com/ptta8Dd.png) * append() 的時間減少約 15.32%、append() + findName() 的時間降為最小，減少約 23.71% --- ## 小結 * 方式1-減少 struct 大小 * 直接有效降低 cache-misses 及消耗時間 * 方式2-將 linked list 的資料結構轉為 balanced binary search tree * 大幅降低 findName() 的時間 * 但因為需要轉變資料結構，整體消耗時間增加 * 方式3-將前兩個方式結合，減少 struct 大小以及將 linked list 轉為 balanced BST * findName() + append() 的時間降到最低 * cache-misses 比方式1多，因為 struct 還是比方式1大一點 * 整體時間跟原始版本差不多 --- ## GitHub commit 修改 * 需要修改的兩個原因 * commit message 寫的不夠清楚 [How to Write a Git Commit Message](https://chris.beams.io/posts/git-commit/) * 檔案名字取的不好 e.g. 原本有兩組檔案為 phonebook_bst.[ch] 和 phonebook_bst_opt.[ch]，因為名字太相近會導致識讀困難 * 參考 [Git 工具 - 重寫歷史](https://git-scm.com/book/zh-tw/v1/Git-%E5%B7%A5%E5%85%B7-%E9%87%8D%E5%AF%AB%E6%AD%B7%E5%8F%B2) * 修改上一次 commit 內容 增加或刪除上一次 commit 的檔案 ``` $ git push 檔名 $ git rm 檔名 ``` 更改檔名 ``` $ git mv 原本檔名 更改檔名 ``` 修改上一次 commit 訊息 ``` $ git commit --amend ``` * 修改前幾次 commit 訊息 HEAD~ 後接的數字為要修改最近幾次提交的訊息 假設 HEAD~3 就是修改最近三次 commit 的訊息 ``` $ git rebase -i HEAD~3 ``` 會顯示以下訊息 將要修改的 commit 訊息設成 edit ``` pick 23decc8 Delete the dead code. pick a638af0 change Linkedlist to balancedBST in phonebook_bst.[ch] pick 9ecbe28 Reduce size of struct & change LinkedLIst to BalanceBST in phoneb ... ``` 接下來 ``` $ git commit --amend ``` 修改完訊息後 ``` $ git rebase --continue ``` 重複前兩個動作直到修改完所有要修改的訊息 --- ## Gnuplot * 參考 [gnuplot 語法解說和示範](https://hackmd.io/s/Skwp-alOg#)中的美圖欣賞，將 label 上色，讓數據比較好讀 * 在各個 label 最後加上 textcolor lt ```=vim plot [:][:0.150]'output.txt' using 2:xtic(1) with histogram title 'original', \ '' using ($0):(0.085):2 with labels title ' ' textcolor lt 1, \ '' using 3:xtic(1) with histogram title 'optimized' , \ '' using ($0):(0.08):3 with labels title ' ' textcolor lt 2, \ '' using 4:xtic(1) with histogram title 'binarysearchtree' , \ '' using ($0):(0.075):4 with labels title ' ' textcolor lt 3, \ '' using 5:xtic(1) with histogram title 'combine' , \ '' using ($0):(0.07):5 with labels title ' ' textcolor lt 4, \ ``` --- ## dataset 是否存在問題？ * 有代表性嗎？跟真實英文姓氏差異大嗎？ * words.txt 中有大量沒有意義的單字(ex.aaaaa)，寫一個比較的程式發現，words.txt 裡總共 349900 筆資料，但是只有 7426 筆資料有在 all-names.txt 裡出現，所以 words.txt 對 phonebook 來說代表性很低。 ``` illusion030@illusion030-X550LD:~/Desktop/2017sysprog/phonebook/dictionary$ ./a.out total = 349900, same = 7426 ``` * 資料難道「數大就是美」嗎？ * 資料量大代表資料比較齊全，但若是大部分資料都為沒有意義的資料 (例如 words.txt 的資料) 反而會增加不必要的搜尋的時間。 * 同樣搜尋在 words.txt 和 find-names.txt 裡都有的名字 (zuzana) ，在 words.txt 中 append() 需要約 0.066 秒而 findName() 需要約 0.0067 秒，但是在 all-names.txt 裡 append() 只需要約 0.016 秒 findName() 只需要約 0.0001 秒。 ``` size of entry : 136 bytes execution time of append() : 0.065577 sec execution time of findName() : 0.006663 sec ``` ``` size of entry : 136 bytes execution time of append() : 0.015767 sec execution time of findName() : 0.000100 sec ``` * 如果我們要建立符合真實電話簿情境的輸入，該怎麼作？ * 可以刪除掉不必要或重複的資料，像輸入時都跟 all-names.txt 的資料比較，如果不存在裡面就不要儲存它。