2016q3 Homework1 (phonebook)

# 2016q3 Homework1 (phonebook) contributed by <`RayPan`> ### Reviewed bt `finalallpass` * 因為沒有使用細部資料，可以考慮重建structure時不需多用一個指標指回細部資料。可以再減少8bytes的entry size。 * 可能可以分析一下為何djb2和BKDR的cache-misses的差異從何而來。 * 修改structure的部分可以補上cache reference的結果 --- ## 開發環境 ![](https://i.imgur.com/RWxX7Ge.png) 第一次使用linux作業系統花了不少時間研究指令 * CPU ``` raypan@raypan-X550JD:~$ lscpu 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: 60 Model name: Intel(R) Core(TM) i5-4200H CPU @ 2.80GHz Stepping: 3 CPU MHz: 2782.281 CPU max MHz: 3400.0000 CPU min MHz: 800.0000 BogoMIPS: 5587.62 Virtualization: VT-x L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 3072K NUMA node0 CPU(s): 0-3 ``` >> 請考慮升級到 Ubuntu 16.04，不然某些軟體套件會太舊 [name=jserv] 升級16.04版 `$ sudo apt-get update && sudo apt-get dist-upgrade` `$ sudo reboot` `$ sudo update-manager -d` ![](https://i.imgur.com/Ua8zf3E.png) --- ## GitHub * 簡介是一個基於網站基礎的託管服務 (hosting service)平台，它提供了以Git為唯一的版本控制系統。 * 常用指令 `$ git init`:要開始使用 Git 你必須先建立一個 Git 的 Repository。 `$ git remote add origin git@github.com:your_account/your_repository.git`:可以連結到遠端的repository。 `$ git clone git@github.com:Username/repository.git`:可將遠端的repository複製一份到本機，若遇防火牆阻隔問題，請改用HTTPS通訊協定:`https://github.com/...` `$ git remote -v`:查看working directory所連結的遠端repository。 `$ git status`：查看目前working directory中所有檔案的情形。 `$ git add`：將未被git追蹤的檔案加入追蹤，可最後加上`.`追蹤全部檔案。 `$ git commit`:將檔案提交。 `$ git push`:上傳到遠端repository。 `$ git pull`:從遠端更新 --- ## 效能分析工具-Perf 應用程式可以利用 PMU (Performance Monitoring Unit), tracepoint 和核心內部的特殊計數器 (counter) 來進行統計，另外還能同時分析運行中的核心程式碼 * 常用指令 `perf list` : 印出perf可以觸發哪些event `perf top` : 找出拖慢系統的熱點 `perf stat` : 已經有個要優化的目標，對這個目標進行特定或一系列的event檢查，進而了解該程序的效能概況。 `perf stat -r 10 cache-misses ./example`表示對特定程式example執行10次perf其cache-misses `perf record` ：針對函式級別進行 event 統計，方便我們對程序「熱點」作更精細的分析和優化。參考資料：[成大wiki-Linux效能分析工具：Perf](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial) --- ## Makefile * #### 規則 `target: dependencies` `<tab>command` * target: 所要建立的檔案。 * dependencies：相依項目，make會依據此決定是否要重新編譯targey。 * commands:建立targets的指令。注意：make 在編譯時，若發現 target 比較新，也就是 dependencies 都比 target 舊，那麼將不會重新建立 target，如此可以避免不必要的編譯動作。 `.PHONY`: 指定後面的為fake項目，利用`.PHONY: clean`來指定clean為fake項目,被視為要建立clean這個檔案，但永不被執行。 * #### 變數宣告 `MACRO = value` ：可利用`$(MACRO)`或`${MARCO}`來存取已定義的變數。 `：=` ：變數的值決定於它在Makefile中的位置，而不是整個Makefile展開後最終的值。 `?=` : 若變數未定義，則替它指定新的值。否則採用原有的值。 * #### 內部變數 `$?` ：已被更新的dependencies的值，i.e.dependencies中，比targets還新的值。 `$@` : targets的值。 `$<` : 第一個dependencies的值。 `$*` : targets所指定的檔案，但不包含副檔名。 * #### 特別字元 `@` ：不要顯示執行的指令在螢幕上。 `-` : 即使該行指令出錯，也不會中斷執行。 `-DMACRO`: 指定一個MARCO的名字。 * 參考資料： [Makefile 語法簡介](http://tetralet.luna.com.tw/?op=ViewArticle&articleId=185)、 [猴子都會寫的Makefile](http://mropengate.blogspot.tw/2015/06/makefile-makefile.html) --- >> 張貼程式碼時，請注意縮排 (空白，而非 tab，與原本程式碼一致的風格) 並且避免單行後方非必要的空白 [name=jserv] >> 延伸閱讀: [The Lost Art of C Structure Packing](http://www.catb.org/esr/structure-packing/) [name=jserv] --- ## 可能的效能改進方法 * 改寫`struct __PHONE_BOOK_ENTRY` * 使用 Hash function 加速查詢 * 使用字串壓縮的演算法，降低資料表示的成本 * 使用 binary search tree 改寫演算法 --- ## 改善過程 #### 未修改之前 ``` size of entry : 136 bytes execution time of append() : 0.053688 sec execution time of findName() : 0.004984 sec ``` ``` Performance counter stats for './phonebook_orig' (100 runs): 1,003,292 cache-misses # 84.258 % of all cache refs ( +- 0.32% ) 1,190,732 cache-references ( +- 0.20% ) 260,911,327 instructions # 1.39 insns per cycle ( +- 0.02% ) 187,778,382 cycles ( +- 0.19% ) 0.057238264 seconds time elapsed ( +- 0.60% ) ``` ### 1. 修改`struct __PHONE_BOOK_ENTRY` 由main.c可知 ```c=75 #ifndef OPT e = pHead; assert(findName(input, e) && "Did you implement findName() in " IMPL "?"); assert(0 == strcmp(findName(input, e)->lastName, "zyxel")); #endif ``` 程式僅透過lastname來查找其他聯絡人資訊可以放入另一個結構中如有需要透過pDetail來索取額外聯絡人資訊可以減少entry的大小達到優化修改後程式碼如下 ```c=9 typedef struct __PHONE_BOOK_DETAILS{ 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]; }details; typedef struct __PHONE_BOOK_ENTRY { char lastName[MAX_LAST_NAME_SIZE]; struct __PHONE_BOOK_DETAILS *pDetails; struct __PHONE_BOOK_ENTRY *pNext; } entry; ``` 執行看看在執行程式之前先清空cache: `$ echo 1 | sudo tee /proc/sys/vm/drop_caches` ``` size of entry : 32 bytes execution time of append() : 0.037598 sec execution time of findName() : 0.004964 sec ``` 如此entry的大小變可縮小至32bytes ``` Performance counter stats for './phonebook_opt' (100 runs): 135,386 cache-misses # 44.511 % of all cache refs ( +- 0.63% ) 304,164 cache-references ( +- 0.45% ) 244,033,296 instructions # 1.94 insns per cycle ( +- 0.02% ) 125,671,746 cycles ( +- 0.20% ) 0.038329599 seconds time elapsed ( +- 0.50% ) ``` 可以發現cache-misses由原本的84.258%下降至44.511% 接著使用makeplot繪製效能比較圖 ***由於main.c中83行，OPT存在才能輸出opt.txt，所以在phonebook.h中必須#define OPT 1*** ```c=83 #if defined(OPT) output = fopen("opt.txt", "a"); ``` 繪圖如下 ![](https://i.imgur.com/7yVWp7r.png) >> 避免用圖片來表達文字輸出 [name=jserv] >> 不要只做執行時間的比較，要對照看 cache reference 的差異，拿出你的專業來 [name=jserv] ### 2.使用Hash function 加速查詢 * #### （1）使用djb2 hash函式參考共筆：[rni c](https://embedded2016.hackpad.com/ep/pad/static/9eSkToGwJvZ) 捨棄原本的sequential search 首先利用`hashInitial（）`建立hash table hash table size訂為65537（質數）結構hashTable內包含`tableSize`及`list` ```clikec=9 hashTable *hashInitial(){ hashTable *ht = NULL; ht = (hashTable *)malloc(sizeof(hashTable)); ht->list = (entry **)malloc(sizeof(entry *)*HASHTABLE_SIZE); for (int i = 0; i < HASHTABLE_SIZE; i++) ht->list[i] = NULL; return ht; } ``` 注意：選擇hashTable大小為質數的原因為避免hash collison（輸入字串不同，雜湊值相同） * hashFunction使用Dan Bernstein提出的[djb2](http://www.cse.yorku.ca/~oz/hash.html)hash函式 ```c=21 unsigned int hashFunction(char *lastName){ unsigned int hashVal = 0; while (*lastName != '\0') hashVal = (hashVal << 5) + *lastName++; return hashVal % HASHTABLE_SIZE; } ``` 改寫append函式可以注意到由於findname長度已定義在MAX_LAST_NAME_SIZE 所以將原本`strcpy`改為`strncpy` 可省去比對其他無效字元。 ```clikec=28 int hashAppend(char *lastName, hashTable *ht){ entry *newEntry; newEntry = (entry *)malloc(sizeof(entry)); strncpy(newEntry->lastName, lastName, MAX_LAST_NAME_SIZE); newEntry->pNext = ht->list[hashFunction(lastName)]; ht->list[hashFunction(lastName)] = newEntry; return 0; } ``` ``` size of entry : 32 bytes execution time of append() : 0.054746 sec execution time of findName() : 0.000008 sec ``` 可以發現到由於須另外建構一個hashtable append的執行時間會略為上升但查找時間會大幅下降 ``` Performance counter stats for './phonebook_opt' (100 runs): 151,896 cache-misses # 38.517 % of all cache refs ( +- 2.53% ) 394,365 cache-references ( +- 0.76% ) 298,128,462 instructions # 1.70 insns per cycle ( +- 0.03% ) 175,143,354 cycles ( +- 0.53% ) 0.053467373 seconds time elapsed ( +- 0.82% ) ``` cache misses也下降到了38.517% ![](https://i.imgur.com/OiKuT1F.png) * #### （2）使用BKDR hash函式參考老師提供的[Programming Small](https://hackmd.io/s/S1rbwmZ6) ```c=29 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 % HASHTABLE_SIZE; } ``` ``` size of entry : 32 bytes execution time of append() : 0.052487 sec execution time of findName() : 0.000008 sec ``` 執行時間大略相同 ``` Performance counter stats for './phonebook_opt' (100 runs): 106,166 cache-misses # 26.940 % of all cache refs ( +- 1.09% ) 394,080 cache-references ( +- 0.26% ) 298,896,581 instructions # 1.71 insns per cycle ( +- 0.03% ) 174,642,726 cycles ( +- 0.57% ) 0.052549821 seconds time elapsed ( +- 0.57% ) ``` 但會發現cache-misses可以再下降到26.397% --- ## 其他筆記 #### 關於前置處理器#if defined 若有兩個c檔案同時include同一個標頭檔，但要同時編譯成一個檔案，會造成衝突。 ``` #if defined（ABC） or #ifdef(ABC) //若ABC有定義過（i.e. #define）程式1 則編譯程式1（非執行） #else 程式2 否則編譯程式2 #endif ``` 參考資料：[ #ifndef#define#endif的用法(整理) 原作者：icwk ](http://huenlil.pixnet.net/blog/post/24339151-%5B%E8%BD%89%5D%23ifndef,-%23define,-%23endif%E7%9A%84%E7%94%A8%E6%B3%95(%E6%95%B4%E7%90%86)-) #### 關於gcc參數 `-c` : 只做編譯並生成目標文件。 `-g` : 編入除錯資訊（使用gdb時必要）。 `-O0` : 不進行優化（注意：是英文字母大歐+零）。 `-Wall` ：顯示所有警告訊息。 #### 關於指標大小 32bits的電腦,指標大小為4bytes 64bits的電腦,指標大小為8bytes --- 作業詳細資訊：[A01: phonebook](https://hackmd.io/s/S1RVdgza) ###### tags:`RayPan` `A01:Phonebook`

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.