# 2016q3 Homework1 (phonebook)
### Reviewed TotallyWrong
其實光是說明影片中就有很多線索可以把這個程式改善，例如利用 Hash 或是利用順序關係是可以省下很多搜尋時間。記憶體除了大小外位置也是很重要的，可以了解一下順序。
## 開發環境
- 作業系統：Kubuntu 16.04.01 LTS (64bit)
- 硬體
- 查看硬體資訊：`$ lscpu`
```shell
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](https://github.com/sysprog21/phonebook/)
- Clone 專案到本地端
```shell
$ git clone git@github.com:GoblinBear/repository.git
```
- 修改專案
- 將新增的檔案加入到 Git 版本控管
```shell
$ git add .
```
- 提交變更到本地端
```shell
$ git commit -m "my commit"
```
- 加入一個遠端儲存庫
```shell
$ git remote add origin http://github.com/GoblinBear/repository.git
```
- 上傳到 GitHub 上的遠端儲存庫
```shell
$ git push origin master
```
### 指令
- `$ git reset`：重設工作目錄的索引狀態
- `$ git log`：查詢版本的歷史紀錄
- `$ git status`：查詢當前工作目錄的詳細狀態
## 學習 Gnuplot
- 用老師的 script 當範例
```shell
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 改寫演算法
### 原版
- 編譯
```shell
$ make
```
- 測試
```shell
$ make run
```
- 輸出
```shell
size of entry : 136 bytes
execution time of append() : 0.034903 sec
execution time of findName() : 0.004713 sec
```
(按下 Ctrl-C 可以離開畫面)
- 清空 cache:
```shell
$ echo 1 | sudo tee /proc/sys/vm/drop_caches
```
- 透過 gnuplot 建立執行時間的圖表
```shell
$ make plot
```
### 優化版 - 改寫資料結構
- 減少`entry`空間
只會用到`lastName`，所以將其他用不到的結構成員隱藏在`detail`中，因此`entry`的空間由 136 byte 降到 32 byte
```clike=
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 比較
- 原版
```shell
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% )
```
- 優化版
```shell
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% )
```
- 執行時間比較
- 效能分析
L1d cache = 32K，`entry`資料變少，cache 可以存更多筆`entry`，因此 cache miss 降低
### 優化版 - 資料大小為 Cache line 的倍數
- 想法：Cache 讀取的資料是 Cache line 的倍數會比較有效率
- 測試機器的 Cache line = 64 byte
- 參考資料
[Intel Skylake](http://www.7-cpu.com/cpu/Skylake.html)
[關於CPU Cache -- 程序猿需要知道的那些事](http://cenalulu.github.io/linux/all-about-cpu-cache/)
- 上面優化版的`entry`資料為 32 byte，已經小於 64 byte
### 優化版 - Hash function 加速查詢
#### 資料閱讀
- [A quick hashtable implementation in c](https://gist.github.com/tonious/1377667)
- [Hash Functions](http://www.cse.yorku.ca/~oz/hash.html)
- [Programming Small](https://hackmd.io/s/S1rbwmZ6)
#### 作法
- Hash function：djb2
- Table size = 42737，有約35萬個英文單字，為了減少碰撞機會，挑了一了蠻大的**質數**
- 精度：優化後`findName()`執行時間小於10^-6^秒，所以我把`fprintf()`的參數`%lf`改成`%.9lf`
### 優化版 - 字串壓縮演算法
#### 資料閱讀
- [演算法筆記 - Compression](http://www.csie.ntnu.edu.tw/~u91029/Compression.html)
- [演算法 Term Project - 算術編碼](http://par.cse.nsysu.edu.tw/~homework/algo01/8934609/index.html)
- [Arithmetic Coding by Matlab (1)](http://chu246.blogspot.tw/2014/01/arithmetic-coding-by-matlab-1.html)
- [[C] printf 引數說明](http://edisonx.pixnet.net/blog/post/35305668-%5Bc%5D-printf-%E5%BC%95%E6%95%B8%E8%AA%AA%E6%98%8E)
- [C語言中關於float、double、long double精度及數值範圍理解](http://blog.sina.com.cn/s/blog_6ebd49350101gdgo.html)
#### 壓縮演算法
- Huffman Compression
- Arithmetic Compression
- 壓縮效果最好，達到了理論極限
- 壓縮速度最快
#### 算術編碼問題
- 用算術編碼壓縮字串，若字串為`zzzzzzzzzz`，使用`long double`精度仍會不夠
```shell
[ 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
```
- 除不盡的小數會造成解碼沒有盡頭，不知道什麼時候要停止，不知道中止條件
Sign in with Wallet
Connect another wallet