# 2016q3 Homework1 (phonebook)
contributed by <`shelly4132`>

### Reviewed by `HaoTse`
- 目前只實作了減少資料結構與使用 hash function 兩種方式，尚有許多方式可以增進效能，例如使用 字串壓縮演算法、二元搜尋樹等等的方法
- 未對 `append()` 效能增進方法做討論
- 使用的 data set 為無意義的英文字母，未使用符合現實的英文姓氏做實驗
- 只使用了 BKDRhash 做實驗，可以繼續探討其他 hash function，並探討對應各個 data set 適合哪一種 hash function
- [commit 6af1b](https://github.com/shelly4132/phonebook/commit/6af1b8913ed48cc728e879bc1451eaec602cda7b) 好像可以不用把 `hash.txt` push 上去，並且 commit 的風格可參考 [How to Write a Git Commit Message](https://hackmd.io/s/BkhIF92p)

## 開發環境
* ### 作業系統：Ubuntu 16.04 LTS
* ### Cache：

	* L1d cache：32K
	* L1i cache：32K
	* L2 cache：256K
	* L3 cache：3072K

## 事前準備
1. 在筆電安裝Ubuntu
2. 照老師的教學先安裝相關開發工具

$ 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

3. [Linux 效能分析工具: Perf ](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial)
4. [Programming Small](https://hackmd.io/s/S1rbwmZ6)
	
## 案例分析：Phone Book
### 未優化版本
原本phonebook的entry中存了很多詳細的資料，每個entry的大小為136bytes。
而我的電腦L1 Cache為32KB = 321024，所以321024 / (136*8) = 30.12，代表裡面只能存 30 筆左右。

size of entry : 136 bytes
execution time of append() : 0.067210 sec
execution time of findName() : 0.005578 sec

從以下結果可以看到未優化前的cache miss高達87.762%。

Performance counter stats for './phonebook_orig' (100 runs):

           96,7265      cache-misses              #   87.762 % of all cache refs      ( +-  0.37% )
          110,2146      cache-references                                              ( +-  0.45% )
       2,6092,3829      instructions              #    1.38  insns per cycle          ( +-  0.02% )
       1,8918,5981      cycles                                                        ( +-  0.72% )

       0.076236355 seconds time elapsed

### 優化版本
#### 第一種優化：縮減struct的大小

其實findName跟append都只用到lastName，所以我們其實可以把那些多餘的訊息都去掉不要，因此我新增了一個比較簡單的struct。

typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    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];
    struct __PHONE_BOOK_ENTRY *pNext;
} detailEntry;

typedef struct __LAST_NAME_ENTRY{
    char lastName[MAX_LAST_NAME_SIZE];
    detailEntry *detail;
    struct __LAST_NAME_ENTRY *pNext;
} entry;

size of entry : 32 bytes
execution time of append() : 0.044284 sec
execution time of findName() : 0.002463 sec

從下面的資訊可以看到，只是單純的把entry的大小減小，就大幅的降低了cache miss，從原本的87.762 %降低到了29.548 %，效果非常驚人。

Performance counter stats for './phonebook_opt' (100 runs):

11,1935 cache-misses # 29.548 % of all cache refs ( +- 0.90% )
37,8822 cache-references ( +- 1.18% )
2,4392,7456 instructions # 1.75 insns per cycle ( +- 0.02% )
1,3909,4113 cycles ( +- 0.97% )

0.056542530 seconds time elapsed

![](https://i.imgur.com/Ww0S0QX.png)

#### 第二種優化：hash function

參考：[BKDRHash](http://www.cnblogs.com/liuliuliu/p/3966851.html)、[vvn](https://hackmd.io/MwUwrAnAZlDGAMBaWAOAhixAWLB2AbImsFoSAEbz4BMWKUwuaAjEA===#)

當我們需要比較的字串數量太龐大的話，我們可以使用hash function來將每個字串轉換成一個數字，而這次我使用的hash function是比較簡單快速的BKDRHash，hash table的大小我設成比較大的質數42737，並且把乘法的部份改成位移運算子，不過我自己測的結果這對於速度的提升似乎沒有太大的幫助。

collision：當兩個不同的字串算出的key一樣時，就發生碰撞。

unsigned int BKDRHash(char lastName[])
{
//unsigned int seed=31;
unsigned int hash=0;
int i=0;
while(i<strlen(lastName)) {
//hash = hash * seed + lastName[i];
hash = (hash << 5) - hash + lastName[i];
++i;
}

return hash % DICLEN;
}

從結果可以看到因為findName()不用再從頭開始找，所以花的時間大幅的往下降，但append()的時間卻往上升了，原因應該是因為每次append()我們都還要再去呼叫一次hash function。

size of entry : 32 bytes
execution time of append() : 0.087076 sec
execution time of findName() : 0.000000 sec

而cache miss也下降到了63.635%。

Performance counter stats for './hash_func' (100 runs):

          109,3919      cache-misses              #   63.635 % of all cache refs      ( +-  0.71% )
          171,9051      cache-references                                              ( +-  0.31% )
       3,7554,6986      instructions              #    1.40  insns per cycle          ( +-  0.14% )
       2,6852,9326      cycles                                                        ( +-  0.46% )

       0.110592162 seconds time elapsed