Try   HackMD

2018q1 Homework2 (prefix-search)

contributed by < AliennCheng >

tags: syshw

開發環境

$ uname -a
Linux alienn-desktop 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 op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                6
On-line CPU(s) list:   0-5
Thread(s) per core:    1
Core(s) per socket:    6
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 158
Model name:            Intel(R) Core(TM) i5-8400 CPU @ 2.80GHz
Stepping:              10
CPU MHz:               2800.000
CPU max MHz:           4000.0000
CPU min MHz:           800.0000
BogoMIPS:              5616.00
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              9216K
NUMA node0 CPU(s):     0-5
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 est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb invpcid_single pti retpoline intel_pt rsb_ctxsw tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap clflushopt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp

這次的作業要求還滿多面向的，因此下面的開發練習我就按照要求的順序，分項逐步參考對應的資料實作，並仔細紀錄過程及心得。AliennCheng

初始測試

$ ./test_cpy
ternary_tree, loaded 259112 words in 0.086816 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: f
find word in tree: Taiwan
  found Taiwan in 0.000001 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): Tain
  Tain - searched prefix in 0.000039 sec

suggest[0] : Tain,
suggest[1] : Tainan,
suggest[2] : Taino,
suggest[3] : Tainter
suggest[4] : Taintrux,

做完 clone 後的初始測試之後，試著來測試一下 a 和 d 的功能。

choice: f
find word in tree: ThisIsANewCity
  ThisIsANewCity not found.

choice: a
enter word to add: ThisIsANewCity
  ThisIsANewCity - inserted in 0.000003 sec. (259113 words in tree)

choice: f
find word in tree: ThisIsANewCity
  found ThisIsANewCity in 0.000003 sec.

choice: d
enter word to del: ThisIsANewCity
  deleting ThisIsANewCity
  deleted ThisIsANewCity in 0.000011 sec

choice: f
find word in tree: ThisIsANewCity
  ThisIsANewCity not found.

可以發現 a 的功能就是在這個資料庫裡新增一個可自行命名的節點，而 d 的功能就是把符合輸入名稱的節點刪除。

修改 MakeFile

作業要求

在 GitHub 上 fork prefix-search，並修改 Makefile 以允許 $ make bench 時，可對 ternary search tree 的實作做出效能評比，涵蓋建立 tst 和 prefix search 的時間，應比照 clz 透過統計模型，取出 95% 信賴區間

  • 測試程式碼應該接受 --bench 的執行參數，得以在沒有使用者輸入的前提下，對 tst 程式碼進行效能分析，應涵蓋 cpy 和 ref 兩種途徑 (詳情參閱 tst.h 的程式碼註解)
  • 解釋 tst 的優點和引入 tst 到電話簿或戶政管理系統的適用性

解讀 MakeFile

修改之前，總是要先搞懂它原本在幹嘛，因此第一步便是解讀 MakeFile，看看整個連結編譯的邏輯如何。

# Control the build verbosity                                                   
ifeq ("$(VERBOSE)","1")
    Q :=
    VECHO = @true
else
    Q := @
    VECHO = @printf
endif

馬上遇到問題，上面這段 code 到底在定義什麼？試圖 google 一下，找到這篇 Controlling verbosity of make，裏面有提到這是一種調整 verbosity 的方式，但是既然這段的目的是為了調整 verbosity，那是不是應該有方法在不改變這段程式碼的同時改變 verbosity，是有什麼指令嗎？換句話說，應該有辦法可以改變 VERBOSE 這個變數，但我目前找不到這個變數定義在哪。

原來只要直接在 make 時加在後面就可以控制了 xD

$ make VERBOSE=1
cc -o test_cpy.o -Wall -Werror -g -c -MMD -MF .test_cpy.o.d test_cpy.c
cc -o tst.o -Wall -Werror -g -c -MMD -MF .tst.o.d tst.c
cc  -o test_cpy test_cpy.o tst.o
cc -o test_ref.o -Wall -Werror -g -c -MMD -MF .test_ref.o.d test_ref.c
cc  -o test_ref test_ref.o tst.o
rm test_cpy.o test_ref.o tst.o

其他沒什麼特別的，大致上在上次的 phonebook 都看過了，架構上也就是分別編譯出 test_cpy 以及 test_ref ，它們同時都有用到 test.o 作為 library。目前這兩個檔案是相同的，在下個部份將會修改到 test_ref 因此編譯及測試需獨立出來。

新增 make bench 功能

比較建立 ternary tree 的時間

