# 2017q1 Homework1(phonebook)

contributed by < `EdisonHsien ` >
>>請加快進度!
>>[name=課程助教][color=red]

## Reviewed by `sufuf3`
* commit message [50f01aa](https://github.com/EdisonHsien/phonebook/commit/50f01aa4950c1c1451614253d058bc2d925d34da) `Hello`是表示什麼！！
commit message 應該是描述你這斷功能的增加或調整的內容描述。請用`git commit --amend` 修正。(ref: https://git-scm.com/book/en/v2/Distributed-Git-Contributing-to-a-Project)
* 若能使用圖表呈現會較佳(`sudo make plot`)。
* `Hash Function` 是還未實作嗎？

## 開發環境

edison@edison-MS-7721:~$ lscpu
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
供應商識別號：  AuthenticAMD
CPU 家族：          21
型號：              48
Model name:            AMD Athlon(tm) X4 860K Quad Core Processor
製程：              1
CPU MHz：             1700.000
CPU max MHz:           3700.0000
CPU min MHz:           1700.0000
BogoMIPS:              7386.21
虛擬：              AMD-V
L1d 快取：          16K
L1i 快取：          96K
L2 快取：           2048K
NUMA node0 CPU(s):     0-3    

---

>>中英文字間請以空白隔開
>>[name=課程助教][color=red]
## 事前準備
* [輕鬆學會 windows /Ubuntu雙系統教學](https://www.youtube.com/watch?v=rjpBTT6AmeU)
* 安裝到一半的時候發現 grub 沒辦法正確安裝，覺得可能是分割磁區的部分少分割了甚麼，譬如 efi partition，最後索性拿了一顆硬碟直接格式化裝了 Ubuntu。
* [perf 原理和實務](https://hackmd.io/s/B11109rdg)
* ```perf stat ``` 比起 ```top```會做更明確且深入的效能檢測
* [終端機，Vim 設定](https://hackmd.io/AwEwzA7AjGBGIFpZVsBAWAbCArAgnAMYBMAhggBzBg7D736ghA==#)
* 之前就有用過 vim，這邊算複習
>> 不要寫「還算 OK」，你要具體標出你懂的地方，還有哪些待釐清之處！
>> 理工科技的學生，說話不該含糊 [name="jserv"]
* [Trace C 程式碼的 vim 設定](http://wen00072.github.io/blog/2016/11/26/vim-setup-for-trace-c-code/)
* 這部分還沒很懂
## 目標與實作
* 改善 [phone book](https://github.com/sysprog21/phonebook/) 的 Cache miss
* STEP 1 將phonebook_opt.h的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;
} entry;

可以發現

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

           576,640      cache-misses              #   14.484 % of all cache refs      ( +-  0.21% )  (75.06%)
         3,981,355      cache-references                                              ( +-  0.44% )  (51.25%)
       263,944,044      instructions              #    0.83  insn per cycle            ( +-  0.21% )  (76.13%)
       317,224,241      cycles                                                        ( +-  0.18% )  (75.53%)

       0.081746195 seconds time elapsed                                          
       ( +-  0.31% )

從 14.484% 下降到 9.718%

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

           195,458      cache-misses              #    9.718 % of all cache refs      ( +-  0.31% )  (73.47%)
         2,011,372      cache-references                                              ( +-  0.64% )  (51.73%)
       243,230,170      instructions              #    1.04  insn per cycle            ( +-  0.22% )  (77.88%)
       234,302,473      cycles                                                        ( +-  0.29% )  (76.57%)

       0.060927358 seconds time elapsed                                          
       ( +-  0.42% )

* STEP2 依照提示使用 hash function
使用BKDR Hash Function

unsigned long BKDRHash(char* str)
   {
      long seed = 131; // 31 131 1313 13131 131313 etc..
      long hash = 0;
      while (*str){
      hash = hash * seed + (*str++);
      }
      return (hash & 0x7FFFFFFF);
   }
   /* End Of BKDR Hash Function */

## 補充
* [How Hash functions work](http://stackoverflow.com/questions/730620/how-does-a-hash-table-work)
* 簡單來說我們將所有的英文字母符號轉換成數字加總當做 Index ，但轉換出來的值往往很大，為了解決這個問題，我們用 modulus calculation ，就是取餘數的方式，但也產生一個新的問題， Hash Collisions