# PhonebookA01
---

照作業步驟跑一次併紀錄問題

### 利用圓周率pi 體會perf top
comment

/*將c語言轉成o檔*/
g++ -c perf_top_example.c	   
/*將o檔輸出為執行檔。*/
g++ perf_top_example.o -o example 
/*運算執行檔。*/
./example			  

><s>輸入perf top -p $pid後，小黑窗說-需要值，請問要如何輸入。[name=HankLo]</s>
>在分析運算效能時，要開兩個小黑窗，一個執行程式，另一個分析效能。在計算圓周率main c 可以看到getpid()，會得到一個值，這應該是個條碼，在另一個黑窗測試效能時要輸入這個條碼，它就會開始分析此程式。[name=HankLo]
>參考[jkrvivian](https://hackmd.io/s/SyOQgOQa)使用sudo perf top -p $! 有一樣的效果，因為 $! 是最後一個輸出，所以會自動抓取example的pid [＄表示讀取命令行參數](https:// "title")。 [name=HankLo]

### 案例探討phonebook
comment
* make直接編譯，make run程式執行，make plot程式直接畫圖。拿計算pi的檔案一樣用黑窗打上束語法得到以下結果。

make: *** No targets specified and no makefile found.  Stop.
make: *** No rule to make target 'run'.  Stop.
make: *** No rule to make target 'plot'.  Stop.

* append time & findname time 如何計算
* makefile有cache-test併透過calculate作sumation。
`perf stat --repeat 100 \-e cache-misses,cache-references,instructions,cycles \`

### 作業
* 透過perf了解phonebook_orig效能分布

`$make run`

size of entry : 136 bytes
execution time of append() : 0.040286 sec
execution time of findName() : 0.005159 sec

* 

##### findName 跟 main 為熱源
* findName
檢查電話簿，電話簿資料容量有123bytes，但只有lastName(16bytes)為需要，絕大多數資料為不需要的，把需要的資料留下來再做搜尋可以減少cache-misses的時間。

##### 方法1
把lastName[]獨立出來。

tneypedef struct __PHONE_INFO {
    char firstName[16];
    char email[16];
    char pho[10];
    char cell[10];
    char addr1[16];
    char addr2[16];
    char city[16];
    char state[2];
    char zip[5];     
    struct __PHONE_INFO *info;
} info;
typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    struct __PHONE_BOOK_ENTRY *pNext;
} entry;

結果size of entry : 24 bytes，且append time 及 findName time下降。

* 

比較cache-misses
原始
`$perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./phonebook_orig`

Performance counter stats for './phonebook_orig' (5 runs):

         3,435,530      cache-misses              #   92.775 % of all cache refs      ( +-  0.20% )
         3,703,072      cache-references                                              ( +-  0.86% )
       263,250,097      instructions              #    1.42  insns per cycle          ( +-  0.16% )
       185,775,020      cycles                                                        ( +-  0.52% )

       0.060823295 seconds time elapsed                                          ( +-  0.85% )
		

* 

修正後
`$perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./phonebook_opt`

 Performance counter stats for './phonebook_opt' (5 runs):

         1,219,623      cache-misses              #   72.976 % of all cache refs      ( +-  0.15% )
         1,671,264      cache-references                                              ( +-  0.85% )
       243,862,712      instructions              #    1.95  insns per cycle          ( +-  0.09% )
       125,283,566      cycles                                                        ( +-  0.61% )

       0.047547781 seconds time elapsed                                          ( +-  7.92% )
		

* 

結果cache-misses從3,435,530降為1,219,623，
cpu time從0.060823295降為0.047547781。
>單位是？[name=HankLo]

##### 方法二 Hush Function

不大了解hash function作用，閱讀[hashing](https://www.csie.ntu.edu.tw/~hsinmu/courses/_media/dsa_12spring/hashing.pdf)。
透過hasu function將原始資料結構改變、壓縮。