# 2017q1 Homework1 (phonebook)
contributed by <`xdennis`>
### Reviewed by `baimao8437`
* 第二個 [commit](https://github.com/xdennisx/phonebook/commit/3fec208661565e81962eb1f5219b5cc119958876) 應該合併至第一個 [commit](https://github.com/xdennisx/phonebook/commit/bc1178c6fe7eca8f80aea27437754d2e852090cf)，否則第二個 commit message 跟修改內容其實沒什麼相關。善用 `git rebase -i` 或 `git commit --amend` 修改歷史。
* 最後一個 commit message: `Use another method to optimize performance:hash` 注意冒號後面應該有空白，以及該 commit 詳細說明部份的換行位置需要多多注意。
---
## 開發環境
```shell
dennis@dennis-X550CC:~$ lscpu
Architecture: x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
每核心執行緒數：2
每通訊端核心數：2
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 58
Model name: Intel(R) Core(TM) i5-3337U CPU @ 1.80GHz
製程： 9
CPU MHz： 2481.257
CPU max MHz: 2700.0000
CPU min MHz: 800.0000
BogoMIPS: 3591.98
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 3072K
NUMA node0 CPU(s): 0-3
```
## 前置作業
### Perf
測試 Perf：執行[Perf教學文](https://hackmd.io/IYDgzARgjArGMFoIDYDsAGBAWATD5SAxjJsjBDHgCbo5RQ5A)裡面的範例程式，因為要在程式結束之前就要執行 `perf top -p $!`，所以我把他打在同一行，`$!`為上一個 pid
```shell
$ ./example & perf top -p $!
```
結果也與範例類似：
不過有時候會卡在這個畫面，我也不知道為何：
## phonebook_original
phonebook_orig.c 就是用最直覺的方式從頭找到尾：
```c=
entry *findName(char lastname[], entry *pHead)
{
while (pHead != NULL) {
if (strcasecmp(lastname, pHead->lastName) == 0)
return pHead;
pHead = pHead->pNext;
}
return NULL;
}
```
先清空 cache
```shell
$ echo 1 | sudo tee /proc/sys/vm/drop_caches
```
執行後：
```shell
dennis@dennis-X550CC:~/phonebook$ ./phonebook_orig
size of entry : 136 bytes
execution time of append() : 0.053898 sec
execution time of findName() : 0.007335 sec
```
cache-miss 頗高:confused:
```shell
Performance counter stats for './phonebook_orig' (100 runs):
1,949,569 cache-misses # 92.209 % of all cache refs ( +- 0.37% )
2,114,300 cache-references ( +- 0.36% )
260,796,586 instructions # 1.31 insns per cycle ( +- 0.02% )
198,662,796 cycles ( +- 0.53% )
0.079193527 seconds time elapsed ( +- 0.67% )
```
## phonebook_optimal
### 改進方法 1：更改資料結構
- 精簡 entry 的內容，因為從頭到尾只有用到 **lastname**，所以我就只留 **lastname**，剩下的丟給 `__OTHER_PHONE_BOOK_ENTRY`
```clike=
typedef struct __OTHER_PHONE_BOOK_ENTRY {
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;
} other_entry;
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];
*/
other_entry *otherInfomation;
struct __PHONE_BOOK_ENTRY *pNext;
} entry;
```
cache-miss 貌似有下降
```shell=
Performance counter stats for './phonebook_opt' (100 runs):
385,069 cache-misses # 68.025 % of all cache refs ( +- 0.18% )
566,068 cache-references ( +- 0.44% )
244,050,187 instructions # 1.70 insns per cycle ( +- 0.02% )
143,360,213 cycles ( +- 0.43% )
0.057411116 seconds time elapsed ( +- 0.55% )
```
:exclamation: `make plot` 之前一定要把 **phonebook_opt.h** 的`#define OPT 1` 前面的斜線拿掉
所花的時間也有下降
### 改進方法2：Hash Table
[參考資料](http://www.cnblogs.com/liuliuliu/p/3966851.html)
35 萬筆資料是相當大的資料量，因此上網找建立 Hash Table 的方法，使用 BKDRHash function
> 決定先寫完後面的作業再回來繼續
>建議按照作業順序完成作業，因為每份作業之間是設計過、有關聯的，請循序漸進，切勿囫圇吞棗。[name=課程助教][color=#f93452]
網路上實作大量字典的方法推荐 BKDR Hash，其中的 hash function 大致上長這樣：
```clike=
unsigned int BKDRHash(char* key)
{
unsigned int seed = 31;
unsigned int hash = 0;
while (*key) {
hash = hash * seed + (*key++);
}
return hash & 0x7FFFFFFF;
}
```
再來就是 Hash Table 的大小，因為字點量接近 35 萬筆，所以找了一個萬開頭且是質數的數字，42737
結果 cache-miss 真的又下降惹
```shell
Performance counter stats for './phonebook_hash' (100 runs):
671,036 cache-misses # 55.205 % of all cache refs ( +- 1.08% )
1,215,532 cache-references ( +- 0.95% )
241,708,346 instructions # 1.29 insns per cycle ( +- 0.02% )
186,926,365 cycles ( +- 1.11% )
0.075120741 seconds time elapsed ( +- 1.34% )
```
而且 `findName` 時間也趨近於 0
查找的時間符合預期，而 `append()` 因為再差入時需要額外運算，所以再時間上也有所上升
## 回答問題：
- 本例選用的 dataset (也就是輸入電話簿的姓名) 是否存在問題？
- 有代表性嗎？跟真實英文姓氏差異大嗎？
> 裏面出現很多應該不會式真實的英文姓名，例如：`aaaaaaaa`、
`zzzzzzzz`
- 資料難道「數大就是美」嗎？
> 當然不是囉，就如同上一題提到的，我們需要的是**有用到**的資訊，不是說把所有有可能的資料都放進來，這樣只會增加 `append` 跟 `findName` 的時間而已
- 如果我們要建立符合真實電話簿情境的輸入，該怎麼作？
> 尋找答案中...想利用下面真實的網站測看看能不能找到什麼
## Reference
- [Progarmming Small](https://hackmd.io/s/HkO2ZpIYe)
- [vitm9907](https://hackmd.io/s/r1YyTRqFe)
- [ktvexe](https://hackmd.io/MYZgnCwGbALAtGArCADPWAjAhgRnpgOwAmY8UAbMJqsLgBxb2ZA=)
- [美國真實電話簿查詢](http://www.whitepages.com/)
Sign in with Wallet
Connect another wallet