2018q1 Homework2 (prefix-search)

contributed by <rwe0214>

tags: rwe0214

開發環境

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

分析程式

首先依照作業要求找到註解內容 FIXME 的地方，並更改以下程式碼：

tst_ins_del(&root, &p, INS, CPY)

為

tst_ins_del(&root, &p, INS, REF)

註：REF 和 CPY 變數於程式開頭便以 enum 定義，分別為 0 和 1

執行結果：

$ ./test_ref
ternary_tree, loaded 259112 words in 0.138627 sec

Commands:
 a  add word to the tree
 f  find word in tree
 s  search words matching prefix
 d  delete word from the tree
 q  quit, freeing all data

choice: s
find words matching prefix (at least 1 char): Taipe
  Taipe - searched prefix in 0.000007 sec

suggest[0] : Taipe
suggest[1] : Taipe
suggest[2] : Taipe
suggest[3] : Taipe
suggest[4] : Taipe

發現執行出來的結果錯誤的離譜，而且打印出來的字串也一樣，這其中一定有什麼誤會。於是我去觀察了 tst.h 和 tst.c 中關於此函式的定義

void *tst_ins_del(tst_node **root, char *const *s, const int del, const int cpy)

而我更動的參數影響的程式碼其實不多，如下幾行：

/* Place nodes until end of the string, at end of stign allocate

* space for data, copy data as final eqkid, and return.

*/

 if (*p++ == 0) {
     if (cpy) { /* allocate storage for 's' */
         const char *eqdata = strdup(*s);
         if (!eqdata)
             return NULL;
         curr->eqkid = (tst_node *) eqdata;
         return (void *) eqdata;
     } else { /* save pointer to 's' (allocated elsewhere) */
         curr->eqkid = (tst_node *) *s;
         return (void *) *s;
     }
}

可以發現因為我傳入 REF 值為 0 ( 即cpy 為 0 )，所以程式並不會進入 9~13 行的 if 而是第 14~16 行的 else 執行。
這裡的差別透過註解可以得知 if 區塊會分配一個新的記憶體空間給新的 tst_node 並把值複製進去，而 else 部份則是直接指向傳入的字串 s 位址。

回到我們的程式碼 test_ref.c ，可以發現從讀檔建立 tst_tree，到最後程式使用 polling 的方式等待使用者輸入字串比對資料皆是使用同一個變數 word ，所以如果我們使用 ref 方式建立這個 tst_tree 就會發生每個節點都指向同一塊記憶體位置，所以當這個位址的資料一改變整棵 tst_tree 的數值也就不正確了，這也是為什麼我們的執行結果會跟我們最後輸入的字串 Taipe 都相同的原因。

為了證實這個想法，我將 test_ref.c 做了修改，觀察是否都是參照到相同的記憶體 ( 8b4ddca )。

執行結果：

$ ./test_ref 
ternary_tree, loaded 259112 words in 0.148404 sec

##NOTE##
Use "*p = word"
The addr pointed by tst-tree's nodes' key is repeated at 259111 times during the tst-tree constructing period.

Commands:
 a  add word to the tree
 f  find word in tree
 s  search words matching prefix
 d  delete word from the tree
 q  quit, freeing all data

choice: 
 

可以看到所有的 key 指向的位址皆一樣，也證實了我的想法。

分析問題

既然已經確定問題是出在全數節點都指向相同的記憶體位置，那麼我在建立 tst_tree 時，只要把每個讀入的字串先行配置記憶體給它就好了阿！這樣每個節點便都會指向不同記憶體也不會造成程序出錯了。

但是仔細想了想，這樣的步驟和使用 cpy 的方法 assign 一塊記憶體給節點有什麼不同呢？

回想第一次的作業 phonebook，好像有做過類似的修改，把一個 struct 的值挪去另一個記憶體空間，再用一個 pointer 指向這塊記憶體。如此一來不但縮小整個 struct 的大小進而減少了 cache miss rate。

沒錯，這個部份和正是 cpy 和 ref 的不同，一個是在 node 內新增一塊記憶體儲存資料，一個則是新增一個 pointer 去指向儲存的資料，根據作業一的想法，在 cpu 使用率上應該會因為減少 cache miss rate 而大幅提昇。

於是我觀察原本的程式碼在 cpy 的情形下是怎麼分配記憶體的

if (cpy) { /* allocate storage for 's' */
         const char *eqdata = strdup(*s);
         if (!eqdata)
             return NULL;
         curr->eqkid = (tst_node *) eqdata;
         return (void *) eqdata;
}

使用的是 strdup() 以字面上來看好像只是 string duplicate 的意思怎麼會有記憶體分配呢？
查詢 Linux Programmer's Manual 後發現：

DESCRIPTION
       The strdup() function returns a pointer to a  new  string  which  is  a
       duplicate  of the string s.  Memory for the new string is obtained with
       malloc(3), and can be freed with free(3).

原來這個函式背後已經偷偷幫我們把記憶體空間給 malloc 出來了，既然如此，我決定如法炮製這個記憶體配置方式並觀察其執行結果如何 (32d6bd9)：

$ ./test_ref 
ternary_tree, loaded 259112 words in 94.825388 sec

##NOTE##
Use "strdup()"
The addr pointed by tst-tree's nodes' key is repeated at 0 times during the tst-tree constructing period.

Commands:
 a  add word to the tree
 f  find word in tree
 s  search words matching prefix
 d  delete word from the tree
 q  quit, freeing all data

choice: s
find words matching prefix (at least 1 char): Taipe
  Taipe - searched prefix in 0.000008 sec

suggest[0] : Taipei,

Commands:
 a  add word to the tree
 f  find word in tree
 s  search words matching prefix
 d  delete word from the tree
 q  quit, freeing all data

choice: 

可以看到記憶體位置已無重複且程式已經可以正確執行。
接著就是比較 cache miss 的部份 (62b771e)：

Performance counter stats for './test_cpy' (1000 runs):

         1,193,397      cache-misses              #   52.608 % of all cache refs      ( +-  0.15% )
         2,268,480      cache-references                                              ( +-  0.10% )
       535,150,940      instructions              #    1.14  insn per cycle           ( +-  0.00% )
       470,590,982      cycles                                                        ( +-  0.07% )

       0.181175585 seconds time elapsed                                          ( +-  0.09% )

Performance counter stats for './test_ref' (1000 runs):

         1,163,763      cache-misses              #   50.195 % of all cache refs      ( +-  0.09% )
         2,318,487      cache-references                                              ( +-  0.03% )
       582,672,201      instructions              #    1.18  insn per cycle           ( +-  0.00% )
       493,821,446      cycles                                                        ( +-  0.04% )

       0.189427892 seconds time elapsed                                          ( +-  0.05% )

WHAT THE …？？？

沒想到竟然和預期的結果有點落差，cpy 和 ref 的 cache miss 竟然相差不遠或者說幾乎一樣，這部份可以能需要再思考幾天了QAQ

反覆思考一會兒，發現我好像對 hw1 的結果有點斷章取義了， hw1 之所以改成 pointer 會降低 cache miss 的原因是因為 pointer 指向的資料是並不是搜尋時會使用到的資料 ( key )，而這次的作業 pointer 指向的資料則是搜尋時會用到的 key ，所以 cpu 會多一個從 pointer 的位址再載入資料的步驟。這一來一往也讓 cache miss 相差不遠。