2018q1 Homework2 (prefix-search)

2018q1 Homework2 (prefix-search) ==== contributed by < `TingL7` > 系統環境 ---- ``` $ uname -r 4.14.0-041400-generic $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian CPU(s): 8 On-line CPU(s) list: 0-7 Thread(s) per core: 2 Core(s) per socket: 4 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 142 Model name: Intel(R) Core(TM) i7-8550U CPU @ 1.80GHz Stepping: 10 CPU MHz: 2000.000 CPU max MHz: 4000.0000 CPU min MHz: 400.0000 BogoMIPS: 3984.00 Virtualization: VT-x L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 8192K 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 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 intel_pt 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 ``` ## Ternary Search Tree * 特性：每個節點有 3 個小孩，在搜尋時，比對每個字元與樹的節點字元的 ASCII code 大小或相等，以決定拜訪哪個小孩，並不斷比對字元直到字尾，觀察字尾所在的節點決定是否為要搜尋的字。 * 優點： * 與 [trie](http://www.cnblogs.com/rush/archive/2012/12/30/2839996.html) 相比，空間的使用率增加。 Trie 要作英文字母的搜尋時，每個節點會有 26 個孩子，但實際上並不是所有孩子都有用到。而 tst 只有 3 個孩子空間使用率會比較高。 ![](https://i.imgur.com/k3I3c57.png) 在只有四個字母的時後，trie 包含 {AB, ABBA, ABCD, BCD} ![](https://i.imgur.com/QUuaPKx.png) 同樣的資料，在 tst 儲存的空間使用率較高。 * 一節點的子孫都有同樣的前綴字，因此適合用在自動補齊單字。 * 引入 tst 到電話簿或戶政管理系統的適用性 * 電話簿或戶政管理系統的特性在於:資料庫有大量類似的字詞，如地址，有很多台南市...的，他們的前綴詞都相同，如果每筆資料都直接存放在記憶體，會有一堆重複的字出現，造成記憶體浪費，因此使用 tst 就很適合。 ## 初始測試 ``` $ make $ ./test_cpy ternary_tree, loaded 259112 words in 0.108185 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.000002 sec. choice: f find word in tree: Chunghwa Chunghwa not found. choice: s find words matching prefix (at least 1 char): Chung Chung - searched prefix in 0.000008 sec suggest[0] : Chunghwa, choice: a enter word to add: tii tii - inserted in 0.000006 sec. (259113 words in tree) choice: f find word in tree: tii found tii in 0.000002 sec. choice: d enter word to del: tii deleting tii deleted tii in 0.000010 sec choice: q ``` * 奇妙的事情出現了，使用 `f` 找不到的東西，使用 `s` 居然找到了，多試了幾筆資料，推測 `f` 能夠查詢的只有國家，而無法查詢城市。 * `test_cpy` 、 `test_ref`在功能測試上，結果相同。 * `a` 功能為在數中新增節點， `d` 為刪除節點。 ## 修改 test_ref.c 開啟 `test_ref.c` * enum 宣告內容為遞增的 int ，因此 `INS` 為 0 ， `DEL` 為 1 。由 define 可以得知 `REF` 為 0 ， `CPY` 為 1 。 ```clike=9 enum { INS, DEL, WRDMAX = 256, STKMAX = 512, LMAX = 1024 }; #define REF INS #define CPY DEL ``` * 需要修改的地方有 3 處: ```clike=54 /* FIXME: insert reference to each string */ if (!tst_ins_del(&root, &p, INS, CPY)) { ``` ```clike=89 /* FIXME: insert reference to each string */ res = tst_ins_del(&root, &p, INS, CPY); ``` ```clike=142 /* FIXME: remove reference to each string */ res = tst_ins_del(&root, &p, DEL, CPY); ``` * 開啟 `tst.c` 查看 `tst_ins_del` 的內容函式功能為在三元樹中插入或刪除節點。主要改變的參數 `cpy` ，決定要幫字串 allocate storage 或 save pointer 只出現在 for 迴圈中： ```clike= void *tst_ins_del(tst_node **root, char *const *s, const int del, const int cpy) { ... /* if not duplicate, insert remaining chars into tree rooted at curr */ for (;;) { ... /* 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; } } pcurr = &(curr->eqkid); } } ``` ### FIXME 1 建立 tst * 將 `CPY` 改成 `REF` ，結果在 command `s` 、 `q` 會出錯： ``` choice: s find words matching prefix (at least 1 char): Chung Chung - searched prefix in 0.000009 sec suggest[0] : Chung suggest[1] : Chung suggest[2] : Chung suggest[3] : Chung choice: q *** Error in `./test_ref': free(): invalid pointer: 0x00007ffd1303a630 *** ======= Backtrace: ========= ... ======= Memory map: ======== ... Aborted (core dumped) ``` * 傳入 `tst_ins_del()` 的參數 `s` 為讀入的 `word` ，在 save pointer 的情況下，直接將 tst 指向 `s`，但 `word` 只是為了讀檔而暫存的地方，資料會不停的被洗掉，因此，有儲存指標，但指標的內容不停被更動。 ```clike=52 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++; } ``` * command `s` * 在使用 `s` 指令時，會呼叫 `tst_search_prefix(const tst_node *root, const char *s, char **a, int *n, const int max)` ，其中參數 `a` 是儲存 `suggest` 的變數，而在這個函數中，決定 `a` 的是一個遞迴函數 ```c void tst_suggest(const tst_node *p, const char c, const size_t nchr, char **a, int *n, const int max) { if (!p || *n == max) return; tst_suggest(p->lokid, c, nchr, a, n, max); if (p->key) tst_suggest(p->eqkid, c, nchr, a, n, max); else if (*(((char *) p->eqkid) + nchr - 1) == c) a[(*n)++] = (char *) p->eqkid; tst_suggest(p->hikid, c, nchr, a, n, max); } ``` 可以發現: `a` 直接取存放在 leaf 的值，也就是在建立 tst 時的 `word` 。但，很不幸的，之前在建立時，由於指向的內容是被修改過的，因此在使用 command `s` 時，建議值會出錯。 * 修改一 * 在不更動 `tst.c` 的前提下，要儲存指標，且內容不得更動，就要使每次進去 `tst_ins_del()` 中的 `word` 位址不同。 * 最直接，且考慮到記憶體連續避免 cache miss 過大，使用 array 使得每次讀進來的 word 存放到不同的位址。 * array 大小：考慮到程式要可以增加資料 (command `a`) ，不適合直接寫死，而且直接寫死要考慮到有 259111 個城市 (word) ，宣告太大的陣列會 stack overflow ，因此以動態陣列的方式宣告比較適合。 * 離開時，要釋放 word_tst 的記憶體。 * 程式碼 ```clike= char (*word_tst)[WRDMAX] = malloc(260000 * sizeof(*word_tst)); while ((rtn = fscanf(fp, "%s", word_tst[idx])) != EOF) { char *p = word_tst[idx]; /* 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++; } ... case 'q': tst_free_all(root); free(word_tst); return 0; break; ``` * 結果 ``` choice: s find words matching prefix (at least 1 char): Tain Tain - searched prefix in 0.000018 sec suggest[0] : Tain, suggest[1] : Tainan, suggest[2] : Taino, suggest[3] : Tainter suggest[4] : Taintrux, choice: q *** Error in `./test_ref': free(): invalid pointer: 0x00007f4cc9d7ef10 *** ======= Backtrace: ========= ... ======= Memory map: ======== ... Aborted (core dumped) ``` * command `s` 沒問題，command `q` 還有錯誤。 * command `q` * `q` 相關的程式碼很單純，主要就是在釋放記憶體。 ```c case 'q': tst_free_all(root); free(word_tst); return 0; break; ``` * 在 `tst.c` 中，與釋放記憶體有關的函式有兩個： ```clike=400 /** free the ternary search tree rooted at p, data storage internal. */ void tst_free_all(tst_node *p) { if (!p) return; tst_free_all(p->lokid); if (p->key) tst_free_all(p->eqkid); tst_free_all(p->hikid); if (!p->key) free(p->eqkid); free(p); } /** free the ternary search tree rooted at p, data storage external. */ void tst_free(tst_node *p) { if (!p) return; tst_free(p->lokid); if (p->key) tst_free(p->eqkid); tst_free(p->hikid); free(p); } ``` 差別在於是否有釋放 leaves 的記憶體。如註解所寫，資料現在儲存在 array 中，可以說儲存在 tst 外，因此不應該由 tst 這邊釋放。因此該使用 `tst_free()` 而非 `tst_free_all()`。 * 修改： * 程式碼 ``` case 'q': tst_free(root); free(word_tst); return 0; break; ``` * 結果正常退出，沒有錯誤訊息。 ### FIXME 2 to add word to the tree * 將 `CPY` 改成 `REF` ```clike case 'a': printf("enter word to add: "); if (!fgets(word, sizeof word, stdin)) { fprintf(stderr, "error: insufficient input.\n"); break; } rmcrlf(word); p = word; t1 = tvgetf(); /* FIXME: insert reference to each string */ res = tst_ins_del(&root, &p, INS, REF); t2 = tvgetf(); if (res) { idx++; printf(" %s - inserted in %.6f sec. (%d words in tree)\n", (char *) res, t2 - t1, idx); } else printf(" %s - already exists in list.\n", (char *) res); break; ``` * 結果在 command `s` 、 `d` 會出錯： ``` choice: a enter word to add: Tiz Tiz - inserted in 0.000009 sec. (259113 words in tree) choice: s find words matching prefix (at least 1 char): Tiz Tiz - searched prefix in 0.000021 sec suggest[0] : Tiz suggest[1] : Tiz suggest[2] : Tiza, suggest[3] : Tizapán suggest[4] : Tizayuca, suggest[5] : Tizi suggest[6] : Tizi-n-Tleta, suggest[7] : Tizimín, suggest[8] : Tiznit, suggest[9] : Tizzano choice: d enter word to del: Tiz deleting Tiz *** Error in `./test_ref': free(): invalid pointer: 0x00007ffe8b614100 *** ======= Backtrace: ========= ... ======= Memory map: ======== ... Aborted (core dumped) ``` * command `s` 出錯的原因在於 insert 時失敗，與 FIXME 1 相同，有 word 指向同一塊位址的問題。因此，仿造上面的作法，以 array 的方式儲存字串。 * command `d` 出錯的原因為沒有正確釋放記憶體。 * 修改 * 程式碼 ```clike=81 case 'a': printf("enter word to add: "); if (!fgets(word_tst[idx], sizeof word_tst[idx], stdin)) { fprintf(stderr, "error: insufficient input.\n"); break; } rmcrlf(word_tst[idx]); p = word_tst[idx]; t1 = tvgetf(); /* FIXME: insert reference to each string */ res = tst_ins_del(&root, &p, INS, REF); t2 = tvgetf(); if (res) { idx++; printf(" %s - inserted in %.6f sec. (%d words in tree)\n", (char *) res, t2 - t1, idx); } else printf(" %s - already exists in list.\n", (char *) res); break; ``` * 結果 ``` choice: a enter word to add: Tiz Tiz - inserted in 0.000010 sec. (259113 words in tree) choice: s find words matching prefix (at least 1 char): Tiz Tiz - searched prefix in 0.000022 sec suggest[0] : Tiz suggest[1] : Tiza, suggest[2] : Tizapán suggest[3] : Tizayuca, suggest[4] : Tizi suggest[5] : Tizi-n-Tleta, suggest[6] : Tizimín, suggest[7] : Tiznit, suggest[8] : Tizzano ``` ### FIXME 3 to delete a word from the tree * command `d` 出錯的地方在 `tst_ins_del()` 中所呼叫的 `tst_del_word()` ```clike=238 return tst_del_word(root, curr, &stk, 1); ``` ```clike=54 static void *tst_del_word(tst_node **root, tst_node *node, tst_stack *stk, const int freeword) { tst_node *victim = node; /* begin deletion w/victim */ tst_node *parent = tst_stack_pop(stk); /* parent to victim */ if (!victim->refcnt) { /* if last occurrence */ if (!victim->key && freeword) /* check key is nul */ free(victim->eqkid); /* free string (data) */ ... ``` * line 64 的 free 是非法的，因為這裡的 string data 實際上是在建立資料庫時的 word array 中，不能直接 free 。 * 註解中提到 `if 'freeword = 0', node->eqkid is stored elsewhere and not freed` ，但從上面這兩段程式碼可以發現 freeword 永遠為 1 ，因次要將 line 238 的 `tst_del_word（）` 最後一個參數改為 `cpy` 。 * 修改 * 程式碼 (in `tst.c`) ```clike=238 return tst_del_word(root, curr, &stk, 238); ``` * 結果 ``` choice: a enter word to add: Tiz Tiz - inserted in 0.000009 sec. (259113 words in tree) choice: d enter word to del: Tiz deleting Tiz deleted Tiz in 0.000014 sec ``` * idx 問題 * 因為 `word_tst` 是由 `idx` 在控制，但在刪除之後， `word_tst` 實際上是沒有減少的，但是會作 `idx--` 因此在之後新增時，會覆蓋到原本 `word_tst` 中的資料。 * 解決：新增控制 `word_tst` 的變數。 * 程式碼 ```clike=40 char (*word_tst)[WRDMAX] = malloc(260000 * sizeof(*word_tst)); int i = 0; ``` ```clike=54 while ((rtn = fscanf(fp, "%s", word_tst[i])) != EOF) { char *p = word_tst[i]; /* 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++; i++; } ``` ```clike=83 case 'a': printf("enter word to add: "); if (!fgets(word_tst[i], sizeof word_tst[i], stdin)) { fprintf(stderr, "error: insufficient input.\n"); break; } rmcrlf(word_tst[i]); p = word_tst[i]; t1 = tvgetf(); /* FIXME: insert reference to each string */ res = tst_ins_del(&root, &p, INS, REF); t2 = tvgetf(); if (res) { i++; idx++; ``` ## 修改 `Makefile` 以做出效能評比 * 參考[tina0405共筆](https://hackmd.io/s/SkEFpwh2-#2017q3-Homework2-prefix-search) * 程式要可接受`--bench` ，作為 main 的參數。 * 意指執行如下指令，`--bench` 會存放在 argv[1] ``` ./test_ref --bench s Tain ``` * 需要在 main function 中判斷，是否在執行 `--bench` ，可透過設立變數 (bench_flag) 來判斷。`test_ref.c` 及 `test_cpy.c` 都要設立。 * 執行 `--bench` 與一般 make ，不一樣的地方在於不用手動輸入資料，要自動的讀資料。先設定讀入的資料只有一筆 (s Tain) ，處理完之後，必須自動執行 command `q` 。 * 部份修改過的程式碼 ```c int bench_flag = (agrc > 1 && !(strcmp(argv[1], "--bench"))?1:0; ... for(;;) char *p; if(bench_flag){ if(bench_flag > 1) strcpy(word, "q"); else{ strcpy(word, argv[2]); bench_flag++; } }else{ printf( "\nCommands:\n" " a add word to the tree\n" " f find word in tree\n" " s search words matching prefix\n" " d delete word from the tree\n" " q quit, freeing all data\n\n" "choice: "); fgets(word, sizeof word, stdin); } p = NULL; switch (*word) { case 'a': if(bench_flag) strcpy(word_tst[i], argv[3]); else{ printf("enter word to add: "); if (!fgets(word_tst[i], sizeof word_tst[i], stdin)) { fprintf(stderr, "error: insufficient input.\n"); break; } } ... ``` * 參考上個作業 [phonebook](https://github.com/TingL7/phonebook) 的 Makefile ，讓程式進行 100 次，並作效能評比 * 程式碼(in `Makefile`) ```clike DATA = s Tain bench: $(TEST) perf stat --repeat 100 \ -e cache-misses,cache-references,instructions,cycles \ ./test_cpy --bench $(DATA) perf stat --repeat 100 \ -e cache-misses,cache-references,instructions,cycles \ ./test_ref --bench $(DATA) ``` * 結果 * cpy ``` ternary_tree, loaded 259112 words in 0.116547 sec Tain - searched prefix in 0.000003 sec, 5 suggests Performance counter stats for './test_cpy --bench s Tain' (100 runs): 2,944,151 cache-misses:u # 37.957 % of all cache refs ( +- 0.21% ) 7,756,549 cache-references:u ( +- 0.17% ) 513,611,005 instructions:u # 1.35 insn per cycle ( +- 0.07% ) 380,216,819 cycles:u ( +- 0.08% ) 0.134732372 seconds time elapsed ( +- 0.18% ) ``` * Ref 版本 ``` ternary_tree, loaded 259112 words in 0.131607 sec Tain - searched prefix in 0.000005 sec,5 suggests Performance counter stats for './test_ref --bench s Tain' (100 runs): 3,644,486 cache-misses:u # 42.456 % of all cache refs ( +- 0.29% ) 8,584,217 cache-references:u ( +- 0.12% ) 483,558,386 instructions:u # 1.23 insn per cycle ( +- 0.00% ) 394,352,557 cycles:u ( +- 0.12% ) 0.168124774 seconds time elapsed ( +- 0.28% ) ``` * 建立 tst 和 prefix search 的時間比較圖 ![](https://i.imgur.com/gSOAFTn.png) * 可以發現 cpy 版本 cache miss 較低，而且建立 tst 的時間也比較低。 * 雖然 cpy 版本中，使用 strdup 有 malloc 記憶體，在使用上並不連續，但是 ref 宣告了一個很大的陣列，但實際上並沒有全部用到，因此 cache miss 會比較高。 ## prefix search 缺陷 * 兩個字以上的城市，在 tst 中會被視為兩個地方。 * 如：Newcastle under Lyme, United States * 不用 fscanf() 讀入，改用 fget(),並以 `, ` 作為 token 且割字串。 * find 找查城市時，需要在末端輸入 `,` * 無法分辨城市、州、國家 * ~~建立 3 棵樹，分別存放城市、州、國家。~~ * 所需的空間比 1 棵樹大。 * 搜尋時，會花費更多時間。 * ~~以 `,` 分辨~~ * 無法分辨州、城市 * 以其他符號分辨？ * 在 tst_node 新增 `iscountry` 欄位 * 城市與國家的關係，毫無聯繫 * 修正 * 程式碼 ```clike= while ((fgets(str_ar, WRDMAX * 3, fp)) != NULL) { str = str_ar; strcpy(word, strsep(&str, ",\n")); while (strcmp(word, "") != 0) { if(word[0] == ' '){ int j; for(j = 1;j < strlen(word);j++) word_tst[i][j-1] = word[j]; word_tst[i][j-1] = '\0'; }else{ int j; for(j = 0;j < strlen(word);j++) word_tst[i][j] = word[j]; word_tst[i][j] = '\0'; } char *p = word_tst[i]; /* 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++; i++; strcpy(word, strsep(&str, ",\n")); } } ``` * 結果 ``` ternary_tree, loaded 206849 words in 0.106141 sec choice: f find word in tree: Tainan found Tainan in 0.000004 sec. choice: f find word in tree: Newcastle under Lyme found Newcastle under Lyme in 0.000004 sec. ``` 實際上只有 206849 個城市、國家。 ## 效能評比 part2 & 分析 `test_cpy` 和 `test_ref` 的效能，並提出改善機制 * 分析 prefix search * 針對所有的資料，取前三個字元來搜尋。 ```clike= char search_word[PREFIX] = ""; int count = 0; fp = fopen(IN_FILE, "r"); while(fscanf(fp, "%s", word) != EOF){ if(strlen(word) < 3) continue; strncpy(search_word, word, PREFIX); t1 = tvgetf(); tst_search_prefix(root, search_word, sgl, &sidx, LMAX); t2 = tvgetf(); fprintf(fp_out2, "%d %.8f\n", count++, t2 - t1); } fclose(fp_out2); ``` * 結果 ![](https://i.imgur.com/4ziTEyX.png) ![](https://i.imgur.com/VAnxWwU.png) * x 軸為資料編號， y 軸為執行 prefix search 的時間。 * 可以看出執行時間大部在 2*10^-6^ sec 以內。觀察分佈發現，有幾個高峰的地方，如第 5000 比資料左右。總體來說，因為 ref 峰值較高，所以平均較高，而 cpy 的分佈則是相對平均。 * 信賴區間 * 參考 [rex662624 共筆](https://hackmd.io/s/SJbHD5sYM#ref-%E5%92%8C-cpy-%E5%85%A9%E8%80%85%E5%81%9A-search-%E7%9A%84%E6%95%88%E8%83%BD%E5%88%86%E6%9E%90) * gnuplot 的分析指令 ``` $gnuplot $stats "cpy.txt" using 2 $stats "ref.txt" using 2 * FILE: cpy.txt ref.txt Records: 254073 254073 Out of range: 0 0 Invalid: 0 0 Blank: 0 0 Data Blocks: 1 1 * COLUMN: Mean: 2.58959e-07 2.16105e-07 Std Dev: 2.15182e-07 2.57175e-07 Sample StdDev: 2.15183e-07 2.57176e-07 Skewness: 21.9973 139.0368 Kurtosis: 2635.6369 38465.3643 Avg Dev: 1.23026e-07 1.06763e-07 Sum: 0.0658 0.0549 Sum Sq.: 2.88026e-08 2.86697e-08 Mean Err.: 4.26901e-10 5.10211e-10 Std Dev Err.: 3.01865e-10 3.60773e-10 Skewness Err.: 0.0049 0.0049 Kurtosis Err.: 0.0097 0.0097 Minimum: 0.0000 [ 6] 0.000[ 11] Maximum: 0.0000 [ 40470] 0.001[ 23637] Quartile: 2.40000e-07 2.40000e-07 Median: 2.40000e-07 2.40000e-07 Quartile: 2.40000e-07 2.40000e-07 ``` The Confidence Interval formula is $x {\pm} z \cdot\dfrac{s}{\sqrt{n}}$ * **X** is the mean = `2.58959e-07` `2.16105e-07` * **Z** : 95% 時 z = 1.960 * **s** is the standard deviation = `2.15182e-07` `2.57175e-07` * **n** is the number of samples = 254073 代入公式，得 : ``` CPY版本 prefix search 95% 信賴區間: 2.58959e-07 ± 8.3672502e-10 (sec) REF版本 prefix search 95% 信賴區間: 2.16105e-07 ± 1.00001281e-9 (sec) ``` * 記憶體配置 * cpy 與 ref 都是使用動態記憶體，在 heap 中取用記憶體，然而，兩者的節點與葉節點的擺放位置不同，造成了效能差異。 * cpy 在建立、搜尋時，由於 strdup 是由 heap 中抓取可用的記憶體，事實上也是順序的，不會差太遠，因此，在找到 leaf 時，也是很順的抓。因此， cache miss 效能較佳。 |node| |----| |node| |node| |leaf| |node| |node| |leaf| * ref 在建立之前，便先宣告 heap 中的一塊給 leaves 用，而每次建立到 leaf 時，都要再回去原本宣告的 leaves 的記憶體，造成記憶體在使用上很不連續， cache miss 就很高。 |leaves| |------| |node| |node| |node| |node| |node| * 改善方法 * 根據記憶體配置差異的想法，可以模仿 cpy 的記憶體配置方式，因此在一開始就宣告一塊給所有 nodes 及 leaves 用，以達到如 cpy 的排列，也可以避免空間浪費，也就是 memory pool 的方式。 ## `tst_traverse_fn` 函式 * callback function * 根據維基百科定義：a **callback** is any executable code that is passed as an argument to other code, which is expected to _call back_ (execute) the argument at a given time. * 在 c 語言中， callback function 就是將 function pointer 當作參數傳入另一個 function 中執行。 * `tst_traverse_fn` function * 就是一個遞迴的 callback function ，它將 fn() 當作參數。 ```c /** tst_traverse_fn(), traverse tree calling 'fn' on each word. * prototype for 'fn' is void fn(const void *, void *). data can * be NULL if unused. */ void tst_traverse_fn(const tst_node *p, void(fn)(const void *, void *), void *data) { if (!p) return; tst_traverse_fn(p->lokid, fn, data); if (p->key) tst_traverse_fn(p->eqkid, fn, data); else fn(p, data); tst_traverse_fn(p->hikid, fn, data); } ``` * 這個函式的功能就是走訪整個樹的節點，並且在 leaves 執行使用者自訂函式 fn()。 * 應用： * 計算 leaves 數量 ``` void fn(const void *p, void *data) { ++*(int *)data; } tst_traverse_fn(root, fn, &data); printf("data: %d\n", data); ``` 結果 ``` data: 85500 ``` * 效能評比可以比較兩者的走訪速度。 ``` t1 = tvgetf(); tst_traverse_fn(root, fn, &data); t2 = tvgetf(); printf("cpy time: %.6f\n", t2-t1); ``` 結果 ``` cpy time: 0.015064 ref time: 0.015275 ``` * 印出資料庫中所有的國家、城市 ``` void fn(const void *p, void *data){ printf("%s\n", tst_get_string(p)); } tst_traverse_fn(root, fn, &data); ``` 結果 ``` ... Tufino, Tuftonboro, Tuganay, Tugas, Tugaya, Tugbong, Tugdan, Tuggen, Tuglie, Tugolesskiy Tugos, Tuguegarao Tugulym, Tugun, ... ```

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.