2017q3 Homework1(phonebook)
===
contributed by <`TsengWen`>
> #### Review by `maskashura`
>- Hash table採用26個字母為key value,是否有考量key value crush所造成的效能瓶頸?
>- 試著用未排序過的資料做輸入,觀察是否有不同的效能差異
>- 試著解釋加入 hash table 對 append() 所造成的影響
## 預期目標
- [x]準備 GNU/Linux 開發工具
- [x]學習使用 Git 與 GitHub
- [x]學習效能分析工具
- [ ]研究軟體最佳化
- [ ]技術報告寫作練習
## 開發環境
### 安裝雙系統
- 作業系統：Ubuntu 16.04 LTS (64bit)
- CPU：4-core 2.50 GHz
- Memory:8G
- Cache
- L1d cache: 32K
- L1i cache: 32K
- L2 cache: 256K
使用 `lscpu` 可查詢硬體資訊
> 也可以使用Portable Hardware Locality (hwloc) 取得硬體資訊 [網址](https://www.open-mpi.org/projects/hwloc/)
```
$sudo apt-get install hwloc
$lstopo
```
### 修改terminal prompt
==vim .bachrc 中加入==
```
## Set git prompt
function git_branch {
ref=$(git symbolic-ref HEAD 2> /dev/null) || return;
echo "("${ref#refs/heads/}")";
}
function git_since_last_commit {
now=`date +%s`;
last_commit=$(git log --pretty=format:%at -1 2> /dev/null) || return;
seconds_since_last_commit=$((now-last_commit));
minutes_since_last_commit=$((seconds_since_last_commit/60));
hours_since_last_commit=$((minutes_since_last_commit/60));
minutes_since_last_commit=$((minutes_since_last_commit%60));
echo "${hours_since_last_commit}h${minutes_since_last_commit}m";
}
PS1="${debian_chroot:+($debian_chroot)}\[\033[01;32m\]\u\[\033[00m\]@\[\033[01;36m\]\h\[\033[00m\]:[\[\033[1;32m\]\w\[\033[0m\]]\[\033[0m\]\[\033[1;36m\]\$(git_branch)\[\033[0;33m\]\$(git_since_last_commit)\[\033[0m\]$ "
```
### vimrc 設定
>中英文字間需以空白隔開
>[name=課程助教][color=red]
參考
- [個人化自己的 vim 文字編輯器(.vimrc 設定教學) | MagicLen](https://magiclen.org/vimrc/)
- [凍仁的筆記: Vim 環境設定 - vimrc](http://note.drx.tw/2008/01/vimrc-config.html)
```
" 自動縮排：啟用自動縮排以後，在貼上剪貼簿的資料時排版可能會亂掉，這時可以手動切換至貼上模式 :set paste 再進行貼上。
set ai
" 文字編碼加入 utf8。
set enc=utf8
" 標記關鍵字。
set hls
" 只在 Normal 以及 Visual 模式使用滑鼠，也就是取消 Insert 模式的滑鼠，
set mouse=nv
" 顯示行號。
" set number
" 搜尋不分大小寫。
set ic
" 自訂縮排 (Tab) 位元數。
set tabstop=2
set shiftwidth=2
" 字數過長時換行。
set wrap
" 自動切換當前目錄。
set autochdir
" 捲動時保留底下 3 行。
set scrolloff=3
" 摺疊 Folding。
set foldenable
set foldmethod=indent
set foldcolumn=1
set foldlevel=5
" 在 fish 裡相容 Vim 裡的 Neobundle。
set shell=/bin/bash
" 複製模式
set paste
```
### Git 操作
- 參考網站
[Learn Git Branching](http://learngitbranching.js.org/)
[GitHub 設定指引](http://wiki.csie.ncku.edu.tw/github)
[連猴子都能懂的Git入門指南 | 貝格樂（Backlog）](https://backlogtool.com/git-guide/tw/)
- 建立好 Git 帳號後 ，ssh 設定
```
$ssh-keygen
$cat ~/.ssh/id_rsa.pub
```
- 將~/.ssh/id_rsa.pub 加入到 Github 網站
測試是否成功
```
$ssh -T git@github.com
結果
Hi TsengWen! You've successfully authenticated, but GitHub does not provide shell access.
```
- [個人設定筆記](https://hackmd.io/s/rkXknFtb)
```
$ git config --global user.email "benson326789@gmail.com"
$ git config --global user.name "TsengWen"
git config --global alias.st status
git config --global alias.cm "commit -m"
git config --global alias.last 'log -1 HEAD'
```
### Perf（效能分析工具）
- 參考網址
[Wiki - Linux 效能分析工具: Perf](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial)
需要先將 perf 權限打開
```
$ sudo sh -c " echo 0 > /proc/sys/kernel/perf_event_paranoid"
```
照著步驟實作了一下，但途中使用到一些指令:
- $ uname 顯示作業系統
- $ uname -r 顯示release time number 應該就是kernel版本
- $ perf top -p <pid> 偵測這個process 每個指令所耗費的CPU cycle
- $ perf list 列出可以偵測的event
- $ perf state --repeat <num> -e <event> <bin>.對這個執行檔，偵測所指定的event
- $ ./phonebook_opt & sudo perf top -p $! 這可以省略寫sleep()再開令一個終端機輸入pid
==$./phonebook_orig & sudo perf top -p $!==
```
Samples: 27 of event 'cycles', Event count (approx.): 1019759
Overhead Shared Object Symbol
40.36% libc-2.23.so [.] __strcasecmp_l_avx
14.18% phonebook_orig [.] findName
9.12% [kernel] [k] release_pages
9.07% [kernel] [k] unmap_page_range
4.56% [kernel] [k] unlink_file_vma
4.55% [kernel] [k] free_pcppages_bulk
4.55% [kernel] [k] free_hot_cold_page_list
4.55% [kernel] [k] free_hot_cold_page
4.54% [kernel] [k] free_pages_and_swap_cache
4.53% [kernel] [k] _raw_spin_lock_irqsave
```
### Valgrind（分析工具）
- 參考網站
- [0140454學長共筆](https://hackmd.io/EwMwhgDBDGBsYFoDsBGWAOBAWdSCsCAnCIQEYLAoRgAmApvHiAMylA==?both)
- [分析工具valgrind的使用](http://ottoshare.blogspot.tw/2012/03/valgrind.html)
- [valgrind 的其他用途](http://rueiyuanlu.blogspot.tw/2011/09/valgrind.html)
- Memory Leak的問題
```
$valgrind --leak-check=full [./要測的檔案]
```
- 原本main.c
```
==13294== LEAK SUMMARY:
==13294== definitely lost: 136 bytes in 1 blocks
==13294== indirectly lost: 16,034,808 bytes in 117,903 blocks
==13294== possibly lost: 31,551,320 bytes in 231,995 blocks
==13294== still reachable: 0 bytes in 0 blocks
==13294== suppressed: 0 bytes in 0 blocks
```
- 參考共筆修改 main.c內
```clike
if (pHead->pNext) free(pHead->pNext);
free(pHead);
```
- 修改成
```clike=
while(pHead->pNext){
entry *next = pHead->pNext;
pHead->pNext = next->pNext;
free(next);
}
free(pHead);
```
>程式碼縮排為四個空白鍵，請修正
>[name=課程助教][color=red]
>>OK[name=TsengWen][color=#29ccf4]
- 再次測試
```
==13448== All heap blocks were freed -- no leaks are possible
```
### Gnuplot（繪圖工具）
- 參考網站
- [語法解說和示範](https://hackmd.io/s/Skwp-alOg)
## 效能分析 - 優化前
程式碼: [phonebook](https://github.com/sysprog21/phonebook)
- make run
```
size of entry : 136 bytes
execution time of append() : 0.068333 sec
execution time of findName() : 0.004988 sec
```
- make cache-test
```
Performance counter stats for './phonebook_orig' (100 runs):
4,733,809 cache-misses # 93.978 % of all cache refs ( +- 0.08% )
5,037,124 cache-references ( +- 0.14% )
262,003,100 instructions # 1.45 insn per cycle ( +- 0.02% )
180,647,686 cycles ( +- 0.17% )
0.060747507 seconds time elapsed ( +- 2.18% )
```
## 效能分析 - 優化後
### 方法一
- 由於筆電為L1-cache -32Kbit，原本entry結構136Byte，
- 計算能放入cache數量
$$\frac{32\times1024}{136\times8}= {30.1}$$
- 將結構化簡，將搜尋用不到的另外弄成指標，希望能再cache放入多一點entry來減少cache miss。
- 計算能放入cache數量
$$\frac{32\times1024}{32\times8}= {128}$$
---
```clike
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
struct __PHONE_BOOK_ENTRY *pNext;
struct __PHONE_BOOK_DETAIL *detail;
} entry;
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;
```
- 修改結果
- cache-miss 下降至70%
- 所花時間也略微下降
```
size of entry : 32 bytes
execution time of append() : 0.034991 sec
execution time of findName() : 0.004266 sec
```
```
Performance counter stats for './phonebook_opt' (100 runs):
1,595,412 cache-misses # 70.061 % of all cache refs ( +- 0.12% )
2,277,159 cache-references ( +- 0.12% )
244,541,000 instructions # 2.07 insn per cycle ( +- 0.02% )
118,021,002 cycles ( +- 0.08% )
0.038790988 seconds time elapsed ( +- 0.52% )
```
### 方法二 - 加上hash
想法：依照26個字母，做26個Linked list，做搜尋時根據開頭做搜尋。
- 加上後，修改結果
```
size of entry : 32 bytes
execution time of append() : 0.032146 sec
execution time of findName() : 0.000010 sec
```
```
Performance counter stats for './phonebook_hash' (100 runs):
510,975 cache-misses # 74.046 % of all cache refs ( +- 0.21% )
690,076 cache-references ( +- 1.02% )
188,311,835 instructions # 1.83 insn per cycle ( +- 0.03% )
102,881,580 cycles ( +- 0.35% )
0.037837179 seconds time elapsed ( +- 7.15% )
```
## astyle
```
$ astyle --style=kr --indent=spaces=4 --indent-switches --suffix=none *.[ch]
```
- style決定程式中，大括弧{ }的擺放方式。
- indent=space決定程式中，每個縮排為設定數值的倍數。
- indent-switches讓程式中 switch-case 的 case statements 對齊
- suffix=none不保留格式化前的文件
Sign in with Wallet
Connect another wallet