# 2017q3 Homework1 (phonebook)

contributed by <`yang196569`>

## 開發環境

### OS : Ubuntu 16.04 LTS
透過`$ lscpu`可以看開發環境的相關資訊

Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                8
On-line CPU(s) list:   0-7
Thread(s) per core:    2
Core(s) per socket:    4
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 60
Model name:            Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz
Stepping:              3
CPU MHz:               3415.869
CPU max MHz:           4000.0000
CPU min MHz:           800.0000
BogoMIPS:              7184.02
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              8192K

## 學習 Perf

參考 [perf原理與實務](https://hackmd.io/s/B11109rdg) 這篇，
練習使用
* `$ perf list`: 看`perf`可以觸發的event
* `$ perf top`: 即時的觀察正在吃資源的程序
* `$ perf stat`: 對特定的目標(要優化的)或event觀察
* `$ perf record & report`:可以更精確的分析與優化(可達函式級別)

## Phonebook
將 [phonebook](https://github.com/sysprog21/phonebook) fork 過來後，先用`gnu plot`來看看原本的 performance


### 優化
參考 [`<jkrvivian>`](https://hackmd.io/s/SyOQgOQa#) 的共筆
#### 1.縮小 structure

在原始的版本中，只有用到`lastname`，所以把其他的先挪掉，可以將entry縮小

typedef struct MORE_INFO {
    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 MORE_INFO *pNext;
} Info;

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

可以透過`$ echo 1 | sudo tee /proc/sys/vm/drop_caches`這段指令清除cache然後再分別對原本以及優化過後的版本做測試，不過我是直接用Makefile裡的做測試: `$ make cache-test`
可以看到cache-misses的比例以及數字的降低。

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

           97,5550      cache-misses              #   81.773 % of all cache refs      ( +-  0.40% )
          119,2992      cache-references                                              ( +-  0.42% )
       2,6188,3953      instructions              #    1.28  insn per cycle           ( +-  0.03% )
       2,0409,6402      cycles                                                        ( +-  0.37% )

       0.053437975 seconds time elapsed                                          ( +-  0.52% )

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

            9,0883      cache-misses              #   45.952 % of all cache refs      ( +-  0.75% )
           19,7778      cache-references                                              ( +-  0.91% )
       2,4107,1384      instructions              #    2.02  insn per cycle           ( +-  0.02% )
       1,1941,4871      cycles                                                        ( +-  0.26% )

       0.031239725 seconds time elapsed                                          ( +-  0.36% )

#### 2.使用BKDR Hash Function

閱讀 [hash function 觀念和實務](https://hackmd.io/s/HJln3jU_e)

影響分布的因子:
* Hash Funtion的取用
* Hash Table的大小

在這邊採用針對字串而設計的 [BKDR Hash Function](http://blog.csdn.net/wanglx_/article/details/40400693)
Tablesize則是參考[質數列表](https://zh.wikipedia.org/wiki/%E8%B3%AA%E6%95%B8%E5%88%97%E8%A1%A8)，選擇第五百大的`3571`

unsigned int BKDRHash(char str[])
{
    unsigned int seed = 1313;
    unsigned int hashValue = 0;

    while (*str) {
        hashValue = hashValue * seed + (*str++);
    }

    return (hashValue % TABLESIZE);
}

可以觀察到 cache-misses明顯減少

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

           97,7574      cache-misses              #   84.132 % of all cache refs      ( +-  0.63% )
          116,1955      cache-references                                              ( +-  0.65% )
       2,6187,6489      instructions              #    1.30  insn per cycle           ( +-  0.03% )
       2,0144,8422      cycles                                                        ( +-  0.18% )

       0.052076459 seconds time elapsed                                          ( +-  0.25% )

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

            5,5214      cache-misses              #   12.344 % of all cache refs      ( +-  1.35% )
           44,7297      cache-references                                              ( +-  0.62% )
       2,3964,5605      instructions              #    1.81  insn per cycle           ( +-  0.02% )
       1,3243,1204      cycles                                                        ( +-  0.22% )

       0.034220580 seconds time elapsed                                          ( +-  0.28% )

#### 按照英文字母排列
這次改成用英文字母的字首為分類方式，也比較像是一般通訊錄會分類的方式。

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

           94,9285      cache-misses              #   81.936 % of all cache refs      ( +-  0.63% )
          115,8564      cache-references                                              ( +-  0.72% )
       2,6189,8446      instructions              #    1.31  insn per cycle           ( +-  0.03% )
       2,0067,7640      cycles                                                        ( +-  0.19% )

       0.051925072 seconds time elapsed                                          ( +-  0.26% )

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

            5,4717      cache-misses              #   46.177 % of all cache refs      ( +-  0.51% )
           11,8494      cache-references                                              ( +-  1.00% )
       1,9246,9902      instructions              #    1.90  insn per cycle           ( +-  0.03% )
       1,0143,8266      cycles                                                        ( +-  0.24% )

       0.026350881 seconds time elapsed                                          ( +-  0.31% )


## 參考內容
* [perf 原理和實務](https://hackmd.io/s/B11109rdg)
* [`<jkrvivian>`的共筆](https://hackmd.io/s/SyOQgOQa#2016q3-homework-1-phonebook)
* [hash function 觀念和實務](https://hackmd.io/s/HJln3jU_e)

###### tags: `MISC`