2018q1 Homework1 (phonebook)

# 2018q1 Homework1 (phonebook) contributed by <`sss31277`> >[name=黃士洋更新][time=Tue, Mar 20, 2018 10:21 PM] ### Reviewed by `rex662624` * 發現 BKDRHash 的平均得分最高，也可以在 BKDRHash 內比較不同 table size 和不同 seed 所造成的影響。 * 發現 hash 的 append 花了較多時間，但現實的狀況 append 完不會馬上 find ，而是兩者分開，因此可以分開做效能評估。 * github commit 好像只有標題，沒有內文詳述做了何種更動。 >目前對第一及第三點做改善， >第一點的實驗以及分析推測在下方部份 >第三點的改善在今天聽過老師一點點修正皆可以commit在做改進 [TOC] --- ## 前置作業學習 * 安裝linux作業系統 * linux指令學習 * 觀看作業教學影片 * 學習perf工具 * 學習gnuplot工具 * 學習HackMD編輯方式 * 學習github同步上傳等操作 > > --- ## Github摸出來的方法 * [ssh綁定](http://wiki.csie.ncku.edu.tw/github) * 複製不成功可以手動```ls ~/.ssh``` ```cat ~/.ssh/rsa檔```複製 * 綁定好後我直接在 [Embedded2016/phonebook](https://github.com/embedded2016/phonebook) 做 ``fork`` 到自己的帳號裡面。 * 接著在專案底下複製自己的網址 ![](https://i.imgur.com/IICyW7r.png) * 在command line輸入複製專案 ``＄git clone 網址`` * 接著如果改動程式碼要同步github輸入 ``＄git add 改的檔案`` * 新增commit ``＄git commit`` * 最後push ``＄git push`` * 上github看有沒有改動過，有的話就成功了。 #### [未來工作]：了解更完整的git指令知識 --- #### astyle規範 ``` $ astyle --style=kr --indent=spaces=4 --indent-switches --suffix=none *.[ch] ``` --- ## phonebook作業 ### 實驗：測試orig的phonebook的效能 ```make cache-test``` ``` Performance counter stats for './phonebook_orig' (100 runs): 2,034,129 cache-misses # 94.926 % of all cache refs ( +- 0.45% ) 2,142,851 cache-references ( +- 0.45% ) 262,565,952 instructions # 1.34 insns per cycle ( +- 0.02% ) 195,946,512 cycles ( +- 0.50% ) 0.075913467 seconds time elapsed ( +- 1.88% ) ``` #### cache miss 高達 94.926% ##### 可能原因：entry過大，cache沒辦法放太多entry，程式中只搜尋last_name ### 解法1：將struct拆解，目前不需要的資訊不要佔用cache空間 ```clike= typedef struct __PHONE_BOOK_ENTRY { char lastName[MAX_LAST_NAME_SIZE]; struct Info *info; struct __PHONE_BOOK_ENTRY *pNext; } entry; typedef struct Info { 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]; } data; ``` #### 實驗 ##### 撞掉cache ```$ echo 1 | sudo tee /proc/sys/vm/drop_caches``` ##### cache miss測試 ```＄ make cache-test``` ##### phonebook中砍掉執行檔以及png ```$ make clean``` ##### cache-test並且畫出append findName的Histogram ```$ make plot``` ``` Performance counter stats for './phonebook_opt' (100 runs): 379,687 cache-misses # 70.876 % of all cache refs ( +- 0.09% ) 535,706 cache-references ( +- 0.27% ) 245,535,162 instructions # 1.76 insns per cycle ( +- 0.02% ) 139,323,326 cycles ( +- 0.18% ) 0.048640435 seconds time elapsed ( +- 1.51% ) ``` ##### 降低至67.7％，但效果仍有待改善。 1. 先行閱讀 [cache 原理和實驗](https://hackmd.io/s/S14L26-_l#) * ```/sys/devices/system/cpu/cpu0/cache``` 裡面查看L1資訊 * cache size : 32KB * 8-way associate * n-way associative: 把 cache 分成多個 set，CPU 必須檢查指定 set 內的每個 block 是否有可用的 cache，利用tag去驗證 * 優點：搜尋時間短（相對fully）且 hit rate 高（相對1-way） * line size = 64B * L1 分成L1 instruction, L1 data 2. 計算cache中能存取的資料數目 * 32x1024/136＝240.xx 只能在cache中快取240筆資料 * 32x1024/32 = 1024 筆資料 3. "推算"67.7％ from [Daniel Chen 共筆](https://hackmd.io/s/BJ9IL2wdM#) * 由2的第二點得知cache中一block能快取兩筆entry * 若相鄰的 entry 存在連續的記憶體空間中，則每兩次 access 就有可能發生一次 cache hit，結果來看 cache miss 約爲 66%，很接近 1/2。 * ~~沒有了解，下次上課請教助教~~ :::danger 依據你對計算機結構的認知，能否「推算」出 67.7% 怎麼來呢？另外，文字訊息「不要用圖片」來表示，否則無法檢索和部分擷取。 :notes: jserv ::: :::info 收到 cache miss rate研究中.. 下次上課cache miss rate詢問助教 ::: ##### 畫張圖看一下時間 ```＄ make plot``` ![](https://i.imgur.com/4vvM9IE.png) >參閱資料：[淺談cache memory](http://opass.logdown.com/posts/249025-discussion-on-memory-cache) , [cache 原理和實驗](https://hackmd.io/s/S14L26-_l#) * 還沒縮減尺寸前的entry size是136 bytes，縮減後的size是32 bytes * 136B / 64B = 2.xx 超過兩個Blocks * 那如果我們進行append以及findName每次存取cache皆必須存取三個blocks並做驗證(tag) * 一旦miss置換的penalty相對縮小entry size也更大 * 32B / 64B = 0.5 一個Block可以存取兩個entry 進而減少cache miss * 進行append以及findName只需要存取一個bolck其中有兩筆entry，因此綠色軸的時間減少 :::danger 什麼叫做分析？你該拿出計算機組織與結構裡頭的背景知識來，能否從 N-way set associative cache 的行為來解釋 (當然要計算得出來！)，而不是說「喔，這樣會變快，我好棒」這種「文組^TM^」說法。到目前為止，你覺得哪裡表現出「你的專業」呢？ :notes: jserv ::: :::info 努力改進下次上課詢問助教 n-way的直接關係 ::: --- ### Cache理解心得我自己的電腦是8-way （後來發現是主流way數） n-way 介在 fully 跟 1-way(direct)中間 fully 理論上cache miss應該會最小但是不可能用fully 我們是快取不是慢取 fully搜尋的速度過慢 worst case是搜完整個cache發現沒有然而也不可能用direct(1-way)存取很快但是時常cache miss所以常常要置換也有可能因為locality的關係一直在置換浪費時間然而8-way 8是蠻神秘的我也不太清楚原因可能原因：這樣算下來一個line(block)會擺好一個資料的大小吧可能要手動算一下一個line(block)多少 **推斷為一個 block8 Bytes可以放置整數倍數的大多數型態** 可在下方路徑查詢各種cache資訊，以我的電腦而言： 32KB cache size (index1 for data) 64B line size 8B block size 8 way-associate ##### 專門用來查詢 CPU 資訊的工具指令: ```lscpu``` ```cat /proc/cpuinfo``` ##### [linux中查看cache](http://blog.csdn.net/ai297313/article/details/44726187) ``` cd /sys/devices/system/cpu/cpu1/cache ``` --- #### 讀書筆記彌補基礎不足 [C語言:結構變數與指標](https://hellolynn.hpd.io/2017/05/30/c-%E8%AA%9E%E8%A8%80%EF%BC%9A%E7%B5%90%E6%A7%8B%E8%AE%8A%E6%95%B8%E8%88%87%E6%8C%87%E6%A8%99/) ```student *one = &lynn;``` * student : 結構(struct) * *one :指標 * &lynn ：已宣告為student結構並初始化好內容的變數位址意思是指向stduent類型的結構 ```(*one).age``` 與 ```one->age``` 等價 * 前者我自己翻譯 one所指內容的age * 後者我自己翻譯 one所指的內容誰的?age的 ```void new_one(student *one){...}``` * 參數需求:student結構的一指標 ```new_one(&lynn);``` * 參數的記憶體位址傳給*one指標接 ``` girls TWICE[3] ＝ {17,{'t','z','u','y','u','\0'}, 19,{'m','i','n','a','\0'}, 20,{'m','o','m','o','\0'}, }; girls *ONCE = TWICE; ``` * 以girls結構宣告一個矩陣 * 再用一個*ONCE指標矩陣指在TWICE的開頭 --- ### 解法2：嘗試使用HashTable資料結構 * Hash function Suvey 資料：[link1](https://www.byvoid.com/zhs/blog/string-hash-compare) BKDRHash 的平均得分最高 * 查一下理由跟原因：[link](http://blog.csdn.net/wanglx_/article/details/40400693) * [link1](https://www.byvoid.com/zhs/blog/string-hash-compare) BKDRHash 在第二種數據（皆是英文單字組成的句子）做hash的碰撞測試，數據結果分數非常高 * [link1](https://www.byvoid.com/zhs/blog/string-hash-compare) 原po也推薦BKDRHash編碼，方便記憶數學也相對簡單 * 目前選定BKDR hash function * 並以31作為seed * 1024作為hash table大小（後來改成2729）原因修正前一次實驗問題補上 * collision解決的方法 * 線性探測 prob linearly * 鏈結法 chaining * 從hash table指出去的ptr插入 * 從hash table插入最後一個 (這次實作的方式) * 分析及探討findName append時間 * 首先，得到findName非常少量的時間 * 推斷原因:解決collision使用的是chaining，在slot後面用link list做連結，若夠分散的話，時間複雜應該可以在O(1)常數內。 * 再來，append多出了蠻多時間 * 推斷原因:比起orig版本我們跑了hashFunction多了不少的運算時間。 * ![](https://i.imgur.com/R9OIfhF.png) #### 實驗結果 ``` Performance counter stats for './phonebook_opt' (100 runs): 330,629 cache-misses # 48.387 % of all cache refs ( +- 0.06% ) 683,306 cache-references ( +- 0.36% ) 240,757,370 instructions # 1.70 insns per cycle ( +- 0.02% ) 141,370,734 cycles ( +- 0.19% ) 0.052443028 seconds time elapsed ( +- 2.02% ) ``` ### 修正前一次實驗問題 1. Hash table的buckets數目 * [Hash學習](http://blog.csdn.net/qll125596718/article/details/6997850)理解Hash table的一些觀念 * Buckets數目宜為質數，常理上除以質數的餘數將會較為分散 * Buckets大小不宜太大或太小，需要配合存放資料的量做調整 * 延伸上點，不只是資料量的問，更有資料輸入hash function得出的數值問題，以及cache大小是否能裝整個hash table 2. 將Hash table大小改成2729或許可以更大，再行實驗看看 * 得到了更低的cache miss 40%左右，下方顯示數據 * 原因:[使用Hash降低cache miss原因](https://www.zhihu.com/question/22911718)cache中存放的Hash table的每個 slot都盡可能直接選中，若cache miss即就要跳轉slot，就會成為cache miss * 未來實驗:若把bucket數設定更大的質數是否能降更低的miss rate呢? ``` 338,995 cache-misses # 40.667 % of all cache refs ( +- 0.10% ) 833,589 cache-references ( +- 0.29% ) 242,874,417 instructions # 1.67 insns per cycle ( +- 0.02% ) 145,334,671 cycles ( +- 0.20% ) 0.056764763 seconds time elapsed ( +- 2.40% ) ``` ### 改動seed並且分析其結果 * 將seed由原先的 31 改成 131 * 遇到了```./phonebook_opt: 程式記憶體區段錯誤``` * 上網查了一下是code有錯的可能很高 * 主要造成原因：存取無法定址的位址 * 把這段 ```hash = hash * seed + (*str++);```印出來 * 印出了這種數值 ``` 5004 -2084 ``` * 在往前印這兩個數值 ``` printf("*lastName:%d\n",*lastName); printf("hashNum*seed:%d\n",hashNum*seed); ``` * 低級錯誤：出現了負數 ``` lastName:97 hashNum*seed:-1278536584 return:-2084 ``` * 解決：將變數型態改成unsigned * 預期結果：應該不會差很多 * 實際結果：掉了2％，那會不會更大的seed可以讓return數值更分散呢？ ``` 363,379 cache-misses # 38.185 % of all cache refs ( +- 0.18% ) 951,621 cache-references ( +- 0.14% ) 240,020,531 instructions # 1.58 insns per cycle ( +- 0.02% ) 151,565,983 cycles ( +- 0.14% ) 0.069020022 seconds time elapsed ( +- 2.65% ) ``` ![](https://i.imgur.com/gmPL1dn.png) * 實驗：seed 變大改成 1313 以及 13131 * 跑完結果，cache miss rate幾乎沒有差別，僅有下降一點點幅度 * 但是計算時間大增把append的時間拉長1.2倍 * 想法：應該是在 5471 hash table大小中已經達到一定分散程度 ##### 探討問題： * cache miss降低的原因 * 改動hashtable大小或者seed實驗 * hash function實作文獻survey --- ###### tags: `course`

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.