2016q3 Homework#1 : phonebook

Linux環境

對於Linux我在2年級去比叢集電腦的時候就有接觸了，電腦裏面也已經裝好Linux Mint了，剛好Mint也是Debian系列的，所以我就用Linux Mint來當作我的開發環境囉~

這裡我遇到了一個小問題，我之前沒有更新版本所以我的Linux核心版本是unstable的發行版(3.8.11)所以找不到linux-tools，這讓我研究了好久…所以記得要把系統更新到最新喔


$ sudo apt-get update  //更新軟體列表
$ sudo apt-get dist-upgrade  //更新Linux發行版本

還有另一個問題我看了超不順眼…就是在linux上面執行chrome會有文字變成標楷體！我特地去找了方法來解決
其實只要把fonts-arphic-ukai 跟fonts-arphic-uming 解除安裝，我的思源黑體就回來了！


$ 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，然後用：


$ git clone your git url    //譬如：git clone https://github.com/workfunction/phonebook.git

先clone下來你自己的repository到你的電腦裏面，之後開始修改你要修改的檔案
接下來要對每個修改過的檔案用：


$ git add file you edit   //譬如： git add phonebook_opt.c 或是用：git add . 提交全部的檔案進索引

這一步就是在把檔案註冊至索引中。
接著提交修改版本到git中(這裡都是在本地電腦裏面clone下來的repository做修改)用：


$ git commit -m "your change log title"   //譬如： git commit -m "1st opt"

這樣一來你就在電腦裡做好一個修訂版本囉！
注意一點如果打了上面的跳出：









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啦，用下面指令


$ git push origin master

這樣就可以把你電腦裏面的修訂版本放到GitHub裏面了喔！
歐對要記得先做astyle再add喔！！

Cache Miss分析

我看完cache miss的成因才真正了解問題的點在哪裡下面是我對這個問題的分析

CPU內部有一個register跟3個層級的cache，下面是不同層級的cache到CPU所需的時間

從CPU到大約需要的CPU周期大約需要的時間






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的數字喔黃鏡清（Jason）

我翻閱了幾個前面學長姐的實作，用刪減Struct的大小，只留下Last name跟指標讓cache裏面可以存更多Last name，於是我跟著這種想法實作。

理工科系的學生應該避免說「我也覺得很有道理」這種話，真相只有一個

我把entry內容拆開，把另外的資訊刪掉並加了一個指標*pDetail指向令一個struct Detail但是執行結果…

兩個時間都變長了阿！比對後原來螢光筆的那行其他人都沒有…









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：












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 像是：








    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真的是非常強大阿！
首先是變數宣告：




CC ?= gcc
CFLAGS_common ?= -Wall -std=gnu99
CFLAGS_orig = -O0
CFLAGS_opt  = -O0

Makefile的變數宣告像是js一樣不用給定變數型式，而?= 是如果沒有定義過再定義。
要叫用變數則要使用 $(CC) 或是 ${CC}

這裡我有個小疑問，為甚麼CC跟CFLAGS_common要用?= 阿？
原來Makefile會自動去找環境變數，所以當環境變數裡面有定義過就不用在定義囉！

再來就是target，也就是makefile裡面類似function的區塊




















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)





define XXX
...
...
...
endef

在指令前面加上 @ 代表執行該指令但不顯示在tremal上面
前面加上 - 代表如果該指令出錯仍繼續執行Makefile
.PHONY:target 帶表這個target沒有輸出檔案，所以Makefile不會去檢查相依性
Makefile會自動猜測編譯的檔案，如果要編譯foo.c要這樣寫：




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 學習讓我受益良多













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軸位置)

參考資料

與王紹華和陳博聖共同討論
性能优化的方法和技巧：总结
 从Java视角理解CPU缓存(CPU Cache)
30 天精通 Git 版本
 連猴子都能懂的Git入門指南
 gnuplot.source
資工wiki
老師youtube講解題目