# 2016 Homework 1 - phonebook

### Reviewed by <`andy19950`>
- 僅測試一種 dataset 沒有考慮使用符合現實情況的 dataset。
- 雖然使用 hash function 後 cache miss 有改善，但是 append 的時間變得太久有點不符合效益。
- 在程式碼內使用 BKDR hash function 很不錯，但是能夠了解一下他的概念並介紹給我們知道更好。
- github 上傳時可以先使用 git add file_name 來選擇要上傳的檔案，然後使用 git commit -m "text" 來註解該檔案的意義，而不是把每個檔案一次上傳然後每個都用同樣的註解。
---
## 開發環境及工具安裝

- Ubuntu 16.04 LTS
- git & github
- perf

## phonebook_origin
- phonebook.h

 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;

entry *findName(char lastName[], entry *pHead);
entry *append(char lastName[], entry *e);

- phonebook.c

entry *findName(char lastName[], entry *pHead)
{
    while (pHead != NULL) {
        if (strcasecmp(lastName, pHead->lastName) == 0)
            return pHead;
        pHead = pHead->pNext;
    }
    return NULL;
}

entry *append(char lastName[], entry *e)
{
    /* allocate memory for the new entry and put lastName */
    e->pNext = (entry *) malloc(sizeof(entry));
    e = e->pNext;
    strcpy(e->lastName, lastName);
    e->pNext = NULL;

    return e;
}

## 改善方式
- #### 改變資料儲存方式

- 藉由改變原本Struct內部儲存內容，，尚未改變來的搜尋方式，達到降低cache miss 及"極細微"降低執行時間。
- 當搜尋電話簿的過程只尋找 lastname 而不需要其他資訊並不完全符合現實情況。

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

- Hash function 使用
- 藉由Hash 的方式，改變搜尋資料的過程。
- 找了一下string hash 的使用，有找到一個[各種Hash 的比較](https://www.byvoid.com/zht/blog/string-hash-compare)，也因此決定使用BKDR Hash 實作。
- 在實作過程中，遇到許多困難，對於 varible 其 pointer 的使用極度不熟悉，在後來參考他人的共筆後才完成。

* cache miss 比較

orig

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

         2,011,628      cache-misses              #   90.346 % of all cache refs      ( +-  0.07% )
         2,226,578      cache-references                                              ( +-  0.05% )
       261,251,457      instructions              #    1.34  insns per cycle          ( +-  0.02% )
       195,112,054      cycles                                                        ( +-  0.23% )

       0.070730799 seconds time elapsed                                          ( +-  0.87% )

opt(struct)

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

           213,815      cache-misses              #   58.056 % of all cache refs      ( +-  0.40% )
           368,290      cache-references                                              ( +-  0.14% )
       240,720,997      instructions              #    1.79  insns per cycle          ( +-  0.02% )
       134,571,324      cycles                                                        ( +-  0.16% )

       0.047346644 seconds time elapsed                                          ( +-  0.50% )	

hash

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

         1,903,707      cache-misses              #   27.554 % of all cache refs      ( +-  0.27% )
         6,909,127      cache-references                                              ( +-  0.03% )
       277,394,837      instructions              #    0.36  insns per cycle          ( +-  0.02% )
       772,581,926      cycles                                                        ( +-  0.13% )

       0.278813297 seconds time elapsed                                          ( +-  0.49% )


## 討論
* hash function append() 時間過高！！，不確定是精準度不夠或是其他原因造成findNamd() 時間是0.0000000

* 除了改變struct 的方式，Hash 也降低了cache miss 比例

## 心得
>效能分析是第一次做，也沒有想到可以用簡單的方式就可以有顯著的改變，更不用說那些我還沒發現的方式
>不熟悉的東西太多了，gnuplot、perf、makefile、predefine macro 語法 使用還需要再更加了解。
>coding 就如同老師說的，以前都是騙自己過來的，之後要再慢慢贖罪。
## 參考資料
[hash比較](https://www.byvoid.com/zht/blog/string-hash-compare)
[anndy19950共筆](https://hackmd.io/MwMwrCAsDsIMYFoAcAjAjATgZAhgUxGTQDYwEMUVQ5gdgKwg?view#)
[predefine macro](https://gcc.gnu.org/onlinedocs/cpp/Defined.html)
[phonebook 作業說明](https://hackmd.io/s/S1RVdgza)