2018q1 Homework1 (phonebook)

contributed by < catpig1630 >

Reviewed by vulxj0j8j8

  • 不認同Q1的回答, 畢竟在像是帳號管理這種應用下, 搜尋不合理的英文組合是可能發生的

    畢竟本次作業的主題是電話簿，不合理的英文組合不太可能會出現在電話簿上。洪培軒

Reviewed by afcidk

  • 請改善 commit message，像是不要只說 Use hash-table to store data，可以在內文寫為什麼要使用 hash table，使用了哪種 hash function，這麼做對改善程式碼有什麼幫助…等。可以參考How to Write a Git Commit Message。
  • 記得實做完要把 TODO 刪掉

Reviewed by workat60474

  • 在方法二中使用Hash funtion 如果能夠引入time complexity 來說明search在hash table和linked-list之間的差異會更好！
  • 是linked-list 而非 link list。
  • Q2的問題回答中，雖然説資料有高關聯度是更好，但是能夠正確的引入適當的資料結構，來對資料進行操作也是很重要的。

開發環境

$ lscpu
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
型號：              70
Model name:            Intel(R) Core(TM) i7-4770HQ CPU @ 2.20GHz
製程：              1
CPU MHz：             2194.938
CPU max MHz:           3400.0000
CPU min MHz:           800.0000
BogoMIPS:              4389.87
虛擬：              VT-x
L1d 快取：          32K
L1i 快取：          32K
L2 快取：           256K
L3 快取：           6144K
L4 快取：           131072K

原始程式

  • 確保 cache 為空
$ echo 1 | sudo tee /proc/sys/vm/drop_caches
  • 執行
$ make run
  • 執行結果
size of entry : 136 bytes
execution time of append() : 0.043403 sec
execution time of findName() : 0.003546 sec
  • cache miss
 Performance counter stats for './phonebook_orig' (100 runs):

           964,210      cache-misses              #   83.354 % of all cache refs      ( +-  0.13% )
         1,156,759      cache-references                                              ( +-  0.19% )
       323,499,296      instructions              #    1.66  insn per cycle           ( +-  0.01% )
       194,555,398      cycles                                                        ( +-  0.26% )

       0.060958565 seconds time elapsed                                          ( +-  0.27% )
  • 繪圖結果

優化程式

方法一 : 減少 entry size 大小

因為 cache miss 十分嚴重，所以若減少 entry size 可以使得 cache 裡放的 entry 數增加，一般來說可以預期 cache miss 會變少，因此效能就可以提昇

  • 修改資料結構，以減少 entry size
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_all;

typedef struct __LASTNAME_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    struct __LASTNAME_ENTRY *pNext;
    entry_all *all;
} entry;
  • cache size : 136 bytes -> 32 bytes
size of entry : 32 bytes
execution time of append() : 0.033645 sec
execution time of findName() : 0.001904 sec
  • cache miss : 90.7% -> 55.1%
Performance counter stats for './phonebook_opt' (100 runs):

           130,021      cache-misses              #   57.671 % of all cache refs      ( +-  0.80% )
           225,455      cache-references                                              ( +-  1.23% )
       283,610,062      instructions              #    2.02  insn per cycle           ( +-  0.02% )
       140,102,305      cycles                                                        ( +-  0.35% )

       0.044067837 seconds time elapsed                                          ( +-  0.35% )

  • orignal vs optimized 效能比較

  • 結論
    跟更改 entry size 前的預想一樣，因為 entry size 變小，使得 cache 可以存的 entry 數變多了，因此在 cache 裡想找到需要的 entry 變得比較容易，所以 cache miss 下降了，效能也隨著 cache miss 下降而提昇了。

方法二 : 使用 hash table 儲存資料

雖然方法一，把效能增加了，但可以發現因為程式是用 link-list 儲存，所以 findName()函式必須一個一個往下找，花費了許多時間，因此可以猜測若用 hash table 的儲存方式應該可以使效能變得更好

  • 使用BKDR_hash 方式
unsigned int bkdr_hash(char lastName[])
{
              
    unsigned int seed = 31;  
    unsigned int hashnum = 0;  
    while (*lastName)  
    {  
        hashnum = hashnum * seed + (*lastName++);  
    }
    hashnum %= 1024;  
    return hashnum;

}
  • 在方法一的 entry size 下使用 hash table
    cache miss : 90.7% -> 24.5%
 Performance counter stats for './phonebook_opt' (100 runs):

            95,844      cache-misses              #   24.532 % of all cache refs      ( +-  2.75% )
           390,683      cache-references                                              ( +-  0.86% )
       234,512,008      instructions              #    1.70  insn per cycle           ( +-  0.02% )
       137,815,782      cycles                                                        ( +-  0.52% )

       0.043312052 seconds time elapsed                                          ( +-  0.52% )

  • original vs 在方法一的 entry size 下使用 hash table 的效能比較

  • 結論
    可以發現使用 hash table 後 findName()速度變得極快，跟預想的結果一樣，但 append() 時間就算已經在方法一(改變 entry size)下有變快了，但因為 hash table 一開始建立資料表較為麻煩，所以仍然比原來的慢。

回答問題

Q1:有代表性嗎？跟真實英文姓氏差異大嗎？
A:測試資料並不具代表性，因為有太多不是單字的英文字串，還有許多不是姓氏的單字。

Q2:資料難道「數大就是美」嗎？
A:資料並不是數大就是美，因為若有許多不相關的資料，那便會增加研究的困難度，因此應該說資料應該要有越多跟想要的資料相關度高的資料才是好的。

Q3:如果我們要建立符合真實電話簿情境的輸入，該怎麼作？
A:中華黃頁網路電話簿，裡面便有許多電話，可供電話簿使用， e.g. 冰店

參考資料

Select a repo