# 2017q1 Homework1 (phonebook) contributed by < `laochanlam` > ###### tags: `laochanlam` ### Reviewed by `yanglin` - 實驗裡面提到預先 allocate 350000 筆 entry 的資料，這個數字是如何得來的？是從輸入資料的規模得到的嗎？那在現實狀況中，要如何決定 memory pool 的大小？ - [commit 75f65b8](https://github.com/laochanlam/phonebook/commit/75f65b8216c577465742db8d166f044d1e5a0b69)， commit message 的長度超過一行72個字元，而且有些冗余的情報。 - 只有使用一種 hash function 做測試，是否能夠比較不同種 hash function 的 performance？ ### Reviewed by `Cayonliow` * 你所使用的 hash function 的參考資料是跟我一樣的， 裏頭的 DJBHash 會更快， 利用不同方式的乘法的復雜度來達到更快的速度， 可以看看[我的共筆](https://hackmd.io/s/r1i2_OhFx#%E5%84%AA%E5%8C%96%E7%89%88%E6%9C%AC) * 沒有提到 如何選取跟制定 hash table 的大小， 如果太大或太小又會怎樣 ## 開發環境 - Ubuntu 16.10 (64bit) >請列出硬體相關資訊，如：cache, memory >[name=課程助教][color=red] >已補上，感謝提醒！ >[name=laochanlam][color=blue] ``` Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian CPU(s): 4 On-line CPU(s) list: 0-3 Thread(s) per core: 2 Core(s) per socket: 2 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 61 Model name: Intel(R) Core(TM) i7-5500U CPU @ 2.40GHz Stepping: 4 CPU MHz: 2400.878 CPU max MHz: 3000.0000 CPU min MHz: 500.0000 BogoMIPS: 4788.90 Virtualization: VT-x L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 4096K NUMA node0 CPU(s): 0-3 ``` ## 相關連結 - [2017 年春季作業說明](https://hackmd.io/s/Bk-1zqIte#) - [2017q1 Homework1 (作業區)](https://hackmd.io/MYJjEYGZITgWgOwCMAmw4BYYwAxyQQKxwBmwGOkAHMDeEgGxA===?view) - [B01: phonebook作業要求](https://hackmd.io/s/rJYD4UPKe#b01-phonebook) - [phonebook Github連結 ( laochanlam ) ](https://github.com/laochanlam/phonebook) - [作業解說 video](https://www.youtube.com/watch?v=ZICRLKf_bVw) - [課程進度與開放資源 Wiki](http://wiki.csie.ncku.edu.tw/sysprog/schedule) ## Phonebook 開發紀錄 ### Optimize 方案 1： 縮小 entry 的 size 理解完整個專案後，終於開始動工了！ 先是依照老師的提示把 entry 的 size 縮小，把除lastName以外的資料都存到新的 struct 中，並在原來的 struct 中建立一個指向 detail 的 pointer 。 #### 原來的版本 ```C 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; ``` 使用Perf分析cache-misses的情況，原來的大約是81%。 ``` Performance counter stats for './phonebook_orig' (100 runs): 3,430,005 cache-misses # 81.729 % of all cache refs ( +- 0.03% ) 4,196,826 cache-references ( +- 0.19% ) 261,712,845 instructions # 1.34 insn per cycle ( +- 0.02% ) 194,998,572 cycles ( +- 0.26% ) 0.066929775 seconds time elapsed ( +- 0.31% ) ``` #### 優化後的版本 ```C typedef struct __PHONE_BOOK_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; typedef struct __PHONE_BOOK_ENTRY { char lastName[MAX_LAST_NAME_SIZE]; struct __PHONE_BOOK_ENTRY *pNext; struct __PHONE_BOOK_DETAIL *pDetail; } entry; ``` cache-miss變成69％了！！ ``` Performance counter stats for './phonebook_opt' (100 runs): 1,223,454 cache-misses # 69.446 % of all cache refs ( +- 0.25% ) 1,761,727 cache-references ( +- 0.99% ) 242,934,591 instructions # 1.74 insn per cycle ( +- 0.02% ) 139,951,145 cycles ( +- 0.91% ) 0.048685568 seconds time elapsed ( +- 1.07% ) ``` 附個小圖： ![Optimize1](http://i.imgur.com/vYzt8hq.png) ### Optimize 方案 2： 利用 Hash function 儲存資料 接下來要進行 Hash 的優化，在參考完[各种字符串Hash函数比较](https://www.byvoid.com/zhs/blog/string-hash-compare)一文及學長姐們的共筆後，決定使用 BKDRHash 來進行本次的優化！ <br> 下方是從[各种字符串Hash函数比较](https://www.byvoid.com/zhs/blog/string-hash-compare)中抓到的 **BKDRHash function**。 ```C unsigned int BKDRHash(char *str) { unsigned int seed = 131; // 31 131 1313 13131 131313 etc.. unsigned int hash = 0; while (*str) { hash = hash * seed + (*str++); } return (hash & 0x7FFFFFFF); } ``` >其中```return (hash & 0x7FFFFFFF)```此處有個不解，查資料時有查到說 ```& 0x7FFFFFFF``` 是為了讓其成為 positive integer ，但既然這個 Hash function 的 return type 已經是 unsigned int ，為何還要 ```& 0x7FFFFFFF``` 而不是 ```& 0xFFFFFFFF``` 呢？ >[name=laochanlam][color=blue] :::danger 盡信書不如無書，你為何不做實驗並分析呢？ 認真看 hash value 的分佈 --jserv ::: <br> 完成了！ 要注意的地方是可能會發生碰撞，而且 Table Size的選取也十分重要。 附個小圖: ![Optmize2](http://i.imgur.com/gdhDuUb.png) 做了 Hash 的優化後 findName() 的時間超級快，不過由於在 Hash table 中採用 Link list 來防止碰撞的緣故，append（）的時間加長了不少。 :::danger 提出具體縮減 `append()` 時間成本的機制 --jserv ::: >好 >[name=laochanlam][color=blue] ``` 416,554 cache-misses # 41.136 % of all cache refs ( +- 0.51% ) 1,012,639 cache-references ( +- 0.50% ) 239,848,481 instructions # 1.58 insn per cycle ( +- 0.02% ) 152,120,552 cycles ( +- 0.28% ) 0.051797760 seconds time elapsed ( +- 0.30% ) ``` Cache miss 又減少了！ ### Optimize 方案 3： 利用 memory pool 改善 append() 時間 在參考 [ierosodin 的共筆](https://hackmd.io/s/SJ4uqs9Yx#)後,有提到可以用 memory pool 的方法改善 append() 的效能，所以來嘗試一下，先分配一個 ```sizeof( 350000 * entry )``` 大小的連續空間當作 memory pool ,在需要時才向 pool 申請空間。 效能分析附圖： ![Imgur](http://i.imgur.com/JMiRGph.png) 雖說 append() 的時筆是減少了，可是減少的程度遠遠不及[ierosodin 的共筆](https://hackmd.io/s/SJ4uqs9Yx#)中來得多，經過思考後可能是 hash table size 的取值不當導致的，所以嘗試改善 table size 的大小。 <br> 經過一番沒有進展的改善後...才發現我有一個地方少寫一行程式碼... 改回來後： ![Imgur](http://i.imgur.com/oYIg2k7.png) 而且 cache miss 也減少了 ``` Performance counter stats for './phonebook_opt_hash_pool' (100 runs): 192,884 cache-misses # 20.701 % of all cache refs ( +- 1.90% ) 931,771 cache-references ( +- 0.96% ) 160,539,514 instructions # 1.47 insn per cycle ( +- 0.04% ) 109,119,512 cycles ( +- 0.71% ) 0.038024759 seconds time elapsed ( +- 0.84% ) ``` 減到 20% 。 <br> ~~總算老懷安慰。~~ ### 回答問題環節： 本例選用的 dataset (也就是輸入電話簿的姓名) 是否存在問題？ <br> ### 1. 有代表性嗎？跟真實英文姓氏差異大嗎？ 我認為代表性不強，畢竟這個世界上英文姓氏 X Y 作開首的遠遠比其他字母來得少，在搜索算法的資源分配可依據字母出現的頻率作調整； ``` Initial Percentage a 5.857 b 4.183 c 6.501 d 6.664 e 4.154 f 1.569 g 2.937 h 2.028 i 0.661 j 11.961 k 3.709 l 5.087 m 9.074 n 1.652 o 0.407 p 2.821 q 0.032 r 7.151 s 5.583 t 3.795 u 0.020 v 1.347 w 2.477 x 0.010 y 0.205 z 0.109 ``` Source from : [Answers](http://answers.google.com/answers/threadview/id/347668.html) 而且本例子中並沒有考慮名字重覆的情況，像是 1990 年代美國最常見姓氏的比例： ``` Name % 1. Smith 1.006 2. Johnson 0.810 3. Williams 0.699 4. Jones 0.621 5. Brown 0.621 6. Davis 0.480 7. Miller 0.424 8. Wilson 0.339 9. Moore 0.312 10. Taylor 0.311 ``` Source from : [Most Common Surnames in the United States 1990](http://surnames.behindthename.com/top/lists/united-states/1990) 但是在現實世界中這情況絕不罕有。 ### 2. 資料難道「數大就是美」嗎？ ### 3. 如果我們要建立符合真實電話簿情境的輸入，該怎麼作？ - 針對字母頻率不同的情況，我們可以在資料結構或查詢算法中，對字母搜尋及儲存的優先順序作調整，把更多的儲存空間讓給 ```a``` ```o``` 等等常見的字母，提升整體效能。 - 針對姓名相同的情況，我們可以給予多項搜尋資訊的輸入，或是二次搜索的回饋等功能，使查詢者能在"芸芸眾生"中找到要尋找的目標。 --- ## 補充知識 - [x] Cache - [x] Perf - [x] gnuplot - [x] astyle - [x] Makefile - [x] Hash function --- ## Cache 若要查找的 memory location 在 cache 中， CPU 從 cache 中讀取或寫入數據，就是 **cache hit** ，反之若要查找的 memory location 不在 cache 中，就為 **cache miss** 。 #### 參考及引用資料 [cache 原理和實驗](https://hackmd.io/s/S14L26-_l#) [cache entry相關資料](http://www.cnblogs.com/miaoyong/p/3416320.html) --- ## 效能分析工具: Perf 安裝完成後我是先把路徑於 `/proc/sys/kernel/perf_event_paranoid` 的值修改掉，不然每次都要sudo很麻煩。 > kernel.perf_event_paranoid 是用來決定你在沒有 root 權限下 (Normal User) 使用 perf 。 > * `2` : 不允許任何量測。但部份用來查看或分析已存在的紀錄的指令仍可使用，如 perf ls、perf report、perf timechart、 perf trace。 > * `1` : 不允許 CPU events data。但可以使用 perf stat、perf record 並取得 Kernel profiling data。 > * `0` : 不允許 raw tracepoint access。但可以使用 perf stat、perf record 並取得 CPU events data。 > * `-1`: 權限全開。 較常用的指令們 - `perf top` - `perf stat` - `perf record` - `perf report` #### 參考及引用資料 [perf 原理和實務](https://hackmd.io/s/B11109rdg#) --- ## 製圖工具: gnuplot - 繪圖 ```$ gnuplot [Script]``` - 查看圖片 ```$ eog [jpg/png...]``` 更多用法參詳[這裡](https://hackmd.io/s/Skwp-alOg) #### 參考及引用資料 [gnuplot 語法解說和示範](https://hackmd.io/s/Skwp-alOg) [gnuplot 读取逗号分隔的数据文件 ](http://blog.csdn.net/liyuanbhu/article/details/8516417) --- ## 程式碼格式化工具: astyle 先來看一下本次作業所要求的規範 ``` $ astyle --style=kr --indent=spaces=4 --indent-switches --suffix=none *.[ch] ``` - ```--style=kr``` 用K&R的風格進行編程 - ```--indent=spaces=4``` 四個空格 - ```--indent-switches``` 關於Case的縮排 > Indent 'switch' blocks, so that the inner 'case XXX:' headers are indented in relation to the switch block. - ```--suffix=none``` 不保存原始文件 - ``` *.[ch]``` 所有的.c或.h檔 #### 參考及引用資料 [Astyle：代码格式化工具简明指南](http://blog.csdn.net/xiaotao2004/article/details/1560538) [astyle格式化代码](http://gaylord.iteye.com/blog/2090616) --- ## Makefile #### 參考及引用資料 [Makefile 語法和示範](https://hackmd.io/s/SySTMXPvl) --- ## Hash function #### 參考及引用資料 [hash function 觀念和實務](https://hackmd.io/s/HJln3jU_e) [各种字符串Hash函数比较](https://www.byvoid.com/zhs/blog/string-hash-compare)
Last changed by  
 
Chan Lam Lao
449
Published on HackMD