# 2016q3 Homework1 (phonebook)
contributed by <`RayPan`>
### Reviewed bt `finalallpass`
* 因為沒有使用細部資料，可以考慮重建structure時不需多用一個指標指回細部資料。可以再減少8bytes的entry size。
* 可能可以分析一下為何djb2和BKDR的cache-misses的差異從何而來。
* 修改structure的部分可以補上cache reference的結果
---
## 開發環境
第一次使用linux作業系統
花了不少時間研究指令
* CPU
```
raypan@raypan-X550JD:~$ lscpu
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: 60
Model name: Intel(R) Core(TM) i5-4200H CPU @ 2.80GHz
Stepping: 3
CPU MHz: 2782.281
CPU max MHz: 3400.0000
CPU min MHz: 800.0000
BogoMIPS: 5587.62
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 3072K
NUMA node0 CPU(s): 0-3
```
>> 請考慮升級到 Ubuntu 16.04，不然某些軟體套件會太舊 [name=jserv]
升級16.04版
`$ sudo apt-get update && sudo apt-get dist-upgrade`
`$ sudo reboot`
`$ sudo update-manager -d`
---
## GitHub
* 簡介
是一個基於網站基礎的託管服務 (hosting service)平台，它提供了以Git為唯一的版本控制系統。
* 常用指令
`$ git init`:要開始使用 Git 你必須先建立一個 Git 的 Repository。
`$ git remote add origin git@github.com:your_account/your_repository.git`:可以連結到遠端的repository。
`$ git clone git@github.com:Username/repository.git`:可將遠端的repository複製一份到本機，若遇防火牆阻隔問題，請改用HTTPS通訊協定:`https://github.com/...`
`$ git remote -v`:查看working directory所連結的遠端repository。
`$ git status`：查看目前working directory中所有檔案的情形。
`$ git add`：將未被git追蹤的檔案加入追蹤，可最後加上`.`追蹤全部檔案。
`$ git commit`:將檔案提交。
`$ git push`:上傳到遠端repository。
`$ git pull`:從遠端更新
---
## 效能分析工具-Perf
應用程式可以利用 PMU (Performance Monitoring Unit), tracepoint 和核心內部的特殊計數器 (counter) 來進行統計，另外還能同時分析運行中的核心程式碼
* 常用指令
`perf list` : 印出perf可以觸發哪些event
`perf top` : 找出拖慢系統的熱點
`perf stat` : 已經有個要優化的目標，對這個目標進行特定或一系列的event檢查，進而了解該程序的效能概況。
`perf stat -r 10 cache-misses ./example`表示對特定程式example執行10次perf其cache-misses
`perf record` ：針對函式級別進行 event 統計，方便我們對程序「熱點」作更精細的分析和優化。
參考資料：[成大wiki-Linux效能分析工具：Perf](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial)
---
## Makefile
* #### 規則
`target: dependencies`
`<tab>command`
* target: 所要建立的檔案。
* dependencies： 相依項目，make會依據此決定是否要重新編譯targey。
* commands:建立targets的指令。
注意：make 在編譯時，若發現 target 比較新，也就是 dependencies 都比 target 舊，那麼將不會重新建立 target，如此可以避免不必要的編譯動作。
`.PHONY`: 指定後面的為fake項目，利用`.PHONY: clean`來指定clean為fake項目,被視為要建立clean這個檔案，但永不被執行。
* #### 變數宣告
`MACRO = value` ： 可利用`$(MACRO)`或`${MARCO}`來存取已定義的變數。
`：=` ： 變數的值決定於它在Makefile中的位置，而不是整個Makefile展開後最終的值。
`?=` : 若變數未定義，則替它指定新的值。否則採用原有的值。
* #### 內部變數
`$?` ： 已被更新的dependencies的值，i.e.dependencies中，比targets還新的值。
`$@` : targets的值。
`$<` : 第一個dependencies的值。
`$*` : targets所指定的檔案，但不包含副檔名。
* #### 特別字元
`@` ： 不要顯示執行的指令在螢幕上。
`-` : 即使該行指令出錯，也不會中斷執行。
`-DMACRO`: 指定一個MARCO的名字。
* 參考資料： [Makefile 語法簡介](http://tetralet.luna.com.tw/?op=ViewArticle&articleId=185)、 [猴子都會寫的Makefile](http://mropengate.blogspot.tw/2015/06/makefile-makefile.html)
---
>> 張貼程式碼時，請注意縮排 (空白，而非 tab，與原本程式碼一致的風格) 並且避免單行後方非必要的空白 [name=jserv]
>> 延伸閱讀: [The Lost Art of C Structure Packing](http://www.catb.org/esr/structure-packing/) [name=jserv]
---
## 可能的效能改進方法
* 改寫`struct __PHONE_BOOK_ENTRY`
* 使用 Hash function 加速查詢
* 使用字串壓縮的演算法，降低資料表示的成本
* 使用 binary search tree 改寫演算法
---
## 改善過程
#### 未修改之前
```
size of entry : 136 bytes
execution time of append() : 0.053688 sec
execution time of findName() : 0.004984 sec
```
```
Performance counter stats for './phonebook_orig' (100 runs):
1,003,292 cache-misses # 84.258 % of all cache refs ( +- 0.32% )
1,190,732 cache-references ( +- 0.20% )
260,911,327 instructions # 1.39 insns per cycle ( +- 0.02% )
187,778,382 cycles ( +- 0.19% )
0.057238264 seconds time elapsed ( +- 0.60% )
```
### 1. 修改`struct __PHONE_BOOK_ENTRY`
由main.c可知
```c=75
#ifndef OPT
e = pHead;
assert(findName(input, e) &&
"Did you implement findName() in " IMPL "?");
assert(0 == strcmp(findName(input, e)->lastName, "zyxel"));
#endif
```
程式僅透過lastname來查找
其他聯絡人資訊可以放入另一個結構中
如有需要
透過pDetail來索取額外聯絡人資訊
可以減少entry的大小達到優化
修改後程式碼如下
```c=9
typedef struct __PHONE_BOOK_DETAILS{
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];
}details;
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
struct __PHONE_BOOK_DETAILS *pDetails;
struct __PHONE_BOOK_ENTRY *pNext;
} entry;
```
執行看看
在執行程式之前先清空cache:
`$ echo 1 | sudo tee /proc/sys/vm/drop_caches`
```
size of entry : 32 bytes
execution time of append() : 0.037598 sec
execution time of findName() : 0.004964 sec
```
如此entry的大小變可縮小至32bytes
```
Performance counter stats for './phonebook_opt' (100 runs):
135,386 cache-misses # 44.511 % of all cache refs ( +- 0.63% )
304,164 cache-references ( +- 0.45% )
244,033,296 instructions # 1.94 insns per cycle ( +- 0.02% )
125,671,746 cycles ( +- 0.20% )
0.038329599 seconds time elapsed ( +- 0.50% )
```
可以發現cache-misses由原本的84.258%下降至44.511%
接著使用makeplot繪製效能比較圖
***由於main.c中83行，OPT存在才能輸出opt.txt，所以在phonebook.h中必須#define OPT 1***
```c=83
#if defined(OPT)
output = fopen("opt.txt", "a");
```
繪圖如下
>> 避免用圖片來表達文字輸出 [name=jserv]
>> 不要只做執行時間的比較，要對照看 cache reference 的差異，拿出你的專業來 [name=jserv]
### 2.使用Hash function 加速查詢
* #### （1）使用djb2 hash函式
參考共筆：[rni c](https://embedded2016.hackpad.com/ep/pad/static/9eSkToGwJvZ)
捨棄原本的sequential search
首先利用`hashInitial（）`建立hash table
hash table size訂為65537（質數）
結構hashTable內包含`tableSize`及`list`
```clikec=9
hashTable *hashInitial(){
hashTable *ht = NULL;
ht = (hashTable *)malloc(sizeof(hashTable));
ht->list = (entry **)malloc(sizeof(entry *)*HASHTABLE_SIZE);
for (int i = 0; i < HASHTABLE_SIZE; i++)
ht->list[i] = NULL;
return ht;
}
```
注意：選擇hashTable大小為質數的原因為
避免hash collison（輸入字串不同，雜湊值相同）
* hashFunction使用Dan Bernstein提出的[djb2](http://www.cse.yorku.ca/~oz/hash.html)hash函式
```c=21
unsigned int hashFunction(char *lastName){
unsigned int hashVal = 0;
while (*lastName != '\0')
hashVal = (hashVal << 5) + *lastName++;
return hashVal % HASHTABLE_SIZE;
}
```
改寫append函式
可以注意到由於findname長度已定義在MAX_LAST_NAME_SIZE
所以將原本`strcpy`改為`strncpy`
可省去比對其他無效字元。
```clikec=28
int hashAppend(char *lastName, hashTable *ht){
entry *newEntry;
newEntry = (entry *)malloc(sizeof(entry));
strncpy(newEntry->lastName, lastName, MAX_LAST_NAME_SIZE);
newEntry->pNext = ht->list[hashFunction(lastName)];
ht->list[hashFunction(lastName)] = newEntry;
return 0;
}
```
```
size of entry : 32 bytes
execution time of append() : 0.054746 sec
execution time of findName() : 0.000008 sec
```
可以發現到
由於須另外建構一個hashtable
append的執行時間會略為上升
但查找時間會大幅下降
```
Performance counter stats for './phonebook_opt' (100 runs):
151,896 cache-misses # 38.517 % of all cache refs ( +- 2.53% )
394,365 cache-references ( +- 0.76% )
298,128,462 instructions # 1.70 insns per cycle ( +- 0.03% )
175,143,354 cycles ( +- 0.53% )
0.053467373 seconds time elapsed ( +- 0.82% )
```
cache misses也下降到了38.517%
* #### （2）使用BKDR hash函式
參考老師提供的[Programming Small](https://hackmd.io/s/S1rbwmZ6)
```c=29
unsigned int BKDRhash(char *str){
unsigned int seed = 131;
// 31 131 1313 13131 131313 etc..
unsigned int hash = 0;
while (*str)
hash = hash * seed + (*str++);
return hash % HASHTABLE_SIZE;
}
```
```
size of entry : 32 bytes
execution time of append() : 0.052487 sec
execution time of findName() : 0.000008 sec
```
執行時間大略相同
```
Performance counter stats for './phonebook_opt' (100 runs):
106,166 cache-misses # 26.940 % of all cache refs ( +- 1.09% )
394,080 cache-references ( +- 0.26% )
298,896,581 instructions # 1.71 insns per cycle ( +- 0.03% )
174,642,726 cycles ( +- 0.57% )
0.052549821 seconds time elapsed ( +- 0.57% )
```
但會發現cache-misses可以再下降到26.397%
---
## 其他筆記
#### 關於前置處理器#if defined
若有兩個c檔案同時include同一個標頭檔，但要同時編譯成一個檔案，會造成衝突。
```
#if defined（ABC） or #ifdef(ABC) //若ABC有定義過（i.e. #define）
程式1 則編譯程式1（非執行）
#else
程式2 否則編譯程式2
#endif
```
參考資料：[ #ifndef#define#endif的用法(整理) 原作者：icwk ](http://huenlil.pixnet.net/blog/post/24339151-%5B%E8%BD%89%5D%23ifndef,-%23define,-%23endif%E7%9A%84%E7%94%A8%E6%B3%95(%E6%95%B4%E7%90%86)-)
#### 關於gcc參數
`-c` : 只做編譯並生成目標文件。
`-g` : 編入除錯資訊（使用gdb時必要）。
`-O0` : 不進行優化（注意：是英文字母大歐+零）。
`-Wall` ： 顯示所有警告訊息。
#### 關於指標大小
32bits的電腦,指標大小為4bytes
64bits的電腦,指標大小為8bytes
---
作業詳細資訊：[A01: phonebook](https://hackmd.io/s/S1RVdgza)
###### tags:`RayPan` `A01:Phonebook`
Sign in with Wallet
Connect another wallet