# 2016q3 Homework1 (phonebook)
contributed by <`GreenYo0413`>
### Reviewed by <`LitSnow`>
* 可以稍微講解一下如何設定 block 的 node 數
* 實驗使用的 data set 皆為無意義的英文字母組成 ， 並不符合現實狀況

## perf使用
參考網址：
http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial
這裡要注意的是在跑第一個範例時，是要在程式跑的途中開令一個terminal執行 ```perf top -p $pid```
#### 執行結果

## Phonebook 改良

---

### 改寫結構
改寫目的是由於cache的容量有限過大的資料結構會讓 cache 的 miss rate上升

typedef struct OTHER_ATTRIBUTES {
    char firstName[16];
    char email[16];
    char addr1[16];
    char addr2[16];
    char city[16];
    char phone[10];
    char cell[10];
    char state[2];
    char zip[5];
} DETAIL;
typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    DETAIL *pDetail;
    struct __PHONE_BOOK_ENTRY *pNext;
} entry;

若在append function實做上不把DETAIL的空間配置出來，其平均會稍微降低
效能比較：

---

原始 cache miss rate

         1,944,548      cache-misses              #   89.353 % of all cache refs      ( +-  0.09% )
         2,176,248      cache-references                                              ( +-  0.10% )
       261,607,304      instructions              #    1.16  insns per cycle          ( +-  0.02% )
       225,186,547      cycles                                                        ( +-  0.26% )

       0.068816848 seconds time elapsed                                          ( +-  0.69% )

最佳化後 cache miss rate

           375,472      cache-misses              #   56.836 % of all cache refs      ( +-  0.15% )
           660,625      cache-references                                              ( +-  0.27% )
       244,104,027      instructions              #    1.63  insns per cycle          ( +-  0.02% )
       150,110,072      cycles                                                        ( +-  0.23% )

       0.046543328 seconds time elapsed                                          ( +-  1.01% )

---

### 改寫資料串連方式
這個想法是基於cache本身是一次取一個區塊的資料，所以在配置記憶體時主動讓資料有空間相依性，其實做方式是在append function時一次配置大一點的記憶體區塊，其大小為一個節點大小的倍數。這麼做的話就可以讓 search function 可以從一個節點到下一個節點時，其取的資料有機會在cache裡Hit。

效能比較：
我設定一個Block是16個node

最佳化後 cache miss rate

           254,170      cache-misses              #   56.816 % of all cache refs      ( +-  0.36% )
           447,357      cache-references                                              ( +-  0.56% )
       182,722,935      instructions              #    1.38  insns per cycle          ( +-  0.03% )
       132,654,640      cycles                                                        ( +-  0.32% )

       0.038942933 seconds time elapsed                                          ( +-  0.70% )