---
# System prepended metadata

title: 2019q3 Homework5 (dict)

---

# 2019q3 Homework5 (dict)
contributed by < `colinyoyo26` >

## Trie ＆ Ternary tree

Trie 能夠實現 prefix search 但會有大量空指標
- 每個 node 需要 $|alphabet set|$ 個指標 

而 ternary tree 可以解決這個問題，其中每個 node 只需要三個指標， 在 [dict](https://github.com/sysprog21/dict) 實作中的 tst.c 可以看到資料結構如下

```cpp
typedef struct tst_node {
    char key;               /* char key for node (null for node with string) */
    unsigned refcnt;        /* refcnt tracks occurrence of word (for delete) */
    struct tst_node *lokid; /* ternary low child pointer */
    struct tst_node *eqkid; /* ternary equal child pointer */
    struct tst_node *hikid; /* ternary high child pointer */
} tst_node;
```

假設目前搜尋到的 prefix = x 被搜尋的 node key = cur 則
- if x == cur
    - x = next prefix
    - node = node->eqkid
    - 繼續比對下個 prefix
- if x > cur 
    - node = node->hikid
    - 往右搜尋
- if x < cur 
    - node = node->lokid
    - 往左搜尋

而其中 `key` 為 0 時代表 `struct tst_node *eqkid` 不是指向下個 node 而是該路徑所代表的字串 

## CPY & REF 機制差異

先看到 `test_cpy.c` 和 `test_ref.c` 以及 `tst.c` 的一小段程式碼

#### tst.c (in `tst_ins_del` function)
```cpp
/* 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;
    }
}
```
從這裡可以看出 cpy 機制在插入時會 malloc 而 ref 不會，因為在 main function 已經 malloc 過了
- Linux Programmer's Manual 
    - The strdup() function returns a pointer to a  new  string  which  is a duplicate  of the string s.  Memory for the new string is obtained with malloc(3), and can be freed with free(3).
   

#### test_cpy.c
```cpp
while ((rtn = fscanf(fp, "%s", word)) != EOF) {
    if (!tst_ins_del(&root, word, INS, CPY)) {
        fprintf(stderr, "error: memory exhausted, tst_insert.\n");
        fclose(fp);
        return 1;
    }
    bloom_add(bloom, word);
    idx++;
}
```
cpy 機制中，每次插入新的字串才會在 `tst_ins_del` function 內 malloc 一個小 chunck 給該字串

#### test_ref.c
```cpp
char *pool = (char *) malloc(poolsize * sizeof(char));
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 */
        fprintf(stderr, "error: memory exhausted, tst_insert.\n");
        fclose(fp);
        return 1;
    }
    bloom_add(bloom, Top);
    idx++;
    Top += strlen(Top) + 1;
}
```
從這段程式碼可以看出， ref 機制一開始就在 main function malloc 很大的 chunk 然後每次加入新的字串都會增加指標位置避免覆蓋，所以在插入 ternary tree 時不用在 malloc

## Bloom filter 空間浪費改善
原本整個 table 都把 byte 當 bit 來用，浪費 7/8 的 table 空間
```cpp
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_create
```cpp
bloom_t bloom_create(size_t size)
{
    bloom_t res = calloc(1, sizeof(struct bloom_filter));
    res->size = size;
    //res->bits = malloc(size + 7);
    res->bits = calloc((size + 7) >> 3, 1);

    bloom_add_hash(res, djb2);
    bloom_add_hash(res, jenkins);

    return res;
}
```
為了改善空間浪費，在 `bloom_create` 內做以上更改 
- 因為從 byte-level 改成 bit-level 所以 res->bits 只需要 malloc 1/8 的空間
- 其中 `res->bits = calloc((size + 7) >> 3, 1)` 先對齊 1-byte (round up) 再 shift 3 bits
    - 這邊不用 `(size + 7) & -8` 因為會 shift 掉
- `res->bits = calloc((size + 7) >> 3, 1)` 改成 `calloc` 因為要確保原本 memory content 為 0

#### bloom_add
```cpp
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_test
```cpp
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 >> 3] & (0x40 >> (hash & 7)))) {
            return false;
        }
        h = h->next;
    }
    return true;
}
```
在以上兩個 function 內，因為 table 的儲存已經改成 bit-level 所以
- `bits[hash >> 3]` 先找到存放位置在第幾個 byte
- `0x40 >> (hash & 7)` 再找到要放在第幾個 bit
    - 在 little-endian 往右 shift 會往低位址移動，但是不影響結果
    - 這裡也可以寫成 `1 << (hash & 7)` 只是前者邏輯上比較直觀

## 引入 test-common.c 統合 test_cpy.c 和 test_ref.c

#### test_common.c
從 `test_ref.c` 做些微更動
- `REF` 改成用 `int` 宣告才能動態改變他的值
```cpp
int REF = INS;
```

- 並在一開始加入以下判斷，要求在使用時輸入 `CPY` 或 `REF` 判斷使用機制
```cpp
int CPYmask = -1;
if (argc < 2) {
        printf("too less argument\n");
        return 1;
    }

if (!strcmp(argv[1], "CPY") || (argc > 2 && !strcmp(argv[2], "CPY"))) {
    CPYmask = 0;
    REF = DEL;
    printf("CPY mechanism\n");
} else
    printf("REF mechanism\n");
    
    ......
    
if(CPYmask){
    /* memory pool */
    pool = (char *) malloc(poolsize * sizeof(char));
    Top = pool;
}
    
    ......
    
/* 更改 argc */    
if (argc > 2 && strcmp(argv[1], "--bench") == 0)  

```
CPYmask 的用途在這，為了最小化影響執行時期效能所以用 bitwise 運算判斷是否增加 `Top` 位址 
```cpp
Top += (strlen(Top) + 1) & CPYmask;
```
原本想說要從編譯時期選擇機制，但以下的地方實在不知道怎麼在 Makefile 只做小幅度更動就可以插入 -D 選擇機制，所以改用以上方法只要把 `test_cpy` 和 `test_ref` 的地方改成 `test_common` 並在 `make test` 的地方加入引數就好 
```cpp
%.o: %.c
	$(VECHO) "  CC\t$@\n"
	$(Q)$(CC) -o $@ $(CFLAGS) -c -MMD -MF .$@.d $<
```

## 紀錄多餘逗號修正

`fscanf` 會在空白還有換行停下來，所以原本城市名後的逗號也被紀錄進去了，造成在搜尋時需要加入逗號才能搜尋的到，所以以下對讀檔迴圈進行修正

```cpp
char buf[WORDMAX];
while (fgets(buf, WORDMAX, fp)) {
    int offset = 0;
    for (int i = 0, j = 0; buf[i + offset]; i++) {
        Top[i] = (buf[i + j] == ',' || buf[i + j] == '\n') ? '\0' : buf[i + j];
        j += (buf[i + j] == ',');
    }

    while (*Top) {
        if (!tst_ins_del(&root, Top, INS, REF)) { /* fail to insert */
            fprintf(stderr, "error: memory exhausted, tst_insert.\n");
            fclose(fp);
            return 1;
        }
        bloom_add(bloom, Top);
        idx++;
        int len = strlen(Top);
        offset += len + 1;
        Top += len + 1;
    }
    Top -= offset & ~CPYmask;
    memset(Top, '\0', WORDMAX);
}
```
上次沒注意到 CPY 機制會出現無窮迴圈，重新修正
- 用 `fgets` 一次讀取一行
- 然後把分隔符號 `,` 和 `\n` 都換成 `\0`
- 然後下面 `while (*Top)` 把字串分別存入
- `memset(Top, '\0', WORDMAX)` 避免 memory content 不為零而進入無窮迴圈
- `offset` 為 CPY 機制紀錄 Top 位移了多少，並在跳出迴圈後減回去
- 第一個 `for` 迴圈中的 `j` 是避免寫入 `,` 後面的空格

## Perf 分析 CPY & REF 機制效能

重現 [隱藏在字典裡的數學](https://hackmd.io/@sysprog/BkE3uSvdN) 實驗
```
$ echo 3 | sudo tee /proc/sys/vm/drop_caches && sudo perf stat -e cache-misses,cache-references,instructions,cycles ./test_common --bench CPY 
3
CPY mechanism
ternary_tree, loaded 259112 words in 0.169224 sec

 Performance counter stats for './test_common --bench CPY':

     1,743,066,134      cache-misses              #   69.060 % of all cache refs    
     2,524,002,636      cache-references                                            
    42,059,333,849      instructions              #    0.96  insn per cycle         
    43,804,369,382      cycles                                                      

      16.446560243 seconds time elapsed

```
```
$ echo 3 | sudo tee /proc/sys/vm/drop_caches && sudo perf stat -e cache-misses,cache-references,instructions,cycles ./test_common --bench REF 
3
REF mechanism
ternary_tree, loaded 259112 words in 0.163192 sec

 Performance counter stats for './test_common --bench REF':

     1,921,314,348      cache-misses              #   70.353 % of all cache refs    
     2,730,957,226      cache-references                                            
    42,059,741,056      instructions              #    0.85  insn per cycle         
    49,411,281,282      cycles                                                      

      22.104687647 seconds time elapsed

```
可以看出 REF 明顯有較多的 `cache-misses` 兩者的差異在於 ternary tree 中的 node `eqkid` 指向的字串位址不同，但為什麼會造成 `cache-misses` 差異這邊還看不出來




### perf record 找 cache-misses 熱點
```
$sudo perf record -e cache-misses ./test_common --bench REF && perf report
```
![](https://i.imgur.com/X8Uby8F.png)

```
$sudo perf record -e cache-misses ./test_common --bench CPY && perf report
```
![](https://i.imgur.com/iUNoUcc.png)

結果熱點都是在 `tst_suggest` function 內部，而 REF 比 CPY 多了一個指令的熱點，雖然不懂 x86_64 組語，但從 `cmp` 接續 `jne` 可以推測出是某個 `if condition`

:::warning
趕快研讀 CS:APP 第 3 章，及早熟悉 x86-64
:notes: jserv
:::

`movzbl (%rax),%eax` 從 `%rax` 放的 address 搬 1 byte 資料到 `%eax` 剩下左邊填零，是這個指令發生 cache-miss 才對  
[StackOverflow](https://stackoverflow.com/questions/43794510/linux-perf-reporting-cache-misses-for-unexpected-instruction) 有討論過類似回報偏差的情形
- Many modern Intel CPUs (and AMD probably too) can and will fuse (combine) some combinations of operations together, and cmp + conditional jump very common instruction combination to be fused. Fused pair may be reported in perf/PMUs/PEBS incorrectly with skew of most events towards one of two instructions.
> 合併指令可以增加 decode bandwidth 但可能使 perf 回報錯誤 [全文](https://www.realworldtech.com/nehalem/5/)

#### 繼續針對相異處做實驗

因為 REF 會在一開始就 malloc 一大塊 memory pool 而且測試的大小會使系統呼叫 `mmap` 在 stack 和 heap 之間分配空間，而 CPY 會在 malloc 完放字串的節點後才會 malloc 空間給字串，所以節點和字串會有很大的機率分配到連續的 chunk
- 以下把節點和字串位址差印出來驗證    

```cpp
else if (*(((char *) p->eqkid) + nchr - 1) == c && *n < max){
        a[(*n)++] = (char *) p->eqkid;
        printf("%ld\n" ,(intptr_t) p->eqkid - (intptr_t) p);
    }
```
結果如下
```
./test_common --bench REF
REF mechanism
ternary_tree, loaded 259112 words in 0.204291 sec
140265660153125
140265654550218
140265650179896
140265647186476
140265651175941
......
```
```
./test_common --bench CPY
CPY mechanism
ternary_tree, loaded 259112 words in 0.175229 sec
48
48
48
48
48
......
```
可以看出 CPY 機制在 virtual address 的差異只有 48 byte 所以資料很大機率會在同一個 cache block 內


## memory leaks 的偵測及修正

先用 valgrind 觀察 heap 情況

```
$ valgrind ./test_common --bench REF


==5207== HEAP SUMMARY:
==5207==     in use at exit: 512,633,248 bytes in 6 blocks
==5207==   total heap usage: 422,602 allocs, 422,596 frees, 526,171,064 bytes allocated
==5207== 
==5207== LEAK SUMMARY:
==5207==    definitely lost: 8,216 bytes in 2 blocks
==5207==    indirectly lost: 625,032 bytes in 3 blocks
==5207==      possibly lost: 512,000,000 bytes in 1 blocks
==5207==    still reachable: 0 bytes in 0 blocks
==5207==         suppressed: 0 bytes in 0 blocks
==5207== Rerun with --leak-check=full to see details of leaked memory

```
很容易看出 REF 機制的 memory pool 沒有 free 所以在結束時把它 free 掉
```cpp
quit:
    free(pool);
    tst_free(root);
    bloom_free(bloom);
    return 0;
```


而執行 CPY 機制時有很多 block 沒有 free ，發現在 `tst_free_all` 內有 free 字串而 `tst_free` 沒有
```cpp
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);
}

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);
}
```
所以把 `test_common.c` 最後改成以下
- CPY 機制需要用 `tst_free_all(root)` 把字串也 `free` 掉
- REF 機制如果也用 `tst_free_all(root)` 會發生 segmentation fault 
```cpp
quit:
    free(pool);
    /* for REF mechanism */
    if(CPYmask)
        tst_free(root);
    else
        tst_free_all(root);
    
    bloom_free(bloom);
    return 0;
```
改過之後 CPY 和 REF 都剩下 5 個 block 的 memory leak 用 `--bench` 測試時會出現，目前還沒找到在哪裡 

```
$ valgrind ./test_common --bench CPY
==4346== HEAP SUMMARY:
==4346==     in use at exit: 633,248 bytes in 5 blocks
==4346==   total heap usage: 505,075 allocs, 505,070 frees, 14,946,207 bytes allocated
==4346== 
==4346== LEAK SUMMARY:
==4346==    definitely lost: 8,216 bytes in 2 blocks
==4346==    indirectly lost: 625,032 bytes in 3 blocks
==4346==      possibly lost: 0 bytes in 0 blocks
==4346==    still reachable: 0 bytes in 0 blocks
==4346==         suppressed: 0 bytes in 0 blocks
```


## 參考資料
[隱藏在字典裡的數學](https://hackmd.io/@sysprog/BkE3uSvdN)
[抓漏 - Gdb 和 Valgrind 合體技](http://wen00072.github.io/blog/2014/11/29/catch-the-leak-gdb-and-valgrind-siamese-juggling/)