Try   HackMD

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