--- tags: sysprog --- # 2019q3 Homework5 (dict) contributed by < `yxguo2536` > ## 使用 test_common.c 統合 test_ref.c 和 test_cpy.c 以 `diff test_ref.c test_cpy.c` 比較 `test_ref.c` 和 `test_cpy.c` 之間的差別： 1. output 檔案不同 ```c 20c20 < #define BENCH_TEST_FILE "bench_ref.txt" --- > #define BENCH_TEST_FILE "bench_cpy.txt" ``` ```c 77c74 < output = fopen("ref.txt", "a"); --- > output = fopen("cpy.txt", "a"); ``` 2. error 訊息不同，但此處應該是 test_ref.c 原本寫錯了。 ```c 45c45 < fprintf(stderr, "error: file open failed '%s'.\n", argv[1]); --- > fprintf(stderr, "error: file open failed '%s'.\n", IN_FILE); ``` 3. REF 機制會事先配置一個 memory pool ```c 47a48 > 52,57c53,54 < /* memory pool */ < char *pool = (char *) malloc(poolsize * sizeof(char)); ``` 4. REF 機制以 `Top` 變數 ( momery pool ) 儲存所有使用者輸入， CPY 機制則是以 `word` 變數暫時存放一筆資料 ```c < char *Top = pool; < while ((rtn = fscanf(fp, "%s", Top)) != EOF) { < /* insert reference to each string */ < if (!tst_ins_del(&root, Top, INS, REF)) { /* fail to insert */ --- > while ((rtn = fscanf(fp, "%s", word)) != EOF) { > if (!tst_ins_del(&root, word, INS, CPY)) { ``` ```c 62c59 < bloom_add(bloom, Top); --- > bloom_add(bloom, word); ``` ```c 64d60 < Top += strlen(Top) + 1; ``` ```c 103,104c100,101 < strcpy(Top, argv[3]); < else if (!fgets(Top, sizeof word, stdin)) { --- > strcpy(word, argv[3]); > else if (!fgets(word, sizeof word, stdin)) { ``` ```c 108,109c105 < rmcrlf(Top); < --- > rmcrlf(word); ``` ```c 111c107 < if (bloom_test(bloom, Top)) /* if detected by filter, skip */ --- > if (bloom_test(bloom, word)) /* if detected by filter, skip */ ``` ```c 114,115c110,111 < bloom_add(bloom, Top); < res = tst_ins_del(&root, Top, INS, REF); --- > bloom_add(bloom, word); > res = tst_ins_del(&root, word, INS, CPY); ``` ```c 120,121c116 < Top += (strlen(Top) + 1); < printf(" %s - inserted in %.10f sec. (%d words in tree)\n", --- > printf(" %s - inserted in %.12f sec. (%d words in tree)\n", ``` ```c 189,190c184 < /* FIXME: remove reference to each string */ < res = tst_ins_del(&root, word, DEL, REF); --- > res = tst_ins_del(&root, word, DEL, CPY); ``` 5. TST free 的行為不同 ： REF 機制只需要釋放每個 TST node 的記憶體，而 CPY 機制還要額外釋放 TST leaf 指向的字串 ```c 66a63 > 72c69 < tst_free(root); --- > tst_free_all(root); ``` ```c 208c202 < tst_free(root); --- > tst_free_all(root); ``` 可以看到，test_ref.c 和 test_cpy.c 的程式碼架構幾乎一樣，主要差別在於函式呼叫的參數 和 memory pool 機制。 所以，我使用 MACRO 機制合併兩者： - [ ] test_common.c ```c #if !defined(CPY) && !defined(REF) #define REF #endif #ifdef REF #define MODE 0 #define BENCH_TEST_FILE "bench_ref.txt" #define OUT_FILE "ref.txt" #define TST_FREE tst_free #endif #ifdef CPY #define MODE 1 #define BENCH_TEST_FILE "bench_cpy.txt" #define OUT_FILE "cpy.txt" #define TST_FREE tst_free_all #endif ``` ```c int main(int argc, char **argv) { #if defined(REF) /* memory pool */ char *pool = (char *) malloc(poolsize * sizeof(char)); char *Top = pool; #define BUFFER Top #elif defined(CPY) char word[WRDMAX] = ""; #define BUFFER word #endif ... ``` ```c #ifdef REF BUFFER += strlen(BUFFER) + 1; #endif ``` ```c else if (!fgets(BUFFER, WORDMAX, stdin)) { ... ``` 當要編譯 test_ref，我就需要在以 gcc 編譯 test_common.c 時加入額外參數 `-DREF`，反之， test_cpy 則加入 `-DCPY` - [ ] Makefile ``` test_%: test_%.o $(OBJS_LIB) $(VECHO) " LD\t$@\n" $(Q)$(CC) $(LDFLAGS) -o $@ $^ -lm test_ref.o: test_ref.c $(VECHO) " CC\t$@\n" $(Q)$(CC) -o $@ $(CFLAGS) -c -MMD -MF .$@.d test_common.c -DREF test_cpy.o: test_cpy.c $(VECHO) " CC\t$@\n" $(Q)$(CC) -o $@ $(CFLAGS) -c -MMD -MF .$@.d test_common.c -DCPY ``` ## 優化 Bloom filter 空間效率 Bloom filter 空間浪費: 整個 table 都把 byte 當 bit 來用，浪費 1/8 的 table 空間 ```c void bloom_add(bloom_t filter, const void *item) { struct bloom_hash *h = filter->func; uint8_t *bits = filter->bits; while (h) { unsigned int hash = h->func(item); hash %= filter->size; bits[hash] = 1; // 每個 uint8_t 不是 1 就是 0 h = h->next; } } ``` 改進 : - [ ] bloom.c ```c bloom_t bloom_create(size_t size) { bloom_t res = calloc(1, sizeof(struct bloom_filter)); res->size = size; // res->bits = malloc(size); res->bits = calloc((size + 7) >> 3, 1); bloom_add_hash(res, djb2); bloom_add_hash(res, jenkins); return res; } ``` 首先，在 `bloom_create` 時將要配置的空間縮小到約 1/8 1. 對於函式參數 `size` 要先對齊 8 (bits)，然後在除以 8 ，也就是 `(size + 7) >> 3` 2. 不用 `malloc` 而改用 `calloc` ，因為後者會對配置空間做初始化 ( 填0 )，以便在 `bloom_add` 可以 `|=` 運算將特定 bit 設成 1 ```c void bloom_add(bloom_t filter, const void *item) { struct bloom_hash *h = filter->func; uint8_t *bits = filter->bits; while (h) { unsigned int hash = h->func(item); hash %= filter->size; // bits[hash] = 1; bits[hash >> 3] |= (0x40 >> (hash & 7)); h = h->next; } } ``` 在 `bloom_add` 中，則根據 $hash \div 8 = N ... M$ ，定位到 table 中的第 N+1 個 Bytes，並把第 M 個 bit 設為 1 ```c bool bloom_test(bloom_t filter, const void *item) { struct bloom_hash *h = filter->func; uint8_t *bits = filter->bits; while (h) { unsigned int hash = h->func(item); hash %= filter->size; // if (!(bits[hash])) { if (!(bits[hash >> 3] & (0x40 >> (hash & 7)))) { return false; } h = h->next; } return true; } ``` 在 `bloom_test` 也是以類似於 `bloom_add` 的技巧取到特定 bit 的值 ## 去除城市後面的逗號 原本程式碼中，使用 `fscanf` 讀取 cities.txt，所以會把 城市名 和 國家名 分開，這是我們想要的。 但問題是 ： cities.txt 中，城市名後面多了一個逗號，這就不是我們想要的。 解決辦法：如果 `rmcrlf` 函式，另外在創建一個函式針對 `fscanf` 後的字串做逗號處理： ```c static void rmcomma(char *s) { sscanf(s, "%[^,]", s); } ``` 這是 [scanf format](https://yodalee.blogspot.com/2012/01/scanf.html) 的規則，意思是「從 s(前者) 中不斷讀取直到遇到逗號（或空格和\n），並把結果輸出到 s(後者)」 然後把這個函式加到原本的 `fscanf` 後面做處理： ```c while ((rtn = fscanf(fp, "%s", word)) != EOF) { rmcomma(word); if (!tst_ins_del(&root, word, INS, CPY)) { ... } ... } ``` >根據 [kaeteyaruyo的共筆](https://hackmd.io/@kaeteyaruyo/2019q3_dict#dict-%E7%A8%8B%E5%BC%8F%E7%A2%BC%E6%AA%A2%E6%9F%A5%E4%BA%8B%E9%A0%85) 得知，cities.txt 裡面紀錄的資料不是只有 `城市名, 國家` 一種 pattern，也有少數例外，如 `建築物名稱, 城鎮名, 城市名, 國名`。 所以程式碼還有改進空間。 ## Memory leaks 的偵測與校正 使用 `valgrind --leak-check=full ./test_ref --bench` 檢查： ``` ==19155== HEAP SUMMARY: ==19155== in use at exit: 512,633,248 bytes in 6 blocks ==19155== total heap usage: 502,763 allocs, 502,757 frees, 528,736,216 bytes allocated ==19155== ==19155== 8,192 bytes in 1 blocks are definitely lost in loss record 3 of 6 ==19155== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==19155== by 0x108E83: bench_test (bench.c:46) ==19155== by 0x109290: main (test_ref.c:96) ==19155== ==19155== 625,056 (24 direct, 625,032 indirect) bytes in 1 blocks are definitely lost in loss record 5 of 6 ==19155== at 0x4C31B25: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==19155== by 0x10AB43: bloom_create (bloom.c:45) ==19155== by 0x109124: main (test_ref.c:75) ==19155== ==19155== 512,000,000 bytes in 1 blocks are possibly lost in loss record 6 of 6 ==19155== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==19155== by 0x10904D: main (test_ref.c:51) ==19155== ==19155== LEAK SUMMARY: ==19155== definitely lost: 8,216 bytes in 2 blocks ==19155== indirectly lost: 625,032 bytes in 3 blocks ==19155== possibly lost: 512,000,000 bytes in 1 blocks ==19155== still reachable: 0 bytes in 0 blocks ==19155== suppressed: 0 bytes in 0 blocks ``` 1. bench.c:46 ```c sgl = (char **) malloc(sizeof(char *) * max); // <-- not freed while (fscanf(dict, "%s", word) != EOF) { if (strlen(word) < sizeof(prefix) - 1) continue; strncpy(prefix, word, sizeof(prefix) - 1); t1 = tvgetf(); tst_search_prefix(root, prefix, sgl, &sidx, max); t2 = tvgetf(); fprintf(fp, "%d %f msec\n", idx, (t2 - t1) * 1000); idx++; } fclose(fp); fclose(dict); return 0; ``` 可以看到，原因是`sgl` 沒有被釋放掉。 這邊只要多加一行 `free(sgl)` 就解決了。 2. bloom.c:45 ```c bloom_t bloom_create(size_t size) { bloom_t res = calloc(1, sizeof(struct bloom_filter)); res->size = size; // res->bits = malloc(size); res->bits = calloc((size + 7) >> 3, 1); bloom_add_hash(res, djb2); bloom_add_hash(res, jenkins); return res; } void bloom_free(bloom_t filter) { if (filter) { while (filter->func) { struct bloom_hash *h = filter->func; filter->func = h->next; free(h); } free(filter->bits); free(filter); } } ``` 這邊的問題出在 `bloom_create()` 的 `res` 沒有被釋放。但奇怪的是：雖然 `bloom_create()` 沒釋放，但我明明有在 `bloom_free()` 釋放掉。 怎麼就報錯了？ 後來想到可能是 `bloom_free()` 根本沒被呼叫，所以去找了一下 `bloom_free()` 到底在哪裡被呼叫到： * test_ref.c ```c int main(int argc, char **argv) { .... if (argc == 2 && strcmp(argv[1], "--bench") == 0) { int stat = bench_test(root, BENCH_TEST_FILE, LMAX); tst_free(root); return stat; } ... quit: tst_free(root); bloom_free(bloom); return 0; } ``` 可以看到，`bloom_free()` 唯一被呼叫到的只有在 `quit` 標籤下。 但如果以 `test_ref --bench` 執行時根本不會跑到那邊去。 改進 ： ```c int main(int argc, char **argv) { .... if (argc == 2 && strcmp(argv[1], "--bench") == 0) { int stat = bench_test(root, BENCH_TEST_FILE, LMAX); tst_free(root); bloom_free(bloom); return stat; } .... } ``` 3. test_ref.c:51 ```c int main(int argc, char **argv) { char *pool = (char *) malloc(poolsize * sizeof(char)); char *Top = pool; } ``` 這邊可以很顯然看到，`pool`沒有被釋放過。 解決辦法： ```c int main(int argc, char **argv) { .... if (argc == 2 && strcmp(argv[1], "--bench") == 0) { int stat = bench_test(root, BENCH_TEST_FILE, LMAX); tst_free(root); bloom_free(bloom); free(pool); // free pool here for it won't goto "quit" return stat; } .... quit: tst_free(root); bloom_free(bloom); free(pool); // free pool at the end return 0; } ``` 因為 `test_cpy` 的程式碼結構與 `test_ref` 幾乎一樣，所以解決辦法也大同小異，在此就不贅述了。 ## 使用 perf 分析程式效能 在 Makefile 新增 `perf-search` 標的 : ``` perf-search: $(TESTS) @for test in $(TESTS); do\ echo 3 | sudo tee /proc/sys/vm/drop_caches; \ perf stat \ -e cache-misses,cache-references,instructions,cycles \ ./$$test --bench; \ done ``` 執行 `make perf-search` ``` Performance counter stats for './test_cpy --bench': 1,084,007,920 cache-misses # 36.204 % of all cache refs 2,994,198,462 cache-references 51,159,308,833 instructions # 1.04 insn per cycle 49,093,968,870 cycles 11.456455024 seconds time elapsed Performance counter stats for './test_ref --bench': 1,175,720,371 cache-misses # 35.819 % of all cache refs 3,282,393,446 cache-references 51,117,407,691 instructions # 0.95 insn per cycle 54,010,192,527 cycles 12.812377055 seconds time elapsed ``` 可以看到，在進行字串搜尋、自動補完時，test_ref 的 cache-misses 比 test_cpy 多 閱讀程式碼，不難發現 test_cpy 和 test_ref 兩個版本僅有的差異在於 ： `p->eqkid` 指向的字串地址的來源不同。 如果說由此會產生 cache misses 上的差異，代表這跟字串的 dereference 脫不了關係，因此可以推斷 cache misses 主要應是發生在 `tst_suggest()`，畢竟只有在此 function 中會需要提取 TST leaf 存放的字串。 為求證明，將 `tst_suggest()` 中有關字串 dereference 部份暫時註解 : ```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 &&*/ *n < max){ // <-- here a[(*n)++] = (char *) p->eqkid; } tst_suggest(p->hikid, c, nchr, a, n, max); } ``` 重新測量 cache misses： ``` Performance counter stats for './test_cpy --bench': 767,307,410 cache-misses # 28.908 % of all cache refs 2,654,274,239 cache-references 47,559,423,073 instructions # 1.17 insn per cycle 40,555,871,794 cycles 9.277660146 seconds time elapsed Performance counter stats for './test_ref --bench': 689,772,296 cache-misses # 25.824 % of all cache refs 2,671,073,305 cache-references 47,539,126,772 instructions # 1.20 insn per cycle 39,667,629,399 cycles 9.233345834 seconds time elapsed ``` 實驗證明 test_ref 的 cache misses 甚至降到比 test_cpy 低了。 接下來，進一步從組合語言層面觀察 test_cpy 和 test_ref 的 cache misses 到底都是分佈在哪些指令上 ： * test_ref : 2 處熱點 ![](https://i.imgur.com/hcqWXK5.png) ![](https://i.imgur.com/dIOo1yv.png) * test_cpy 1 處熱點 ![](https://i.imgur.com/YrnZfLz.png) ![](https://i.imgur.com/ct99yNK.png) 可以看到，在 test_ref 中有 2 個 cache misses 熱點，分別是 `mov -0x10(%rbp),%r8d` 和 `cmp %al,-0xc(%rbp)`。 但因為 CPU 會合併特定組合的指令一起執行，所以 [有時 perf 的測量會不準](https://stackoverflow.com/questions/43794510/linux-perf-reporting-cache-misses-for-unexpected-instruction)，在此例，實際上造成 cache misses 的是他們的上一道指令，即 `mov 0x8(%rax),%rax` 和 `movzbl (%rax) %eax` 先看 `mov 0x8(%rax),%rax` ： 它對應到的 C 語言為 `p->lokid`。 其中，`(%rax)` 對應到 `*p`， `0x8` 的則是 `lokid` 的 offset，因為 `p->lokid` == `*(p+8)`。 而從 C 程式上下文可以知道這裡是 tst_suggest() 中第一次對 p 做 dereference，所以原本 cache 中沒有存放其值也無可厚非。 但由於現代 cache 都有資料預取的機制，當我們第一次取得 `0x8(%rax)`，電腦就會預測、並將附近的資料事先搬入 cache。所以可以看到後續執行 `0xN(%rax)` 所造成的 cache misses 有顯著降低。 所以，真正造成兩版本 cache misses 差距的是 test_ref 的 `movzbl (%rax) %eax` 從組語上下文可知，`movzbl (%rax) %eax` 對應的 C 程式是 `*(((char *) p->eqkid) + nchr - 1)` ，即「 提取 TST 中字串 」的指令。 這行指令在 test_ref 上跑出了全程式第二高的 cache misses，在 test_cpy 上則沒有特別容易 cache misses 的跡象，怎麼會這樣？ 這就關係到上述 cache 的資料預取機制。 先由程式打印出字串地址跟 p 之間的距離： ```c void tst_suggest( ... ) { ... if (p->key) ... else if (*(((char *) p->eqkid) + nchr - 1) == c && *n < max){ printf("%ld\n", (intptr_t)(void*)(((char *)p->eqkid) + nchr - 1) - (intptr_t)(void*)&p->eqkid); ... } ... } ``` 執行結果 : * test_ref ``` 45899055606528 45899061029716 45899051142739 45899059059294 ... ``` * test_cpy ``` 34 34 34 34 ... ``` 在 test_cpy 中，leaf `&p->lokid` 與 字串 `p->eqkid` 的地址很接近，所以當前面做完 `mov 0x10(%rax),%rax` ，即 `p->eqkid` 時，電腦就很有可能會把在字串也一起載入 cache 中。 在 CPY 機制中，建立 leaf 後會間接呼叫 malloc 配置新空間給字串。 而在此之前最後一次 malloc 是發生在配置 leaf 空間時，因此兩者在記憶體內部的位置很有可能會是相鄰的 : ```c void *tst_ins_del(tst_node **root, const char *s, const int del, const int cpy) { ... for (;;) { if (!(*pcurr = calloc(1, sizeof **pcurr))) { // tst node allocation ... } ... if (*p++ == 0) { if (cpy) { // CPY const char *eqdata = strdup(s); // string allocation if (!eqdata) return NULL; curr->eqkid = (tst_node *) eqdata; return (void *) eqdata; } else { // REF curr->eqkid = (tst_node *) s; return (void *) s; } } ... } } ``` 而 REF 機制則是在進入 `tst_ins_del()` 建立 TST 前就把字串的空間配置出來了，所以兩者地址差距會很大，也因此 cache misses 機率高。 ## 參考資料 1. [colinyoyo26 的共筆](https://hackmd.io/@colinyoyo26/2019q3dict) 2. [kaeteyaruyo 的共筆](https://hackmd.io/@kaeteyaruyo/2019q3_dict) 3. [Makefile 語法和示範](https://hackmd.io/@sysprog/SySTMXPvl?type=view)