2018q1 Homework1 (phonebook)

tags: rwe0214

Reviewed by nashi5566

• 既然提到資料和現實生活不符，那是不是可以試著用作業中 all-name.txt 的資料做實驗呢？
• 推論 hash-alv 對於 cache misses 的影響能不能夠用更詳盡的論述說明推論的理由

原本有想到要使用只有 avl 的版本去做比較，但是因為原資料執行 avl 的版本時間耗費太大，又怕只用小資料會造成變因過多，所以就沒有做出 avl 的比較，之後會再思考要用什麼方式呈現Willy Chiu

• github 上多 push 了 phonebook_hash_alv_opt 的 executable file

Reviewed by raygoah

• 可以加入解釋 hash table 的 buckets 為什麼選擇 524288
• 可以比較 hash table size 不同時，使用 AVL tree 得到的 cache miss 差異，以及該選擇哪種 hash table size 得到的結果最好
• .gitignore 需要更新，hash_avl_opt.txt 以及 phonebook_hash_alv_opt 不需上傳
• commit message 可以再寫清楚一點，並且句子的第一個字母要大寫，可參考
  【譯】如何撰寫Git提交訊息

開發環境

willy@willy-X555LN:~$ 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) i5-4210U CPU @ 1.70GHz
製程：                          1
CPU MHz：                      2394.512
CPU max MHz:                   2700.0000
CPU min MHz:                   800.0000
BogoMIPS:                      4789.02
虛擬：                          VT-x
L1d 快取：                      32K
L1i 快取：                      32K
L2 快取：                       256K
L3 快取：                       3072K
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

原始檔案結構分析（ phonebook_orgi ）

phonebook_orig 使用 single-linklist 的資料結構儲存，其建立和搜尋的時間複雜度皆為 O(n)，而因為 node ( 即 struct entry ) 的數量非常大，所以在搜尋 ( findName() ) 上耗費的時間非常可觀。
另外本次作業也提到觀察 cache miss 的情形，在原始結構所採用的 node 中除了儲存用來當作 index 的 lastName 外，也一併儲存其他資料 ( e.g. firstName, email, phone … )，導致一個 node 的資料大小大過於 index 非常多，又因為 cache 一次是載入一個一個 node ，再加上 cache 大小有限，所以 cache 中有著許多搜尋時用不到的資訊且而浪費了空間，所以導致此版本的 CPU 效率不彰。

for example 的縮寫是 e.g.，不是 ex，後者是「前」女友、「前」老闆一類的前綴詞

jserv

謝謝老師提醒，已更改！Willy Chiu

改善想法 ( phonebook_opt )

基於上述的分析，大概把問題分成兩個部份，一個是從資料儲存結構下手，一個是從 node 的大小做修改，以上分別對應到 findName() 的時間和 cache miss 的情況。

1. 若採用 BST 中的 AVL tree 結構，則可把搜尋的時間複雜度從 O(n) 降為 O(logn)。
2. 縮小 node 的大小，讓 cache 一次可以載入較多個 node ，進而降低 cache miss 的情況，畢竟在 cache miss penalty 的處理是很花時間的。
   • 思考問題：如何縮小？使用指標還是 hash ？

實做

首先實做出 AVL-tree 的 function 並套用進 phonebook_opt 中，但是發現了一個非常糟糕的情形，就是 append() 300,000 筆資料進 AVL-tree 非常耗時，完全超出我的想像。雖然在 findName() 的時間進步到趨近於 0，但是由於 append() 的時間過於龐大，勢必需要改良。

註：以下圖片為資料量 10,000 筆的情形，因為 300,000 筆資料建置 AVL-tree 的過程我的電腦有點不堪負荷，所以先以這個資料量做比較。

新想法

因為 300,000 個節點的 AVL-tree 建置時間過長，若我能建置多棵節點沒那麼多的 AVL-tree 時間是否會降低呢？
於是我先使用 hash 把 300,000 的資料量縮小在 524288 個 buckets 的 hash table 中，然後針對每個發生 collision 的 bucket 以 AVL-tree 的資料結構儲存它所有的 slots，因為 hash table 的 access time 為 O(1)，所以 findName() 整體的時間複雜度仍為 O(logn)，但是實際上 AVL-tree 的節點數量下降了，應該能有效降低 append() 的時間。

此圖片資料為完整資料量約 300,000 筆資料。

有關 cache miss

想法：使用指標縮小 entry，讓 cache 一次能載入更多個 entry ，以期減少 cache。

