HackMD
2016q3 Homework1 (phonebook)
contributed by <carolc0708>
開發環境
- Ubuntu 16.04.1 LTS
- CPU: Intel® Core™ i5-4570 CPU @ 3.20GHz
- Cache:
$ lscpu | grep cache- L1d cache: 32K
- L1i cache: 32K
- L2 cache: 256K
- L3 cache: 6144K
cache line issue
Perf效能分析工具
phonebook_orig的分析:
Performance counter stats for './phonebook_orig' (100 runs):
1,220,664 cache-misses # 85.971 % of all cache refs ( +- 0.39% )
1,419,851 cache-references ( +- 0.26% )
261,811,357 instructions # 1.21 insns per cycle ( +- 0.02% )
216,828,386 cycles ( +- 0.42% )
0.066546829 seconds time elapsed ( +- 0.56% )
phonebook_orig的執行時間:
size of entry : 136 bytes
execution time of append() : 0.047410 sec
execution time of findName() : 0.005756 sec
gnuplot 製圖
更改\scripts\runtime.gp檔中的製圖參數
reset
set ylabel 'time(sec)'
set style fill solid
set title 'perfomance comparison'
set term png enhanced font 'Verdana,10'
set output 'runtime.png'
plot [:][:0.100]'output.txt' using 2:xtic(1) with histogram title 'original', \
'' using ($0-0.06):($2+0.001):2 with labels title ' ', \
'' using 3:xtic(1) with histogram title 'optimized' , \
'' using 4:xtic(1) with histogram title 'hash' , \
'' using ($0+0.3):($3+0.0015):3 with labels title ' ', \
'' using ($0+0.4):($4+0.0015):4 with labels title ' '
並在calculate.c當中增加將hash.txt讀入output.txt的部分
案例分析:Phonebook
在phonebook_orig.h中phonebook的資料結構定義如下:
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];//16 byte
char firstName[16];//16 byte
char email[16];//16 byte
char phone[10];//10 byte
char cell[10];//10 byte
char addr1[16];//16 byte
char addr2[16];//16 byte
char city[16];//16 byte
char state[2];//16 byte
char zip[5];//5 byte
struct __PHONE_BOOK_ENTRY *pNext;//8 byte
} entry;
可以看到一個entry總共占用了 136 byte，然而cache L1的大小為32 Kbit，若每次透過findName()函式進行比對，cache只能讀入32 * 1024 / 136 * 8 = 30.12，約 30 筆entry，在進行350000筆資料的比對時，會造成大量的cache miss。
Hint: 可能的效能改進方式
- 改寫 struct __PHONE_BOOK_ENTRY 的成員，搬動到新的結構中
- 使用 hash function 來加速查詢
- 既然 first name, last name, address 都是合法的英文 (可假設成立)，使用字串壓縮的演算法，降低資料表示的成本
- 使用 binary search tree 改寫演算法
- 本例選用的 dataset (也就是輸入電話簿的姓名) 是否存在問題？
有代表性嗎？跟真實英文姓氏差異大嗎？
資料難道「數大就是美」嗎？
如果我們要建立符合真實電話簿情境的輸入，該怎麼作？
挑戰題
- 除了降低
findName()的 cache miss 與執行成本，append()也該想辦法縮減時間- 建立 phone book 時，既然 lastName 是索引值，可以優先建立搜尋表格，其他資料可稍後再補上
- 用 PThread 建立 manager/worker thread model
- 支援 fuzzy search，允許搜尋 lastName 時，不用精準打出正確的寫法
- 比方說電話簿有一筆資料是
McDonald，但若使用者輸入MacDonald或McDonalds，也一併檢索出來 - 延伸閱讀: Levenshtein Distance (編輯距離)
- 比方說電話簿有一筆資料是
- 改善電話簿的效能分析，透過大量的重複執行，找出 95% 信賴區間，而且允許動態新增資料 (較符合現實) 和查詢
- 以 gnuplot 繪製效能分析圖表
METHOD1: 改變entry大小
在phonebook_orig.c中，可以發現每次進行findName()時，只用到lastName，卻須將整個entry 136 byte載入cache中。
entry *findName(char lastName[], entry *pHead)
{
while (pHead != NULL) {
if (strcasecmp(lastName, pHead->lastName) == 0)
return pHead;
pHead = pHead->pNext;
}
return NULL;
}
所以在phonebook_opt.h中重新設計phonebook的資料結構，將比對時不會用到的資料(即lastName、*pNext以外的資料)包裝為另一個struct，
typedef struct __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;
並用一指標*detailInfo指向它。
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
detail *detailInfo;
struct __PHONE_BOOK_ENTRY *pNext;
} entry;
如此一來，原本的__PHONE_BOOK_ENTRY只佔用了16(lastName) + 8(*pNext) + 8(*detailInfo) = 32 byte，cache每次能讀取32 * 1024 / 32 * 8 = 128 筆entry，可大幅減少cache miss。
- [ ]TODO: 嘗試這部分實作並測試效能是否改善
課程資料當中提到:" 因為若在 append 過程中 malloc() 空間給 *detail，會增加很多 cache miss，嚴重影響到效能表現，經過實測，總體效能甚至比原始版本還差一點。目前想法是將 *detail 的 assign （當有需要時）交給另外一個 function 處理，畢竟我們一開始只有 last name 的資訊。 "
- 改善後，執行時間如下:
size of entry : 32 bytes
execution time of append() : 0.028434 sec
execution time of findName() : 0.001888 sec
改善後，cache miss由85%降到45%左右。
Performance counter stats for './phonebook_opt' (100 runs):
197,061 cache-misses # 45.603 % of all cache refs ( +- 1.47% )
432,126 cache-references ( +- 0.72% )
244,209,456 instructions # 1.85 insns per cycle ( +- 0.02% )
131,874,631 cycles ( +- 0.41% )
0.041165375 seconds time elapsed ( +- 0 .93% )
findName()執行時間上有減少。
- 和未優化版本比較:
METHOD2: 使用 hash function
這邊在實作的時候程式碼亂成一團，把它用條件編譯的方式好好整理一下，參考這裡。
- djb2
參考課程資料:Programming Small中對於實作hash function的探討，而hash function的選擇參考 hash function for string，實作了 djb2。
djb2 hash function給定初始hash值為5381，將key編為hash*33，再加上字串的內容。考慮phonebook資料結構的設計，輸入字串可以是lastName(16 byte)或結合所有的字串(127 byte)，在此由於findName()只有用到lastName的比較，只輸入lastName去編key。
不知道兩種效果是否差很多，可以試試看Carol Chen
unsigned int DJB2_hash(char lastName[], int hash_table_size)
{
unsigned int hash = 5381;
int c;
int i = 0;
while (c = lastName[i++])
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash %= hash_table_size;
}
在這邊實作append()時，有另外定義全域變數entry* hash_table_cur[HASH_NUM_SIZE]，用來紀錄hash table發生collision時chaining的linked list已經存到第幾個。這樣一來每次在加入新的資料的時候，就不用整條linked list從頭走一次，可以減去一些執行時間。
hash table size = 256
size of entry : 32 bytes
execution time of append() : 0.038605 sec
execution time of findName() : 0.000015 sec
hash table size = 1000
size of entry : 32 bytes
execution time of append() : 0.038603 sec
execution time of findName() : 0.000003 sec
hash table size = 2000
size of entry : 32 bytes
execution time of append() : 0.039207 sec
execution time of findName() : 0.000001 sec
可以發現append()的時間與未優化前沒有差太多，而findName()的執行時間則是隨著hash table的大小增加而逐漸縮減。
Performance counter stats for './phonebook_hash' (100 runs):
580,489 cache-misses # 50.242 % of all cache refs ( +- 0.29% )
1,155,387 cache-references ( +- 0.06% )
293,285,085 instructions # 1.28 insns per cycle ( +- 0.02% )
229,464,841 cycles ( +- 0.34% )
0.066811857 seconds time elapsed ( +- 0.37% )
cache miss由未優化前的85%降至50%左右。比縮小entry的優化版本(45%)稍微高一點。
- BKDR hash
unsigned int BKDR_hash(char lastName[], int hash_table_size)
{
unsigned int seed = 131;
unsigned int hash = 0;
int i = 0;
while(lastName[i] != '\0')
{
hash = hash * seed + lastName[i];
i++;
}
return hash %= hash_table_size;
}
hash table size = 256
size of entry : 32 bytes
execution time of append() : 0.040698 sec
execution time of findName() : 0.000029 sec
hash table size = 1000
size of entry : 32 bytes
execution time of append() : 0.041464 sec
execution time of findName() : 0.000003 sec
hash table size = 2000
size of entry : 32 bytes
execution time of append() : 0.041498 sec
execution time of findName() : 0.000001 sec
可以發現append()的時間與未優化前沒有差太多，但約比djb2的時間長一些。而findName()的執行時間則是隨著hash table的大小增加而逐漸縮減。
Performance counter stats for './phonebook_hash' (100 runs):
593,343 cache-misses # 50.444 % of all cache refs ( +- 0.25% )
1,176,231 cache-references ( +- 0.07% )
292,144,527 instructions # 1.22 insns per cycle ( +- 0.01% )
239,491,289 cycles ( +- 0.30% )
0.069722688 seconds time elapsed ( +- 0.33% )
cache miss從未優化前的85%降到50%左右，和djb2的版本差不多。
- 和為優化版與縮減entry大小版本比較如下:
