2017q1 Homework1 (phonebook)

# 2017q1 Homework1 (phonebook) contributed by <==maxxacre==> ### Reviewed by `natetang` * 使用 hash function 改善後，為什麼 append() 時間不降反升?? * Hash table 的 size 應該可以調整看看會有什麼影響 * 尚未回答作業所詢問之問題 ### Reviewed by `cdq7` * Should divide into two commits if both the modifications are not closely related. * How come the optimised hash function does not show huge improvement to the original one? ## 開發環境 ``` Architecture: x86_64 CPU 作業模式： 32-bit, 64-bit Byte Order: Little Endian CPU(s): 4 On-line CPU(s) list: 0-3 每核心執行緒數：1 每通訊端核心數：4 Socket(s): 1 NUMA 節點： 1 供應商識別號： GenuineIntel CPU 家族： 6 型號： 158 Model name: Intel(R) Core(TM) i5-7500 CPU @ 3.40GHz 製程： 9 CPU MHz： 799.987 CPU max MHz: 3800.0000 CPU min MHz: 800.0000 BogoMIPS: 6800.00 虛擬： VT-x L1d 快取： 32K L1i 快取： 32K L2 快取： 256K L3 快取： 6144K NUMA node0 CPU(s): 0-3 ``` --- ## Git 指令學習 * 先在[github](https://github.com/sysprog21/phonebook) fork ==phonebook== * 下載 ==phonebook== ```shell git clone https://github.com/maxxacre/phonebook.git ``` * 建立目錄 ```shell git init ``` * 檢查修改過的程式碼 ```shell git status ``` * 上傳 ```shell git add . git commit -m "message" git push origin master ``` --- ## perf修改權限 1. 將kernel.perf_event_paranoid權限改成最大(-1) 2. 取消 kernel pointer 的禁用 ```shell $ sudo sh -c " echo -1 > /proc/sys/kernel/perf_event_paranoid" $ sudo sh -c " echo 0 > /proc/sys/kernel/kptr_restrict" ``` --- ## Origin 透過perf查詢origin所占時間發現findName()占了17.85% ```shell 39.18% phonebook_orig libc-2.23.so [.] __strcasecmp_l_avx 17.85% phonebook_orig phonebook_orig [.] findName 15.10% phonebook_orig libc-2.23.so [.] _int_free 7.03% phonebook_orig [kernel.kallsyms] [k] clear_page_c_e 3.86% phonebook_orig [kernel.kallsyms] [k] _raw_spin_lock 3.14% phonebook_orig libc-2.23.so [.] free 2.17% phonebook_orig phonebook_orig [.] main 1.67% phonebook_orig [kernel.kallsyms] [k] __rmqueue 1.34% phonebook_orig [kernel.kallsyms] [k] copy_user_enhanced_fast_string 1.22% phonebook_orig [kernel.kallsyms] [k] get_mem_cgroup_from_mm 0.93% phonebook_orig libc-2.23.so [.] __strcasecmp_avx 0.61% phonebook_orig [kernel.kallsyms] [k] get_page_from_freelist 0.50% phonebook_orig [kernel.kallsyms] [k] try_charge 0.47% phonebook_orig [kernel.kallsyms] [k] __alloc_pages_nodemask 0.47% phonebook_orig [kernel.kallsyms] [k] free_pcppages_bulk 0.46% phonebook_orig [kernel.kallsyms] [k] handle_mm_fault 0.38% phonebook_orig [kernel.kallsyms] [k] mem_cgroup_try_charge 0.36% phonebook_orig [kernel.kallsyms] [k] page_remove_rmap 0.36% phonebook_orig [kernel.kallsyms] [k] vm_normal_page 0.35% phonebook_orig phonebook_orig [.] free@plt 0.28% phonebook_orig libc-2.23.so [.] __GI___printf_fp_l ``` 執行 ==$ make cache-test== 發現cache miss 高達91.24% ```shell Performance counter stats for './phonebook_orig' (100 runs): 5,681,529 cache-misses # 91.240 % of all cache refs ( +- 0.11% ) 6,227,025 cache-references ( +- 0.07% ) 323,455,083 instructions # 1.50 insn per cycle ( +- 0.01% ) 216,202,224 cycles ( +- 0.08% ) 0.059083012 seconds time elapsed ( +- 0.43% ) ``` --- ## 開發進度 ### 未優化版本執行: ```$ ./phonebook_orig``` ```shell size of entry : 136 bytes execution time of append() : 0.036421 sec execution time of findName() : 0.004886 sec ``` 參考[0140454](https://hackmd.io/s/Bkx3cYX6#reviewed-bt-finalallpass)同學發現釋放memory不完整的情況導致memory leak 修改**main.c** ```clike if (pHead->pNext) free(pHead->pNext); ``` 改成 ```clike while(pHead->pNext) { entry *next = pHead->pNext; pHead->pNext = next->pNext; free(next); } ``` 使用valgrind 測試發現memory leak問題解決了 ![](https://i.imgur.com/r2CPeKp.png) ### 優化版本1 : 修改phonebook_orig.h struct ```clike 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內 ```clike typedef struct __PHONE_BOOK_ENTRY { char lastName[MAX_LAST_NAME_SIZE]; struct __PHONE_BOOK_LIST *pList; struct __PHONE_BOOK_ENTRY *pNext; } entry; typedef struct __PHONE_BOOK_LIST { 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]; } phbook_detail; ``` 執行```./phonebook.opt```後發現與未優化版本比較有提升 ```clike size of entry : 32 bytes execution time of append() : 0.030456 sec execution time of findName() : 0.002205 sec ``` 執行```$ make plot```得到gnuplot ![](https://i.imgur.com/a8lpLFS.png) > 筆電前幾天灌雙系統掛了，先用虛擬機QQ 近期會向同學借電腦測試使用structure 改動後發現cache miss 降低到63.683% 還是很高 ```shell Performance counter stats for './phonebook_opt' (100 runs): 1,779,126 cache-misses # 63.683 % of all cache refs ( +- 0.54% ) 2,793,722 cache-references ( +- 0.10% ) 284,955,038 instructions # 2.24 insn per cycle ( +- 0.02% ) 127,023,432 cycles ( +- 0.10% ) 0.034964356 seconds time elapsed ( +- 0.16% ) ``` ### 優化版本2 : Hash function (BKDR-hash) 看了一下[Hash原理](https://en.wikipedia.org/wiki/Hash_function)了解到它把資料分配到儲存位置再利用key丟到hash function 來算出資料應該存放在哪個index. ![](https://i.imgur.com/6YorOhP.png) ~~看到這張圖秒選DKDRHash~~ * [BKDR hash 推導](http://blog.csdn.net/wanglx_/article/details/40400693) hash table size 原先用12251 cache-miss 雖有降低過還在54.32% 我在想是因為collision次數高所以我把table size 提高到 46691 cache-miss下降到42.564% collision次數下降 ``` Performance counter stats for './phonebook_hash' (100 runs): 561,405 cache-misses # 42.564 % of all cache refs ( +- 0.92% ) 1,318,971 cache-references ( +- 0.29% ) 235,164,742 instructions # 1.89 insn per cycle ( +- 0.02% ) 124,104,841 cycles ( +- 0.29% ) 0.036242964 seconds time elapsed ( +- 0.57% ) ``` ### 效能分析圖 ![](https://i.imgur.com/4f1I0Xl.png) --- ## Week3 上課之後修改 [my week3 note](https://hackmd.io/EYNmCYDMBMFNwLQBYAcBmEyUEMDsCUQAGAVgRAEYRckkBjWYnIA=?both) 1. 簡潔程式碼 ==if(!strcasecmp(lastName,pHead->lastName) ~~==0~~ )== 2. malloc 可能會失敗(回傳<b>null</b>), 故做了一些判斷 ```clike if(pHead == NULL){ printf("no memory please check!\n"); return -1; }else{ printf("size of entry : %lu bytes\n", sizeof(entry)); e = pHead; e->pNext = NULL; } ``` --- ## 參考資料 * [phone book 作業區](https://hackmd.io/s/rJYD4UPKe) * [cache 原理和實驗](https://hackmd.io/s/S14L26-_l) * [perf 原理和實務](https://hackmd.io/s/B11109rdg) * [gnuplot 語法解說和示範](https://hackmd.io/s/Skwp-alOg) * [cpp分析工具](http://ivan7645.github.io/2016/07/01/linux_cppcheck/) * [valgrind memory leak偵測](http://blog.yslin.tw/2014/03/c-valgrind.html) * [共筆同學 1](https://hackmd.io/s/rJCs_ZVa#) * [共筆同學 2](https://hackmd.io/s/Bkx3cYX6#reviewed-bt-finalallpass)

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.