2018q1 Homework2 (prefix-search)

2018q1 Homework2 (prefix-search) ================================ contributed by <`potter903p`> ## 開發環境 ``` Architecture: x86_64 CPU 作業模式： 32-bit, 64-bit Byte Order: Little Endian CPU(s): 4 On-line CPU(s) list: 0-3 每核心執行緒數： 1 每通訊端核心數： 4 Socket(s): 1 NUMA 節點： 1 供應商識別號： GenuineIntel CPU 家族： 6 型號： 94 Model name: Intel(R) Core(TM) i5-6500 CPU @ 3.20GHz 製程： 3 CPU MHz： 200.000 CPU max MHz: 3600.0000 CPU min MHz: 800.0000 BogoMIPS: 6384.00 虛擬： VT-x L1d 快取： 32K L1i 快取： 32K L2 快取： 256K L3 快取： 6144K 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 art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault invpcid_single pti retpoline intel_pt rsb_ctxsw tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 erms invpcid rtm mpx rdseed adx smap clflushopt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp ``` ## 作業需求 - 在 GitHub 上 fork [prefix-search](https://github.com/sysprog21/prefix-search)，並修改 `Makefile` 以允許 `$ make bench` 時，可對 ternary search tree 的實作做出效能評比，涵蓋建立 tst 和 prefix search 的時間，應比照 [clz](https://hackmd.io/s/Hyl9-PrjW) 透過統計模型，取出 95% 信賴區間 - 測試程式碼應該接受 `--bench` 的執行參數，得以在沒有使用者輸入的前題下，對 tst 程式碼進行效能分析，應涵蓋 `cpy` 和 `ref` 兩種途徑 (詳情參閱 `tst.h` 的程式碼註解) - 解釋 tst 的優點和引入 tst 到電話簿或戶政管理系統的適用性 - 修改 [test＿ref.c](https://github.com/sysprog21/prefix-search/blob/master/test_ref.c)，參照裡頭標註 `FIXME` 的部分，替換成真正有效的 API 和對應的程式碼，這裡要求你學習分析現有的程式碼並得以擴充 - 分析 `test_cpy` 和 `test_ref` 兩種方式 (copy/reference) 的效能，並且針對現代處理器架構，提出效能改善機制 - 指出目前實作中，針對各國城市的 prefix search 有無缺陷呢？比方說無法區分城市和國家，並提出具體程式碼的修正 - 新增 `phonebook.c`，將之前 [phonebook](https://hackmd.io/s/SykZ8IMOf) 的基礎工作引入，透過 [ternary search tree](https://en.wikipedia.org/wiki/Ternary_search_tree) 讓電話簿程式得以更符合人性，當使用者新增資料時，可以在居住地透過 prefix search 找出最接近的城市並避免輸入錯誤 - 應該要能夠切換 command line interface (CLI) 和 benchmarking 模式 - 允許程式碼產生的隨機輸入，讓 tst 自動找到匹配的國家和城市名稱 - 以上述機率分佈函數來解釋，並且提出改善猜測精準度的方案 - 研究程式碼的 `tst_traverse_fn` 函式，並思考如何運用這個實作，注意到 [callback function](https://en.wikipedia.org/wiki/Callback_(computer_programming)) 的程式開發技巧/模式 - 將你的觀察、上述要求的解說、應用場合探討，以及各式效能改善過程，善用 gnuplot 製圖，紀錄於「[作業區](https://hackmd.io/s/BykAwRuKz)」 ## 開發過程首先是將 `test_ref.c` 中需要 `FIXEME` 的 function 裡面的 `CPY` 更改為 `REF` 希望能達到 save pointer 的效果。接著就是重新測試程式 ``` 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): Tai Tai - searched prefix in 0.000486 sec suggest[0] : Tai suggest[1] : Tai suggest[2] : Tai suggest[3] : Tai suggest[4] : Tai suggest[5] : Tai suggest[6] : Tai ``` 這邊雖然有顯示出近似搜尋的結果，但是顯示出來的結果都是相同的數值，所以到 `tst.c` 中的 `tst_ins_del` 一探究竟 ```clike= /* 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; } } ``` * 而 `CPY` 和 `REF` 的差別就在上面這個判斷式中 : * `CPY` 的作法是重新分配新的記憶體位置用來儲存傳入的 s * `REF` 是直接將所傳入的 s 之位置直接儲存起來再看到 `tst_ref.c` 中建立 tst 時會發生什麼事 ```clike= while ((rtn = fscanf(fp, "%s", word)) != EOF) { char *p = word; /* FIXME: insert reference to each string */ if (!tst_ins_del(&root, &p, INS, REF)) { fprintf(stderr, "error: memory exhausted, tst_insert.\n"); fclose(fp); return 1; } idx++; } ``` 這裡可以發現在使用 `ref` 的方式建立 tst 會保存所傳入之 s 的記憶體位址，但是上面這段程式碼中每次所傳入位址 p 的值都會是 word 的記憶體位址，這樣會導致在建樹的時候每次都是指向同一塊記憶體位址改進辦法 : 改變每次讀取資料的 word 的記憶體位址