# 2016q3 Homework1 (phonebook)
contributed by <`ierosodin`>

## 開發環境

作業系統 : CentOS 7

`$ lscpu`

Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 45
Model name: Genuine Intel(R) CPU @ 3.30GHz
Stepping: 5
CPU MHz: 1277.976
BogoMIPS: 6600.19
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 15360K
NUMA node0 CPU(s): 0-11

## 軟體安裝
yum install perf
yum install gnuplot
[astyle for centos](http://www.melvilletheatre.com/articles/el6/astyle-2.03-3.el6.x86_64.rpm)
rpm -ivh astyle-2.03-3.el6.x86_64.rpm

## Astyle
To format your file you can execute below command:

astyle --style=kr --indent=spaces=4 --indent-switches --suffix=none *.[ch]

## GitHub
fork to your GitHub

$ git add .
$ git commit -m 'Ver.1'
$ git remote set-url origin https://github.com/ierosodin/phonebook 
$ git push origin master

## PhoneBook 效能分析
`$ ./phonebook_orig &perf top -p $!`

  21.55%  libc-2.17.so    [.] __strcasecmp_l_avx
  17.30%  phonebook_orig  [.] findName
   6.40%  [kernel]        [k] clear_page_c
   5.79%  libc-2.17.so    [.] _IO_fgets

熱點發生在strcasecmp( 不斷的比較字串 )

### 可能的改善方向
老師提到可能的效能改進方向有

* 改寫 struct __PHONE_BOOK_ENTRY 的成員，搬動到新的結構中
* 使用 hash function 來加速查詢
* 既然 first name, last name, address 都是合法的英文 (可假設成立)，使用字串壓縮的演算法，降低資料表示的成本
* 使用 binary search tree 改寫演算法

### 原始Code效能
`$ make run`

size of entry : 136 bytes
execution time of append() : 0.083056 sec
execution time of findName() : 0.007171 sec

`$ perf stat --repeat 100 -e cache-misses,cache-references,instructions,cycles ./phonebook_orig`

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

         1,990,809      cache-misses              #   86.735 % of all cache refs      ( +-  0.24% )
         2,295,273      cache-references                                              ( +-  0.11% )
       247,251,886      instructions              #    1.11  insns per cycle          ( +-  0.02% )
       223,340,345      cycles                                                        ( +-  0.24% )

       0.068523391 seconds time elapsed                                          ( +-  0.30% )

## 嘗試一( phonebook_opt.[ch] )
發現在search時, 只會使用到last name, 嘗試修改phonebook_opt.h中的`__PHONE_BOOK_ENTRY`, 僅保留`char lastName[MAX_LAST_NAME_SIZE]`

### 效能影響
`$ watch -d -t "./phonebook_opt && echo 3 | sudo tee /proc/sys/vm/drop_caches"`

size of entry : 32 bytes
execution time of append() : 0.039816 sec
execution time of findName() : 0.002610 sec

entry縮減到32 bytes, append與fineName時間都有明顯縮短
entry大小會影響到電腦cache的使用
`$ perf stat --repeat 100 -e cache-misses,cache-references,instructions,cycles ./phonebook_opt`

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

           365,862      cache-misses              #   49.537 % of all cache refs      ( +-  0.90% )
           738,568      cache-references                                              ( +-  0.37% )
       224,825,485      instructions              #    1.65  insns per cycle          ( +-  0.02% )
       136,519,429      cycles                                                        ( +-  0.29% )

       0.042013263 seconds time elapsed                                          ( +-  0.37% )

## 嘗試二( phonebook_hash.[ch] )
嘗試老師提到的hash function加速查詢
==需要在Makefile, main.c, calculate.c中作額外的修改==
參考hash tables寫法 : http://algs4.cs.princeton.edu/34hash/

int hash = 0;
for (int i = 0; i < s.length(); i++)
    hash = (R * hash + s.charAt(i)) % M;

### 效能影響
`$ watch -d -t "./phonebook_hash && echo 3 | sudo tee /proc/sys/vm/drop_caches"`

size of entry : 24 bytes
execution time of append() : 0.057173 sec
execution time of findName() : 0.000026 sec

hash tables可以減少資料的比對次數, 對search的速度有明顯的提升, 但實際使用時, 造成append的時間變長
是否有方法可以使hash tables對append的影響降低?
`$ perf stat --repeat 100 -e cache-misses,cache-references,instructions,cycles ./phonebook_hash`

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

           269,028      cache-misses              #   36.329 % of all cache refs      ( +-  0.58% )
           740,533      cache-references                                              ( +-  0.77% )
       213,131,517      instructions              #    1.47  insns per cycle          ( +-  0.03% )
       145,081,096      cycles                                                        ( +-  0.63% )

       0.057804122 seconds time elapsed                                          ( +-  1.17% )

## 三種版本的比較圖