# 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
```
```
$sudo perf record -e cache-misses ./test_common --bench CPY && perf report
```
結果熱點都是在 `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/)
Sign in with Wallet
Connect another wallet