因為在老師推薦lubuntu之前就灌了雙系統,選用Ubuntu 14.0.4,之前有灌過作業系統,但是是直接全部刷掉,所以每一步都很隨便,這次要灌雙系統,如果踏錯一步可能就回天乏術(怕怕),特別是在分割磁碟的地方特別小心:
分割了50GB給Ubuntu的根目錄 / 以及 2GB 給 SWAP
在安裝雙系統時,設定開機選項為Ubuntu的grub,因為看網上好像有人因為選Windows boot manager而找不到linux的開機口,雖然選擇了grub,而grub預設開機選項為Ubuntu,而且只有10秒的時間可以選擇,但是我平常還是會使用windows,因此會有需求開機預設為windows,查了一下:
我主要是改這兩個設定而已,再執行# sudo update-grub ,更動將會自動寫入grub.cfg
結果圖:
參考資料:
GRUB2中文指南第二版
GRUB 2 是在 10.04 以後才於許多作業系統中使用
參考了DADA的筆記 ,找到這篇BASH color prompt 才知道可以改Terminal的顏色
參考自 凍仁的筆記
vim是vi的進化,再編輯檔案時,會用顏色來編式不同的文˙字,可是跟以前用的編輯器(ex.notepad++)之類的比起來,不能自動縮排讓手酸的要命,所以就來搬救兵了
照著這篇,我加了這個設定
本來有加入set number顯示行號,結果複製程式碼時,行號也過來了,所以乾脆關掉
Makefile學習
之前摸Linux時是碰一套叫LAMMPS的科學計算軟體,makefile只是把路徑填進去,未深入了解
老師提供的教學,其他教學
以下是Makefile的基本編譯格式:
請讀第一手的資料: 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: 165+102+5+2+(alignment)+8(pointer)
字串陣列總合是123 由於此struct最大元素為8byte,所以alignment是8byte,所以123要加上5btye,最後加上8byte指標=136
entry大小為136byte,很快就會佔滿cache,cahce-miss也就很多,如果能減少entry大小,cache就能容納更多資料,cache-miss也能減少
因為在執行findName()時只會用到lastName,所以把其他資料包進detail裏面
新的entryˇ大小為32byte
Performance counter stats for ’./phonebook_opt1’ (100 runs):
cache-miss由93% -> 80%,執行時間也有縮短,這些節省的時間就是原本受cache-miss影響。
使用 Hash funtion
我第一次使用的hashfunction和hashtable:
SIZE = 100
hashtable append()
結果跑了兩分鐘,append()都沒結束(冏),果然35萬筆資料不是蓋的QQ,每個,這次改成array大小為300,同時也要更改hashfunction的mod值,
發現時間還是太久了,但是原本這個hashfunction產生的值大約在5百多,所以要再加快的話,勢必要用不一樣function,
第三次改成將ASCIIcode做相乘,hash value平均大約到8千萬,以3萬的array去做hash table
跑出來成績沒有別人好,但是已經是大進步了
跟自己比!
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
可以看到幾乎所有array都有hash到,所以linked list搜尋長度自然也減小,減少excutiontime和cache-miss
另外,因為append時間過長,主因是在延伸linked list時,需要向後爬很久,和 王紹華 討論後,發現可以把新增的資料放在第1個entry這樣就不必每次都要爬到最後了
新的append():
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是一個免費且功能強大的繪圖軟體,但都是由文字指令來使用,也因為這樣不同的組合會有無限可能,製造出自己想要的圖表
這是我最後的runtime.gp
本來也是看不懂,所以試著改,沒想到改對了,但還是不知道在幹嘛。後來看過別人的hachpad ,才比較懂一些:
第3行後的using前都有個空白的單引號,代表同上的檔案
** with labels
->做標籤,第一個參數和第二個參數為座標位置,第三個參數為要印出的字串,也就是資料本身, $2-4 -> 一樣是第某column的資料,只用在用算時,區別常數與參數, title ’ ’ = notitle -> 不需標題#
為註解,但是不可以在 \ 後面,\ 後面連空白都不能有(上面只是做說明多加的)參考資料
與同學 黃鏡清 王紹華 共同討論
GRUB2中文指南第二版
assert manual
gnuplot.source
老師的案例分析
http://enginechang.logdown.com/posts/249025-discussion-on-memory-cache