2017q1 Homework1 (phonebook)

contributed by <janetwei>

Reviewed by `ierosodin`

以後 mac 灌 ubuntu 雙系統找妳
hash 有很多種，比較不同 hash function 的資料分散程度
電話簿是否能支援動態增減資料
將電話簿的人名做排序，再以此來搜尋
可以嘗試改變資料儲存的結構

Reviewed by `SeanCCC`

請問在使用外接硬碟做為主硬碟時，有遇到因為傳輸速度慢造成載入也慢的問題嗎?

開發環境

$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 61
Model name: Intel® Core™ i5-5250U CPU @ 1.60GHz
Stepping: 4
CPU MHz: 1233.187
CPU max MHz: 2700.0000
CPU min MHz: 500.0000
BogoMIPS: 3200.16
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 3072K
NUMA node0 CPU(s): 0-3

請列出硬體相關資訊（cache, memory 等等）
課程助教

好的魏孜昀

上星期寫作業到一定進度之後，由於之前的開發環境的設定，沒有安全安裝好 ubuntu ，因此在我誤打指令，重新設定開機選項後就找不到我原本使用的 ubuntu 硬碟，花了兩三天的時間修復，但是都徒勞無功，最後決定重灌，而且因為是使用 Macbook Air ，本身只有 128GB 的硬碟，因此想要重灌在外接硬碟
Installing Ubuntu onto a bootable USB stick or other device on a Mac

優化前

$ make run


size of entry : 136 bytes
execution time of append() : 0.048162 sec
execution time of findName() : 0.005631 sec

$ make plot

$ make cache-test

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

          338,5886      cache-misses              #   92.608 % of all cache refs      ( +-  0.07% )
          365,6162      cache-references                                              ( +-  0.19% )
       2,6155,9863      instructions              #    1.46  insns per cycle          ( +-  0.02% )
       1,7905,6194      cycles                                                        ( +-  0.33% )

       0.069157022 seconds time elapsed                                          ( +-  0.49% )

優化

1.縮小 struct 體積
將 first name、email、phone number、address、zip 等資訊另外建一個 struct ，因為題目只有要搜尋 last name

size of entry : 32 bytes
execution time of append() : 0.040283 sec
execution time of findName() : 0.002284 sec

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

          118,9152      cache-misses              #   73.496 % of all cache refs      ( +-  0.09% )
          161,7982      cache-references                                              ( +-  0.11% )
       2,4391,2558      instructions              #    1.97  insns per cycle          ( +-  0.02% )
       1,2355,5490      cycles                                                        ( +-  0.12% )

       0.047152542 seconds time elapsed                                          ( +-  0.14% )

cache-misses 從 92.608% 降低到 73.496%

2.hash function
利用 lastName 的字串當做搜尋的 key ，在 append() 運用到 hash function，建立一個 hash table 提供更快速的搜尋

unsigned int BKDRhash(char lastName[])
{
    unsigned int hash = 0;
    int R=13;
    for (int i = 0; i < strlen(lastName); i++)
        hash = (R * hash + lastName[i])%SIZE;
    return hash;
}

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

          158,3284      cache-misses              #   67.733 % of all cache refs      ( +-  0.12% )
          233,7545      cache-references                                              ( +-  0.13% )
       3,8000,5035      instructions              #    1.48  insns per cycle          ( +-  0.02% )
       2,5714,5502      cycles                                                        ( +-  0.45% )

       0.105263097 seconds time elapsed                                          ( +-  1.80% )

原始和兩種優化的時間

2017q1 Homework1 (phonebook)

Reviewed by ierosodin

Reviewed by SeanCCC

開發環境

優化前

優化

Reviewed by `ierosodin`

Reviewed by `SeanCCC`