首先我參照上次 phonebook 的方式，先在 test_cpy.c 及 test_ref.c 中加入新的 struct 名為 _TIME_NODE，用來記錄每次執行 prefix search 所耗的時間。

typedef struct _TIME_NODE {
    double time;
    int sum;
    struct _TIME_NODE *next;
} time_node;

接著利用下面的方式讓程式碼接受 --bench 的指令，使其在沒有使用者輸入的情況下可透過對 cities.txt 中每個城市的前三碼進行 prefix search，以評估 prefix search 的效能。之所以採用這種對全部程式的前三碼進行搜尋的評估方式，一方面是為了讓 benchmark 的輸入具有一般性，也就是讓輸入顯的更合理，避免有 bbb 這樣子的輸入而錯估效能；另一方面，也讓輸入的分佈更趨近於現實，換句話說，就是愈多城市具有的相同 prefix 會在 benchmark 中更顯的重要。




    if (argc == 2 && strcmp(argv[1], "--bench") == 0) {
        /* evaluate the performance here */
    }

接著在 Makefile 中加入 make bench 指令如下，最終可輸出兩張圖，一張評估 test_cpy 及 test_ref 建立 ternary tree 的效能；另一張用前述的方式評估兩者 prefix search 的效能。

bench: $(TESTS)
	$(RM) $(TXT) $(PNG)
	./test_cpy --bench
	./test_ref --bench
	gnuplot scripts/runtime.gp

輸出

因為目前尚未更動 test_ref.c，因此目前兩者的程式碼是幾乎一致的，也就是從下兩個圖只能得到「輸出功能正常」這個結論而已。
build_time_ori
prefix_search_ori

取出信賴區間

目前卡在無法叫用 math.h 函式庫，詳情在下面問題紀錄。沒有開根號就不能算標準差啊！

這部份我先擱著，計算式都寫好了只差編譯問題而已，等到後面完成得差不多再回來解決。AliennCheng

解釋 tst 的好處

解釋 tst 的優點和引入 tst 到電話簿或戶政管理系統的適用性
三元樹的效率如何優秀，直接看時間複雜度最清楚：

Linear search binary search tree ternary search tree
insert O( n ) O( log(n) ) O( log3(n) )
delete O( n ) O( log(n) ) O( log3(n) )
search O( n ) O( log(n) ) O( log3(n) )

也因為這個優勢，使得在需要建立搜尋資料庫時，tst 是個好的選擇。
電話簿方面的應用，由於都是由長短相近的數字組成，因此字串的比較上相對容易，tst 也顯的容易實現。但戶政管理系統往往需要多種搜尋方法，如果只單單靠一棵 tst 可能會使效率不彰，舉例來說，如果用了電話當 tst 建立的基礎，但需要搜尋地址時可能就沒辦法透過樹的搜尋找到所需要的資料節點。

修改 test＿ref.c

作業要求

修改 test＿ref.c，參照裡頭標註 FIXME 的部分，替換成真正有效的 API 和對應的程式碼，這裡要求你學習分析現有的程式碼並得以擴充

分析 test_cpy 和 test_ref

作業要求

分析 test_cpy 和 test_ref 兩種方式 (copy/reference) 的效能，並且針對現代處理器架構，提出效能改善機制

針對各國城市的 prefix search 當中缺陷的探討

作業要求

指出目前實作中，針對各國城市的 prefix search 有無缺陷呢？比方說無法區分城市和國家，並提出具體程式碼的修正

引入 phonebook

作業要求

新增 phonebook.c，將之前 phonebook 的基礎工作引入，透過 ternary search tree 讓電話簿程式得以更符合人性，當使用者新增資料時，可以在居住地透過 prefix search 找出最接近的城市並避免輸入錯誤

  • 應該要能夠切換 command line interface (CLI) 和 benchmarking 模式
  • 允許程式碼產生的隨機輸入，讓 tst 自動找到匹配的國家和城市名稱
  • 以上述機率分佈函數來解釋，並且提出改善猜測精準度的方案

研究程式碼的 tst_traverse_fn 函式

研究程式碼的 tst_traverse_fn 函式，並思考如何運用這個實作，注意到 callback function 的程式開發技巧/模式

參考資料

dywang 的 makefile 教學
st9007a同學的共筆

問題紀錄與解答

在嘗試使用 math.h 當中的函式時，編譯時會出現 undefined reference to sqrt，而無法編譯成功。
網路上找了一下，找到的解決方法都是在編譯的時候加上 -lm 這個 flag，但是我在 Makefile 中修正過後目前仍然會出現 undefined reference to sqrt。

Last changed by 
 
AliennCheng
0
257
Published on HackMD