2016q3 Homework 1 (phonebook)

# 2016q3 Homework 1 (phonebook) contributed by <`jkrvivian`> ### Reviewed by `0140454` * 在 commit 前應多多注意，避免無意義的 commit 產生。也可善用 `git revert` 來復原 commit。例如 [commit "Add smaz-master"](https://github.com/jkrvivian/phonebook-1/commit/e29169987a9d39423b1f228356b4632deb0f7346) 和 [commit "delete"](https://github.com/jkrvivian/phonebook-1/commit/9c6a9c1f3aef1b93215c5c9cefa9849ec699243c)。 * 應該善用 .gitignore 來排除測試時由程式所產生的檔案。如 [commit "add smaz string compression algorithm"](https://github.com/jkrvivian/phonebook-1/commit/5ace5a8806a4692fbb28363d15d77a0eca7f0717) 中的 `smaz.txt`。 * `malloc()` 是一個開銷很大的 function，未來可提出相對應的改善方案。 * 可嘗試使用多種 hash function 並比較其效能差異。 --- 繼續改進效能與研究: * 字串壓縮的演算法，降低資料表示的成本 * binary search tree * 研究dataset問題 > 挑戰進階題>"< [春季班連結](https://embedded2016.hackpad.com/2016q1-Homework1-X6DOgpgSkkC) ## 案例分析：phonebook 優化前： ![before](https://i.imgur.com/G8wScPf.png) >> 避免用圖片表示文字訊息 [name=jserv] 用perf找尋熱點: `./phonebook_orig & sudo perf top -p $!` `findName()` 為熱點，佔了12.91%; append()只佔了1.34%，但append()的執行時間卻遠遠超過findName() ![](https://i.imgur.com/ms1MEbl.png) cache misses 居然到96.047% ![](https://i.imgur.com/2Ebj88V.png) ## 優化 ### 方法： * 減少structure大小 (findName()只看lastname) * hash function #### 優化1 ：減少structure大小把lastName以外的資訊刪掉 ```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; ``` 結果： * structure size從136byte縮減為24byte ![](https://i.imgur.com/7SVllPu.png) * cache misses cache missis從原先的96.047%降至70.018% ![](https://i.imgur.com/CpBHY4h.png) * plot ![](https://i.imgur.com/QcfqEOu.png) * 之前的只有註解掉好遜喔！所以把資料搬動到新結構中 ```C== typedef struct __PHONE_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]; } info; typedef struct __PHONE_BOOK_ENTRY { char lastName[MAX_LAST_NAME_SIZE]; struct __PHONE_INFO *information; struct __PHONE_BOOK_ENTRY *pNext; } entry; ``` 結果： * 大小變為32byte ``` size of entry : 32 bytes execution time of append() : 0.038601 sec execution time of findName() : 0.002589 sec ``` * cache misses降至62.990% ``` Performance counter stats for './phonebook_opt' (100 runs): 407,872 cache-misses # 62.990 % of all cache refs ( +- 0.49% ) 647,521 cache-references ( +- 0.93% ) 246,533,337 instructions # 1.67 insns per cycle ( +- 0.02% ) 147,266,812 cycles ( +- 1.02% ) 0.050819024 seconds time elapsed ( +- 1.33% ) ``` * plot ![](https://i.imgur.com/wPW0C7Y.png) #### 優化2 ：hash **hash** : 一般是一個整數，通過某種算法，可以把一個字符串”壓縮” 成一個整數 >感覺這裡用把字符串"壓縮"成一個整數這個解釋好像有點奇怪，應該是透過算法把字符串變成一個index ，這個index在 hash table裡面就會指向這個字串的bucket(可以當作門牌) **衝突**：對不同的關鍵字可能得到同一雜湊地址，即k1!=k2, f(k1)=f(k2) **hash table**: hash table大小越是質數，mod取餘數就越可能均勻分布在表的各處 * 利用字母ASCII碼算出每個字串的hash值，若hash值相同則使用linked list串起來另外多添加了hash function的 .c .h檔 * 使用BKDR hash ```C== unsigned int BKDRHash(char lastName[]) { unsigned int seed=31; unsigned int hash=0; int i=0; while (lastName[i] != '\0') { hash = hash * seed + lastName[i]; ++i; } return hash %= SIZE; } ``` * 多看了orig版的程式碼幾次，才知道應該怎麼修正，回頭看看自己寫的原版hash，真是一團糟，根本是胡亂拼湊@@ 所以重新再大修改一翻，總算成功了 * 結果：Hash Table size為256 * 執行時間： * findName()時間驟減 * 可是append()的時間卻到了十二秒多，增加太多太多了！ ``` size of entry : 24 bytes execution time of append() : 12.750197 sec execution time of findName() : 0.000022 sec ``` * cache-misses是從96%降至64.743% ``` Performance counter stats for './phonebook_hash1' (10 runs): 153,348,502 cache-misses # 64.743 % of all cache refs ( +- 0.89% ) 236,855,570 cache-references ( +- 0.14% ) 2,033,121,783 instructions # 0.06 insns per cycle ( +- 0.24% ) 36,137,260,010 cycles ( +- 1.41% ) 12.420656874 seconds time elapsed ( +- 0.90% ) ``` 推測應該是Hash Table size太小，造成碰撞率很高，所以改成==1051== * 結果：append()的時間仍然超過太多但已有顯著下降 ``` size of entry : 24 bytes execution time of append() : 3.235966 sec execution time of findName() : 0.000005 sec ``` 再從維基百科中找一個大一點的質數試試3571 * 結果：append()下降至0.575651秒但還是比原本超出太多了 ``` size of entry : 24 bytes execution time of append() : 0.575651 sec execution time of findName() : 0.000000 sec ``` * 推測：在append()裡原先是從每一個linked list的頭去找最後一個再新增資料，就是因為找尋最後一個節點的迴圈太花費時間 * 改善：直接把pointer指向每個linked list的最後一個，append完後再統一還原指向每個linked list的頭，以便findeName()進行 * 結果： append的時間果然下降很多！ ``` size of entry : 24 bytes execution time of append() : 0.083959 sec execution time of findName() : 0.000001 sec ``` * cache-misses也從70.999%降至57.058% ``` Performance counter stats for './phonebook_hash1' (100 runs): 865,677 cache-misses # 57.058 % of all cache refs ( +- 0.49% ) 1,517,185 cache-references ( +- 1.46% ) 348,528,862 instructions # 1.16 insns per cycle ( +- 0.02% ) 300,277,793 cycles ( +- 1.04% ) 0.100966169 seconds time elapsed ( +- 0.99% ) ``` * plot ![orig_opt_hash](https://i.imgur.com/Fswd5bR.png) ----- ## 新進度 * 本例選用的 dataset (也就是輸入電話簿的姓名) 是否存在問題？ * 有代表性嗎？跟真實英文姓氏差異大嗎？ * 瀏覽整份`words.txt`，裡頭的名字跟真實英文姓氏差異很大，很多沒有意思的辭彙(ex:aaaa) * 資料難道「數大就是美」嗎？ * 如果我們要建立符合真實電話簿情境的輸入，該怎麼作？ * 網路搜尋 * >該怎麼切入這個問題呢？ ### 使用字串壓縮法在[字串壓縮法](http://stackoverflow.com/questions/1138345/an-efficient-compression-algorithm-for-short-text-strings)中，有很多朋友們介紹了不同的字串壓縮法，決定先以最高人氣的SMAZ試驗 * [SMAZ](https://github.com/antirez/smaz) * 簡介：短字串的壓縮非常顯著，英文小寫的字串效果最好，若字串中有穿插數字效果較差 * functions: * 壓縮：`int smaz_compress(char *in, int inlen, char *out, int outlen);` * 解壓縮：`int smaz_decompress(char *in, int inlen, char *out, int outlen);` * 皆回傳壓縮和解壓縮後的字串長度 * 節錄README的測試結果： ``` 'This is a small string' compressed by 50% 'foobar' compressed by 34% 'the end' compressed by 58% 'not-a-g00d-Exampl333' enlarged by 15% '1000 numbers 2000 will 10 20 30 compress very little' compressed by 10% ``` * 改寫`findName()`和`append()` ```C== entry *findName(char lastname[], entry *pHead) { while (pHead != NULL) { if (strcasecmp(lastname, pHead->lastName) == 0) return pHead; pHead = pHead->pNext; } return NULL; } entry *append(char lastName[], entry *e) { e->pNext = (entry *) malloc(sizeof(entry)); e = e->pNext; /* compress string */ smaz_compress(lastName,sizeof(lastName),e->lastName,sizeof(lastName)); e->pNext = NULL; return e; } ``` ### 字串長度真的"全部"縮短了嗎？ * 並非如此，不少字串經壓縮後反而比原本還長 * 以下為試驗： ### original 加SMAZ 結果： * append時間比前面的方法都大的多，因為每次append都要經過SMAZ演算法，此演算法甚至比BKDR hash更繁複 * findName的時間與opt差不多 ``` size of entry : 32 bytes execution time of append() : 0.269562 sec execution time of findName() : 0.003497 sec ``` * cache-misses: cache-misses比起原版cache-misses仍從70%降低至56%,推測:壓縮字串後，有更多空間可以儲存資料 ``` Performance counter stats for './phonebook_smaz' (100 runs): 613,100 cache-misses # 56.363 % of all cache refs ( +- 0.57% ) 1,087,780 cache-references ( +- 2.52% ) 1,143,419,207 instructions # 1.44 insns per cycle ( +- 0.00% ) 794,834,236 cycles ( +- 0.61% ) 0.264604214 seconds time elapsed ``` * plot ![](https://i.imgur.com/1vzO4DU.png) * 問題 * ## 參考資料 * wikipedia * [林佳瑩學姊](https://embeddedhomework.hackpad.com/Homework-2-ZFMBm6jTeIr) * [吳勃興學長](https://embedded2016.hackpad.com/2016q1-Homework-1-DdP67a0ke8Q#:h=%E9%96%8B%E7%99%BC%E7%92%B0%E5%A2%83) * [makefile和前置處理](http://deanjai.blogspot.tw/2006/03/makefiledefineif.html) * hash: * 各hash比較： https://www.byvoid.com/blog/string-hash-compare * hash介紹ppt: http://www.eecs.wsu.edu/~ananth/CptS223/Lectures/hashing.pdf * BKDR hash : http://blog.csdn.net/wanglx_/article/details/40400693 ###### tags: `system embedded` `HW1-1`

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.