# 2017q1 Homework1 (phonebook)
contributed by < `laochanlam` >
###### tags: `laochanlam`
### Reviewed by `yanglin`
- 實驗裡面提到預先 allocate 350000 筆 entry 的資料，這個數字是如何得來的？是從輸入資料的規模得到的嗎？那在現實狀況中，要如何決定 memory pool 的大小？
- [commit 75f65b8](https://github.com/laochanlam/phonebook/commit/75f65b8216c577465742db8d166f044d1e5a0b69)， commit message 的長度超過一行72個字元，而且有些冗余的情報。
- 只有使用一種 hash function 做測試，是否能夠比較不同種 hash function 的 performance？
### Reviewed by `Cayonliow`
* 你所使用的 hash function 的參考資料是跟我一樣的， 裏頭的 DJBHash 會更快， 利用不同方式的乘法的復雜度來達到更快的速度， 可以看看[我的共筆](https://hackmd.io/s/r1i2_OhFx#%E5%84%AA%E5%8C%96%E7%89%88%E6%9C%AC)
* 沒有提到 如何選取跟制定 hash table 的大小， 如果太大或太小又會怎樣
## 開發環境
- Ubuntu 16.10 (64bit)
>請列出硬體相關資訊，如：cache, memory
>[name=課程助教][color=red]
>已補上，感謝提醒！
>[name=laochanlam][color=blue]
```
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: 61
Model name: Intel(R) Core(TM) i7-5500U CPU @ 2.40GHz
Stepping: 4
CPU MHz: 2400.878
CPU max MHz: 3000.0000
CPU min MHz: 500.0000
BogoMIPS: 4788.90
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 4096K
NUMA node0 CPU(s): 0-3
```
## 相關連結
- [2017 年春季作業說明](https://hackmd.io/s/Bk-1zqIte#)
- [2017q1 Homework1 (作業區)](https://hackmd.io/MYJjEYGZITgWgOwCMAmw4BYYwAxyQQKxwBmwGOkAHMDeEgGxA===?view)
- [B01: phonebook作業要求](https://hackmd.io/s/rJYD4UPKe#b01-phonebook)
- [phonebook Github連結 ( laochanlam ) ](https://github.com/laochanlam/phonebook)
- [作業解說 video](https://www.youtube.com/watch?v=ZICRLKf_bVw)
- [課程進度與開放資源 Wiki](http://wiki.csie.ncku.edu.tw/sysprog/schedule)
## Phonebook 開發紀錄
### Optimize 方案 1： 縮小 entry 的 size
理解完整個專案後，終於開始動工了！
先是依照老師的提示把 entry 的 size 縮小，把除lastName以外的資料都存到新的 struct 中，並在原來的 struct 中建立一個指向 detail 的 pointer 。
#### 原來的版本
```C
typedef struct __PHONE_BOOK_ENTRY {
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 __PHONE_BOOK_ENTRY *pNext;
} entry;
```
使用Perf分析cache-misses的情況，原來的大約是81%。
```
Performance counter stats for './phonebook_orig' (100 runs):
3,430,005 cache-misses # 81.729 % of all cache refs ( +- 0.03% )
4,196,826 cache-references ( +- 0.19% )
261,712,845 instructions # 1.34 insn per cycle ( +- 0.02% )
194,998,572 cycles ( +- 0.26% )
0.066929775 seconds time elapsed ( +- 0.31% )
```
#### 優化後的版本
```C
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];
struct __PHONE_BOOK_ENTRY *pNext;
struct __PHONE_BOOK_DETAIL *pDetail;
} entry;
```
cache-miss變成69％了！！
```
Performance counter stats for './phonebook_opt' (100 runs):
1,223,454 cache-misses # 69.446 % of all cache refs ( +- 0.25% )
1,761,727 cache-references ( +- 0.99% )
242,934,591 instructions # 1.74 insn per cycle ( +- 0.02% )
139,951,145 cycles ( +- 0.91% )
0.048685568 seconds time elapsed ( +- 1.07% )
```
附個小圖：
### Optimize 方案 2： 利用 Hash function 儲存資料
接下來要進行 Hash 的優化，在參考完[各种字符串Hash函数比较](https://www.byvoid.com/zhs/blog/string-hash-compare)一文及學長姐們的共筆後，決定使用 BKDRHash 來進行本次的優化！
<br>
下方是從[各种字符串Hash函数比较](https://www.byvoid.com/zhs/blog/string-hash-compare)中抓到的 **BKDRHash function**。
```C
unsigned int BKDRHash(char *str)
{
unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
unsigned int hash = 0;
while (*str)
{
hash = hash * seed + (*str++);
}
return (hash & 0x7FFFFFFF);
}
```
>其中```return (hash & 0x7FFFFFFF)```此處有個不解，查資料時有查到說 ```& 0x7FFFFFFF``` 是為了讓其成為 positive integer ，但既然這個 Hash function 的 return type 已經是 unsigned int ，為何還要 ```& 0x7FFFFFFF``` 而不是 ```& 0xFFFFFFFF``` 呢？
>[name=laochanlam][color=blue]
:::danger
盡信書不如無書，你為何不做實驗並分析呢？
認真看 hash value 的分佈 --jserv
:::
<br>
完成了！
要注意的地方是可能會發生碰撞，而且 Table Size的選取也十分重要。
附個小圖:
做了 Hash 的優化後 findName() 的時間超級快，不過由於在 Hash table 中採用 Link list 來防止碰撞的緣故，append（）的時間加長了不少。
:::danger
提出具體縮減 `append()` 時間成本的機制 --jserv
:::
>好
>[name=laochanlam][color=blue]
```
416,554 cache-misses # 41.136 % of all cache refs ( +- 0.51% )
1,012,639 cache-references ( +- 0.50% )
239,848,481 instructions # 1.58 insn per cycle ( +- 0.02% )
152,120,552 cycles ( +- 0.28% )
0.051797760 seconds time elapsed ( +- 0.30% )
```
Cache miss 又減少了！
### Optimize 方案 3： 利用 memory pool 改善 append() 時間
在參考 [ierosodin 的共筆](https://hackmd.io/s/SJ4uqs9Yx#)後,有提到可以用 memory pool 的方法改善 append() 的效能，所以來嘗試一下，先分配一個 ```sizeof( 350000 * entry )``` 大小的連續空間當作 memory pool ,在需要時才向 pool 申請空間。
效能分析附圖：
雖說 append() 的時筆是減少了，可是減少的程度遠遠不及[ierosodin 的共筆](https://hackmd.io/s/SJ4uqs9Yx#)中來得多，經過思考後可能是 hash table size 的取值不當導致的，所以嘗試改善 table size 的大小。
<br>
經過一番沒有進展的改善後...才發現我有一個地方少寫一行程式碼...
改回來後：
而且 cache miss 也減少了
```
Performance counter stats for './phonebook_opt_hash_pool' (100 runs):
192,884 cache-misses # 20.701 % of all cache refs ( +- 1.90% )
931,771 cache-references ( +- 0.96% )
160,539,514 instructions # 1.47 insn per cycle ( +- 0.04% )
109,119,512 cycles ( +- 0.71% )
0.038024759 seconds time elapsed ( +- 0.84% )
```
減到 20% 。
<br>
~~總算老懷安慰。~~
### 回答問題環節：
本例選用的 dataset (也就是輸入電話簿的姓名) 是否存在問題？
<br>
### 1. 有代表性嗎？跟真實英文姓氏差異大嗎？
我認為代表性不強，畢竟這個世界上英文姓氏 X Y 作開首的遠遠比其他字母來得少，在搜索算法的資源分配可依據字母出現的頻率作調整；
```
Initial Percentage
a 5.857
b 4.183
c 6.501
d 6.664
e 4.154
f 1.569
g 2.937
h 2.028
i 0.661
j 11.961
k 3.709
l 5.087
m 9.074
n 1.652
o 0.407
p 2.821
q 0.032
r 7.151
s 5.583
t 3.795
u 0.020
v 1.347
w 2.477
x 0.010
y 0.205
z 0.109
```
Source from : [Answers](http://answers.google.com/answers/threadview/id/347668.html)
而且本例子中並沒有考慮名字重覆的情況，像是 1990 年代美國最常見姓氏的比例：
```
Name %
1. Smith 1.006
2. Johnson 0.810
3. Williams 0.699
4. Jones 0.621
5. Brown 0.621
6. Davis 0.480
7. Miller 0.424
8. Wilson 0.339
9. Moore 0.312
10. Taylor 0.311
```
Source from : [Most Common Surnames in the United States 1990](http://surnames.behindthename.com/top/lists/united-states/1990)
但是在現實世界中這情況絕不罕有。
### 2. 資料難道「數大就是美」嗎？
### 3. 如果我們要建立符合真實電話簿情境的輸入，該怎麼作？
- 針對字母頻率不同的情況，我們可以在資料結構或查詢算法中，對字母搜尋及儲存的優先順序作調整，把更多的儲存空間讓給 ```a``` ```o``` 等等常見的字母，提升整體效能。
- 針對姓名相同的情況，我們可以給予多項搜尋資訊的輸入，或是二次搜索的回饋等功能，使查詢者能在"芸芸眾生"中找到要尋找的目標。
---
## 補充知識
- [x] Cache
- [x] Perf
- [x] gnuplot
- [x] astyle
- [x] Makefile
- [x] Hash function
---
## Cache
若要查找的 memory location 在 cache 中， CPU 從 cache 中讀取或寫入數據，就是 **cache hit** ，反之若要查找的 memory location 不在 cache 中，就為 **cache miss** 。
#### 參考及引用資料
[cache 原理和實驗](https://hackmd.io/s/S14L26-_l#)
[cache entry相關資料](http://www.cnblogs.com/miaoyong/p/3416320.html)
---
## 效能分析工具: Perf
安裝完成後我是先把路徑於 `/proc/sys/kernel/perf_event_paranoid` 的值修改掉，不然每次都要sudo很麻煩。
> kernel.perf_event_paranoid 是用來決定你在沒有 root 權限下 (Normal User) 使用 perf 。
> * `2` : 不允許任何量測。但部份用來查看或分析已存在的紀錄的指令仍可使用，如 perf ls、perf report、perf timechart、 perf trace。
> * `1` : 不允許 CPU events data。但可以使用 perf stat、perf record 並取得 Kernel profiling data。
> * `0` : 不允許 raw tracepoint access。但可以使用 perf stat、perf record 並取得 CPU events data。
> * `-1`: 權限全開。
較常用的指令們
- `perf top`
- `perf stat`
- `perf record`
- `perf report`
#### 參考及引用資料
[perf 原理和實務](https://hackmd.io/s/B11109rdg#)
---
## 製圖工具: gnuplot
- 繪圖 ```$ gnuplot [Script]```
- 查看圖片 ```$ eog [jpg/png...]```
更多用法參詳[這裡](https://hackmd.io/s/Skwp-alOg)
#### 參考及引用資料
[gnuplot 語法解說和示範](https://hackmd.io/s/Skwp-alOg)
[gnuplot 读取逗号分隔的数据文件 ](http://blog.csdn.net/liyuanbhu/article/details/8516417)
---
## 程式碼格式化工具: astyle
先來看一下本次作業所要求的規範
```
$ astyle --style=kr --indent=spaces=4 --indent-switches --suffix=none *.[ch]
```
- ```--style=kr``` 用K&R的風格進行編程
- ```--indent=spaces=4``` 四個空格
- ```--indent-switches``` 關於Case的縮排
> Indent 'switch' blocks, so that the inner 'case XXX:'
headers are indented in relation to the switch block.
- ```--suffix=none``` 不保存原始文件
- ``` *.[ch]``` 所有的.c或.h檔
#### 參考及引用資料
[Astyle：代码格式化工具简明指南](http://blog.csdn.net/xiaotao2004/article/details/1560538)
[astyle格式化代码](http://gaylord.iteye.com/blog/2090616)
---
## Makefile
#### 參考及引用資料
[Makefile 語法和示範](https://hackmd.io/s/SySTMXPvl)
---
## Hash function
#### 參考及引用資料
[hash function 觀念和實務](https://hackmd.io/s/HJln3jU_e)
[各种字符串Hash函数比较](https://www.byvoid.com/zhs/blog/string-hash-compare)
Sign in with Wallet
Connect another wallet