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

### Reviewed by `aweimeow`
* [git 是否沒有配置好呢？](https://github.com/tang7526/phonebook-1/commit/d0e169179bc4ede8a52a505847c74ffb6372d6e8)
* 應該在 commit message 的地方可以連結到用戶，是不是沒有設置 username, email
* git config --global user.name yourname
* git config --global user.email yourmail
> 我有設定username跟email，因為沒設定的話是沒辦法commit的，至於為什麼它沒有連結到用戶，我也不知道原因，要再試試看。[name=tang7526][time=Thu, Oct 6, 2016 4:14 PM][color=#ff0000]

* commit 感覺應該要分兩次做，因為連結中的 commit msg 是 `reduce data structure`，但是修改的程式碼不只像 message 說的那樣，還實作了搜尋的程式碼，故我認為應該要分開寫下 commit
> 嗯，是我漏掉了。[name=tang7526][time=Thu, Oct 6, 2016 4:16 PM][color=#ff0000]

* (這點單純是我的疑惑) [[2]](https://www.byvoid.com/blog/string-hash-compare) 能做文獻嗎，我覺得它只是 blog 文章 XD
> OK，我將文獻一詞改成參考資料。[name=tang7526][time=Thu, Oct 6, 2016 4:18 PM][color=#ff0000]

## 開發環境
OS：Linux Mint 18 "Sarah" - MATE (64-bit)
Linux Kernel：4.4.0-21-generic

### 系統CPU資訊
要讀取系統cpu資訊，可以使用 lscpu 指令，以下是我的系統的CPU資訊：

Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                2
On-line CPU(s) list:   0,1
Thread(s) per core:    1
Core(s) per socket:    2
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 23
Stepping:              10
CPU MHz:               1600.000
BogoMIPS:              4787.74
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              3072K
NUMA node0 CPU(s):     0,1

---

在執行程式(phonebook_orig 和 phonebook_opt) 前，先清空 cache:

$ echo 1 | sudo tee /proc/sys/vm/drop_caches

## 優化前的執行結果

$ perf stat -e cache-misses ./phonebook_orig

size of entry : 136 bytes
execution time of append() : 0.085271 sec
execution time of findName() : 0.016910 sec

 Performance counter stats for './phonebook_orig':

           83,9333      cache-misses                                               

       0.140261546 seconds time elapsed

## 改進方向(1) - reduce data structure
改寫 struct __PHONE_BOOK_ENTRY 的成員，搬動到新的結構中。

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;

typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    struct __DETAIL *pDetail;
    struct __PHONE_BOOK_ENTRY *pNext;
} entry;

## 優化後的執行結果

$ perf stat -e cache-misses ./phonebook_opt

size of entry : 32 bytes
execution time of append() : 0.061269 sec
execution time of findName() : 0.005793 sec

 Performance counter stats for './phonebook_opt':

            4,8396      cache-misses                                                

       0.079880126 seconds time elapsed

比較優化前和優化後的執行結果，可看到：
1. entry的size從136bytes變成32bytes
2. append和findName的執行時間皆有降低
3. cache-misses從83,9333降到4,8396。

## 使用gnuplot來製圖

$ make plot


## 改進方向(2) - hash function
目的：使用 hash function 來加速查詢。

根據參考資料[1]，hash function會將輸入的資料壓縮，使得資料量變小，重新建立一個叫做雜湊值的指紋，雜湊值通常用來代表一個短的隨機字母和數字組成的字串。

hash function有很多種，根據參考資料[2]，目前最好的hash function為BKDRHash，參考資料[2]亦將各種hash function的C語言程式碼列了出來，BKDRHash function的程式碼如下：

// BKDR Hash Function
unsigned int BKDRHash(char *str)
{
    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
    unsigned int hash = 0;

    while (*str)
    {
        hash = hash * seed + (*str++);
    }

    return (hash & 0x7FFFFFFF);
}

### 參考資料
[1] [雜湊函數-維基百科](https://zh.wikipedia.org/wiki/%E6%95%A3%E5%88%97%E5%87%BD%E6%95%B8)
[2] [各種字符串Hash函數比較](https://www.byvoid.com/blog/string-hash-compare)

## hash function優化後的執行結果
to be continued...