HackMD
2016q3 Homework 1 (phonebook)
contributed by <jkrvivian>
Reviewed by 0140454
- 在 commit 前應多多注意，避免無意義的 commit 產生。也可善用
git revert來復原 commit。
例如 commit "Add smaz-master" 和 commit "delete"。 - 應該善用 .gitignore 來排除測試時由程式所產生的檔案。
如 commit "add smaz string compression algorithm" 中的smaz.txt。 malloc()是一個開銷很大的 function，未來可提出相對應的改善方案。- 可嘗試使用多種 hash function 並比較其效能差異。
繼續改進效能與研究:
- 字串壓縮的演算法，降低資料表示的成本
- binary search tree
- 研究dataset問題
挑戰進階題>"<
案例分析：phonebook
優化前：
避免用圖片表示文字訊息 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以外的資訊刪掉
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
-
之前的只有註解掉好遜喔！ 所以把資料搬動到新結構中
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
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)
- 瀏覽整份
- 資料難道「數大就是美」嗎？
- 如果我們要建立符合真實電話簿情境的輸入，該怎麼作？
- 網路搜尋
-
該怎麼切入這個問題呢？
- 有代表性嗎？跟真實英文姓氏差異大嗎？
使用字串壓縮法
在字串壓縮法中，有很多朋友們介紹了不同的字串壓縮法，決定先以最高人氣的SMAZ試驗
- 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()
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
- 林佳瑩學姊
- 吳勃興學長
- makefile和前置處理
- hash:
