# 2017q3 Homework1 (phonebook)
contributed by < `maskashura` >
## Perf 設定筆記
#### kernel.perf_event_paranoid權限設定:
在開始執行效能測試前,先注意一些設定權限是否打開:
> kernel.perf_event_paranoid 是用來決定你在沒有 root 權限下 (Normal User) 使用 perf 時，你可以取得哪些 event data。預設值是 1 ，你可以輸入
> ==cat /proc/sys/kernel/perf_event_paranoid==
>
> 一共有四種權限值:
>
> * 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: 權限全開。
將kernel.perf_event_paranoid權限設成1
==sudo sh -c " echo 1 > /proc/sys/kernel/perf_event_paranoid"==
#### 取消kernel pointer 禁用:
如欲檢測 cache miss event ，需要先取消 kernel pointer 的禁用。
==sudo sh -c " echo 0 > /proc/sys/kernel/kptr_restrict"==
#### perf stat指令說明:
==perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./filename==
--repeat <n>或是-r <n> 可以重複執行 n 次該程序，並顯示每個 event 的變化區間。
cache-misses,cache-references和 instructions,cycles類似這種成對的 event，若同時出現 perf 會很貼心幫你計算比例。
#### perf top指令說明:
最後要觀察其他 event ( 預設 cycles ) 和指定取樣頻率 ( 預設每秒4000次 ) :
==perf top -e cache-misses -c 5000==
* [perf 原理和實務 (共筆)](https://hackmd.io/s/B11109rdg)
----
## GitHub設定
### 綁訂機器的 SSH key
產生 SSH 登入用的金鑰，可以使用 ssh-keygen 這個指令。在建立金鑰之前，要先建立 ~/.ssh 這個目錄，並設定正確的權限：
==mkdir -p ~/.ssh==
==chmod 700 ~/.ssh==
然後以 ssh-keygen 產生金鑰：
==ssh-keygen -t rsa -C "your_email@example.com"==
>Your identification has been saved in /root/.ssh/id_rsa.
>Your public key has been saved in /root/.ssh/id_rsa.pub.
查看ssh key
==cat ~/root/.ssh/id_rsa.pub==
將ssh key加入到 Github 網站,驗證有沒有綁定
==ssh -T git@github.com==
會得到下列訊息表示成功
>Hi maskashura! You've successfully authenticated, but GitHub does not provide shell access.
### GitHub指令
#### 同步
將本機 repository 和遠端 Github repository 同步
==git remote add origin git@github.com:your_account/your_repository.git
git push -u origin master==
再輸入
==git push==
或參考git指引:
```shell
echo "# system.software2017" >> README.md
git init
git add README.md
git commit -m "first commit"
git remote add origin git@github.com:maskashura/system.software2017.git
git push -u origin master
```
#### clone
將遠端的 repository 複製一份到本機:
==git clone git@github.com:Username/repository.git==
如果沒有寫入權限 (Collaborators) 的話，因為這個專案是公開的，所以你還是可以用 Git 通訊協定 clone 下來：
==git clone git://github.com/Username/repository.git==
若因遭逢防火牆問題 (如成功大學校園環境)，請改用 HTTPS 通訊協定：
==git clone https://github.com/Username/repository.git==
#### Pull
從遠端更新
==git pull==
或
==git pull origin master==
#### Push
==git push==
或
==git push origin master==
參考資料
[GitHub 設定指引](http://wiki.csie.ncku.edu.tw/github)
[SSH 公開金鑰認證](https://blog.gtwang.org/linux/linux-ssh-public-key-authentication/)
----
## 取得電腦環境
**OS使用Lubuntu 17.04 , 64位元版本**
取得cache大小, 輸入 ==lscpu== 可得:
```shell
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: 42
Model name: Intel® Core™ i3-2350M CPU @ 2.30GHz
Stepping: 7
CPU MHz: 799.890
CPU max MHz: 2300.0000
CPU min MHz: 800.0000
BogoMIPS: 4589.87
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 3072K
NUMA node0 CPU(s): 0-3
```
----
## 實作驗證
由於不太熟悉整體效能測試流程，先參考了[0140454同學共筆](https://hackmd.io/EwMwhgDBDGBsYFoDsBGWAOBAWdSCsCAnCIQEYLAoRgAmApvHiAMylA==?view), 以其流程做修改測試
先記錄下修改前, 執行phonebook_orig結果
==./phonebook_orig==
```shell
size of entry : 136 bytes
execution time of append() : 0.070063 sec
execution time of findName() : 0.006372 sec
```
再執行==make cache-test==
make cache-test 內容:
```shell
cache-test: $(EXEC)
perf stat --repeat 100
-e cache-misses,cache-references,instructions,cycles
./phonebook_orig
perf stat --repeat 100
-e cache-misses,cache-references,instructions,cycles
```
執行 ==make cache-test== 後可得下列結果, 我們可看到 cache miss 高達91%
```shell
Performance counter stats for './phonebook_orig' (100 runs):
2,040,979 cache-misses # 91.415 % of all cache refs ( +- 0.06% )
2,232,662 cache-references ( +- 0.07% )
261,727,331 instructions # 1.33 insn per cycle ( +- 0.02% )
196,762,949 cycles ( +- 0.11% )
0.088329791 seconds time elapsed ( +- 0.26% )
```
執行 ==./phonebook_org ; sudo perf top -p $!== , 觀察程式中的效能瓶頸
*(利用"$!", 可取得前面執行的程序pid )*
```shell=
Samples: 89 of event 'cycles', Event count (approx.): 43058077
Overhead Shared Object Symbol ◆
26.59% phonebook_orig [.] findName ▒
9.27% libc-2.24.so [.] 0x000000000014d719 ▒
7.92% libc-2.24.so [.] 0x000000000014ecf8 ▒
7.18% libc-2.24.so [.] 0x000000000014ed06 ▒
6.04% libc-2.24.so [.] 0x000000000014ecfc ▒
4.85% libc-2.24.so [.] 0x000000000014ecf4 ▒
4.03% [kernel] [k] unmap_page_range ▒
3.27% libc-2.24.so [.] 0x000000000014d756 ▒
3.26% libc-2.24.so [.] 0x000000000014ecf0 ▒
3.03% libc-2.24.so [.] 0x000000000014d6e5 ▒
3.02% [kernel] [k] free_hot_cold_page ▒
3.00% [kernel] [k] release_pages ▒
2.12% libc-2.24.so [.] 0x000000000014d711 ▒
2.02% libc-2.24.so [.] 0x000000000014d742 ▒
2.02% [kernel] [k] free_pages_and_swap_cache ▒
1.99% [kernel] [k] free_pcppages_bulk ▒
1.86% phonebook_orig [.] append ▒
1.30% libc-2.24.so [.] 0x000000000014d6f7 ▒
1.06% libc-2.24.so [.] 0x000000000014ed0b ▒
1.01% libc-2.24.so [.] 0x000000000014d74e ▒
1.01% libc-2.24.so [.] 0x000000000014ed09
```
其中 findName 佔25% , 而 append 只佔1.8%
### 思考Cache miss
* 詳細閱讀 [programming small](https://hackmd.io/KYFgbAJgHMCcwFoBGBGVCTCkhBDAZrAAx5gDGsusATEQKwgi5A==?view) 裡頭的電話簿程式，研究降低 cache miss 的方法
打開 phonebook_orig.h ,我們可看到PHONE_BOOK_ENTRY的結構
```clike=
#define MAX_LAST_NAME_SIZE 16
/* 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;
```
而 phonebook.c 中則描述 findName() 及 append()
```clike=
/* original version */
entry *findName(char lastName[], entry *pHead)
{
while (pHead != NULL) {
if (strcasecmp(lastName, pHead->lastName) == 0)
return pHead;
pHead = pHead->pNext;
}
return NULL;
}
entry *append(char lastName[], entry *e)
{
/* allocate memory for the new entry and put lastName */
e->pNext = (entry *) malloc(sizeof(entry));
e = e->pNext;
strcpy(e->lastName, lastName);
e->pNext = NULL;
return e;
}
```
#### 1. 使用空間較小的 struct
以我的筆電為例L1 Cach 為 32KB = 32 * 1024 byte ，而 PhoneBook size = 136 bytes
以原先設計 ==32 * 1024 / (136*8) = 30.12 (大約只能存 30 筆左右)==
剛看到題目時很傻的要直接簡化structure大小(想針對phone,cell,zip...etc.,及一些固定內容的資料state & city 做簡化增加空間利用), 但題目再往下拉就發現走錯路了...且降低的cache miss少的可憐
故我採用[programming small](https://hackmd.io/KYFgbAJgHMCcwFoBGBGVCTCkhBDAZrAAx5gDGsusATEQKwgi5A==?view)中所說的，因為要求在於有沒有找到 last name , 而 struct 的其他資訊並無參考到，故我們可以先新增一個 struct 針對 last name , 再加上2指標 , 一指向擁有完整訊息的 struct "PHONE_BOOK_TOTAL" 另一指標為筆資料位址, 大小剛好是提示的==32byte, 2 * 1024 / (32 * 8) = 128 筆 , 可以降低cache miss==
新建struct "PHONEBOOK_LNAME" 並重新連結指標指向原 struct "PHONE_BOOK_ENTRY"
```clike=
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
struct __PHONE_BOOK_TOTAL *total_data;
struct __PHONE_BOOK_ENTRY *pNext;
} entry;
```
執行 ==make clean; make run_opt== 檢視修改後結果
```shell
size of entry : 32 bytes
execution time of append() : 0.053531 sec
execution time of findName() : 0.003749 sec
```
整理最佳化前後的時間比較如下:
| | Orig | Opt |
| -------------- | -------- | -------- |
| size of entry | 128 byte | 36 byte |
| append() | 0.070063 sec | 0.053531 sec |
| findName() | 0.006372 sec |0.003749 sec |
再經過修改後空間較小的 struct , findName() 時間從0.0063降為0.0037sec , 而append() 由0.638降至0.055sec
執行 ==make plot== 產生效能比較圖如下所示
再來檢查 cache miss 是否有改善, 輸入==make cache-test== , 可以發現cache miss從原本的91.745%降到了62.092% ，提昇了29%的效能
```shell
Performance counter stats for './phonebook_orig' (100 runs):
2,001,838 cache-misses # 91.745 % of all cache refs ( +- 0.05% )
2,181,958 cache-references ( +- 0.06% )
262,277,307 instructions # 1.36 insn per cycle ( +- 0.02% )
192,614,661 cycles ( +- 0.10% )
0.087413542 seconds time elapsed ( +- 0.29% )
Performance counter stats for './phonebook_opt' (100 runs):
346,679 cache-misses # 62.092 % of all cache refs ( +- 0.08% )
558,328 cache-references ( +- 0.22% )
243,357,563 instructions # 1.64 insn per cycle ( +- 0.02% )
148,287,579 cycles ( +- 0.12% )
0.068586419 seconds time elapsed ( +- 0.34% )
```
#### 2. 使用 hash function 改善查詢速度
由 phone_orig.c 中可發現原先的 search 是採循序分析一一比對去找到目標，其時間複雜度為$O_{(n)}$ , 在找大量資料時相當浪費時間，故我們改用HASH法, 找到和 phonebook 相關的 key並建立對應的 hash function 增進尋速度。
說到 phonebook 查詢 , 一般人都會採用字母先做篩選, 故我想先用字母做為 key value , 再用 linked list 去解決 collision 問題 在此有想到一個問題， 由於26個字母下 collision 的名字太多了, 有可能造成搜尋瓶頸, 不過目前想先把以字母為 key value 的搜尋完成再來探討有沒有更佳的 hash function.
在修改完程式並將三次測試結果圖示顯示後可以發現，加入字母為 key value 的 hash function 後==findname時間明顯下降 (0.0037->0.00002 sec)== , 大大降低了搜尋時間
#### 參考資料
1. [0140454同學共筆](https://hackmd.io/EwMwhgDBDGBsYFoDsBGWAOBAWdSCsCAnCIQEYLAoRgAmApvHiAMylA==?view)
2. [benson326同學共筆](https://hackmd.io/s/Hy2uUcEoZ)
3. [programming small](https://hackmd.io/KYFgbAJgHMCcwFoBGBGVCTCkhBDAZrAAx5gDGsusATEQKwgi5A==?view)
4. [雜湊表(wikipedia)](https://zh.wikipedia.org/wiki/)
5. 圖解資料結構-使用c語言 作者:胡昭明
Sign in with Wallet
Connect another wallet