# 2017q1 Homework1 (phonebook)
contributed by <`rayleigh0407`>
### Reviewed by `yachiyang01`
- 測試一中削減資料大小的方法，可以嘗試將一些不需要放在struct中的資料獨立出來。
- Commit Message內文應說明是什麼、為什麼而不是如何做。
### Reviewed by `illusion030`
* commit message 寫得不清楚
* 沒有當 malloc 失敗時的防呆
### Reviewed by `SeanCCC`
* 沒有解釋hash table大小怎麼決定的
## 開發環境
```shell
**Desktop**
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: 94
Model name: Intel(R) Core(TM) i7-6700K CPU @ 4.00GHz
Stepping: 3
CPU MHz: 800.000
CPU max MHz: 4200.0000
CPU min MHz: 800.0000
BogoMIPS: 8016.72
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 8192K
NUMA node0 CPU(s): 0-7
**Laptop**
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 69
Model name: Intel(R) Core(TM) i5-4210U CPU @ 1.70GHz
Stepping: 1
CPU MHz: 1694.531
CPU max MHz: 2700.0000
CPU min MHz: 800.0000
BogoMIPS: 4788.93
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 3072K
NUMA node0 CPU(s): 0-3
```
## 前置作業
### Dual system
系統方面,我使用 ubuntu 16.04.1 LTS
因為半年前換電腦時就先灌好雙系統了
所以直接沿用
```shell
rayleigh@rayleigh-System-Product-Name:~$lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description: Ubuntu 16.04.1 LTS
Release: 16.04
Codename: xenial
```
### Vim 編輯器
大一的時候還覺得很難用
不過現在學了一些基本修改及安裝插件
直接變成 coding 神器阿XD
感謝老師及助教提供的資料
這裡有個小工具能夠改變語法顏色
```shell
Plugin 'octol/vim-cpp-enhanced-highlight'
```
可以修改一些基本語法的顏色和字體
```shell
hi Character cterm=bold ctermfg=DarkRed ctermbg=NONE
hi SpecialChar cterm=bold ctermfg=DarkGreen ctermbg=NONE
hi Function cterm=bold ctermfg=DarkBlue
```
參考資料：
[syntax highlight plugin](https://github.com/octol/vim-cpp-enhanced-highlight)
[vim syntax](http://vimdoc.sourceforge.net/htmldoc/syntax.html)
### Perf
linux 相當強大的效能統計軟體
稍微看一下使用的說明
```shell
$ perf --help
usage: perf [--version] [--help] [OPTIONS] COMMAND [ARGS]
The most commonly used perf commands are:
...
list List all symbolic event types
...
stat Run a command and gather performance counter statistics
...
top System profiling tool.
...
```
這次作業主要是使用 stat
```shell
$ perf stat --help
NAME
perf-stat - Run a command and gather performance counter statistics
SYNOPSIS
perf stat [-e <EVENT> | --event=EVENT] [-a] <command>
perf stat [-e <EVENT> | --event=EVENT] [-a] — <command> [<options>]
.
.
*-e, --event=
Select the PMU event.
-p, --pid=<pid>
stat events on existing process id (comma separated list)
-a, --all-cpus
system-wide collection from all CPUs
*-d, --detailed
print more detailed statistics, can be specified up to 3 times
-d: detailed events, L1 and LLC data cache
-d -d: more detailed events, dTLB and iTLB events
-d -d -d: very detailed events, adding prefetch events
*-r, --repeat=<n>
repeat command and print average + stddev (max: 100). 0 means forever.
-o file, --output file
Print the output into the designated file.
--append
Append to the output file designated with the -o option. Ignored if -o is not specified.
.
.
```
藉由 perf list 可以得知有哪些 PMU event
參考資料
[perf 原理和實務](https://hackmd.io/s/B11109rdg#)
[Perf -- Linux下的系统性能調優工具](https://www.ibm.com/developerworks/cn/linux/l-cn-perf1/)
### gnuplot
>請在中英文字間加上空白區隔
>[name=課程助教][color=red]
>好的, 謝謝助教
參考資料
[gnuplot 語法解說和示範](https://hackmd.io/s/Skwp-alOg#)
### cache
實作前,不得不先了解 cache 這東西
cache 算是一個 cpu 專屬的記憶體
通常取資料時會先從 cache 裡找
這是為了提昇整體運算的效能（畢竟 ram 現在還是慢 cpu 很多）
藉由下列指令,可以得知使用者目前電腦 cache 的資訊
```shell
$ lscpu
$ sudo lshw -C memory
$ x86info -c(須先安裝x86info)
$ sudo dmidecode -t cache
```
或是開啟 /proc/cpuinfo 檔案,也可以看到該電腦 cpu 的資訊
```shell
$ cat /proc/cpuinfo | grep cache
cache size : 3072 KB
cache_alignment : 64
cache size : 3072 KB
cache_alignment : 64
cache size : 3072 KB
cache_alignment : 64
cache size : 3072 KB
cache_alignment : 64
(有幾個核心就會顯示幾次)
```
參考資料
[cache原理和實驗](https://hackmd.io/s/S14L26-_l#)
[關於CPU Cache -- 程序猿需要知道的那些事](http://cenalulu.github.io/linux/all-about-cpu-cache/)
[Stackoverflow](http://stackoverflow.com/questions/5401464/finding-the-cache-block-size) and [stackexchange](http://unix.stackexchange.com/questions/167038/is-there-any-way-to-know-the-size-of-l1-l2-l3-cache-and-ram-in-linux)
## 開發過程
### **1. 原始版**
先執行原始程式碼,來看看他的效能如何
```shell
$ perf stat --repeat 100 -e cache-misses,cache-references,instructions,cycles ./phonebook_orig
Performance counter stats for './phonebook_orig' (100 runs):
126,1316 cache-misses # 90.600 % of all cache refs ( +- 0.23% )
139,2178 cache-references ( +- 0.16% )
2,6076,3251 instructions # 1.45 insns per cycle ( +- 0.02% )
1,7966,5430 cycles ( +- 0.11% )
0.068607172 seconds time elapsed ( +- 0.43% )
```
cache miss 高達90%
目前猜測原因有兩個：
1. **資料量大使用量卻少**
還有一個,正常的phonebook可能本身就有給予多種資料
但在原始碼裡卻只用lastName找資料
其他資料浪費的空間
也可能是導致cache-miss過高的原因
2. **資料儲存方式**
看一下原始碼,資料是以linked list直接串接成一列
要從這麼大的資料鏈(我猜是word.txt : 約350000筆)裡找一筆相符的
可能就是導致cache-miss過高的原因
### **2. 測試一: 削減資料大小**
先從1開始下手
把 entry 裡除了 lastName 以外的資料另外創一個type
名為 otherData
並在 entry 裡宣告一個指向 otherData的pointer
有需要在分配記憶體給它儲存資料
>就直接把兩個完整的 structure 貼上來吧!
>[name=課程助教][color=red]
```c=
...
typedef struct __PHONE_BOOK_OTHER_DATA {
//put data expect lastName
} otherData;
typedef struct __PHONE_BOOK_ENTRY {
...
otherData *data;
...
} entry
...
```
測試結果：
**Cache-miss:**
```shell
Performance counter stats for './phonebook_opt' (100 runs):
12,4501 cache-misses # 28.264 % of all cache refs ( +- 0.59% )
44,0500 cache-references ( +- 0.46% )
2,4398,0290 instructions # 1.94 insns per cycle ( +- 0.02% )
1,2562,6360 cycles ( +- 0.19% )
0.048758786 seconds time elapsed ( +- 0.30% )
```
結果意外地理想,大幅降低 cache-miss ,搜尋及插入資料的時間也變少了。
但是這只算是**治標不治本**
假設每筆資料都要填入其他相關資訊(e.g. 姓氏)
問題就會回到原點
這邊我讓每筆資料新增一塊空的 otherData
```c=
phonebook_opt.c:
...
e->data = (otherData *) malloc(sizeof(otherData));
strcpy(e->lastName, lastName);
...
```
測試結果：
```shell
Performance counter stats for './phonebook_opt' (100 runs):
151,8995 cache-misses # 94.176 % of all cache refs ( +- 0.07% )
161,2927 cache-references ( +- 0.09% )
3,4121,7546 instructions # 1.46 insns per cycle ( +- 0.02% )
2,3358,1072 cycles ( +- 0.13% )
0.090065262 seconds time elapsed ( +- 0.20% )
```
可以看到 cache-miss 又增加了
還比原始版本還高
執行時間也比原本的長
可見此方法不怎麼可行
### 3. 測試二 ： 嘗試使用Hash table
第二次,我使用 Hash table 來儲存所有資料
建立一個 entry type 的 Hash table, 大小大概是350000
利用每個 lastName 所對應的 hash value
對 table size 取餘數來當作索引值
```c=
...
hash_index = hash_function(entry->lastName);
put entry into table[hash_index];
...
```
但不見得每筆資料的 hash value 都是獨立的
因此當遇到 hash collision (兩個變數的 hash value 相同)時
就以 linked list 的方式串接（如下圖所示）
然而 Hash function 有很多種
這邊就來測試以下六種 Hash function
1. **DJB2**
測試結果：
cache-misses:
```shell
Performance counter stats for './phonebook_hash_opt' (100 runs):
254,7001 cache-misses # 58.420 % of all cache refs ( +- 0.22% )
435,9795 cache-references ( +- 0.24% )
2,2879,0814 instructions # 1.18 insns per cycle ( +- 0.04% )
1,9360,8219 cycles ( +- 0.34% )
0.053086737 seconds time elapsed ( +- 0.33% )
```
2. **BKDR**
測試結果：
cache-misses:
```shell
Performance counter stats for './phonebook_hash_opt' (100 runs):
255,0878 cache-misses # 59.273 % of all cache refs ( +- 0.30% )
430,3633 cache-references ( +- 0.26% )
2,3726,8911 instructions # 1.20 insns per cycle ( +- 0.04% )
1,9828,2803 cycles ( +- 0.36% )
0.054561474 seconds time elapsed ( +- 0.35% )
```
3. **AP**
測試結果：
cache-misses:
```shell
Performance counter stats for './phonebook_hash_opt' (100 runs):
251,9352 cache-misses # 58.323 % of all cache refs ( +- 0.29% )
431,9651 cache-references ( +- 0.37% )
2,5446,4326 instructions # 1.26 insns per cycle ( +- 0.04% )
2,0218,2336 cycles ( +- 0.43% )
0.055191749 seconds time elapsed ( +- 0.39% )
```
4. **JS**
測試結果:
cache-misses:
```shell
Performance counter stats for './phonebook_hash_opt' (100 runs):
247,0955 cache-misses # 56.622 % of all cache refs ( +- 0.23% )
436,3923 cache-references ( +- 0.21% )
2,3718,4584 instructions # 1.21 insns per cycle ( +- 0.04% )
1,9667,2118 cycles ( +- 0.28% )
0.054124701 seconds time elapsed ( +- 0.32% )
```
5. **RS**
測試結果:
cache-misses:
```shell
Performance counter stats for './phonebook_hash_opt' (100 runs):
215,5988 cache-misses # 52.947 % of all cache refs ( +- 0.26% )
407,1983 cache-references ( +- 0.75% )
2,3803,1769 instructions # 1.27 insns per cycle ( +- 0.04% )
1,8734,7593 cycles ( +- 0.28% )
0.049808275 seconds time elapsed ( +- 0.37% )
```
6. **SDB**
測試結果:
cache-misses:
```shell
Performance counter stats for './phonebook_hash_opt' (100 runs):
242,4593 cache-misses # 57.131 % of all cache refs ( +- 0.26% )
424,3887 cache-references ( +- 0.25% )
2,3704,8982 instructions # 1.22 insns per cycle ( +- 0.04% )
1,9386,2498 cycles ( +- 0.27% )
0.053005389 seconds time elapsed ( +- 0.28% )
```
比較圖
---
- time:
- cache-miss:
## 問題討論 ： 本例選用的 dataset (也就是輸入電話簿的姓名) 是否存在問題？
- 有代表性嗎？跟真實英文姓氏差異大嗎？
就現實情況來講差異還蠻大的, 許多名字根本沒有母音（我不知道如何發音）, 或是只含一種字母（ aaaaaa ）,例如下面這些名字是從 word.txt 裡面擷取出來的:
```shell
bbbb
bbbbb
bbbbbb
bbbbbbb
bbbbbbbb
bbbbe
bbbbut
bbbppsll
bbcc
```
利用join指令去比對 words.txt 及 all-names.txt 兩個檔案
發現共有的名字有 <font color="red">14536</font> 個, 重疊的比例大概一半( 7110 個名字已重複)
不過如果這是一個人的別名或一個電話號碼的標籤, 就還說的過去
再加上 words.txt 幾乎沒有重複使用的名字, 雖然測資只有 35 萬, 但重複的比例也太低, 這裡有個網站名叫 name statistics, 統計了美國最多人取的名字, 像 Smith 的比例足足有 1.006%, 意思是 3 億多的美國人中, 有百萬多個名為 Smith, 對比到 words.txt, 可見相似率相對的低
[name statistics](http://www.namestatistics.com/)
- 資料難道「數大就是美」嗎？
就如同剛剛提到的, words.txt 雖然有35萬資料, 卻沒有涵蓋住資料量只有 16000 的 all-names.txt, 可見資料不僅要大, 還要有意義, 才能算是好的資料, 如何才是有意義的資料, 會在下個問題來探討
- 如果我們要建立符合真實電話簿情境的輸入，該怎麼作？
或許可以沿用 words.txt, 將其定位為"電話簿的別名", 並在同一列中加入其他屬性的資料, 像是地址, 信箱, 或是現代常用的 facebook, line ID 等等, 增加資料的可信度,
參考資料：
- [hash function 觀念和實務](https://hackmd.io/s/HJln3jU_e#)
- [哈希表之bkdrhash算法解析及擴展](http://blog.csdn.net/wanglx_/article/details/40400693)
- [字符串哈希函数](http://blog.csdn.net/wanglx_/article/details/40300363)
- [HackMD Command](https://hackmd.io/s/S1vAcMjFe#)
>同學您好，助教這邊沒有您的個人資料，請正確填寫課程表單[name=課程助教][color=#c04932]
>助教抱歉,已填寫[name=戴子祐]
Sign in with Wallet
Connect another wallet