# 2017 q3 Homework1 (作業區)
==contributed by<`williamchangTW`>==
###### tags: `Class_Project`, `Jserv`
### Reviewed by `zhanyangch`
* 針對 orig 與 opt 的比較不應只有時間差異，應探討造成此差異的原因，利用 perf 等工具可以協助分析。
* 對 cache 的介紹可以不夠詳盡，可以參考老師提供的 [Computer Architecture](https://hackmd.io/s/H1sZHv4R) [(NOTE)](https://hackmd.io/s/rkloHgHcx) 的 memory 章節。
### Reviewed by `tina0405`
* 縮減 structure 裡的大小後，也可以考慮在其他方面去優化，像資料結構或記憶體的分析方面
* 利用 perf 工具去分析現況 [perf stat 輸出解讀](https://zhengheng.me/2015/11/12/perf-stat/)
## Phonebook
### 建置環境所遇到的問題
- 在這我在使用 perf top 的時候遇到一個問題，花了點時間解決，就是一開始想把權限全打開，預設值是 3 ，我預先執行一段 command line : `gedit /proc/sys/kernel/perf_event_paranoid` 打開後想直接更換為 -1 ，可是出現 `you do not have the permissions necessary to save the file.Please...` 這一段使我不能更改這個檔案，我試過 `sudo su` 及 `vim` 和 `gksudo` 等方法去試著更改其中的值，最後我使用 [sudo sh -c 'echo -1 > /proc/sys/kernel/perf_event_paranoid'](https://superuser.com/questions/980632/run-perf-without-root-rights) ，最後是因為覺得跟 kernel 檔案的關係比較大才找到解決辦法。
- 最後做 `cat /proc/sys/kernel/perf_event_paranoid` 的值確定為 -1 。

### 還沒有優化前資料
- 再來當我輸入 `perf top` 如下顯示：
- 再來是一開始的 `make plot`:(opt code copy from orig)

- main.c define：
~~~c=
#ifdef OPT
#define OUT_FILE "opt.txt"
#else
#define OUT_FILE "orig.txt"
#endif
~~~
- 這裡是一種類似於 if ... else 判斷式的定義，依照 #ifdef(+條件定義) 及 ＃else(+條件定義) #endif結束判斷式。

- 這裡可以看到當有 OPT 這個 headerfile 就定義 **OUT_FILE 生成 "opt.txt" 反之生成 "orig.txt"**。

- 再來看 phonebook_opt.c code，我想從 orig去改 code 所以複製了一份去試試， trace 完後發現一個地方會忘了把 malloc free 。
~~~c=
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#include "phonebook_orig.h"

/* 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;
}
~~~
- 更改完後
~~~c=
entry *append(char lastName[], entry *e)
{
e->pNext = (entry *) malloc(sizeof(entry));
e = e->pNext;
strcpy(e->lastName, lastName);
e->pNext = NULL;
free(e->pNext);
return e;
}
~~~
- 再來我朝 **findName go down** 開始，一開始想說在 while loop 中每次都要做**判斷式**，想減少他的 branch times ，因為 branch 是影響效能比重最重的一個 stage，可是想不出怎麼提出到外面解決，後來想說**減少單次判斷所需等待時間著手**。

- 先看 OPT 這個 headerfile ，於是找出 phonebook_opt.h
~~~c=
#ifndef _PHONEBOOK_H
#define _PHONEBOOK_H

#define MAX_LAST_NAME_SIZE 16

/* TODO: After modifying the original version, uncomment the following
* line to set OPT properly */
// #define OPT 1
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;

entry *findName(char lastName[], entry *pHead);
entry *append(char lastName[], entry *e);

#endif
~~~
- 上述**這段冗長的資料要花一點時間去做**，每一次都要花這麼多時間，我決定除了 lastName 留下外其他放到一個新的結構內做需要的時候在搜尋它。其餘不變。
~~~c=
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
struct __PHONE_BOOK_DET *pDet;
struct __PHONE_BOOK_ENTRY *pNext;
}entry;

typedef struct __PHONE_BOOK_DET {
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];
} det;
~~~
- 很明顯的 find() 時間變短了，而 append() 小幅下降。

- 把註解掉的 OPT 打開。
~~~c=
#define OPT 1
~~~
### cache 詳閱
- 首先是為何要有 cache ，從下面這張圖可以明顯地知道，為了填補 cpu ~ main memory 之間的差異，進而需要階層式的 table 來填補速度上的差異和 reduce cpu idle time。
- cache 被設計成一個 hash table 內存數組 index address，簡單概述的說 fully associative 不可能實現，因為這樣需要大量的尋找就損失原本的意義。
- direced mapped 也不好用，前幾個區塊常被用到，後面幾個區塊幾乎不用，浪費空間，使用率可能會很差。
- N-way associative & (LRU or Random) implemented.
- 把最近常用到的資料放在越靠近 CPU 的 memory 作儲存，這樣在抓取資料時 responds time 較短較有效率。