2017q1 Homework1 (phonebook) - HackMD

owned this note owned this note

<style> h2.part{color:#000000;} h3.part{color:#D92424;} h4.part{color:#005BB0;} h5.part{color:#FD6F0A;} h6.part{color:#4400B0;} </style> # 2017q1 Homework1 (phonebook) contributed by <`paul5566`> ### Reviewed by `claaaaassic` * 推上 Github 上的程式碼沒有符合一致的 coding style，如果你是使用 terminal 下 git commit 會給你提示訊息說明你哪裡有問題，commit 154d7c3cc2123d9a63a9f2362b54fa76094badb9 上面有別人給的建議，如果要修改掉這次的 commit messages 可以使用 `git commit --amend`，我使用 `git rebase -i` * 第二次改進的程式似乎是不會減少 cache-misses 也使得原本的 free 功能消失 ~~if (pHead->pNext) free(pHead->pNext);~~ ~~free(pHead);~~ ```clike= while((e = pHead)){ pHead = pHead->pNext; free(e); } ``` * 除了使用較小的結構，應該還有別的方法可以最佳化，像是使用 hashtable 大幅減少 findName() 的時間 * 在標點符號與英文與數字之間應該要留下空白，可讓人更好讀懂，可以在別人給予建議之後修正內容，不然會顯得你沒有在乎別人的看法。 * 心得後面的問題，`ifdef OPT` 是如果有定義 OPT 就可以不一定要 0，檔案讀寫可以 `man fopen/fclose/fgets/fprintf` 來讀文件比較好找到你要找的問題，至於 `git commit` 的練習可以在 client 端不斷練習只要不 `push` 基本上玩壞了弄不回來可以重新 clone 就好 ## 開發目標 <s>我基礎很爛,所以要是有心向學的人可以直接把頁面關掉參考別人資料。</s> :::danger 就是因為基礎不扎實，所以學習歷程才要詳盡列出，接受各界批評指教。不要強調自己非資工科系，我甚至沒受過高等教育。決心和實踐更重要 --jserv ::: 敝魯非資工科系因此我會先以讀懂code為主學習做最簡單的方法,操作界面工具開發為主 - 初步熟悉HackMD使用方式 - 初步熟悉linuix熟悉指令方式 - 簡單理解相關背景知識 - Perf的基本使用方式 - 理解cache miss(使用) ### HackMD 在看完助教大大清晰明瞭的[從無到有學習HackMD](https://www.youtube.com/watch?v=r5FOR-YU33c&t=1224s)後,覺得HackMD拿來作筆記蠻有用的比之前弄googledoc或是evernote好用非常多,可以提昇學習效益。e.g.程式的格式不會跑掉但我還是不知道到底要幹麻？所以決定先用抄襲的方式學習怎樣使用。因此我直接複製之前學長的格式來更改！！！ :::danger "example" 的縮寫是 [e.g.](https://en.wiktionary.org/wiki/e.g.)，不是 "ex"，後者是「前」女友一類詞彙的前綴，不要用錯了 --jserv ::: 方式就是進入別人作業頁面後進入編輯,然後點選坐上角的很像書的標示後觀看別人如何撰寫HackMD的語法,然後複製貼上別人的語法。 ### 初步學習linuix指令網路上google就有很多資料例如： [25 Linux commands for System Administrators](https://www.getfilecloud.com/blog/2014/01/25-linux-commands-for-system-administrators/#.WLvalyGGO00) [GNU/Linux 初學之旅](http://linux.vbird.org/linux_basic/0120howtolinux/0120howtolinux_3.php) [我自己整理的筆記](https://hackmd.io/s/SkXQqDWol) 感謝jserv大大的指證 ### 開發環境 #### Lubuntu 16.04 LTS 系統效能-指令 ``` $ lscpu ``` - CPU: Intel(R) Core(TM) i5-3210M CPU @ 2.50GHz - Mem: 8 GB - Cache: L1d cache: 32 KB L1i cache: 32 KB L2 cache: 256 KB L3 cache: 4096 KB ![](https://i.imgur.com/yQRa6pp.png) * [Portable Hardware Locality](https://www.open-mpi.org/projects/hwloc/) (hwloc) 指令 ``` $ lstopo ``` 這時後看compiler出現訊息會發現要安裝套件才能使用 ``` The program 'lstopo' can be found in the following packages: * hwloc * hwloc-nox ``` 因此要下指令去載這份套件 ``` $ sudo apt-get install hwloc ``` ## 案例分析 - Phonebook ### 目標 - **減少Cache miss** - **提升效能** #### ►根據[提示](https://hackmd.io/s/S1rbwmZ6)可以減少==Cache miss==或==提升效能==的修改方向： - [x] 改用較小的結構 ### 1. 未優化版本 #### ►原本的結構 ==**(共計 136 bytes)**== - 一個char佔1個byte,因此16+16+16+10+10+16+16+16+2+5=123 而在記憶體會有[alignment](http://stackoverflow.com/questions/381244/purpose-of-memory-alignment)所以之後有128-byte 最後加上pointer的size(在64-bit中為8-byte)：128+8=136 ```clike= #define MAX_LAST_NAME_SIZE 16 #define OPT 1 typedef struct __PHONE_BOOK_ENTRY { char lastName[MAX_LAST_NAME_SIZE]; char firstName[16]; char email[16];https://linux.die.net/man/3/strcasecmp 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; ``` #### ►執行時間 ``` size of entry : 136 bytes execution time of append() : 0.083878 sec execution time of findName() : 0.006866 sec ``` #### ►Memory Leakage #### [valgrind指令](http://ottoshare.blogspot.tw/2012/03/valgrind.html) ``` valgrind --leak-check=full ./phonebook_orig ``` 我使用 valgrind指令這個套件來檢視Memoey Leakage的問題 ``` ==20539== HEAP SUMMARY: ==20539== in use at exit: 47,586,264 bytes in 349,899 blocks ==20539== total heap usage: 349,906 allocs, 7 frees, 47,596,856 bytes allocated ``` #### ►Performance & Cache-misses(100 runs) 2,041,476 cache-misses # 96.129 % of all cache refs ( +- 0.41% ) 2,123,687 cache-references ( +- 0.39% ) 261,088,821 instructions # 1.46 insns per cycle ( +- 0.02% ) 179,254,129 cycles ( +- 0.31% ) 0.069793722 seconds time elapsed ( +- 1.80% ) ### 2. 優化版本 - ==使用較小的結構== #### ►新增結構 ==**(只有24 bytes)**== ```clike= typedef struct __LAST_NAME{ char lastName[MAX_LAST_NAME_SIZE]; struct __PHONE_BOOK_ENTRY *pNext; }entry; ``` #### ►改善memory leakage的問題在main.c裡面原來free程式的地方 ```clike= if (pHead->pNext) free(pHead->pNext); free(pHead); ``` 在main.c裡面修正後 ```clike= while((e = pHead)){ pHead = pHead->pNext; free(e); } ``` 一樣我們用了這些valgrin這個套件去檢視memory leakage的問題有無改善 ``` ==20492== HEAP SUMMARY: ==20492== in use at exit: 0 bytes in 0 blocks ==20492== total heap usage: 349,906 allocs, 349,906 frees, 47,596,856 bytes allocated ``` ##### 這邊compiler建議我要加（）？？？ ##### graphviz語法畫圖（可以google去找） ``` main.c: In function ‘main’: main.c:93:2: warning: suggest parentheses around assignment used as truth value [-Wparentheses] while(e=pHead) { ^ cc -Wall -std=gnu99 -O0 \ -DIMPL="\"phonebook_opt.h\"" -o phonebook_opt \ main.c phonebook_opt.c main.c: In function ‘main’: main.c:93:2: warning: suggest parentheses around assignment used as truth value [-Wparentheses] while(e=pHead) { ^ ``` #### ►執行時間 size of entry : 24 bytes execution time of append() : 0.071729 sec execution time of findName() : 0.003978 sec #### ►Performance & Cache-misses(100 runs) 391,915 cache-misses # 72.783 % of all cache refs ( +- 0.15% ) 538,472 cache-references ( +- 0.22% ) 282,727,160 instructions # 1.92 insns per cycle ( +- 0.01% ) 146,960,098 cycles ( +- 0.26% ) 0.051075581 seconds time elapsed ( +- 0.93% ) ## 心得前面花太多時間浪費在測試程式和發呆還有尻尻應該直接照著前人的血淚做並提早著手開發紀錄,整理自己所學的。 :::danger 跟 GNU/Linux 培養感情，很好呀 --jserv ::: ## C學習筆記 :::danger 剩下是我必須要釐清的基本觀念,之後補上範例和練習。 ::: - [ ] ifdef用法 ```clike= ＃include IMPL =>去check Makfile ``` 因為現在有兩個.c檔 .h檔我們需要去辨識哪個檔可以使用 -DIMPL ex: ```clike= #if defined(__BST__) e = pHead; BST *root = sortedListToBSTRecur( &e, list_len); #endif ``` 當你下-D __BST__就會跑這一段（search tree) ```clike= e = pHead; BST *root = sortedListToBSTRecur( &e, list_len); ``` main.c: ```clike= #ifdef OPT #define OUT_FILE "opt.txt" #else #define OUT_FILE "orig.txt" #endif if OPT = 1 file would out put opt.txt else file would out put to "orig.txt" phonebook_opt.h: #define OPT 1 struct timespecmemory allocate一筆資料 ``` - [ ] FILE *fp用法 fp指到一個你要開的檔 man fread/fwrite - [ ] FILE fgets用法 ```clike= while (fgets(line, sizeof(line), fp)) { // find the terminate byte, '\0' while (line[i] != '\0') i++; line[i - 1] = '\0'; // reset i for caculating the next line i = 0; // append this line into linked list e = append(line, e); } ``` - [ ] FILE fgets用法 man/example:assert - [ ] Segment Fault example:why we use while loop to instead of using memory leakage的問題 (malloc =>free) /* if (pHead->pNext) free(pHead->pNext); */ - [ ] git commit的使用 ### reference * 前人的筆記 [louielu](https://hackmd.io/CYJgZgHA7AnADAFgLQGMCmaCGSEGYCsyMARjPkgIwhS4gT4VwogJA===?view) * 程式碼 [Sean1127](https://github.com/Sean1127/phonebook) 觀念資料 [cache miss 找圖](https://www.google.com.tw/search?espv=2&tbm=isch&q=memory+hierarchy&spell=1&sa=X&ved=0ahUKEwjj5ILft8nSAhWCKMAKHZ0jBDoQvwUIFygA&biw=1346&bih=598&dpr=1) [cache and memoey](https://www.google.com.tw/search?q=one+word+wide+memory+organization&espv=2&source=lnms&tbm=isch&sa=X&ved=0ahUKEwjXif77t8nSAhVoKsAKHbL3Bp0Q_AUIBigB&biw=1346&bih=598#imgrc=8DeoSDaebIQDZM:) [cache and memoey concern](http://pflashsheep.blogspot.tw) [memorial leakage](https://hackmd.io/s/Bkx3cYX6#reviewed-bt-finalallpass) 待整理 http://alumni.cs.ucr.edu/~vladimir/cs161/lecture_9.html [phonebook-cuncurrent](https://hackmd.io/s/HJFhaiAp#%E9%80%B2%E4%B8%80%E6%AD%A5%E5%84%AA%E5%8C%96-append)

Cheatsheet

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.