typedef   struct   __PHONE_BOOK_DETAIL {
    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];
} phonebook_detail;

typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    phonebook_detail *detail;
    struct __PHONE_BOOK_ENTRY *pNext;
} entry;

未縮小前：

size of entry : 136 bytes
execution time of append() : 0.050650 sec
execution time of findName() : 0.005392 sec

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

           995,466      cache-misses              #   87.239 % of all cache refs      ( +-  0.40% )
         1,141,076      cache-references                                              ( +-  0.33% )
       263,434,281      instructions              #    1.39  insn per cycle           ( +-  0.02% )
       189,180,674      cycles                                                        ( +-  0.72% )

       0.074608521 seconds time elapsed                                          ( +-  1.03% )

縮小後：

size of entry : 32 bytes
execution time of append() : 0.048451 sec
execution time of findName() : 0.004391 sec

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

           126,346      cache-misses              #   30.294 % of all cache refs      ( +-  1.26% )
           417,067      cache-references                                              ( +-  1.24% )
       245,111,755      instructions              #    1.87  insn per cycle           ( +-  0.02% )
       131,043,506      cycles                                                        ( +-  0.67% )

       0.051576872 seconds time elapsed                                          ( +-  0.89% )

小結：以上結果可以看出 cache miss 從 87％ 降低至 30％ 。但是，如果套用到 hash-avl 的版本也會是如此嗎？

hash table size 為 524,288

size of entry : 40 bytes
execution time of append() : 0.108751 sec
execution time of findName() : 0.000000 sec

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

         1,570,234      cache-misses              #   79.919 % of all cache refs      ( +-  0.27% )
         1,964,773      cache-references                                              ( +-  0.23% )
       389,367,241      instructions              #    0.96  insn per cycle           ( +-  0.01% )
       407,322,946      cycles                                                        ( +-  0.21% )

       0.164066737 seconds time elapsed                                          ( +-  0.23% )

hash table size 為 1024

size of entry : 40 bytes
execution time of append() : 5.820135 sec
execution time of findName() : 0.000000 sec

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

        90,263,902      cache-misses              #   71.898 % of all cache refs      ( +-  0.59% )
       125,544,404      cache-references                                              ( +-  0.24% )
    12,512,828,631      instructions              #    0.85  insn per cycle           ( +-  0.00% )
    14,645,829,026      cycles                                                        ( +-  0.51% )

       5.906534319 seconds time elapsed                                          ( +-  0.62% )

總結：在 hash-avl 版本中，cache miss 卻大幅度的上升，試著縮小 hash table size 也指下降了一小部份，因而研判在建 AVL-tree 的過程中的樹結構的調整產生了大量的 cache miss 情形。而且發現了一個有趣的事情，就是雖然 table size 較小的 cache miss 相較比 table size 大的 cache miss 還要低，但是實際的 cache references 卻高出了非常多。

問題與討論

• 回答以下問題：本例選用的 dataset (也就是輸入電話簿的姓名) 是否存在問題？
  1. 有代表性嗎？跟真實英文姓氏差異大嗎？
     • 從兩個方面來分析，若單純以資料量的方面來說，300,000 筆的資料量的確可以代表一本電話簿蒐集了相當豐富的資料，如果以台灣來舉例，一個鄉鎮甚至是一個縣市說不定都不具有 300,000 的人口數。
     • 但是若從資料的內容來分析的話，可以看到本例選用的 dataset 裡的資料非常不符合真實性，並不像是真實世界中人名的格式，只是單純的字母的排列組合（ e.g. zzzz, zzzzz, zzzzzz ），其對照來看比較像是在網路世界中的 ID 組合，但是也不完全排除有人真的取名為 zzzz，畢竟這個世界是很自由的，只是在我的觀點，這不太容易存在在真實世界中。
  2. 資料難道「數大就是美」嗎？
     • 如果每筆資料都是相當 specific ，那資料的確是數大便是美。但是如果蒐集了許多無用的資料，不僅在分析上常常浪費許多資源，甚至分析結果也是一個錯誤的結果。
     • 所以數大就是美的前提，應該是在蒐集資料的過程中，儘量的確保我們蒐集的每筆資料都是我們所需要的且正確的資料。
  3. 如果我們要建立符合真實電話簿情境的輸入，該怎麼作？
     • 以台灣地區來說，可以上中華民國政府網路資料開放平台，有提供 CSV 和 API 接口供人使用