2018q1 Homework1 (phonebook)
===
### Reviewed by `vulxj0j8j8`
* 在Hash Function的部份, 沒有嘗試不同的seed的結果, 不同的seed應該可以減少cache miss及執行時間
### Reviewed by `e94046165`
* 在實作 hash search 的時候只有看到 findName 的 performance 變好就停手，實在是太可惜了。hash search 還有許多學問在裡頭，例如：不同的 seed 或 hash function 造成的 cache-misses/效能差異；不同 hash_table_size 的影響等都是可以嘗試的議題。
* github 上並未上傳配合實作 hash search(phonebook_bkdr)的 Makefile 和 gnuplot scripts 建議可以補上(其他人才不用辛苦得 gcc 編譯、跑perf 分析等等)。
### Reviewed by `chasingfar`
* 開頭加上 contributed by < `...` > 方便辨認
* BKDR hash findName() 的時間無法計測，可嘗試改變 `main.c` 的實驗方式，如增加 findName() 的執行次數。
* 最後一張圖 BKDR hash 的 `h` 發生了什麼事?XD
---
# 安裝Ubuntu
* 之前就已經有看過助教的雙系統安裝影片，所以信心滿滿的去安裝ubuntu，結果馬上被很很打臉
```
[Firmware Bug]: TSC_DEADLINE disabled due to Errata;
please update microcode to version: 0x25 (or later)
```
* 在一開始要從USB開機時，按完 try ubuntu without install 後跑出了這個東西
* 上網找了一下，反正就是 [update intel microcode](https://askubuntu.com/questions/984970/firmware-bug-tsc-deadline-disabled-due-to-errata-what-should-i-do-about-thi) ，重灌BIOS就好了
---
* 在以為可以順利進到"試用畫面"的時候，又出現了ACPI的問題
```
ACPI Error: [PEGO.PEGP.EASP] Namespace lookup failure, AE_NOT_FOUND
ACPI Error: Method parse/execution failed AE_NOT_FOUND
```
* 我試著在 boot parameters 輸入 [ACPI=OFF](https://askubuntu.com/questions/953666/acpi-errors-when-booting-cant-boot)，但結果還是一樣，進入 try ubuntu without install 之後就會當機， check disc for defects 後原因還是出現在 ACPI
* 最後，我只能退而求其次，試試 ubuntu 16.04.1 ，終於順利安裝成功
---
# 系統環境
```
$ uname -a
Linux blake-GL62-7RD 4.4.0-116-generic #140-Ubuntu SMP Mon Feb 12 21:23:04 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
$ lscpu
Architecture: x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
每核心執行緒數：1
每通訊端核心數：4
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 158
Model name: Intel(R) Core(TM) i5-7300HQ CPU @ 2.50GHz
製程： 9
CPU MHz： 800.000
CPU max MHz: 3500.0000
CPU min MHz: 800.0000
BogoMIPS: 4991.91
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 6144K
NUMA node0 CPU(s): 0-3
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 art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf eagerfpu pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch epb invpcid_single intel_pt retpoline kaiser tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap clflushopt xsaveopt xsavec xgetbv1 dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp
```
---
# Phonebook
## 未優化之效能分析 phonebook.orig
* entry 大小與執行時間
```
size of entry : 136 bytes
execution time of append() : 0.043110 sec
execution time of findName() : 0.004989 sec
```
* perf 分析
```
$ perf stat --repeat 100 -e cache-misses,cache-references,instructions,cycles ./phonebook_orig
```
```
5,836,255 cache-misses # 94.112 % of all cache refs ( +- 0.13% )
6,201,420 cache-references ( +- 0.07% )
321,545,101 instructions # 1.49 insns per cycle ( +- 0.01% )
215,972,415 cycles ( +- 0.20% )
0.071345386 seconds time elapsed ( +- 0.40% )
```
---
```
$ ./phonebook_orig & perf top -p $!
```
```
13.82% libc-2.23.so [.] __strcasecmp_l_avx
12.90% libc-2.23.so [.] _int_free
12.04% phonebook_orig [.] main
10.15% phonebook_orig [.] findName
8.15% libc-2.23.so [.] _int_malloc
5.74% libc-2.23.so [.] _IO_fgets
```
## 縮小 struct 之優化效能分析 phonebook.opt
* 觀察尚未優化的 phonebook 可以發現 entry 使用了 136 bytes，而真正會用到的卻只有 lastName 32 bytes，因此使用兩個 struct 來建構 phonebook，一個是 findlastName() 會用到的 entry，另一個則是 detail 來存取其他資料，兩者用指標連接起來。
```
typedef struct __PHONE_BOOK_DETAIL {
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];
} detail;
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
detail *details;
struct __PHONE_BOOK_ENTRY *pNext;
} entry;
```
* 執行過後，可以發現 entry 與執行時間皆有顯著改變
```
size of entry : 32 bytes
execution time of append() : 0.041372 sec
execution time of findName() : 0.001988 sec
```
* 將圖片 plot 出來後兩者的比較
* 可以發現執行時間 append() 和 findName() 皆有下降，cache miss 也有下降不少。
```
Performance counter stats for './phonebook_opt' (100 runs):
1,954,377 cache-misses # 68.777 % of all cache refs ( +- 0.41% )
2,841,633 cache-references ( +- 0.12% )
282,105,930 instructions # 2.07 insns per cycle ( +- 0.02% )
136,007,481 cycles ( +- 0.20% )
0.043787342 seconds time elapsed ( +- 0.67% )
```
---
## 使用 hash 方法之優化效能分析 phonebook.bkdr
* 在搜尋[網路資料](https://www.byvoid.com/zht/blog/string-hash-compare)之後，若要針對字串做 hash，效能最佳的是使用 BKDR Hash，因此我便使用了此方法來增進 phonebook 的效能。
* 此為 BKDR hash function
```
// BKDR Hash Function
int BKDR_hash(char *str)
{
int seed = 26;
long long hash = 0;
while (*str)
hash = hash * seed + (*str++);
return hash % HASH_TABLE_SIZE;
}
```
* 可以發現，執行 findName() 的時間幾乎為零了
```
size of entry : 32 bytes
execution time of append() : 0.071141 sec
execution time of findName() : 0.000000 sec
```
* 然而，cache miss 卻沒有下降太多
```
Performance counter stats for './phonebook_bkdr' (100 runs):
2,472,395 cache-misses # 73.482 % of all cache refs ( +- 0.52% )
3,364,611 cache-references ( +- 0.18% )
331,778,774 instructions # 1.58 insns per cycle ( +- 0.02% )
209,744,271 cycles ( +- 0.27% )
0.080400874 seconds time elapsed ( +- 0.35% )
```
* 針對原始版本，縮小 struct 版本與 hash 版本做出的 plot 比較
---
## 針對真實 Name 做資料分析
* 由於原本的資料所使用的 Name 有 aaaaa、aaaaaaa 等等奇怪的名字，在真實世界的 phonebook 不太可能存在，因此我上網尋找了一個 [free name database](http://www.quietaffiliate.com/Files/names_database_sql.sql)，用來作為我資料庫
* 現實中一定會遇到的問題，**名字重複啊阿**
*
Sign in with Wallet
Connect another wallet