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

GRUB_DEFAULT=0   # 設定預設選單選項  在 /boot/grub/grub.cfg 中的第一筆「選單選項」為 0，第二筆為 1，以此類推
GRUB_TIMEOUT=10  # 多久之後自動以預設作業系統開機

我主要是改這兩個設定而已，再執行# sudo update-grub ，更動將會自動寫入grub.cfg
結果圖：

參考資料：
GRUB2中文指南第二版

GRUB 2 是在 10.04 以後才於許多作業系統中使用

修改Terminal顏色：

參考了DADA的筆記 ，找到這篇BASH color prompt 才知道可以改Terminal的顏色

修改vim

參考自 凍仁的筆記
vim是vi的進化，再編輯檔案時，會用顏色來編式不同的文˙字，可是跟以前用的編輯器(ex.notepad++)之類的比起來，不能自動縮排讓手酸的要命，所以就來搬救兵了
照著這篇，我加了這個設定

set ai           " 自動縮排
set tabstop=4    " 自訂縮排 (Tab) 位元數
set shiftwidth=4 " 自訂縮排 (Tab) 位元數 符合格式

本來有加入set number顯示行號，結果複製程式碼時，行號也過來了，所以乾脆關掉

案例分析

Makefile學習

之前摸Linux時是碰一套叫LAMMPS的科學計算軟體，makefile只是把路徑填進去，未深入了解
老師提供的教學，其他教學

以下是Makefile的基本編譯格式:

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
收到！！在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

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: 165+102+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裏面

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()

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

    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

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

老師的案例分析

# 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