# 2016q1 Homework1 (phonebook)
## 環境架設
因為在老師推薦lubuntu之前就灌了雙系統，選用Ubuntu 14.0.4，之前有灌過作業系統，但是是直接全部刷掉，所以每一步都很隨便，這次要灌雙系統，如果踏錯一步可能就回天乏術(怕怕)，特別是在分割磁碟的地方特別小心：
分割了50GB給Ubuntu的根目錄 / 以及 2GB 給 SWAP
## Ubuntu grub
在安裝雙系統時，設定開機選項為Ubuntu的grub，因為看網上好像有人因為選Windows boot manager而找不到linux的開機口，雖然選擇了grub，而grub預設開機選項為Ubuntu，而且只有10秒的時間可以選擇，但是我平常還是會使用windows，因此會有需求開機預設為windows，查了一下:
* 主要選單檔，/boot/grub/grub.cfg，不應再被手動編輯，即使是由「root」身份
* grub.cfg 會在任何有更新、核心被加入/移除或是使用者執行 update-grub 的時候被覆寫
* 主要用來改變顯示設定的設定檔是 /etc/default/grub
```shell
GRUB_DEFAULT=0 # 設定預設選單選項 在 /boot/grub/grub.cfg 中的第一筆「選單選項」為 0，第二筆為 1，以此類推
GRUB_TIMEOUT=10 # 多久之後自動以預設作業系統開機
```
我主要是改這兩個設定而已，再執行# sudo update-grub ，更動將會自動寫入grub.cfg
結果圖：
參考資料：
[GRUB2中文指南第二版](http://wiki.ubuntu-tw.org/index.php?title=GRUB2%E4%B8%AD%E6%96%87%E6%8C%87%E5%8D%97%E7%AC%AC%E4%BA%8C%E7%89%88%28%E4%B8%8A%EF%BC%89#.E8.A8.AD.E5.AE.9A_GRUB_2)
> GRUB 2 是在 10.04 以後才於許多作業系統中使用
## 修改Terminal顏色：
參考了[DADA的筆記](https://embedded2016.hackpad.com/2016q1-Homework-1-YkqjhwgnQcA) ，找到這篇[BASH color prompt](https://richardnotes.wordpress.com/2011/05/15/bash-color-prompt/) 才知道可以改Terminal的顏色
## 修改vim
參考自 [凍仁的筆記](http://note.drx.tw/2008/01/vimrc-config.html)
vim是vi的進化，再編輯檔案時，會用顏色來編式不同的文˙字，可是跟以前用的編輯器(ex.notepad++)之類的比起來，不能自動縮排讓手酸的要命，所以就來搬救兵了
照著這篇，我加了這個設定
```shell
set ai " 自動縮排
set tabstop=4 " 自訂縮排 (Tab) 位元數
set shiftwidth=4 " 自訂縮排 (Tab) 位元數 符合格式
```
> 本來有加入set number顯示行號，結果複製程式碼時，行號也過來了，所以乾脆關掉
# 案例分析
Makefile學習
> 之前摸Linux時是碰一套叫LAMMPS的科學計算軟體，makefile只是把路徑填進去，未深入了解
老師提供的[教學](http://tetralet.luna.com.tw/?op=ViewArticle&articleId=185)，[其他教學](http://kevincrazy.pixnet.net/blog/post/29780477-makefile%E7%B0%A1%E6%98%93%E6%95%99%E5%AD%B8...)
以下是Makefile的基本編譯格式:
```shell
target: dependencies1 dependencies2....
<tab>commands...
target: 要建立的檔案
dependency: 相依檔案 若相依檔案時間都比tartget舊，則不進行編譯
commands: 一定要以一個縮排開頭
```
* make 指令會參考 all 這個目標項目，並依據它的dependencies 來決定要建立哪些項目，EX.作業中的all會導向orig跟opt的編譯，如果沒有all則編譯第一項target
* 如果dependency 不存在於資料夾中，就無從比對新舊，所以就會在Makefile中尋找此target，找到會先執行
* 如果有多個Makefile 可用 # make -f MakefileName
* -DIMPL="\"$@.h\""
* 有define的作用，定義IMPL=某個字串
* $@：代表 targets
* 另外，/$^代表所有dependency(不同於$<：第一個dependency)
### assert function(main.c)
* 在研究main.c時，發現assert這個沒見過的function
assert(findName(input0, e) &&
"Did you implement findName() in " IMPL "?");
assert(0 == strcmp(findName(input0, e)->lastName, "zyxel"));
~~查到資料說："當自己寫的函式庫要提供他人使用時，適當的利用維護敘述，可以建立安全的使用介面，避免他人因為使用不當，而造成不可預期的後果"，所以若assert後面的判斷句為否，則程式停止ˋ，可以避免後續錯誤~~
> 請讀第一手的資料: http://linux.die.net/man/3/assert
> 這裡寫說:assert是幫助程式設計師debug用的，所以其實這個部份對於user來說是無用的，所以如果是完整版的程式，就可以把assert function砍掉，省時間囉~
> 不需要移除，只要變更編譯參數即可，請見 [man assert](http://linux.die.net/man/3/assert)
> 收到！！在Makefile中新增： CFLAGS_common ?= -Wall -std=gnu99 -DNDEBUG
> 而這裡應該是為了避免findname()的錯誤，例如沒有更改phonebook—opt.c中的的return NULL的話，就會產生中斷，但是缺點是會執行多餘的程式，看起來會多執行兩次findname，以下是orig版的cache-miss
> 文字訊息不要用「圖片」！
我認為既然都是執行findname，應該也會佔用多餘的執行˙間，以及造成更多cache-miss，~~所以將main.c的assert都註解掉~~，在編譯參數中加入"-DNDEBUG"，這樣編譯時assert就不會被編譯出來，下是其cache-miss
> 不要把 assert 移除，變更編譯參數即可！
由此可見，assert的部份的確會造成更多的cache-miss，我認為，在findname()是被完整的其況下並不太需要做assert的動作，省去這個部份的程式碼，也不算影響其原功能
或者是在做保護測試的同時，也能避免過多的cache-miss->簡短findname()
# 優化方式
## 使用體積較小的 struct
### orig版本的entry
```c
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;
```
計算struct: 16*5+10*2+5+2+(alignment)+8(pointer)
字串陣列總合是123 由於此struct最大元素為8byte，所以alignment是8byte，所以123要加上5btye，最後加上8byte指標=136
* 程式驗證
```
sizeof("%d\n",(int)entry)
```
entry大小為136byte，很快就會佔滿cache，cahce-miss也就很多，如果能減少entry大小，cache就能容納更多資料，cache-miss也能減少
因為在執行findName()時只會用到lastName，所以把其他資料包進detail裏面
```c
typedef struct __PHONE_BOOK_ENTRY_DETAIL {
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];
} detail;
/* original version */
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
struct __PHONE_BOOK_ENTRY_DETAIL *pDetail;
struct __PHONE_BOOK_ENTRY *pNext;
} entry;
```
新的entryˇ大小為32byte
Performance counter stats for ’./phonebook_opt1’ (100 runs):
```
353,109 cache-misses # 80.672 % of all cache refs
453,700 cache-references
206,288,675 instructions # 1.70 insns per cycle
125,162,971 cycles
0.055469342 seconds time elapsed ( +- 1.52% )
```
cache-miss由93% -> 80%，執行時間也有縮短，這些節省的時間就是原本受cache-miss影響。
使用 Hash funtion
* 概念: 給定一個Char array 透過hash function的運算，可以放入hash table的array，如果hash value重複 就在後面建linked list，搜尋時同樣將key輸入hash function
我第一次使用的hashfunction和hashtable:
SIZE = 100
```
int mod = 100;
unsigned sum;
int i;
for (sum=1, i=0; i < 16&&key[i]>0; i++){
if(key[i]>0)
sum += key[i]; //加總ASCIIcode當hash value
}
return sum % mod;
```
hashtable append()
```c
entry *append(char lastName[], entry *hashtable[])
{
entry *e;
e = (entry *) malloc(sizeof(entry));
strcpy(e->lastName, lastName);
e->pNext = NULL;
unsigned id = hash_fun(lastName);
if (!hashtable[id]) {
hashtable[id]=e;
} else {
entry *temp = hashtable[id];
while(temp->pNext) {
temp= temp->pNext;
}
temp->pNext = e;
}
return e;
}
```
結果跑了兩分鐘，append()都沒結束(冏)，果然35萬筆資料不是蓋的QQ,每個，這次改成array大小為300，同時也要更改hashfunction的mod值，
```
int mod = 300;
unsigned sum;
int i;
for (sum=1, i=0; i < 16&&key[i]>0; i++){
if(key[i]>0)
sum += key[i];
}
return sum % mod;
```
發現時間還是太久了，但是原本這個hashfunction產生的值大約在5百多，所以要再加快的話，勢必要用不一樣function，
第三次改成將ASCIIcode做相乘，hash value平均大約到8千萬，以3萬的array去做hash table
```c
int mod = 300000;
unsigned sum;
int i;
for (sum=1, i=0; i < 16&&key[i]>0; i++){
if(key[i]>0)
sum *= key[i]; //ASCIIcode 相乘
}
return sum % mod;
```
跑出來成績沒有別人好，但是已經是大進步了
跟自己比！
execution time of append() : 0.198321 sec
execution time of findName() : 0.000032 sec
make cache-miss
1,589,357 cache-misses # 65.627 % of all cache refs
2,603,703 cache-references
284,554,622 instructions # 0.61 insns per cycle
467,728,346 cycles
我把hash table每格的第一個entry印出來，結果卻是:有hash到跟null比起來大約只有1:3，這樣子就會有很多空的entry，而且array中的linked_list會太長，要再找分布更均勻的hashfunction
查到這個djb2 algorithm，這是一個很有名的String hash function
DJB2 優點: 選用shift當成乘法，加快運算 hash值相當均勻分布
至於為什麼選5381和33這兩個數字，好像沒有人能有個合適的解釋，只能說33是由測試中找出來最適合的數字
djb2 hash function
```c
unsigned hash_fun(char key[]) //djb2 hash function
{
int mod = TABLE_SIZE;
unsigned hash = 5381;
int i=0;
while (key[i]>0)
{
hash = ((hash << 5) + hash) + key[i++]; /* hash * 33 + ASCII */
}
return hash % mod ;
}
```
可以看到幾乎所有array都有hash到，所以linked list搜尋長度自然也減小，減少excutiontime和cache-miss
另外，因為append時間過長，主因是在延伸linked list時，需要向後爬很久，和 王紹華 討論後，發現可以把新增的資料放在第1個entry這樣就不必每次都要爬到最後了
新的append():
```
entry *append(char lastName[], entry *hashtable[])
{
entry *e = (entry *) malloc(sizeof(entry));
strcpy(e->lastName, lastName);
e->pNext = NULL;
unsigned id = hash_fun(lastName);
if(!hashtable[id]) {
hashtable[id]=e;
} else {
e->pNext = hashtable[id]->pNext;
hashtable[id]->pNext = e;
}
return e;
}
```
target: zyxel
find zyxel
execution time of append() : 0.086690 sec
execution time of findName() : 0.000026 sec
size of entry : 32 bytes
646,316 cache-misses # 51.121 % of all cache refs
1,317,499 cache-references
263,443,203 instructions # 1.32 insns per cycle
207,572,891 cycles
-orig opt1 opt2執行時間比較
一如預期，因為透過hash_function快速的找到目標linked list，也減小list長度，所以findName()的執行時間超極少，但是append也因此增長了，由這個圖來看的話，hash的優化方法甚至式最差的，因為把總執行時間加總起來，是OPT2最久QQ，但是回頭想一想，hashtable的建製雖然耗時，但是只要建立完成後，不管查幾筆資料都是超快速，所以以長遠來看，當然還是hash_opt顯勝
orig OPT1 OPT2
cache-miss: 91% 80% 51%
append() 0.057 0.048 0.069
findName() 0.0057 0.003255 0.00003
為此我會多做多幾比查詢，另外，我一直覺得，如果每次都是找預設的"zvbel"，這樣不準的，應該要亂數隨機挑選查詢，才比較公平
更改main.c，在append()後，會進行10次random的查詢:
可見findName部份，opt2幾乎沒增加，
## gnuplot 學習
gnuplot是一個免費且功能強大的繪圖軟體，但都是由文字指令來使用，也因為這樣不同的組合會有無限可能，製造出自己想要的圖表
這是我最後的runtime.gp
本來也是看不懂，所以試著改，沒想到改對了，但還是不知道在幹嘛。後來看過別人的hachpad ，才比較懂一些：
```
reset # 清除之前所有的設定
set ylabel ’time(sec)’ # y軸座標
set style fill solid # 圖形填滿 Set style fill
set title ’perfomance comparison’ # 圖表標題
set term png enhanced font ’Verdana,10’ # 輸出png設定 term: terminal set term png
# 圖表內字型
set output ’runtime.png’ # 輸出檔案
plot [:][:0.10]’output.txt’\ # 引入檔案 設置XY軸數據範圍
using 2:xtic(1) with histogram title ’original’, \ # * Orig資料
’’ using 3:xtic(1) with histogram title ’optimized1’ ,\ # * opt1資料
’’ using 4:xtic(1) with histogram title ’optimized2’ ,\ # * opt2資料
’’ using ($0-0.06):($2+0.0015):2 with labels title ’’, \ #** orig顯示數值
’’ using ($0+0.2):($3+0.0015):3 with labels title ’’, \ #** opt1顯示數值
’’ using ($0+0.4):($4+0.0015):4 with labels title ’’ #** opt2顯示數值
```
第3行後的using前都有個空白的單引號，代表同上的檔案
* with histogram -> 以長條圖做圖，xtic -> x軸 tick label 第一個數字是取第幾個column作為資料，xtic(1)代表取哪個column當作X軸標記，所以是取1，也就是 append()跟findName() ，title ’optimized1’ -> 資料標題
`** with labels` ->做標籤，第一個參數和第二個參數為座標位置，第三個參數為要印出的字串，也就是資料本身， $2-4 -> 一樣是第某column的資料，只用在用算時，區別常數與參數， title ’ ’ = notitle -> 不需標題
把印數字都放到最後是因為怕圖形把數字蓋掉了，因為gnuplot也是一行一行讀下來，所以後執行的會把先執行的蓋掉
`#` 為註解，但是不可以在 \ 後面，\ 後面連空白都不能有(上面只是做說明多加的)
參考資料
與同學 黃鏡清 王紹華 共同討論
GRUB2中文指南第二版
assert manual
gnuplot.source
老師的案例分析
```shell
# lscpu
# cat /sys/devices/system/cpu/cpu0/cache/index*/size //cache size
# cat /sys/devices/system/cpu/cpu0/cache/index*/coherency_line_size //cache_line size (cache最小單位)
```
http://enginechang.logdown.com/posts/249025-discussion-on-memory-cache
Sign in with Wallet
Connect another wallet