2016q3 Homework1 (phonebook)

contributed by <tang7526>

Reviewed by `aweimeow`

git 是否沒有配置好呢？
- 應該在 commit message 的地方可以連結到用戶，是不是沒有設置 username, email
- git config –global user.name yourname
- git config –global user.email yourmail

我有設定username跟email，因為沒設定的話是沒辦法commit的，至於為什麼它沒有連結到用戶，我也不知道原因，要再試試看。tang7526Thu, Oct 6, 2016 4:14 PM

commit 感覺應該要分兩次做，因為連結中的 commit msg 是 reduce data structure，但是修改的程式碼不只像 message 說的那樣，還實作了搜尋的程式碼，故我認為應該要分開寫下 commit

嗯，是我漏掉了。tang7526Thu, Oct 6, 2016 4:16 PM

(這點單純是我的疑惑) [2] 能做文獻嗎，我覺得它只是 blog 文章 XD

OK，我將文獻一詞改成參考資料。tang7526Thu, Oct 6, 2016 4:18 PM

開發環境

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

比較優化前和優化後的執行結果，可看到：

entry的size從136bytes變成32bytes
append和findName的執行時間皆有降低
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] 雜湊函數-維基百科
[2] 各種字符串Hash函數比較

hash function優化後的執行結果

to be continued…