# [phonebook](https://hackmd.io/s/S1RVdgza)
[github](https://github.com/diana0651/phonebook) contributed by <`diana0651`>
###### tags: `d0651` `sys`
> Reviewed by <`LitSnow`>
`*dNext`已經搬到新的 `__PHONE_BOOK_ENTRY` 結構中 ， 舊的` __PHONE_BOOK_DETAIL_ENTRY` 結構中的 `struct __PHONE_BOOK_DETAIL_ENTRY *dNext;`就可以不用留著
>>已經修正
## 案例分析
### 作業要求
適度修改 phonebook_opt.c 和 phonebook_opt.h 兩個檔案，使得這兩者執行時期的 cache miss 降低。
### 預期目標
- [x] 學習使用 Git 與 GitHub
- [x] 學習效能分析工具
- [ ] 可能的效能改進方向：
- [x] 改寫 `struct__PHONE_BOOK_ENTRY` 的成員，搬動到新的結構中
- [x] 使用 hash function 來加速查詢
- [x] 既然 first name, last name, address 都是合法的英文 (可假設成立)，使用字串壓縮的演算法，降低資料表示的成本
- [ ] 使用 binary search tree 改寫演算法
### 開發環境
- `$ cat /etc/issue`
Ubuntu 14.04.5 LTS \n \l
- `$ cat /proc/version`
Linux version 4.2.0-42-generic (buildd@lgw01-55) (gcc version 4.8.4 (Ubuntu 4.8.4-2ubuntu1~14.04.3) )
- `$ lscpu`
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 8192K
---
## Makefile
### makefile規則的基本結構
- 目標(Target) : 一個目標檔，可以是Object檔，也可以是執行檔，還可以是一個標籤(Label)。
- 依賴(Dependency,Prerequisites) : 要產生目標檔(target)所依賴哪些檔。
- 命令(Command) : 建立專案時需要執行的shell命令 (命令部分的每行的縮進必須要使用Tab鍵而不能使用多個空格)。
- 注意：
- make只在意依賴性
- 顯式make命令
- 在Makefile中的命令，必須要以[Tab]鍵開始。
### 變數宣告
- MACRO = value ： 可利用`$(MACRO)`或`${MARCO}`來存取已定義的變數。
- := ： 變數的值決定於它在 Makefile 中的位置，而不是整個 Makefile 展開後最終的值。
- ?= ： 若變數未定義，則替它指定新的值。否則採用原有的值。
### 內部變數
- $?： 代表已被更新的 dependencies 的值。也就是 dependencies 中，比 targets 還新的值。
- $@ ： 代表 targets 的值。
- $< ： 代表第一個 dependencies 的值。
- $* ： 代表 targets 所指定的檔案，但不包含副檔名。
### 參考資料
http://maxubuntu.blogspot.tw/2010/02/makefile.html
http://mropengate.blogspot.tw/2015/06/makefile-makefile.html
http://mropengate.blogspot.tw/2015/06/makefile-makefile-2.html
http://tetralet.luna.com.tw/?op=ViewArticle&articleId=185
---
## Gnuplot
[gnuplot](http://www.gnuplot.info/) 是一個用於生成趨勢圖和其他圖形的工具。它通常用於收集基於時間的數據，同時也可以使用靜態數據。
>[gnuplot introduction(中文版)](https://dl.dropboxusercontent.com/u/1091156/yong/text/gnuplot%20introduction.pdf)
>[gnuplot manual](http://www.gnuplot.info/docs_5.0/gnuplot.pdf)
### 簡易設定
- 設定標題：set title "title_description"
- 設定 x 軸 Label：set xlabel "x_description (unit)"
- 設定 x 軸值範圍：set xrange [ m : n ]
- 呈現圖式：plot
- 輸出圖檔：set output 'filename.png'
### 資料呈現
- 點與線：plot "filename" with linespoints
線條寬度(linewidth)、點大小(pointsize)。兩者都可以設置为整數或小數。
- 點：plot "filename" with points
點型(pointtype)，主要用於設置點得形狀
- 線：plot "filename" with line
線型(linetype )，主要用於設置線條的顏色
### 參考資料
http://applezu.netdpi.net/2014/02/gnuplot.html
http://fanli7.net/a/bianchengyuyan/C__/20160414/558945.html
---
## GitHub
* `git init` 建立目錄 `.git`
* `git status` 確認現在所有檔案的狀況
* `git add 檔名` 追蹤此檔案
* `git commit` 確認檔案並snapshot（有點像暫時存檔）
* `git remote add <nickname> <repository-URL>` 連結遠端的repository並給他取代稱
* `git push <nickname>` 把檔案上傳到指定的repository
## Linux 效能分析工具: Perf
[Perf (Performance Event)](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial) 提供一個簡便的效能分析方案，另有即時的效能分析等應用，是用來進行軟體性能分析的工具。
- `$ uname` : 顯示作業系統
- `sudo perf top` : 查看整體系統負載
- `perf list` : 列出所有能夠觸發 perf 採樣點的事件
- Perf 能觸發的事件分為三類
- hardware : 由 PMU 產生的事件，比如 cache-misses、cpu-cycles、instructions、branch-misses …等等，通常是當需要瞭解程序對硬體特性的使用情況時會使用。
- software : 是核心程式產生的事件，比如 context-switches、page-faults、cpu-clock、cpu-migrations …等等。
- tracepoint : 是核心中的靜態 tracepoint 所觸發的事件，這些 tracepoint 用來判斷在程式執行時期，核心的行為細節，比如 slab 記憶體配置器的配置次數等。
- `perf stat` : 概括提供程序運行的整體情況
### 參考資料
http://mropengate.blogspot.tw/2016/04/perf.html
---
## 未優化版本 phonebook_orig
### 測試程式效能
- `make run` 執行時間
``` clike=
size of entry : 136 bytes
execution time of append() : 0.102741 sec
execution time of findName() : 0.007556 sec
3
```
- `make cache-test` ==**cache-misses 90%**==
``` clike=
Performance counter stats for './phonebook_orig' (100 runs):
2,029,918 cache-misses # 89.885 % of all cache refs
2,275,583 cache-references
263,219,831 instructions # 1.22 insns per cycle
221,815,824 cycles
0.076515784 seconds time elapsed ( +- 1.48% )
```
:::info
解釋：
cache-misses: 沒有在cache中找到需要的資料, 反過來就是cache hit
cache-references: 讀取cache的次數
instructions: 機器指令的數目
cycles: 程式中的指令所需要的總cycle次數
:::
- `sudo perf top` 尋找熱點
### 小結
>L1 Cache : 32KB = 32\*1024，PhoneBook size = 136 bytes，321024 / (136\*8) = 30.12 (只能存 30 筆左右)
若把整個 `__PHONE_BOOK_ENTRY` 的 struct 都丟進 `findName()` 尋找， L1 cache 最多也只能放 30 個 entry，一共有 35 萬個單字，必定會發生頻繁的 cache miss。
- 效能：findName() 較 append() 好
- 執行時間：append() 較 findName() 久
- 目標：==**縮短 findName() 的執行時間**==
### 改善方向
- Reduce search times
- Hash table
- Binary Search Tree
- Reduce struct size
- Data structure
- string compression
---
## 優化版本 phonebook_opt: 1。減少資料結構大小
搜尋時只比對 lastName, 所以針對 cache-misses，嘗試將 `struct __PHONE_BOOK_ENTRY` 縮小，把其它資訊包裝起來放到 `struct __DETAIL_ENTRY`，再用指標指向他
```clike=
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];\
struct __DETAIL_ENTRY *pDetail;
struct __PHONE_BOOK_ENTRY *pNext;
} entry;
```
### 測試程式效能
- `$ make cache-test`
size of entry : 136 -> 32
cache-miss : 90% -> 53%
```clike=
size of entry : 32 bytes
execution time of append() : 0.046319 sec
execution time of findName() : 0.003430 sec
Performance counter stats for './phonebook_opt' (100 runs):
406,381 cache-misses # 53.221 % of all cache refs
685,441 cache-references
246,015,882 instructions # 1.60 insns per cycle
147,728,355 cycles
0.048182165 seconds time elapsed ( +- 0.81% )
```
- `$ eog runtime.png `
## 優化版本 phonebook_opt: 2。 hash function 加速查詢
[Hash](https://www.csie.ntu.edu.tw/~hsinmu/courses/_media/dsa_12spring/hashing.pdf) 將資料透過特別的函數轉換成表格索引進行存取，所以實做的重點在於**建立表格**及**建立轉換的函數**。
> >[參考概念](https://embedded2016.hackpad.com/2016q1-Homework-1--NcHhQCQ4ijr)
>
> >[參考實作](https://hackmd.io/KYZgDGCcAcYIwFoBMAWAZgYwSkkDsC0IOCeIAJsHsGkgEbDlJA==)
- hash function：
先將字串資料轉換成數值，使用最容易實做的 division 計算 index。
- hash table size：
為了降低 collision 發生，我們希望 hash table 愈大愈好，然而較大的 table 容易造成空間的浪費。
由於 hash function 採用 division，在實做上table size＝ D，且為了降低 collision 的發生，所以選擇 D 為質數。
- overflow handling：
當 hash value 對應到 hash table 中的欄位已經有資料了，使用 Chaining，可以有效利用原本結構體的 pNext 將 overflow 的資料加進該欄位的 list 中。
### 測試程式效能
``` clike=
$ ./phonebook_hash
size of entry : 32 bytes
execution time of append() : 0.077230 sec
execution time of findName() : 0.000000 sec
Performance counter stats for './phonebook_hash' (100 runs):
446,120 cache-misses # 75.538 % of all cache refs
589,839 cache-references
303,567,973 instructions # 1.67 insns per cycle
181,623,645 cycles
0.062899824 seconds time elapsed ( +- 1.29% )
```
#### 改善方向
- 測試 hash table size
### 其他的 HASH function
>[各種字符串Hash函數比較](https://www.byvoid.com/zht/blog/string-hash-compare)
#### 可以實作的方向
[Programming Small](https://hackmd.io/s/S1rbwmZ6)
提到 ==djb2 hash function== & ==BKDR hash function==
> >[參考實作](https://hackmd.io/BwVgJgzBxgjAtAU2LY8AstEAZ4EMAjANnXm2WwCYBjCMYYa2IA==)
- djb2 hash function
初始 hash 值為 5381，key 為 hash\*33 加上字串的內容。
```clike=
unsigned int DJB2_hash(char lastName[], int hash_table_size)
{
unsigned int hash = 5381;
int c;
int i = 0;
while (c = lastName[i++])
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash %= hash_table_size;
```
- BKDR hash function
計算過程中有係數(seed)參與，seed為31 131 1313
```clike=
unsigned int BKDR_hash(char lastName[], int hash_table_size)
{
unsigned int seed = 131;
unsigned int hash = 0;
int i = 0;
while(lastName[i] != '\0')
{
hash = hash * seed + lastName[i];
i++;
}
return hash %= hash_table_size;
}
```
## 優化版本 phonebook_opt: 3。字串壓縮的演算法，降低資料表示的成本
:::info
[Smaz](https://github.com/antirez/smaz) is a simple compression library suitable for compressing very short strings.
:::
> >[參考實作](https://hackmd.io/MwUwrAnAZlDGAMBaWAOAhixAWLB2AbImsFoSAEbz4BMWKUwuaAjEA===)
### 測試程式效能
```clike=
$ ./phonebook_smaz
size of entry : 32 bytes
execution time of append() : 0.181449 sec
execution time of findName() : 0.008812 sec
Performance counter stats for './phonebook_smaz' (100 runs):
681,816 cache-misses # 58.851 % of all cache refs
1,191,106 cache-references
806,187,790 instructions # 1.46 insns per cycle
554,662,350 cycles
0.163610323 seconds time elapsed ( +- 0.51% )
```
### 其他的資料壓縮方法
> >[參考](https://mimihalo.hackpad.com/HW2--D5sU0CfNmJH)
- 資料壓縮
- 失真壓縮
- 影像處理
- 無失真壓縮
- 字串壓縮
- 常見之壓縮方法
- 霍夫曼編碼
將資料先搜尋一遍來建編碼樹
- smaz 方法
即時的壓縮方法
適合短字串, 英文字串效果好
- [shoco 方法](http://ed-von-schleck.github.io/shoco/#quick-start)
即時運算的壓縮方法
特性與 smaz 相反
## 優化版本 phonebook_opt: 4。 binary search tree 改寫演算法
...
## Code Review
- coding style
`$ astyle --style=kr --indent=spaces=4 --indent-switches --suffix=none *.[ch]`
- github
- commit 的敘述明確
- branch 的版本控制
---
<style>
h2.part {color: red;}
h3.part {color: green;}
h4.part {color: blue;}
h5.part {color: black;}
</style>
Sign in with Wallet
Connect another wallet