# 2017q3 Homework1 (phonebook)
contributed by <`yuan922`>
## Ubuntu執行環境
輸入指令列出環境條件:
```shell
yuan@yuan-OptiPlex-7020:~$ lscpu
```
```shell
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
型號： 60
Model name: Intel(R) Core(TM) i5-4590 CPU @ 3.30GHz
製程： 3
CPU MHz： 3390.435
CPU max MHz: 3700.0000
CPU min MHz: 800.0000
BogoMIPS: 6584.89
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 6144K
NUMA node0 CPU(s): 0-3
```
## 權限修改
```shell
yuan@yuan-OptiPlex-7020:~$ sudo sh -c " echo 0 > /proc/sys/kernel/kptr_restrict"
yuan@yuan-OptiPlex-7020:~$ cat /proc/sys/kernel/perf_event_paranoid
1
```
## 執行phonebook_orig
```shell
yuan@yuan-OptiPlex-7020:~/phonebook$ ./phonebook_orig
```
```shell
size of entry : 136 bytes
execution time of append() : 0.036134 sec
execution time of findName() : 0.005949 sec
```
## 察看cache miss
先把phonebook_orig複製到phone_opt察看效能
```shell
Performance counter stats for './phonebook_opt' (100 runs):
1,085,488 cache-misses # 83.938 % of all cache refs ( +- 0.23% )
1,293,209 cache-references ( +- 0.14% )
260,626,303 instructions # 1.25 insn per cycle ( +- 0.02% )
208,589,047 cycles ( +- 0.37% )
0.058856944 seconds time elapsed ( +- 0.50% )
```
得知catch—misses高達83%
## 縮減struct大小
參考[maskashura同學](https://hackmd.io/s/SkA9HZOj-)跟[tina0405同學](https://hackmd.io/GYFgpghgrAHDEFoAmUBsSHgMwCMERAGMBOBQgdlQEYAGGKnVYiGIA)的共筆，
因為findName這個函式只針對lastName做搜尋，所以剩下的資料都先放到另一個struct來減少大小。
```
$ make cache-test
```
**phonebook_orig**
```clike=
/* original version */
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;
```
```shell
Performance counter stats for './phonebook_orig' (100 runs):
1,059,506 cache-misses # 83.015 % of all cache refs ( +- 0.23% )
1,276,287 cache-references ( +- 0.14% )
260,622,858 instructions # 1.25 insn per cycle ( +- 0.02% )
207,843,315 cycles ( +- 0.13% )
0.058152146 seconds time elapsed ( +- 0.18% )
```
**phonenbook_opt**
```clike=
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
struct __PHONE_BOOK_ENTRY *pNext;
struct __PHONE_BOOK_REMAIN *others;
} entry;
typedef struct __PHONE_BOOK_REMAIN {
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];
} remain;
```
```shell
Performance counter stats for './phonebook_opt' (100 runs):
168,899 cache-misses # 43.901 % of all cache refs ( +- 0.52% )
384,724 cache-references ( +- 0.27% )
242,944,744 instructions # 1.81 insn per cycle ( +- 0.02% )
134,185,951 cycles ( +- 0.22% )
0.037666468 seconds time elapsed ( +- 0.31% )
```
**結果**
* entry size從136bytes變成32bytes
* append時間有下降
* cache-miss下降了40%
```shell
$ make plot
```
* **append()** 跟 **findName()** 的時間都有縮短
Google Drive
Gist
Clipboard
Sign in with Wallet
