# 2018q3 Homework3 (dict) contributed by < `ChingChieh` > ###### tags: `2018q3` ## 開發環境 ``` $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian CPU(s): 4 On-line CPU(s) list: 0-3 Thread(s) per core: 2 Core(s) per socket: 2 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 142 Model name: Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz Stepping: 9 CPU MHz: 500.067 CPU max MHz: 3500.0000 CPU min MHz: 400.0000 BogoMIPS: 5808.00 Virtualization: VT-x L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 4096K NUMA node0 CPU(s): 0-3 ``` ## bench.c bug 一開始先來實作讓 ./test_ref --bench 可以執行時發現產生出來的 bench__cpy.txt 有很多次的時間都是 0.00000 於是先去看 bench_test() 後發現這個函式裏面又呼叫了 tst_search_prefix 而且計時是計算這個函式花了多少時間，然後利用 printf 大法在最後 return NULL 前面加上 printf("Not Found\n")。 ``` while (curr) { ... } printf("Not Found\n"); retunr NULL; ``` 結果也時如預期: ``` ... Not Found Not Found Not Found ... ``` 去看了一下發現問題是在test_bench裏面: ``` char prefix[3] = ""; ... strncpy(prefix, word, 3); tst_search_prefix(root, prefix, sgl, &sidx, max); ``` 因為使用 strncpy(char *dest, const char *src, size_t n) 時如果 src 前 n byte 沒有 NULL byte 那 dest 裡的 string 會被視為從 dest 開始到下一個 NULL byte，所以很可能包含原本沒有的 character 所以才會找不到。 此外在 tst_search_prefix 中有個if判斷式是多餘的，根本不會跑進去: ```c= int diff = *s - curr->key; /* calculate the difference */ if (diff == 0) { /* handle the equal case */ /* check if prefix number of chars reached */ if ((size_t)(s - start) == nchr - 1) { /* call tst_suggest to fill a with pointer to matching words */ tst_suggest(curr, curr->key, nchr, a, n, max); return (void *) curr; } // -----------以下的if不會跑進去--------- if (*s == 0){ /* no matching prefix found in tree */ return (void *) curr->eqkid; } // ----------------------------------- s++; curr = curr->eqkid; } ``` 因為當 *s == 0 發生之前一定會先跑進前面的 if 然後就 return 了 test_ref.c 沒有 free memory pool 因為 tst_free 只有 free tst 上的每個 node ```c= 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); } ``` 所以要在 quit 時加上 free(pool): ```c quit: case 'q': tst_free(root); free(pool); return 0; break; ``` ## test_cpy 和 test_ref 的差別 #### 建立 TST 時儲存字串的 memory 空間來源 * test_ref ```c= /* memory pool */ char *pool = (char *) malloc(poolsize * sizeof(char)); char *Top = pool; //top is for recording top of the pool while ((rtn = fscanf(fp, "%s", Top)) != EOF) { char *p = Top; /* insert reference to each string */ if (!tst_ins_del(&root, &p, INS, REF)) { /* fail to insert */ fprintf(stderr, "error: memory exhausted, tst_insert.\n"); fclose(fp); return 1; } else { /* update bloom filter */ bloom_add(bloom, Top); } idx++; Top += (strlen(Top) + 1); } ``` 先建立一個可以放的下整個 cities.txt 裏面全部字串的 memory pool，然後利用 Top 指標依序把讀到的字串放到 pool 中。 因為已經建立好 memory pool 所以在 tst_ins_del 中要把字串存起來只需要 ```c curr->eqkid = (tst_node *) *s; ``` * test_cpy 這個版本在建立 TST 時是透過每讀到一個新的字串就 malloc 一塊空間來存相同的字串: ```c= const char *eqdata = strdup(*s); if (!eqdata) return NULL; curr->eqkid = (tst_node *) eqdata; ``` ## gnuplot 初體驗 修改 Makefile 增加 plot 功能 ``` plot: gnuplot scripts/runtimept.gp eog runtime2.png & ``` ## perf 初體驗 * 測試./test_ref --bench ``` $ perf stat -e cache-misses,cache-references,instructions,cycles ./test_ref --bench ternary_tree, loaded 259112 words in 0.162133 sec Performance counter stats for './test_ref --bench': 1,923,015,911 cache-misses # 64.523 % of all cache refs 2,980,334,289 cache-references 47,108,955,394 instructions # 0.88 insn per cycle 53,604,126,759 cycles 18.511945817 seconds time elapsed ``` * 測試./test_cpy --bench ``` $ perf stat -e cache-misses,cache-references,instructions,cycles ./test_cpy --bench ternary_tree, loaded 259112 words in 0.149182 sec Performance counter stats for './test_cpy --bench': 1,749,974,080 cache-misses # 64.071 % of all cache refs 2,731,310,762 cache-references 47,123,815,504 instructions # 0.98 insn per cycle 48,108,397,687 cycles 15.847157502 seconds time elapsed ``` 發現 test_ref 花比較多時間，因為 cache-misses 多了一億多次 > 究竟是發生了什麼事，待研究