2016q3 Homework1 (phonebook)

# 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()`執行時間上有減少。 * 和未優化版本比較: ![](https://i.imgur.com/0KMntkl.jpg) ## 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大小版本比較如下: ![](https://i.imgur.com/H5iIJRp.png) ## METHOD3: SMAZ字串壓縮 * [smaz字串壓縮演算法](https://github.com/antirez/smaz)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.