2016q3 Homework1 (phonebook)

contributed by <shelly4132>

Reviewed by `HaoTse`

目前只實作了減少資料結構與使用 hash function 兩種方式，尚有許多方式可以增進效能，例如使用字串壓縮演算法、二元搜尋樹等等的方法
未對 append() 效能增進方法做討論
使用的 data set 為無意義的英文字母，未使用符合現實的英文姓氏做實驗
只使用了 BKDRhash 做實驗，可以繼續探討其他 hash function，並探討對應各個 data set 適合哪一種 hash function
commit 6af1b 好像可以不用把 hash.txt push 上去，並且 commit 的風格可參考 How to Write a Git Commit Message

開發環境

作業系統：Ubuntu 16.04 LTS
Cache：

$ lscpu | grep cache
- L1d cache：32K
- L1i cache：32K
- L2 cache：256K
- L3 cache：3072K

事前準備

在筆電安裝Ubuntu
照老師的教學先安裝相關開發工具

$ sudo apt-get update
$ sudo apt-get install build-essential
$ sudo apt-get install linux-tools-common linux-tools-generic
$ sudo apt-get install astyle colordiff gnuplot

案例分析：Phone Book

未優化版本

原本phonebook的entry中存了很多詳細的資料，每個entry的大小為136bytes。
而我的電腦L1 Cache為32KB = 321024，所以321024 / (136*8) = 30.12，代表裡面只能存 30 筆左右。

./phonebook_orig

size of entry : 136 bytes
execution time of append() : 0.067210 sec
execution time of findName() : 0.005578 sec

從以下結果可以看到未優化前的cache miss高達87.762%。

Performance counter stats for './phonebook_orig' (100 runs):

           96,7265      cache-misses              #   87.762 % of all cache refs      ( +-  0.37% )
          110,2146      cache-references                                              ( +-  0.45% )
       2,6092,3829      instructions              #    1.38  insns per cycle          ( +-  0.02% )
       1,8918,5981      cycles                                                        ( +-  0.72% )

       0.076236355 seconds time elapsed

優化版本

第一種優化：縮減struct的大小

其實findName跟append都只用到lastName，所以我們其實可以把那些多餘的訊息都去掉不要，因此我新增了一個比較簡單的struct。



















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;
} detailEntry;

typedef struct __LAST_NAME_ENTRY{
    char lastName[MAX_LAST_NAME_SIZE];
    detailEntry *detail;
    struct __LAST_NAME_ENTRY *pNext;
} entry;

./phonebook_opt

size of entry : 32 bytes
execution time of append() : 0.044284 sec
execution time of findName() : 0.002463 sec

從下面的資訊可以看到，只是單純的把entry的大小減小，就大幅的降低了cache miss，從原本的87.762 %降低到了29.548 %，效果非常驚人。

Performance counter stats for './phonebook_opt' (100 runs):

           11,1935      cache-misses              #   29.548 % of all cache refs      ( +-  0.90% )
           37,8822      cache-references                                              ( +-  1.18% )
       2,4392,7456      instructions              #    1.75  insns per cycle          ( +-  0.02% )
       1,3909,4113      cycles                                                        ( +-  0.97% )

       0.056542530 seconds time elapsed

第二種優化：hash function

參考：BKDRHash、vvn

當我們需要比較的字串數量太龐大的話，我們可以使用hash function來將每個字串轉換成一個數字，而這次我使用的hash function是比較簡單快速的BKDRHash，hash table的大小我設成比較大的質數42737，並且把乘法的部份改成位移運算子，不過我自己測的結果這對於速度的提升似乎沒有太大的幫助。

collision：當兩個不同的字串算出的key一樣時，就發生碰撞。













unsigned int BKDRHash(char lastName[])
{
    //unsigned int seed=31;
    unsigned int hash=0;
    int i=0;
    while(i<strlen(lastName)) {
        //hash = hash * seed + lastName[i];
        hash = (hash <<  5) - hash + lastName[i]; 
        ++i;
    }

    return hash % DICLEN;
}

從結果可以看到因為findName()不用再從頭開始找，所以花的時間大幅的往下降，但append()的時間卻往上升了，原因應該是因為每次append()我們都還要再去呼叫一次hash function。
./hash_func

size of entry : 32 bytes
execution time of append() : 0.087076 sec
execution time of findName() : 0.000000 sec

而cache miss也下降到了63.635%。

Performance counter stats for './hash_func' (100 runs):

          109,3919      cache-misses              #   63.635 % of all cache refs      ( +-  0.71% )
          171,9051      cache-references                                              ( +-  0.31% )
       3,7554,6986      instructions              #    1.40  insns per cycle          ( +-  0.14% )
       2,6852,9326      cycles                                                        ( +-  0.46% )

       0.110592162 seconds time elapsed