2018q1 Homework2 (prefix-search)

contributed by < chasingfar >

系統環境

$ uname -a
Linux chasingjar-V5-591G 4.4.0-116-generic #140-Ubuntu SMP Mon Feb 12 21:23:04 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):                8
On-line CPU(s) list:   0-7
每核心執行緒數：2
每通訊端核心數：4
Socket(s):             1
NUMA 節點：         1
供應商識別號：  GenuineIntel
CPU 家族：          6
型號：              94
Model name:            Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz
製程：              3
CPU MHz：             800.007
CPU max MHz:           3500.0000
CPU min MHz:           800.0000
BogoMIPS:              5183.88
虛擬：              VT-x
L1d 快取：          32K
L1i 快取：          32K
L2 快取：           256K
L3 快取：           6144K
NUMA node0 CPU(s):     0-7
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 aperfmperf eagerfpu 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 epb invpcid_single intel_pt retpoline kaiser 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 dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp
$ free
              total        used        free      shared  buff/cache   available
Mem:        8029896     2599920     3639168      386196     1790808     4751816
置換：     3999740           0     3999740

作業要求

修改 Makefile 以允許 $ make bench

可對 ternary search tree 的實作做出效能評比，涵蓋建立 tst 和 prefix search 的時間，應比照 clz 透過統計模型，取出 95% 信賴區間

新增的部份

bench: $(TESTS)  
   echo 3 | sudo tee /proc/sys/vm/drop_caches  
   perf stat --repeat 100 \  
      -e cache-misses,cache-references,instructions,cycles \  
      ./test_cpy --bench cmd.txt  
   echo 3 | sudo tee /proc/sys/vm/drop_caches  
   perf stat --repeat 100 \  
      -e cache-misses,cache-references,instructions,cycles \  
      ./test_ref --bench cmd.txt

接受 --bench 的執行參數

在沒有使用者輸入的前提下，對 tst 程式碼進行效能分析，應涵蓋 cpy 和 ref 兩種途徑 (詳情參閱 tst.h 的程式碼註解)

在 main() 加入

FILE *cmdin=stdin;  
int bench_mode=0;  
if(argc>=2){  
    if(strcmp(argv[1],"--bench")==0){  
        bench_mode=1;  
    }  
    if(argc>2){  
        cmdin=fopen(argv[2], "r");  
        if (!cmdin) { /* prompt, open, validate file for reading */  
            fprintf(stderr, "error: file open failed '%s'.\n", argv[3]);  
            return 1;  
        }  
    }  
}

解釋 tst 的優點和引入 tst 到電話簿或戶政管理系統的適用性

修改 FIXME 的部分

分析 test_cpy 和 test_ref 兩種方式 (copy/reference)

針對現代處理器架構，提出效能改善機制

目前實作中，針對各國城市的 prefix search 有無缺陷呢？

比方說無法區分城市和國家，並提出具體程式碼的修正

將 phonebook 的基礎工作引入

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

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

研究程式碼的 tst_traverse_fn 函式

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