# 2016q3 Homework1 (phonebook)
contributed by <`carolc0708`>
[作業說明A01: phonebook](https://hackmd.io/s/S1RVdgza)
## 開發環境
* Ubuntu 16.04.1 LTS
* CPU: Intel(R) Core(TM) i5-4570 CPU @ 3.20GHz
* Cache: `$ lscpu | grep cache`
* L1d cache: 32K
* L1i cache: 32K
* L2 cache: 256K
* L3 cache: 6144K
>cache line issue
## Perf效能分析工具
* `phonebook_orig`的分析:
```
Performance counter stats for './phonebook_orig' (100 runs):
1,220,664 cache-misses # 85.971 % of all cache refs ( +- 0.39% )
1,419,851 cache-references ( +- 0.26% )
261,811,357 instructions # 1.21 insns per cycle ( +- 0.02% )
216,828,386 cycles ( +- 0.42% )
0.066546829 seconds time elapsed ( +- 0.56% )
```
* `phonebook_orig`的執行時間:
```
size of entry : 136 bytes
execution time of append() : 0.047410 sec
execution time of findName() : 0.005756 sec
```
## gnuplot 製圖
更改`\scripts\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.06):($2+0.001):2 with labels title ' ', \
'' using 3:xtic(1) with histogram title 'optimized' , \
'' using 4:xtic(1) with histogram title 'hash' , \
'' using ($0+0.3):($3+0.0015):3 with labels title ' ', \
'' using ($0+0.4):($4+0.0015):4 with labels title ' '
```
並在`calculate.c`當中增加將`hash.txt`讀入`output.txt`的部分
>[gnuplot introduction(中文版)](https://dl.dropboxusercontent.com/u/1091156/yong/text/gnuplot%20introduction.pdf)
>[gnuplot manual](http://www.gnuplot.info/docs_5.0/gnuplot.pdf)[color=blue]
## 案例分析:Phonebook
在`phonebook_orig.h`中phonebook的資料結構定義如下:
```clike=
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];//16 byte
char firstName[16];//16 byte
char email[16];//16 byte
char phone[10];//10 byte
char cell[10];//10 byte
char addr1[16];//16 byte
char addr2[16];//16 byte
char city[16];//16 byte
char state[2];//16 byte
char zip[5];//5 byte
struct __PHONE_BOOK_ENTRY *pNext;//8 byte
} entry;
```
可以看到一個entry總共占用了 136 byte，然而cache L1的大小為32 Kbit，若每次透過`findName()`函式進行比對，cache只能讀入32 * 1024 / 136 * 8 = 30.12，約 30 筆entry，在進行350000筆資料的比對時，會造成大量的cache miss。
## Hint: 可能的效能改進方式
- [x] 改寫 struct __PHONE_BOOK_ENTRY 的成員，搬動到新的結構中
- [x] 使用 hash function 來加速查詢
- [ ] 既然 first name, last name, address 都是合法的英文 (可假設成立)，使用[字串壓縮的演算法](http://stackoverflow.com/questions/1138345/an-efficient-compression-algorithm-for-short-text-strings)，降低資料表示的成本
- [ ] 使用 binary search tree 改寫演算法
- [ ] 本例選用的 dataset (也就是輸入電話簿的姓名) 是否存在問題？
有代表性嗎？跟真實英文姓氏差異大嗎？
資料難道「數大就是美」嗎？
如果我們要建立符合真實電話簿情境的輸入，該怎麼作？
## 挑戰題
- [ ] 除了降低 `findName()` 的 cache miss 與執行成本，`append()` 也該想辦法縮減時間
* 建立 phone book 時，既然 lastName 是索引值，可以優先建立搜尋表格，其他資料可稍後再補上
* 用 PThread 建立 [manager/worker thread model](http://stackoverflow.com/questions/12282393/how-to-synchronize-manager-worker-pthreads-without-a-join)
- [ ] 支援 [fuzzy search](http://www.informit.com/articles/article.aspx?p=1848528)，允許搜尋 lastName 時，不用精準打出正確的寫法
* 比方說電話簿有一筆資料是 `McDonald`，但若使用者輸入 `MacDonald` 或 `McDonalds`，也一併檢索出來
* 延伸閱讀: [Levenshtein Distance (編輯距離)](https://charles620016.hackpad.com/ep/pad/static/Japi4qFyAzt)
- [ ] 改善電話簿的效能分析，透過大量的重複執行，找出 95% 信賴區間，而且允許動態新增資料 (較符合現實) 和查詢
- [x] 以 [gnuplot](http://www.gnuplot.info/) 繪製效能分析圖表
## METHOD1: 改變entry大小
在`phonebook_orig.c`中，可以發現每次進行`findName()`時，只用到`lastName`，卻須將整個entry 136 byte載入cache中。
```clike=
entry *findName(char lastName[], entry *pHead)
{
while (pHead != NULL) {
if (strcasecmp(lastName, pHead->lastName) == 0)
return pHead;
pHead = pHead->pNext;
}
return NULL;
}
```
所以在`phonebook_opt.h`中重新設計phonebook的資料結構，將比對時不會用到的資料(即`lastName`、`*pNext`以外的資料)包裝為另一個struct，
```clike=
typedef struct __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;
```
並用一指標`*detailInfo`指向它。
```clike=
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
detail *detailInfo;
struct __PHONE_BOOK_ENTRY *pNext;
} entry;
```
如此一來，原本的`__PHONE_BOOK_ENTRY`只佔用了16(`lastName`) + 8(`*pNext`) + 8(`*detailInfo`) = 32 byte，cache每次能讀取32 * 1024 / 32 * 8 = 128 筆entry，可大幅減少cache miss。
>[C/C++ typedef , struct , typedef struct 差別](http://vincecc.blogspot.tw/2013/10/cc-typedef-struct-typedef-struct.html)[color=blue]
>- [ ]TODO: 嘗試這部分實作並測試效能是否改善
>[課程資料](https://hackmd.io/s/S1rbwmZ6)當中提到:" 因為若在 append 過程中 malloc() 空間給 *detail，會增加很多 cache miss，嚴重影響到效能表現，經過實測，總體效能甚至比原始版本還差一點。目前想法是將 *detail 的 assign （當有需要時）交給另外一個 function 處理，畢竟我們一開始只有 last name 的資訊。 "
---
* 改善後，執行時間如下:
```
size of entry : 32 bytes
execution time of append() : 0.028434 sec
execution time of findName() : 0.001888 sec
```
改善後，cache miss由85%降到45%左右。
```
Performance counter stats for './phonebook_opt' (100 runs):
197,061 cache-misses # 45.603 % of all cache refs ( +- 1.47% )
432,126 cache-references ( +- 0.72% )
244,209,456 instructions # 1.85 insns per cycle ( +- 0.02% )
131,874,631 cycles ( +- 0.41% )
0.041165375 seconds time elapsed ( +- 0 .93% )
```
`findName()`執行時間上有減少。
* 和未優化版本比較:
## METHOD2: 使用 hash function
>[複習 hash function](https://www.csie.ntu.edu.tw/~hsinmu/courses/_media/dsa_12spring/hashing.pdf)
>[其他字串可用的Hash function](https://www.byvoid.com/zht/blog/string-hash-compare)[color=blue]
>這邊在實作的時候程式碼亂成一團，把它用條件編譯的方式好好整理一下，參考[這裡](http://blog.sina.com.cn/s/blog_4b4b54da0100r2l6.html)。
* djb2
參考[課程資料:Programming Small](https://hackmd.io/s/S1rbwmZ6)中對於實作hash function的探討，而hash function的選擇參考 [hash function for string](http://stackoverflow.com/questions/7666509/hash-function-for-string)，實作了 [djb2](http://www.cse.yorku.ca/~oz/hash.html)。
djb2 hash function給定初始hash值為5381，將key編為hash*33，再加上字串的內容。考慮phonebook資料結構的設計，輸入字串可以是`lastName`(16 byte)或結合所有的字串(127 byte)，在此由於`findName()`只有用到`lastName`的比較，只輸入`lastName`去編key。
>不知道兩種效果是否差很多，可以試試看[name=Carol Chen]
```C=
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;
}
```
在這邊實作`append()`時，有另外定義全域變數`entry* hash_table_cur[HASH_NUM_SIZE]`，用來紀錄hash table發生collision時chaining的linked list已經存到第幾個。這樣一來每次在加入新的資料的時候，就不用整條linked list從頭走一次，可以減去一些執行時間。
hash table size = 256
```
size of entry : 32 bytes
execution time of append() : 0.038605 sec
execution time of findName() : 0.000015 sec
```
hash table size = 1000
```
size of entry : 32 bytes
execution time of append() : 0.038603 sec
execution time of findName() : 0.000003 sec
```
hash table size = 2000
```
size of entry : 32 bytes
execution time of append() : 0.039207 sec
execution time of findName() : 0.000001 sec
```
可以發現`append()`的時間與未優化前沒有差太多，而`findName()`的執行時間則是隨著hash table的大小增加而逐漸縮減。
```
Performance counter stats for './phonebook_hash' (100 runs):
580,489 cache-misses # 50.242 % of all cache refs ( +- 0.29% )
1,155,387 cache-references ( +- 0.06% )
293,285,085 instructions # 1.28 insns per cycle ( +- 0.02% )
229,464,841 cycles ( +- 0.34% )
0.066811857 seconds time elapsed ( +- 0.37% )
```
cache miss由未優化前的85%降至50%左右。比縮小entry的優化版本(45%)稍微高一點。
---
* BKDR hash
```C=
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;
}
```
hash table size = 256
```
size of entry : 32 bytes
execution time of append() : 0.040698 sec
execution time of findName() : 0.000029 sec
```
hash table size = 1000
```
size of entry : 32 bytes
execution time of append() : 0.041464 sec
execution time of findName() : 0.000003 sec
```
hash table size = 2000
```
size of entry : 32 bytes
execution time of append() : 0.041498 sec
execution time of findName() : 0.000001 sec
```
可以發現`append()`的時間與未優化前沒有差太多，但約比djb2的時間長一些。而`findName()`的執行時間則是隨著hash table的大小增加而逐漸縮減。
```
Performance counter stats for './phonebook_hash' (100 runs):
593,343 cache-misses # 50.444 % of all cache refs ( +- 0.25% )
1,176,231 cache-references ( +- 0.07% )
292,144,527 instructions # 1.22 insns per cycle ( +- 0.01% )
239,491,289 cycles ( +- 0.30% )
0.069722688 seconds time elapsed ( +- 0.33% )
```
cache miss從未優化前的85%降到50%左右，和djb2的版本差不多。
* 和為優化版與縮減entry大小版本比較如下:
## METHOD3: SMAZ字串壓縮
* [smaz字串壓縮演算法](https://github.com/antirez/smaz)
Sign in with Wallet
Connect another wallet