HackMD
2017q1 Homework1 (phonebook)
contributed by < steven0203 >
Reviewed by ryanwang522
- Git Commit Message 過於簡略，可以在表達的詳細一點，commit 的目的跟過程都可以在詳加描述，參考 How to wirte git commit message，或者我的共筆有稍微做一點淺見整理供你參考。
- 缺乏利用 Binary Search Tree 進行查找的實作，並注意 Cache line 的大小適當調整 node 的結構。
Reviewed by tina0405
- 感覺可以在一些資料結果下面多做一點自己的分析，順便可以讓讀者知道為什麼有不同的想法轉變嘗試。
- 可以試試看不同的方法，例如BST或其他的HASH。
中英文字間請記得以空白隔開!
進度落後，趕工趕工!
課程助教
開發環境
os: Ubuntu 16.04 LTS
Architecture: x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
每核心執行緒數：2
每通訊端核心數：4
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 58
Model name: Intel(R) Core(TM) i7-3610QM CPU @ 2.30GHz
製程： 9
CPU MHz： 1200.132
CPU max MHz: 3300.0000
CPU min MHz: 1200.0000
BogoMIPS: 4589.56
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 6144K
未優化版本
- 執行：
$./phonebook_orig- append() 和 findName() 執行時間：
size of entry : 136 bytes execution time of append() : 0.100508 sec execution time of findName() : 0.006552 sec - cache_test:
$make cache-test- 未優化版本的 cache miss 高達94.61%
Performance counter stats for './phonebook_orig' (100 runs): 2,040,618 cache-misses # 94.610 % of all cache refs ( +- 0.14% ) 2,156,864 cache-references ( +- 0.14% ) 260,715,620 instructions # 1.42 insns per cycle ( +- 0.02% ) 183,005,647 cycles ( +- 0.60% ) 0.081705608 seconds time elapsed ( +- 1.88% ) - 使用perf尋找程式熱點：
$sudo perf record -e cycles ./phonebook_orig
$sudo perf report
從上圖可以知道 findName()(10.63%) 的效能比 append()(1.24%) 多,但執行時間卻是 append()(0.0065sec) 比 findName()(0.1005sec) 少
優化版本 1 - 減少資料結構大小
因為再做搜尋的時候只需要 lastName 不需要其他資料所以可以將原本的資料結構縮小,來減少cache miss
- 將原本的 struct 改成只有 lastName 的資料、指向下一個的指標和指向原有其他資料的指標
typedef struct __PHONE_BOOK_DETAIL {
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];
}detail;
typedef struct __LAST_NAME_ENTRY{
char lastName[MAX_LAST_NAME_SIZE];
detail *entryDetail;
struct __LAST_NAME_ENTRY *pNext;
}entry;
- 執行：
$make plot- cache miss 從95.04%降到了67.9%
Performance counter stats for './phonebook_orig' (100 runs):
2,032,413 cache-misses # 95.041 % of all cache refs ( +- 0.20% )
2,138,451 cache-references ( +- 0.21% )
260,684,240 instructions # 1.38 insns per cycle ( +- 0.02% )
189,355,737 cycles ( +- 0.30% )
Performance counter stats for './phonebook_opt' (100 runs):
390,124 cache-misses # 67.908 % of all cache refs ( +- 0.35% )
574,490 cache-references ( +- 0.51% )
243,875,613 instructions # 1.85 insns per cycle ( +- 0.02% )
131,948,525 cycles ( +- 0.22% )
append()時間從 0.057sec 降到了 0.043sec
findName()時間也從 0.0062sec 降到了 0.0027sec
- perf
$sudo perf record -e cycles ./phonebook_orig
$sudo perf report
findName所佔的效能明顯下降
優化版本 2 - 使用Hash function
這裡使用 BKDRHash 來優化, hash function 如下,我將 HASH_TABLE_SIZE 設成42737,參考 nekoneko 的實驗結果
unsigned int BKDRHash(char *str)
{
unsigned int seed = 131;
unsigned int hash = 0;
while (*str) {
hash = hash * seed + (*str++);
}
return hash%MAX_HASH_TABLE_SIZE;
}
儲存每一個 entry 資料是使用跟優化版本一同樣的 struct , hash table 是儲存經過 hash 後同樣 index 的 linked list 的 head
typedef struct __HASH_TABLE_ENTRY {
entry *head;
} tableEntry;
- 初始化
tableEntry *initializeTable()
{
tableEntry *hashTable=(tableEntry*)malloc(sizeof(tableEntry)*MAX_HASH_TABLE_SIZE);
for(int i=0; i<MAX_HASH_TABLE_SIZE; ++i) {
(hashTable+i)->head=NULL;
}
return hashTable;
}
- append
void append(char lastName[], tableEntry *hashTable)
{
int index=BKDRHash(lastName);
entry *newEntry=(entry *)malloc(sizeof(entry));
strcpy(newEntry->lastName,lastName);
newEntry->pNext=hashTable[index].head;
hashTable[index].head=newEntry;
}
- find
entry *findName(char lastName[],tableEntry *hashTable)
{
int index=BKDRHash(lastName);
entry *head=hashTable[index].head;
while (head) {
if (strcasecmp(lastName, head->lastName) == 0)
return head;
head = head->pNext;
}
return NULL;
}
結果：
- 執行： `$make plot'
Performance counter stats for './phonebook_opt_hash' (100 runs):
347,546 cache-misses # 54.858 % of all cache refs ( +- 0.55% )
633,536 cache-references ( +- 1.14% )
235,882,703 instructions # 1.69 insns per cycle ( +- 0.02% )
139,960,783 cycles ( +- 0.66% )
0.060647815 seconds time elapsed ( +- 2.36% )
cache-misses 從之前的 68% 降到了 54.86%
append 的執行時間因為每次都要花時間在處理 hash function,所以比起只有減少資料結構大小時間有增加,但是 findName 的部份減到很少
參考資料
Phonebook
Dada Chan
hash function 觀念和實務
哈希表之bkdrhash算法解析及扩展
各种字符串Hash函数比较
nekoneko
