owned this note   changed 7 years ago  
Linked with GitHub

2018q1 Homework1 (phonebook)

contributed by < f74034067 >

Reviewed by TingL7

  • 使用hash加速findName()中，Hash table size、function的選擇動機是什麼？可以試著比較不同hash function的效能分析。
  • 請試著分析結果，例如append()時間增加的原因、cache miss下降的原因。

Reviewed by LinYunWen

  • 可以多說明一下自己的思考路徑，為什麼優化會先嘗試降低 entry size 、使用 hash function 並且閱讀完相關文章可以寫下些想法
  • 可以多些對數據的分析，尤其針對 cache miss rate 及執行速度
  • commit message 上可以多做一些解釋，在這個 commit 中做了甚麼事

Reviewed by catpig1630

  • 問題討論應該自己做實驗後拿實驗結果當佐證回答比較好，而不是只是靠自己的感覺回答

開發環境

$ uname -a
Linux suchihhan-S551LN 4.13.0-36-generic #40~16.04.1-Ubuntu SMP Fri Feb 16 23:25:58 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux

$ lscpu
Architecture:          x86_64
CPU 作業模式：    32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
每核心執行緒數：2
每通訊端核心數：2
Socket(s):             1
NUMA 節點：         1
供應商識別號：  GenuineIntel
CPU 家族：          6
型號：              69
Model name:            Intel(R) Core(TM) i7-4500U CPU @ 1.80GHz
製程：              1
CPU MHz：             2394.417
CPU max MHz:           3000.0000
CPU min MHz:           800.0000
BogoMIPS:              4788.83
虛擬：              VT-x
L1d 快取：          32K
L1i 快取：          32K
L2 快取：           256K
L3 快取：           4096K
NUMA node0 CPU(s):     0-3
Flags:                 fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 movbe popcnt aes xsave avx f16c rdrand lahf_lm abm cpuid_fault epb invpcid_single pti retpoline tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt dtherm ida arat pln pts

原始版本

  • 清空 cache
$ echo 1 | sudo tee /proc/sys/vm/drop_caches
  • 執行
$ make run

size of entry : 136 bytes
execution time of append() : 0.044759 sec
execution time of findName() : 0.005746 sec
3
  • 觀察 cache-misses
$ make cache-test

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

         1,264,772      cache-misses              #   91.021 % of all cache refs      ( +-  0.15% )
         1,389,539      cache-references                                              ( +-  0.14% )
       263,700,620      instructions              #    1.38  insn per cycle           ( +-  0.02% )
       190,770,983      cycles                                                        ( +-  0.10% )

       0.065283811 seconds time elapsed                                          ( +-  0.15% )
  • 利用 gnuplot 製圖
$ make plot
$ eog runtime.png

優化版本

更改儲存結構 降低 entry size

typedef struct __PHONE_BOOK_DETAILS {
    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];
}details;
typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    struct __PHONE_BOOK_DETAILS *pDetails;
    struct __PHONE_BOOK_ENTRY *pNext;
} entry;
  • size of entry 從 136 bytes 降到 32 bytes
size of entry : 32 bytes
execution time of append() : 0.035513 sec
execution time of findName() : 0.002131 sec
3
  • cache-misses 從 91.021% 降到 28.291%
Performance counter stats for './phonebook_opt' (100 runs):

           136,779      cache-misses              #   28.291 % of all cache refs      ( +-  0.54% )
           483,463      cache-references                                              ( +-  0.80% )
       244,903,216      instructions              #    1.81  insn per cycle           ( +-  0.02% )
       134,977,356      cycles                                                        ( +-  0.75% )

       0.047471423 seconds time elapsed                                          ( +-  0.85% )

使用 hash function 加速 findName()

unsigned int bkdr_hash(const char *key)
{
    unsigned int seed = 31;
    unsigned int hash = 0;
    while (*key) {
        hash = hash * seed +(*key++);
    }
    return (hash % MAX_TABLE_SIZE);
}
  • data structure 示意圖
  • cache-misses 從 28.291% 降到 20.894%
Performance counter stats for './phonebook_opt' (100 runs):

            87,260      cache-misses              #   20.894 % of all cache refs      ( +-  2.80% )
           417,621      cache-references                                              ( +-  0.84% )
       233,879,770      instructions              #    1.66  insn per cycle           ( +-  0.02% )
       140,497,240      cycles                                                        ( +-  0.56% )

       0.049157785 seconds time elapsed                                          ( +-  0.72% )
  • append() 的時間稍微增加，findName() 的時間顯著的降低

問題討論

  • 有代表性嗎？跟真實英文姓氏差異大嗎？
    • 雖然跟真實英文姓名姓氏差異有點大，但若是要應用在建立搜尋帳號 ID 或是暱稱上也是有可能出現這種資料的
  • 資料難道「數大就是美」嗎？
    • 有用的資料才是多多益善，若是太多零碎無意義的資料反而可能會造成功能效能不佳
  • 如果我們要建立符合真實電話簿情境的輸入，該怎麼作？
    • 顧及到隱私問題，可能得透過表單請願意協助的人填寫資料

參考資料

Select a repo