# 2017q1 Homework1(phonebook)
contributed by<`yanang`>
###### tags:`yananag`
## **Reviewed by `csielee`**
* 最後 append() 時間上沒有下降，可以考慮實作 memory pool ，讓 malloc 呼叫次數減少，讓 append() 時間下降
## 開發環境
* OS: Ubuntu 16.04 LTS
* L1d cache: 32K
* L1i cache: 32K
* L2 cache: 256K
* L3 cache: 3072K
* Architecture: x86_64
* CPU 作業系統: 32-bit, 64-bit
* Byte Order: Little Endian
* CPU(s): 4
* Model name: Intel(R) Core(TM) i5-7200U CPU @ 2.50GHz
*
Linux yanang 4.8.0-36-generic
#36~16.04.1-Ubuntu SMP
## 未優化版本
* 執行: `$ ./phonebook_orig`
```
size of entry : 136 bytes
execution time of append() : 0.105205 sec
execution time of findName() : 0.004954 sec
```
* cache test `$sudo make cache-test`
```Performance counter stats for './phonebook_orig' (100 runs):
4,868,866 cache-misses # 93.482 % of all cache refs ( +- 0.20% )
5,208,353 cache-references ( +- 0.38% )
262,398,775 instructions # 1.35 insn per cycle ( +- 0.02% )
194,347,267 cycles ( +- 0.77% )
0.064319469 seconds time elapsed
```
## version 1 - 減少資料結構
* 在 main.c append() findName() 當中可以發現目前只使用了 lastName 這項數據，也就是說其他項數據都是可以忽略的，但是考慮到不能喪失原本 phonebook 的功能，所以我們將其餘的數據到另一個 struct 。
```c=
typedef struct __PHONE_BOOK_ENTRY_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];
struct __PHONE_BOOK_ENTRY *pNext;
} entry_remain;
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
struct __PHONE_BOOK_ENTRY_REMAIN *remain;
struct __PHONE_BOOK_ENTRY *pNext;
} entry;
```
* 資料將以 linklist 方式
* 執行時間：
```
size of entry : 32 bytes
execution time of append() : 0.137438 sec
execution time of findName() : 0.002579 sec
```
* cache test
* **cache miss 明顯降低**
```Performance counter stats for './phonebook_opt' (100 runs):
1,679,608 cache-misses # 68.692 % of all cache refs ( +- 0.48% )
2,445,143 cache-references ( +- 0.81% )
244,480,047 instructions # 1.84 insn per cycle ( +- 0.02% )
132,706,657 cycles ( +- 1.11% )
0.044007362 seconds time elapsed
```
* 圖表分析：
雖然由此來看 append() 的時間是減少的，但是如果要使用到其餘的資料，則 append() 的時間應該會略高於原本的時間。
## version 2 - hash function
* 在閱讀許多資料後，我將 hash table 建於 main.c ，並利用 `#ifdef OPT_HASH` 達到目的。
* 因為在 [各種字符串Hash函数比較](https://www.byvoid.com/zhs/blog/string-hash-compare) 當中 BKDRHash 函數的綜合評分最高，所以就選用此種方式。
>可以參考閱讀 [BKDR hash 詳盡解說](http://blog.csdn.net/wanglx_/article/details/40400693) 並嘗試引入其他 hash function 實驗比較[name=課程助教][color=red]
```c=
unsigned int BKDRHash(char *str)
{
unsigned int seed = 131;
unsigned int hash = 0;
while (*str)
{
hash = hash * seed + (*str++);
}
return (hash & 0x7FFFFFFF) % SIZE_OF_TABLE;
}
```
* 原先想以後置的方式將資料 link 起來，但是若要找到 list 的尾端將需要多 loop ，為了增進效能就放棄改為前置。
```c=
entry *pHead = (entry *) malloc (sizeof(entry));
pHead->pNext = e[hash];
e[hash] = pHead;
strcpy(pHead->lastName,lastName);
/* entry *pLast = (entry *) malloc (sizeof(entry));
pLast -> pNext = NULL ;
strcpy(pLast->lastName,lastName);
e[hash] -> pNext = pLast;
* not finished
* should add loop to find the last data
*/
```
* 執行時間：
```
size of entry : 24 bytes
execution time of append() : 0.039091 sec
execution time of findName() : 0.000009 sec
```
* cache test：
```Performance counter stats for './phonebook_opt_hash' (100 runs):
437,137 cache-misses # 58.419 % of all cache refs ( +- 1.13% )
748,282 cache-references ( +- 2.45% )
232,794,043 instructions # 1.82 insn per cycle ( +- 0.02% )
127,598,545 cycles ( +- 0.89% )
0.042041802 seconds time elapsed
```
* 圖表分析：
* hash 主要是將 findname() 的時間大幅減少。
## 修改錯誤訊息
* git push 之後突然發現 git commit 的 message 打錯字了，參閱 [XYZ的筆記本](http://xyz.cinc.biz/2016/07/git-edit-commit-message-after-push.html)
```
$ git commit --amend
$ git push --force-with-lease origin master
```
Sign in with Wallet
Connect another wallet