# 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
優化前：
>> 避免用圖片表示文字訊息 [name=jserv]
用perf找尋熱點:
`./phonebook_orig & sudo perf top -p $!`
`findName()` 為熱點，佔了12.91%; append()只佔了1.34%，
但append()的執行時間卻遠遠超過findName()
cache misses 居然到96.047%
## 優化
### 方法：
* 減少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
* cache misses
cache missis從原先的96.047%降至70.018%
* plot
* 之前的只有註解掉好遜喔！ 所以把資料搬動到新結構中
```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
#### 優化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
-----
## 新進度
* 本例選用的 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
* 問題
*
## 參考資料
* 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`
Sign in with Wallet
Connect another wallet