# 2016q3 Homework1（phonebook）
###### tags: `tundergod` `hw1` `2016q3`
contributed by <`tundergod`>

### Reviewed by `TempoJiJi`
* 沒有詳細說明關於hash function的實做，也沒有比較不同的hash table size
* 沒有具體說明改進後效能變好的原因
* 沒有關於perf的使用記錄等
* 沒有關注cache miss，以及做對應的相關實驗
* 應該探討如何降低append的時間
* [commit 7dcb319](https://github.com/tundergod/phonebook-1/commit/427e76234df7bca08c8dfca727d8198e9c90eb2a)寫的太爛！完全不知道你做了什麼

## 作業說明
* [A01: phonebook](https://hackmd.io/s/S1RVdgza)

## 開發環境
* Linux 版本: Ubuntu 16.04 LTS

* 硬體資訊：使用`lscpu`查看

Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
Thread(s) per core:    2
Core(s) per socket:    2
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 69
Model name:            Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz
Stepping:              1
CPU MHz:               1661.660
CPU max MHz:           2600.0000
CPU min MHz:           800.0000
BogoMIPS:              4589.54
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              3072K
NUMA node0 CPU(s):     0-3

## 原始效能分析數據與圖表
* 數據：

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

          106,1028      cache-misses              #   84.454 % of all cache refs      ( +-  0.81% )
          125,6338      cache-references                                              ( +-  0.67% )
       2,6075,7557      instructions              #    1.31  insns per cycle          ( +-  0.02% )
       1,9910,2540      cycles                                                        ( +-  0.86% )

       0.085194952 seconds time elapsed                                          ( +-  1.00% )

* 圖表：

## 效能改進
### 改寫 struct __PHONE_BOOK_ENTRY
* 原本的phonebook entry有136bytes的資料，而程式的執行只需要通過尋找lastname，建立新的struct取代原本的struct,只用以下三個參數作爲結構元素只有32bytes(因爲對齊)的資料
* 建立一個all指標避免破壞原始功能

typedef struct __LASTNAME_ENTRY{
        char lastName[MAX_LAST_NAME_SIZE];		//16bytes
        entry_all *all;//for finding more detail	//4bytes
        struct __LASTNAME_ENTRY *pNext;		//4bytes
} entry;

* 改寫後數據與圖表：

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

           12,6876      cache-misses              #   31.314 % of all cache refs      ( +-  0.53% )
           40,5171      cache-references                                              ( +-  0.93% )
       2,4402,2088      instructions              #    1.81  insns per cycle          ( +-  0.02% )
       1,3457,9688      cycles                                                        ( +-  0.36% )

       0.056097970 seconds time elapsed                                          ( +-  0.48% )


### 使用Hash function
* 使用BKDRhash function進行修改
* 改寫後數據與圖表

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

            9,4098      cache-misses              #   42.218 % of all cache refs      ( +-  1.12% )
           22,2888      cache-references                                              ( +-  1.28% )
       2,4101,5594      instructions              #    1.91  insns per cycle          ( +-  0.02% )
       1,2608,5592      cycles                                                        ( +-  0.40% )

       0.052481990 seconds time elapsed