HackMD
2016q3 Homework1 Phonebook
contributed by <finalallpass>
Reviewed bt RayPan
- 錯別字 struc -> struct
- 尚未比較不同hash function之間的造成的效能差異
- 尚未闡明BKDR hash hunction造成cache misses較djb2 hash function低的原因
安裝開發環境Ubuntu 14.04
- 由於手邊正好有14.04版本的光碟便拿來安裝win10和Ubuntu雙系統，但遇到了問題如下圖
所幸最後在學長的幫忙下有安裝成功。(有向老師粉專詢問不過當時按下Ctrl+Alt+F7也沒有反應)
安裝過後花了點時間了解linux。
請升級到 Ubuntu 16.04，否則可能會遇到套件太舊的狀況 jserv
畫面本來就是 Linux 終端，就可以輸入指令
1.修改struc
嘗試將原本的phonebook_opt.h更改為
#ifndef _PHONEBOOK_H
#define _PHONEBOOK_H
#define MAX_LAST_NAME_SIZE 16
/*
typedef struct __PHONE_BOOK{
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];
};
*/
typedef struct __PHINE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
//struct __PHONE_BOOK;
struct __PHONE_BOOK_ENTRY *pNext;
}entry;
entry *findName(char lastName[], entry *pHead);
entry *append(char lastName[], entry *e);
#endif
這樣跑出的結果為
size of entry : 24 bytes
execution time of append() : 0.032780 sec
execution time of findName() : 0.001741 sec
可以看到跟原本相比進步了不少
size of entry : 136 bytes
execution time of append() : 0.050244 sec
execution time of findName() : 0.005072 sec
使用gnuplot將圖形描繪出方便對照
然後再對照兩者的cache missed
未改善前的cache-misses高達90.513%
Performance counter stats for './phonebook_orig' (100 runs):
4,486,432 cache-misses # 90.513 % of all cache refs
4,946,858 cache-references
262,201,908 instructions # 1.59 insns per cycle
改善struc之降為68.396%
Performance counter stats for './phonebook_opt' (100 runs):
956,466 cache-misses # 60.158 % of all cache refs
1,625,589 cache-references
241,776,255 instructions # 2.33 insns per cycle
103,304,383 cycles
和原本相比已經好上了不少，90% -> 60%。
接下來想說在新的結構中加上指標指向原本更加詳細的資訊
typedef struct __PHONE_BOOK{
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];
}more;
typedef struct __PHINE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
struct __PHONE_BOOK *more;
struct __PHONE_BOOK_ENTRY *pNext;
}entry;
entry *append(char lastName[], entry *e)
{
e->pNext = (entry *) malloc(sizeof(entry));
e->more= (more *)malloc(sizeof(more));
e = e->pNext;
strcpy(e->lastName, lastName);
e->pNext = NULL;
return e;
}
這樣會變成
size of entry : 32 bytes
execution time of append() : 0.049442 sec
execution time of findName() : 0.001894 sec
entry的部份因為結構中多了一個指標而多了8bytes
和原本entry為24bytes時相比，append的時間稍微多了一些，但還是比original的好。
使用hash function來進一步的優化
- 由於之前沒有接觸過hash還有對於雙重指標的不熟悉，昨天花了時間在閱讀書籍相關資料上，今天來嘗試將系統進一步的改善
- 在更改的過程中遇到問題，當使用BKDR hash function時，出現(core dumped)錯誤。
hashIndex hash(char *key)
{
unsigned int seed = 13;
unsigned int hashVal = 0;
while (*key) {
hashVal = hashVal * seed + (*key++);
}
return hashVal;
}
試算了一下BKDR可能出現的hash值非常大，所以會造成overflow 導致錯誤。那修改最後return的部份，去取餘數。
unsigned int seed = 13;
unsigned int hashVal = 0;
while (*key) {
hashVal = hashVal * seed + (*key++);
}
return hashVal % tablesize;
重新測試一次
size of entry : 24 bytes
execution time of append() : 0.048484 sec
execution time of findName() : 0.000027 sec
Performance counter stats for './phonebook_opt' (100 runs):
397,301 cache-misses # 34.368 % of all cache refs
1,164,390 cache-references
282,565,019 instructions # 2.17 insns per cycle
130,712,769 cycles
0.045373804 seconds time elapsed ( +- 2.29% )
- 所以先嘗試了另一種演算法，就沒有出現錯誤。
hashIndex hash(char *key)
{
unsigned int hashVal = 0;
while (*key != '\0') {
hashVal = (hashVal << 5) + *key++;
}
return hashVal % sizetable;
}
- 修改後結果為
size of entry : 24 bytes
execution time of append() : 0.055109 sec
execution time of findName() : 0.000005 sec
可以看到findName的時間大幅度的減少
再來檢測cache-mises
Performance counter stats for './phonebook_opt' (100 runs):
381,434 cache-misses # 32.500 % of all cache refs
1,153,347 cache-references
283,006,169 instructions # 2.18 insns per cycle
123,954,407 cycles
0.047213072 seconds time elapsed ( +- 1.06% )
和只修改structure相比cache-misses也少了快要30%
不過為了做hash function的優化，我有修改main.c的程式碼，現在要去研究一下Makefile將圖繪出比較。
-
運用了#if defined在main.c中讓他可以同時run opt跟orig。可以得到下圖。
-
雖然append時間變成但findName變得十分的快。
