2017q1 Homework1(phonebook)

contributed by < EdisonHsien >

請加快進度!
課程助教

Reviewed by `sufuf3`

commit message 50f01aa 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

中英文字間請以空白隔開
課程助教

事前準備

輕鬆學會 windows /Ubuntu雙系統教學
- 安裝到一半的時候發現 grub 沒辦法正確安裝，覺得可能是分割磁區的部分少分割了甚麼，譬如 efi partition，最後索性拿了一顆硬碟直接格式化裝了 Ubuntu。
perf 原理和實務
- perf stat 比起 top會做更明確且深入的效能檢測
終端機，Vim 設定
- 之前就有用過 vim，這邊算複習

不要寫「還算 OK」，你要具體標出你懂的地方，還有哪些待釐清之處！
理工科技的學生，說話不該含糊 "jserv"

Trace C 程式碼的 vim 設定
- 這部分還沒很懂

目標與實作

改善 phone book 的 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
- 簡單來說我們將所有的英文字母符號轉換成數字加總當做 Index ，但轉換出來的值往往很大，為了解決這個問題，我們用 modulus calculation ，就是取餘數的方式，但也產生一個新的問題， Hash Collisions

2017q1 Homework1(phonebook)

Reviewed by sufuf3

開發環境

事前準備

目標與實作

補充

Reviewed by `sufuf3`