HackMD
2016 Homework 1 - phonebook
Reviewed by <andy19950>
- 僅測試一種 dataset 沒有考慮使用符合現實情況的 dataset。
- 雖然使用 hash function 後 cache miss 有改善，但是 append 的時間變得太久有點不符合效益。
- 在程式碼內使用 BKDR hash function 很不錯，但是能夠了解一下他的概念並介紹給我們知道更好。
- github 上傳時可以先使用 git add file_name 來選擇要上傳的檔案，然後使用 git commit -m "text" 來註解該檔案的意義，而不是把每個檔案一次上傳然後每個都用同樣的註解。
開發環境及工具安裝
- Ubuntu 16.04 LTS
- git & github
- perf
phonebook_origin
- phonebook.h
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;
entry *findName(char lastName[], entry *pHead);
entry *append(char lastName[], entry *e);
- phonebook.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)
{
/* allocate memory for the new entry and put lastName */
e->pNext = (entry *) malloc(sizeof(entry));
e = e->pNext;
strcpy(e->lastName, lastName);
e->pNext = NULL;
return e;
}
改善方式
-
改變資料儲存方式
- 藉由改變原本Struct內部儲存內容，，尚未改變來的搜尋方式，達到降低cache miss 及"極細微"降低執行時間。
- 當搜尋電話簿的過程只尋找 lastname 而不需要其他資訊並不完全符合現實情況。
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
struct __PHONE_BOOK_ENTRY *pNext;
} entry;
- Hash function 使用
- 藉由Hash 的方式，改變搜尋資料的過程。
- 找了一下string hash 的使用，有找到一個各種Hash 的比較，也因此決定使用BKDR Hash 實作。
- 在實作過程中，遇到許多困難，對於 varible 其 pointer 的使用極度不熟悉，在後來參考他人的共筆後才完成。
- cache miss 比較
orig
Performance counter stats for './phonebook_orig' (100 runs):
2,011,628 cache-misses # 90.346 % of all cache refs ( +- 0.07% )
2,226,578 cache-references ( +- 0.05% )
261,251,457 instructions # 1.34 insns per cycle ( +- 0.02% )
195,112,054 cycles ( +- 0.23% )
0.070730799 seconds time elapsed ( +- 0.87% )
opt(struct)
Performance counter stats for './phonebook_opt' (100 runs):
213,815 cache-misses # 58.056 % of all cache refs ( +- 0.40% )
368,290 cache-references ( +- 0.14% )
240,720,997 instructions # 1.79 insns per cycle ( +- 0.02% )
134,571,324 cycles ( +- 0.16% )
0.047346644 seconds time elapsed ( +- 0.50% )
hash
Performance counter stats for './phonebook_hash' (100 runs):
1,903,707 cache-misses # 27.554 % of all cache refs ( +- 0.27% )
6,909,127 cache-references ( +- 0.03% )
277,394,837 instructions # 0.36 insns per cycle ( +- 0.02% )
772,581,926 cycles ( +- 0.13% )
0.278813297 seconds time elapsed ( +- 0.49% )
討論
-
hash function append() 時間過高！！，不確定是精準度不夠或是其他原因造成findNamd() 時間是0.0000000
-
除了改變struct 的方式，Hash 也降低了cache miss 比例
心得
效能分析是第一次做，也沒有想到可以用簡單的方式就可以有顯著的改變，更不用說那些我還沒發現的方式
不熟悉的東西太多了，gnuplot、perf、makefile、predefine macro 語法 使用還需要再更加了解。
coding 就如同老師說的，以前都是騙自己過來的，之後要再慢慢贖罪。
