2016q3 Homework1（phonebook）

tags: tundergod hw1 2016q3

contributed by <tundergod>

Reviewed by TempoJiJi

• 沒有詳細說明關於hash function的實做，也沒有比較不同的hash table size
• 沒有具體說明改進後效能變好的原因
• 沒有關於perf的使用記錄等
• 沒有關注cache miss，以及做對應的相關實驗
• 應該探討如何降低append的時間
• commit 7dcb319寫的太爛！完全不知道你做了什麼

作業說明

• A01: phonebook

開發環境

• Linux 版本: Ubuntu 16.04 LTS

• 硬體資訊：使用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:                 69
Model name:            Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz
Stepping:              1
CPU MHz:               1661.660
CPU max MHz:           2600.0000
CPU min MHz:           800.0000
BogoMIPS:              4589.54
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              3072K
NUMA node0 CPU(s):     0-3

原始效能分析數據與圖表

• 數據：

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

          106,1028      cache-misses              #   84.454 % of all cache refs      ( +-  0.81% )
          125,6338      cache-references                                              ( +-  0.67% )
       2,6075,7557      instructions              #    1.31  insns per cycle          ( +-  0.02% )
       1,9910,2540      cycles                                                        ( +-  0.86% )

       0.085194952 seconds time elapsed                                          ( +-  1.00% )

• 圖表：
  

效能改進

改寫 struct __PHONE_BOOK_ENTRY

• 原本的phonebook entry有136bytes的資料，而程式的執行只需要通過尋找lastname，建立新的struct取代原本的struct,只用以下三個參數作爲結構元素只有32bytes(因爲對齊)的資料
• 建立一個all指標避免破壞原始功能

typedef struct __LASTNAME_ENTRY{
        char lastName[MAX_LAST_NAME_SIZE];		//16bytes
        entry_all *all;//for finding more detail	//4bytes
        struct __LASTNAME_ENTRY *pNext;		//4bytes
} entry;

• 改寫後數據與圖表：

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

           12,6876      cache-misses              #   31.314 % of all cache refs      ( +-  0.53% )
           40,5171      cache-references                                              ( +-  0.93% )
       2,4402,2088      instructions              #    1.81  insns per cycle          ( +-  0.02% )
       1,3457,9688      cycles                                                        ( +-  0.36% )

       0.056097970 seconds time elapsed                                          ( +-  0.48% )

使用Hash function

• 使用BKDRhash function進行修改
• 改寫後數據與圖表

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

            9,4098      cache-misses              #   42.218 % of all cache refs      ( +-  1.12% )
           22,2888      cache-references                                              ( +-  1.28% )
       2,4101,5594      instructions              #    1.91  insns per cycle          ( +-  0.02% )
       1,2608,5592      cycles                                                        ( +-  0.40% )

       0.052481990 seconds time elapsed