# 2017q3 Homework1 (phonebook)
contributed by <`yayachen`>

## 系統環境

$ uname -a
Linux ncku-ProLiant-ML350-Gen9 4.10.0-35-generic #39~16.04.1-Ubuntu SMP Wed Sep 13 09:02:42 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux


$ lscpu
Architecture:          x86_64
CPU 作業模式：    32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                32
On-line CPU(s) list:   0-31
每核心執行緒數：2
每通訊端核心數：8
Socket(s):             2
NUMA 節點：         2
供應商識別號：  GenuineIntel
CPU 家族：          6
型號：              79
Model name:            Intel(R) Xeon(R) CPU E5-2620 v4 @ 2.10GHz
製程：              1
CPU MHz：             1218.000
CPU max MHz:           2100.0000
CPU min MHz:           1200.0000
BogoMIPS:              4190.34
虛擬：              VT-x
L1d 快取：          32K
L1i 快取：          32K
L2 快取：           256K
L3 快取：           20480K
NUMA node0 CPU(s):     0-7,16-23
NUMA node1 CPU(s):     8-15,24-31
Flags:                 fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid dca sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch epb cat_l3 cdp_l3 intel_ppin intel_pt tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 erms invpcid rtm cqm rdt_a rdseed adx smap xsaveopt cqm_llc cqm_occup_llc cqm_mbm_total cqm_mbm_local dtherm ida arat pln pts

$ free
              total        used        free      shared  buff/cache   available
Mem:       65839000      496496    64905824       95408      436680    64678636
置換：    31998972           0    31998972

## 原始版本

$ make run
size of entry : 136 bytes
execution time of append() : 0.078587 sec
execution time of findName() : 0.008229 sec

* 分析熱點函式
`$ ./phonebook_orig & perf top -p $!`

  33.89%  libc-2.23.so    [.] __strcasecmp_l_avx
  28.04%  phonebook_orig  [.] findName
   6.58%  phonebook_orig  [.] main
   6.46%  [kernel]        [k] clear_page_c_e
   3.77%  libc-2.23.so    [.] _int_malloc
   3.50%  [kernel]        [k] release_pages
   3.12%  libc-2.23.so    [.] _IO_fgets
   2.33%  [kernel]        [k] unmap_page_range
   1.75%  libc-2.23.so    [.] __strcpy_sse2_unaligned
   1.29%  [kernel]        [k] _raw_spin_lock
   0.78%  [kernel]        [k] get_mem_cgroup_from_mm
   0.75%  [kernel]        [k] 

> 使用最多的是 __strcasecmp_l_avx 字串比較的地方，佔了33% 。

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

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

         2,418,351      cache-misses              #   71.136 % of all cache refs      ( +-  0.07% )
         3,399,627      cache-references                                              ( +-  0.05% )
       262,907,715      instructions              #    1.31  insn per cycle           ( +-  0.02% )
       199,931,591      cycles                                                        ( +-  0.44% )

       0.102490864 seconds time elapsed                                          ( +-  1.20% )

>cache-misses 有 71.13% 。相較於其他同學的 9x% 小了不少。
>我想是因為我的cache有大約20MB吧。entry 的 size 是 136 bytes ，136 bytes * 35萬筆資料大概是45MB。
## 縮小size of entry

* 查看了 `findname()` 發現 entry 中只會用到 lastName ，但其他的資料也會被一並寫進 cache 中，當然會造成很高的 cache-misses ，所以先嘗試縮小 entry。
* 重寫 entry 將其他資料搬入另一個 struct 中獨立出來。

* 更改資料結構為 :

typedef struct __PHONE_BOOK_DATA {
    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];
} Data;

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

* 比較圖
*

* 更改後 size of entry 只剩 32 bytes

size of entry : 32 bytes
execution time of append() : 0.051377 sec
execution time of findName() : 0.002047 sec

* 分析 cache-misses

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

           177,749      cache-misses              #   14.773 % of all cache refs      ( +-  0.61% )
         1,203,164      cache-references                                              ( +-  0.04% )
       245,122,721      instructions              #    2.00  insn per cycle           ( +-  0.02% )
       122,438,119      cycles                                                        ( +-  0.16% )

       0.063742222 seconds time elapsed                                          ( +-  0.99% )

>cache-misses 竟然只剩 14% 。計算一下現在被寫入的資料量大概是 32 bytes * 35萬筆資料大概為10 MB。比原先的 45 MB 小了很多，也小於我的 cache size 。

## 回答以下問題：本例選用的 dataset (也就是輸入電話簿的姓名) 是否存在問題？

* 有代表性嗎？跟真實英文姓氏差異大嗎？
> 字典檔裡有太多無意義的單字了，也不符合英文名字。例如 : aaaaa,zzzzz。
* 資料難道「數大就是美」嗎？
> 如在做機器學習、資料探勘等當然是數據越充足結果越準確。但也建立在這些資料是被篩選，正規處理後的"真正有用的資料"。
> 而當資料超過一定程度後，可能對結果沒有明顯的改善，但卻會拖垮整體效能。
* 如果我們要建立符合真實電話簿情境的輸入，該怎麼作？
>將字典檔改成英文人名的檔案，輸入前幾個字母後能跳出使用者可能想輸入的人名。

## 參考資料
[benson326同學共筆](https://hackmd.io/s/Hy2uUcEoZ)
[LanKuDot學長的Git筆記](http://wiki.csie.ncku.edu.tw/git)
[Programming Small](https://hackmd.io/s/SkfffA-jZ)