# 2016q3 Homework1 (phonebook)
contributed by <`jayfeng0225`>
###### tags: `jayfeng0225`
## 系統安裝與設定
系統 : Ubuntu 16.04 LTS
配備 :
安裝相關開發工具
```shell
$ sudo apt-get update
$ sudo apt-get install build-essential
$ sudo apt-get install linux-tools-common linux-tools-generic
$ sudo apt-get install astyle colordiff gnuplot`
```
#### HIME 中文輸入法使用起來比較接近新注音
設定教學 : [小克's 部落格](http://goodjack.blogspot.tw/2013/08/linux-phonetic-setting.html)
```shell
$ sudo apt-get install hime
```
---
## Git設定
參考下列網址即可完成設定
[GitHub的設定引指](http://wiki.csie.ncku.edu.tw/github)
[學習Git](http://learngitbranching.js.org/)
[Git 版本控制系統](https://ihower.tw/blog/archives/2620)
### git push
```shell
$ git commit -m "comment"
$ git push -u origin master
```
### git branch
```shell
$ git branch <new_branch_name> 建立本地 local branch
$ git branch -m <old_name> <new_name> 改名字 (如果有同名會失敗，改用 -M 可以強制覆蓋)
$ git branch 列出目前有那些 branch 以及目前在那個 branch
$ git checkout <branch_name> 切換 branch (注意到如果你有檔案修改了卻還沒 commit，會不能切換 branch，解法稍後會談)
$ git checkout -b <new_branch_name> (<from_branch_name>) 本地建立 branch 並立即 checkout 切換過去
$ git branch -d <branch_name> 刪除 local branch
```
---
## Gnuplot Script 分析
參考網站 : [Gnuplot (Part I)](http://gtchen.pixnet.net/blog/post/5873441-gnuplot-(part-i))
### runtime.gp
```
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.100]'output.txt' using 2:xtic(1) with histogram title 'original', \
'' using ($0-0.1):($2+0.002):2 with labels title ' ', \
'' using 3:xtic(1) with histogram title 'struct optimized' , \
'' using ($0+0.05):($3+0.002):3 with labels title ' ', \
'' using 4:xtic(1) with histogram title 'hash function' , \
'' using ($0+0.3):($4+0.002):4 with labels title ' ', \
```
### output.txt
```
append() 0.067780 0.053012 0.084497
findName() 0.006792 0.003539 0.000000
```
* xtic(1) : x軸使用第一項也就是append()與findName()
* using 2 , 3 and 4代表後面三項數字
* ($0 - 0.1) : 表示以$0(append and findName)往左0.1個單位的位置
* ($2+0.002) : 表示將數值標記在以$2(opt time)的長條往上0.002單位的位置
---
## 案例分析
根據[案例分析](https://embedded2016.hackpad.com/ep/pad/static/1vvUk25C0fI)的內容來探討改進的方法以及造成cache miss的原因
使用perf來看cache miss的比率，原來的架構大約有67%的cache-miss
```
$ perf stat -r 10 -e cache-misses,cache-references,L1-dcache-load-misses,L1-dcache-store-misses,L1-dcache-prefetch-misses,L1-icache-load-misses ./phonebook_orig
```
```
Performance counter stats for './phonebook_orig' (10 runs):
1,337,063 cache-misses # 66.914 % of all cache refs (63.90%)
1,930,629 cache-references (64.94%)
2,663,069 L1-dcache-load-misses (68.04%)
895,559 L1-dcache-store-misses (70.16%)
2,627,222 L1-dcache-prefetch-misses (69.13%)
111,859 L1-icache-load-misses (65.85%)
0.109293886 seconds time elapsed ( +- 15.40% )
```
再來查看電腦的資訊
```
$ lscpu | grep cache
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 3072K
```
### 效能改進方向
- [x] 改寫 struct __PHONE_BOOK_ENTRY 的成員，搬動到新的結構中
- [x] 使用 hash function 來加速查詢
- [ ] 使用 binary search tree 改寫演算法
## Optimization
首先，根據程式要求，只要找到lasyname就算符合結果
```clike=
entry *findName(char lastname[], entry *pHead)
{
while (pHead != NULL) {
if (strcasecmp(lastname, pHead->lastName) == 0)
return pHead;
pHead = pHead->pNext;
}
return NULL;
}
```
### 針對L1-cache來調整struct大小做優化
原先的struct有==136byte==的大小
所以可以改變struct的架構來降低原來的cahce miss比率
新的struct只留下search的結果lastname
```clike=
#define MAX_LAST_NAME_SIZE 16
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
struct __PHONE_BOOK_ENTRY *pNext;
} entry;
```
L1 cache有32Kbyte，每筆entry有`136bytes`。
==32*1024 / 136 = 240.9==，每次大約能夠存240筆資料在cache
而改善後struct的大小為`24byte`
==32*1024/24 = 1365.33==，能夠存高達1365筆資料在cache，因此效能能夠大大提升
改善後的效能結果 :
可以看到append與findName的時間都減了，而cache miss的部份
```
Performance counter stats for './phonebook_orig' (100 runs) :
1,420,611 cache-misses # 72.836 % of all cache refs
1,916,229 cache-references
272,770,687 instructions # 1.35 insns per cycle
194,818,050 cycles
0.097316509 seconds time elapsed ( +- 1.46% )
```
```
Performance counter stats for './phonebook_opt' (100 runs):
90,950 cache-misses # 29.957 % of all cache refs
300,289 cache-references
244,047,904 instructions # 1.72 insns per cycle
142,529,076 cycles
0.068250922 seconds time elapsed ( +- 1.45% )
```
__可以看到cache-misses由72.8%下降到29.9%！__
### 使用hash function來減少cache-misses的發生
參考[案例分析 : phonebook](https://embedded2016.hackpad.com/ep/pad/static/1vvUk25C0fI)的方法，我採用的是[djb2 hash](http://www.cse.yorku.ca/~oz/hash.html)演算法
```clike=
unsigned int hash(char *key){
unsigned int hashVal = 0;
while(*key != '\0')
hashVal = (hashVal << 5) + *key++;
return hashVal % 42737;
}
```
我並沒有針對儲存hash的資料結構做優化，而是直接採用陣列式的struct entry
所以最後實作出來的append效率很差，比上原始版本高上不少
> 會再針對append的部分做優化 [name=JayFeng]
```clike=
entry *findName(char lastname[], entry **e)
{
int hashindex;
hashindex = hash(lastname);
entry *pHead;
pHead = e[hashindex];
/* TODO: implement */
while (pHead != NULL) {
if (strcasecmp(lastname, pHead->lastName) == 0){
return pHead;
}
pHead = pHead->pNext;
}
return NULL;
}
```
雖然append時間增加，但findName的時間幾乎是小於0.000001，比之前的版本好上很多
```
Performance counter stats for './phonebook_hash' (100 runs):
352,837 cache-misses # 28.865 % of all cache refs
1,218,066 cache-references
247,999,356 instructions # 1.36 insns per cycle
188,666,811 cycles
0.096232347 seconds time elapsed ( +- 1.62% )
```
這邊可以看到cache-misses也下降了很多，比起僅修改struct大小在好一點 ==( 29.9% -> 28.8% )==
## 參考資料
* [案例分析: Phone Book](https://embedded2016.hackpad.com/ep/pad/static/1vvUk25C0fI)
* [GitHub的設定引指](http://wiki.csie.ncku.edu.tw/github)
* [Gnuplot (Part I)](http://gtchen.pixnet.net/blog/post/5873441-gnuplot-(part-i))
Sign in with Wallet
Connect another wallet