# 2016q3 Homework#1 : phonebook
## Linux環境
對於Linux我在2年級去比叢集電腦的時候就有接觸了，電腦裏面也已經裝好Linux Mint了，剛好Mint也是Debian系列的，所以我就用Linux Mint來當作我的開發環境囉~
- 這裡我遇到了一個小問題，我之前沒有更新版本所以我的Linux核心版本是unstable的發行版(3.8.11)所以找不到linux-tools，這讓我研究了好久...所以記得要把系統更新到最新喔
```shell=
$ sudo apt-get update //更新軟體列表
$ sudo apt-get dist-upgrade //更新Linux發行版本
```
- 還有另一個問題我看了超不順眼...就是在linux上面執行chrome會有文字變成標楷體！我特地去找了方法來解決
其實只要把fonts-arphic-ukai 跟fonts-arphic-uming 解除安裝，我的思源黑體就回來了！
```shell=
$ sudo apt-get remove fonts-arphic-ukai && sudo apt-get remove fonts-arphic-uming
```
## Git & GitHub
### Git基本原理
首先，git的終極目標就是要能管理龐大的多人合作專案。那到底如何管理呢？全部都藏在`.git` 這個資料夾裡面了！
git可以幫你儲存版本紀錄，每次提交新的版本，git都會把舊的版本存在.git裡面。git分成3個部份：工作目錄、索引、數據庫。在工作目錄中相檔案add進索引時會進行比對，找出更新的部份，再用commit提交進數據庫。
### Git管理並上傳自己的repository
首先在網頁上fork老師的phonebook，然後用：
```shell=
$ git clone your git url //譬如：git clone https://github.com/workfunction/phonebook.git
```
先clone下來你自己的repository到你的電腦裏面，之後開始修改你要修改的檔案
接下來要對每個修改過的檔案用：
```shell=
$ git add file you edit //譬如： git add phonebook_opt.c 或是用：git add . 提交全部的檔案進索引
```
這一步就是在把檔案註冊至索引中。
接著提交修改版本到git中(這裡都是在本地電腦裏面clone下來的repository做修改)用：
```shell=
$ git commit -m "your change log title" //譬如： git commit -m "1st opt"
```
這樣一來你就在電腦裡做好一個修訂版本囉！
注意一點如果打了上面的跳出：
```shell=
On branch master
Your branch is up-to-date with 'origin/master'.
Changes not staged for commit:
modified: main.c
modified: phonebook_opt.c
modified: phonebook_opt.h
no changes added to commit
```
代表他列的那些檔案被修改過可是你忘記add囉，所以就在把他列的檔案add進去吧！
最後就是上傳回去GitHub啦，用下面指令
```shell=
$ git push origin master
```
這樣就可以把你電腦裏面的修訂版本放到GitHub裏面了喔！
歐對要記得先做astyle再add喔！！
## Cache Miss分析
我看完cache miss的成因才真正了解問題的點在哪裡 下面是我對這個問題的分析
CPU內部有一個register跟3個層級的cache，下面是不同層級的cache到CPU所需的時間
從CPU到 大約需要的CPU周期 大約需要的時間
```shell=
Register 1 cycle
L1 Cache ~3-4 cycles ~0.5-1 ns
L2 Cache ~10-20 cycles ~3-7 ns
L3 Cache ~40-45 cycles ~15 ns
跨CPU傳輸 ~20 ns
Memory ~120-240 cycles ~60-120ns
```
Cache miss的原因有下列三種:
- Compulsory misses：也稱為cold start misses，第一次存取未曾在cache內的block而發生的cache miss。
- Conflict misses：發生在set-associative或direct-mapped caches，當多個blocks競爭相同的set。通常也稱作collision misses。
- Capacity misses：因為在程式執行期間，cache無法包含所有需要的block而產生的cache miss，也就是資料量過大無法同時存進cache。發生在一個block被取代後，稍後卻又需要用到，這個就是這次作業主要遇到的cache miss的原因。
CPU的一級數據緩存(L1 Data Cache)通常採用組相聯的方式來緩存數據，數據緩存是以Cache Line爲單位進行的，即緩存不命中時，相鄰的一組數據將被載入Cache Line，而不僅僅是當前數據。我的的處理器L1 Data Cache是8路組相聯的緩存，每個Cache Line大小爲64 Byte，總共是32 KByte。所以，爲減少Cache Miss的出現，每個指令讀取的數據最好是相鄰的。
## 程式修改方面
### 讓每個Last name在記憶體中的位置連續
> 因為main裡面有判斷OPT是否被定義過了 不然make plot會跑不出opt的數字喔[name=黃鏡清（Jason）]
我翻閱了幾個前面學長姐的實作，用刪減Struct的大小，只留下Last name跟指標讓cache裏面可以存更多Last name，於是我跟著這種想法實作。
> 理工科系的學生應該避免說「我也覺得很有道理」這種話，真相只有一個
我把entry內容拆開，把另外的資訊刪掉並加了一個指標*pDetail指向令一個struct Detail但是執行結果...
兩個時間都變長了阿！比對後原來螢光筆的那行其他人都沒有...
```clike=
entry *append(char lastName[], entry *e)
{
e -> pNext = (entry *) malloc(sizeof(entry));
e = e -> pNext;
strcpy(e -> lastName, lastName);
e -> pNext = NULL;
e -> pDetail = (detail *) malloc(sizeof(detail));
return e;
}
```
>程式碼不要用「圖片」！直接用 hackpad 貼程式碼的功能，然後用「螢光筆」標注
>改好了！
發現我在append裡面加了一段malloc出detail的大小根本沒有意義，在記憶體中的排列根本沒變：
假設我的cache大小剛好只能放一個原本的Entry下面情況有3個Entry，每次要找last name時把整個Entry load進cache裡面，當要找下一個的時候，下一個last name不在cache裡面造成cache miss(屬於Capacity misses)，而藍色的部份沒有更動到last name的順序，所以基本上效率不會提升，
反而因為多了一個指標造成更多cache miss，所以真正要有效果的減少Capacity misses的排列方式應該是要像下面這樣：
這樣我一次cache就可以load 2個多一點的last name，cache miss的比例就會大幅縮減啦！
所以應該還要在append的時候先把Entry的link list malloc出來，然後在獨立另一個函數malloc出後面的Detail才會有上面的記憶體排列，這樣新的append跟findName的時間都一起減少了
> 我目前還沒想到的方法沒辦法用append一個函數就完成連續排列，所以下面的圖是尚未malloc detail的append與findName的效果
所以有方向啦！現在可以讓資料都排在一起了有效的減少了Capacity misses的發生！接下來就是想辦法讓要快取的東西越小，減少Compulsory misses的發生囉！
### 縮小快取參照的大小
縮小快曲參照的方式最簡單的就是hash啦！因為CPU運算的時間比cache miss的時間還要短很多，所以用hash這個方法是用增加CPU運算的時間來減少cache的使用空間，可以說是時間複雜度增加而空間複雜度減少。只要一個hash table放在cache裏面，用CPU運算來算出last name有沒有在裏面就可以大幅減少cache miss了！
首先是設計hash table的結構，如下圖
我用一個array存了30000個指標指向linked list的第一個entry。然後我參考了王紹華同學的list建構方式，把新的entry插在list的最前面，這樣就不需要每次新增項目的時後還要跑到list的最後面在加入了！
再來是實作的部份，我新增了phonebook_hash.c & phonebook_hash.h，把append改成void回傳然後把傳入值改成傳入lastName跟hash table：
```clike=
void append(char lastName[], entry *table[])
{
unsigned nHash = hash(lastName);
entry *e = (entry *) malloc(sizeof(entry));
e -> pNext = table[nHash];
if(!table[nHash]) {
table[nHash] = e;
} else {
table[nHash] -> pNext = e;
}
strcpy(e -> lastName, lastName);
}
```
標注螢光筆的地方很重要！我一開始沒有想到第一個放進去的entry會有問題所以compile完執行之後出現segmentation fault。第一次遇到這種情況，我又不會用gdb(今天看到老師要教耶~開心~~)，所以我只能每行每行加上printf慢慢找問題在哪裡，結果就如上面說的啦，在還沒有東西的時候用table[nHash] -> pNext = e會讓程式改到其他地方的記憶體位置，所以就segmentation fault了。
然後我修改了main.c calculate.c runtime.gp讓3個結果可以同時輸出，最後跑出來的結果：
>這裡也是參考王紹華同學的原始碼做修改的
cache miss的比例從原本77.455%到縮減entry 45.499%到最後hash只剩10.025 %！append()的時間只有增加一點點，而findName()幾乎是瞬間完成了！
## C語言 & Makeflie的語法
> 我在修改整個專案讓3個結果可以同時顯示花了我很多心力，來跟大家分享一下吧
### C語言的指示詞與Makefile在compile的配合
首先來說說我在這次作業學到的C語言特別用法：指示詞，指示詞其實我們一直在用就是在開頭要引入函式庫的#include跟要定義.h的時候的#ifndef都是指示詞的一種。這裡我用到很多#if defined () 跟 #else 還有 #elif 像是：
```clike=
FILE *output;
#if defined(OPT)
output = fopen("opt.txt", "a");
#elif defined(HASH)
output = fopen("hash.txt", "a");
#else
output = fopen("orig.txt", "a");
#endif
```
這些功能跟一般if else的判斷式功能上沒有甚麼不同 差別在於指示詞是給compiler看的，if else是在執行的時候才判斷的，所以當指示詞條件成立時，其他區塊的code不會被compile，在執行的時候就不會多浪費時間去判斷了！因為我的hash方法函式傳入值不同，所以在append跟findname我都有用指示詞判斷多寫出一塊專門給hash用的code，然後在Makefile裡面用-D來定義一個參數再用指示辭去判斷這個參數有沒有被定義。
> 理工科系的學生不要沒事就說「的感覺」這種話！
> 說話要精確，這不是「類似 function overloading」。只是 preprocessor 的參數而已
所以3個compile出來的執行檔大小就完全不一樣啦！
### Makefile語法
Makefile在各種linux的程式上非常常見，最常見的用法是在編譯前給他電腦的環境參數，譬如系統、GCC、其他相依性軟體的位置等等。其實Makefile也有點像是bash，他都是在執行一段shell指令。所以Makefile真的是非常強大阿！
首先是變數宣告：
```ruby=
CC ?= gcc
CFLAGS_common ?= -Wall -std=gnu99
CFLAGS_orig = -O0
CFLAGS_opt = -O0
```
Makefile的變數宣告像是js一樣不用給定變數型式，而`?=` 是如果沒有定義過再定義。
要叫用變數則要使用 `$(CC)` 或是 `${CC}`
這裡我有個小疑問，為甚麼CC跟CFLAGS_common要用`?=` 阿？
原來Makefile會自動去找環境變數，所以當環境變數裡面有定義過就不用在定義囉！
再來就是target，也就是makefile裡面類似function的區塊
```ruby=
all: $(EXEC)
SRCS_common = main.c
phonebook_orig: $(SRCS_common) phonebook_orig.c phonebook_orig.h
$(CC) $(CFLAGS_common) $(CFLAGS_orig) \
-DIMPL="\"$@.h\"" -o $@ \
$(SRCS_common) $@.c
phonebook_opt: $(SRCS_common) phonebook_opt.c phonebook_opt.h
$(CC) $(CFLAGS_common) $(CFLAGS_opt) \
-DIMPL="\"$@.h\"" -o $@ \
-DOPT=0 \
$(SRCS_common) $@.c
phonebook_hash: $(SRCS_common) phonebook_hash.c phonebook_hash.h
$(CC) $(CFLAGS_common) $(CFLAGS_opt) \
-DIMPL="\"$@.h\"" -o $@ \
-DHASH=0 \
$(SRCS_common) $@.c
```
target就是螢光筆劃起來的區塊開頭，all的意思就是當你執行`make`的時候要執行哪些target，其他如果要執行一個特定的區塊就打`make phonebook_orig` 就可以執行phonebook_orig這個target了。
再來是`：` 後面的東西是指相依性的檔案，Makefile會去比較輸出的檔案跟後面給定相依性檔案的時間關係，如果在：後面放的是原始碼的檔案，比較後發現輸出檔案比較新，表示原始碼沒有被改過，就不用在重新編譯一次，所以這一段target就會被跳過不執行。
後面的指令要用<tab>開頭代表指令。
- `$@` 是一個代名詞，代表target的名字。
- `$?` 是代表比target還新的相依性檔案中已更新的值
- `$<` 代表第一個相依性檔案
- `$*` targets 所指定的檔案，但不包含副檔名
- Makefile會先把整個檔案展開再決定變數值，所以變數會以最後定義的為主，如果想要讓他照Makefile裡面的順序，要把 `=` 改成 `:=`
- define的用法跟定義變數最大的差別是define可以包含斷行(\n)
```ruby=
define XXX
...
...
...
endef
```
- 在指令前面加上 `@` 代表執行該指令但不顯示在tremal上面
- 前面加上 `-` 代表如果該指令出錯仍繼續執行Makefile
- `.PHONY:target` 帶表這個target沒有輸出檔案，所以Makefile不會去檢查相依性
- Makefile會自動猜測編譯的檔案，如果要編譯foo.c要這樣寫：
```ruby=
foo.o: common.h
gcc -c foo.c
也可以直接寫成：
foo.o: common.h
```
Makefile會自動依你的副檔名猜測如何編譯它！
- Makefile裡面判斷式：`ifeq` `ifneq` `ifdef` `ifndef` 後面可以接 `else` 再用 `endif` 表示結束
- `include` 可以把後面指定的檔案全部引用進來
## Gnuplot研究
> 參考陳博聖同學2016q1 Homework 1: gnuplot 學習 讓我受益良多
```ruby=
reset
set ylabel 'time(sec)' `設定Y軸名稱`
set style fill solid `設定圖形屬性 fill solid是直方圖`
set title 'perfomance comparison' `設定設定圖片標題`
set term png enhanced font 'Verdana,10' `設定圖片的字體`
set output 'runtime.png' `設定輸出檔名`
plot [:][:0.060]'output.txt' using 2:xtic(1) with histogram title 'original', \
'' using ($0-0.1):($2+0.002):2 with labels title ' ', \
'' using 3:xtic(1) with histogram title 'optimized' , \
'' using ($0+0.1):($3+0.002):3 with labels title ' ', \
'' using 4:xtic(1) with histogram title 'hashed' , \
'' using ($0+0.3):($4+0.0015):4 with labels title ' '
```
- 基本語法：`using 2:xtic(1) with histogram title 'original', ` `'' using ($0-0.1):($2+0.002):2 with labels title ' ',`
第一行`using 2`的意思是以output.txt的第二欄當作資料， `xtic(1)` 是用第一欄當作X軸的標題(就是append()跟findname())
第二行是來設定直方圖上面的顯示數字位置(x軸位置):(y軸位置)
## 參考資料
與 [王紹華](https://embedded2016.hackpad.com/ep/profile/HrlSjJ931Te) 和 [陳博聖](https://embedded2016.hackpad.com/ep/profile/nIcuQa8uYsP) 共同討論
[性能优化的方法和技巧：总结](http://www.kernelchina.org/content/%E6%80%A7%E8%83%BD%E4%BC%98%E5%8C%96%E7%9A%84%E6%96%B9%E6%B3%95%E5%92%8C%E6%8A%80%E5%B7%A7%EF%BC%9A%E6%80%BB%E7%BB%93)
[从Java视角理解CPU缓存(CPU Cache)](http://astar.baidu.com/forum/forum.php?mod=viewthread&tid=460)
[30 天精通 Git 版本](https://github.com/doggy8088/Learn-Git-in-30-days)
[連猴子都能懂的Git入門指南](https://www.facebook.com/l.php?u=https%3A%2F%2Fbacklogtool.com%2Fgit-guide%2Ftw%2F&h=kAQHuJXzV&enc=AZOlF8WR2Hn5Af9dS28VCUg4Mdk6DOG66zUJm37bWYbvgVbi89mGF1yDj5h4ABtS4kdYKLmbKByx5aNjPlVYrR1DXl3fvDc90mbKwWhmu2UhWZhFRRLcU_pRnnAykadGExT8I8NfsuPkTRdqheJmbIM-tbn2yxJoCe298IIKZuThwjB0VatCMDHeM_f9yQC2t4c&s=1)
[gnuplot.source](http://gnuplot.sourceforge.net/docs_4.2/node458.html)
資工wiki
老師youtube講解題目
Sign in with Wallet
Connect another wallet