# 2017q1 Homework1 (phonebook)
contributed by <`litingyang`>

### Reviewed by `laochanlam`
- Markdown 的程式碼區塊可指定程式語言，像是 C 語言的話可以這樣

printf(" I am C ");

可以 lightlight 程式碼，使閱讀更舒服
- 可嘗試實作 Memory Pool 來減少 append() 的執行時間
- 可善用 **.gitignore** 優化開發程序
- 在本地端修改 git config 以取回GitHub commit 中的用戶名及頭像（？
- commit 中可適當加上 Why 及 How ，資訊太少，會被罵（噓

## 開發環境

Architecture:          x86_64
CPU 作業模式：    32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
每核心執行緒數：2
每通訊端核心數：2
Socket(s):             1
NUMA 節點：         1
供應商識別號：  GenuineIntel
CPU 家族：          6
型號：              60
Model name:            Intel(R) Core(TM) i5-4200H CPU @ 2.80GHz
製程：              3
CPU MHz：             1499.968
CPU max MHz:           3400.0000
CPU min MHz:           800.0000
BogoMIPS:              5587.02
虛擬：              VT-x
L1d 快取：          32K
L1i 快取：          32K
L2 快取：           256K
L3 快取：           3072K
NUMA node0 CPU(s):     0-3

## 實做

### origin

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;
} entry;

size of entry : 136 bytes

         1,213,548      cache-misses              #   85.624 % of all cache refs      ( +-  0.34% )
         1,417,297      cache-references                                              ( +-  0.28% )
       261,385,334      instructions              #    1.38  insns per cycle          ( +-  0.02% )
       189,397,975      cycles                                                        ( +-  0.13% )

       0.057404208 seconds time elapsed                                          ( +-  0.56% )

### 減少 entry 大小

typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    struct more_info *more;
    struct __PHONE_BOOK_ENTRY *pNext;
} entry;

typedef struct more_info {
    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;

size of entry : 32 bytes


           154,240      cache-misses              #   40.278 % of all cache refs      ( +-  0.49% )
           382,935      cache-references                                              ( +-  0.41% )
       244,279,089      instructions              #    1.96  insns per cycle          ( +-  0.02% )
       124,542,326      cycles                                                        ( +-  0.13% )

       0.037623995 seconds time elapsed                                          ( +-  0.15% )

append 速度以及 findname 速度都有提昇

### use hash function

unsigned int hash(char lastName[])
{
    unsigned int sum = 1;
    while(*lastName) {
        sum = ( sum + (sum << 2 + sum) * (*(lastName)) ) % MOD;

        lastName++;
    }
    return sum;
}


           150,124      cache-misses              #   27.893 % of all cache refs      ( +-  3.26% )
           538,221      cache-references                                              ( +-  0.34% )
       271,223,334      instructions              #    1.42  insns per cycle          ( +-  0.02% )
       191,212,278      cycles                                                        ( +-  0.34% )

       0.057488312 seconds time elapsed                                          ( +-  0.34% )

hash table size = 10007
append 速度下降而 findname 速度有明顯提昇
[hash function](https://brilliant.org/wiki/rabin-karp-algorithm/)

### use trie

typedef struct __PHONE_BOOK_ENTRY {
    int isword;
    struct more_info *more;
    struct __PHONE_BOOK_ENTRY *pNext[26];
} entry;

size of entry : 224 bytes


           353,098      cache-misses              #   68.819 % of all cache refs      ( +-  0.52% )
           513,080      cache-references                                              ( +-  0.72% )
       498,826,561      instructions              #    1.46  insns per cycle          ( +-  0.01% )
       341,208,312      cycles                                                        ( +-  0.18% )

       0.102322192 seconds time elapsed                                          ( +-  0.20% )

記憶體的使用量大、node 數多，append 時間長，findname 時間少