# 2020q3 Homework3 (dict)
contributed by < `JimmyLiu530` >
###### tags: `進階電腦系統理論與實作`
[詳細作業解說](https://hackmd.io/@sysprog/2020-dict#I04-dict)
## 程式原理
### CPY 與 REF 機制
在 `test_common.c` 程式碼中，針對字串地址的特性有兩種不同的機制:
> - copy 機制 (`CPY`): 傳入 `tst_ins_del` 的字串地址所表示的值**隨時會被覆寫**，因此 `eqkid` 需要 `malloc` 新空間將其 copy 存起來;
> - reference 機制 (`REF`): 傳進來的字串地址所表示的值**一直屬於該字串**，因此可將其當作 reference 直接存起來，不用 `malloc` 新空間。
```c=
if (!strcmp(argv[1], "CPY") || (argc > 2 && !strcmp(argv[2], "CPY"))) {
CPYmask = 0;
REF = DEL;
printf("CPY mechanism\n");
} else
printf("REF mechanism\n");
```
而在下面這兩段程式碼完全體現出這兩種機制的差異:
#### Memory pool
```c=
if (CPYmask) {
/* memory pool */
pool = (char *) malloc(poolsize * sizeof(char));
Top = pool;
}
```
只有 REF 機制才會配置 [memory pool](https://en.wikipedia.org/wiki/Memory_pool)
#### 對於儲存字串空間的差別
```c=
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);
}
```
從 cities.txt 中逐行讀取，並以 ',' 及 '\n' 分割出名稱。
接著在 `tst_ins_del` 函式中若是 `CPY` 機制，會去呼叫 strdup 而這個 strdup 會再去呼叫 malloc，因此符合上述所說的**需要新空間儲存**。也因為已配置新的空間給字串儲存了，因此需要將 `Top -= offset` 回到儲存前的位置;
若是 `REF` 機制，不會配置新的空間，字串直接儲存在 memory pool 中，因此 Top 的位置不需要改變。
### tst_ins_del (tst_node **root, const char *s, const int del, const int cpy)
主要處理字串插入及刪除 ternary search tree 的函式。分三個部份來看:
#### 變數意義及條件
```c=
int diff;
const char *p = s;
tst_stack stk = {.data = {NULL}, .idx = 0};
tst_node *curr, **pcurr;
if (!root || !s)
return NULL;
if (strlen(s) + 1 > STKMAX / 2)
return NULL;
```
- `stk`會紀錄是如何走訪的，以便在 `tst_del_word` 函式中能夠照順序處理
- TST 為空 或是 字串為空，則 return
- 當字串長度(含'\0')超過 `STKMAX / 2`，也直接 return
#### 字串已在 TST
```c=
pcurr = root;
while ((curr = *pcurr)) {
diff = *p - curr->key;
if (diff == 0) {
if (*p++ == 0) {
if (del) {
(curr->refcnt)--;
return tst_del_word(root, curr, &stk, cpy);
} else
curr->refcnt++;
return (void *) curr->eqkid; /
}
pcurr = &(curr->eqkid);
} else if (diff < 0) { /
pcurr = &(curr->lokid);
} else {
pcurr = &(curr->hikid);
}
if (del)
tst_stack_push(&stk, curr);
}
```
首先，會去比較字串 p 及 TST 節點的字元大小，因此又會分成三種可能
- 相等: 若 `if (*p++ == 0)`，代表已走到字串 p 的 '\0' 了(即此字串已在 TST 中)，所以
- 若要刪除字串，則將 `(curr->refcnt)--` 並呼叫 `tst_del_word` 函式去處理;
- 若要插入字串，則將`curr->refcnt++` 並回傳 `curr->eqkid`。
否則，往下一個 eqkid 繼續走
- 小於: 往下一個 lowkid 繼續走
- 大於: 往下一個 hikid 繼續走
#### 字串不完全在 TST
```c=
for (;;) {
if (!(*pcurr = calloc(1, sizeof **pcurr))) {
fprintf(stderr, "error: tst_insert(), memory exhausted.\n");
return NULL;
}
curr = *pcurr;
curr->key = *p;
curr->refcnt = 1;
curr->lokid = curr->hikid = curr->eqkid = NULL;
if (!*root) /
*root = *pcurr;
if (*p++ == 0) {
if (cpy) {
const char *eqdata = strdup(s);
if (!eqdata)
return NULL;
curr->eqkid = (tst_node *) eqdata;
return (void *) eqdata;
} else {
curr->eqkid = (tst_node *) s;
return (void *) s;
}
}
pcurr = &(curr->eqkid);
}
```
將剩餘未在 TST 的字元加入到 TST。
- 配置一個空間給剩餘的字元 `*pcurr = calloc(1, sizeof **pcurr` 並初始化
- 持續加入字元到 TST 直到字串結尾，分成 CPY 或 REF 機制
- CPY: 複製字元到一個新配置空間，並將新空間的位置 assign 給 `curr->eqkid`
- REF: 直接將此字元的位置 assign 給 `curr->eqkid`
----------------------------------------
## 視覺化 ternary search tree + bloom filter 的效能表現並分析
### [gnuplot](https://hackmd.io/@sysprog/Skwp-alOg?type=view#gnuplot-script)
將畫圖的設定寫入 gnuplot script `CPYplot.gp`
```gnuplot=
reset
set xlabel 'experiment'
set ylabel 'time(msec)'
set title 'bench for prefix search without bloom filter'
set term png enhanced font 'Verdana,10'
set output 'CPYbench.png'
set format x "%8.0f"
set xtic 50000
set xtics rotate by 90 right
plot [:250000][:1.0]'bench_ref.txt' using 1:2 with points title 'CPY'
```
接著直接在 terminal 上輸入
```shell=
$ gnuplot CPYplot.gp
```
或 若將 gnuplot script 放在 scripts 中
```shell=
$ gnuplot scripts/CPYplot.gp
```
就會產生對應的圖
### 效能分析
為了方便進行實驗，在原始程式碼中額外寫一段程式類似如下：
```c=
if (argc == 3 && strcmp(argv[1], "--bench") == 0) {
...
else if (argc == 3 && strcmp(argv[1], "--perf") == 0) {
/* 測試用的程式 */
}
```
因此，只須透過 `./test_common --perf CPY`的命令，就可以根據撰寫的程式設計對應的實驗並計算運行的時間。
#### 實驗1: 以 `cities.txt` 中城市、國家作為搜尋字串
| | 0.01-0.02 msec | 0.02up msec |
| ------------ | ------------ | ------------|
| no bloom CPY | 1 | 0 |
| no bloom REF | 1 | 0 |
| bloom CPY | 7 | 0 |
| blomm REF | 14 | 1 |
> 此為不同機制分別達到 0.01-0.02 msec 及 0.02 msec以上的數量
不管是有沒有使用 `bloom filter` 或是採取不同的 `CPY` 還是 `REF` 機制，大多數的 `tst_search` 所花的時間幾乎趨近於 0 msec，只有少部份的花到 0.01 msec 或是以上。雖然如此還是可以看出使用 bloom filter 後，導致速度變慢。這是因為這實驗是以 `cities.txt` 中的城市跟國家去做搜尋的，當初也是用這些去建 TST，所以一定可以在 TST 中搜尋的到，也就說 bloom filter 在此實驗毫無作用，只會增加整體的運算時間而已。為了體現出 bloom filter 的優點，於是設計了實驗2
#### 實驗2: 搜尋字串與 `cities.txt` 中的字串僅最後一個字元不同
如同實驗1所說， bloom filter 的功用在於以極低的錯誤率提早測得該字串未在 TST 中，避免後續的搜尋。而實驗2就是實驗1的另一個極端 - 欲搜尋的字串都不在 TST 中，得到以下的效能數據:
| | 0.01-0.02 msec | 0.02up msec |
| ------------ | ------------ | ------------|
| no bloom CPY | 22 | 0 |
| no bloom REF | 6 | 1 |
| bloom CPY | 0 | 0 |
| blomm REF | 1 | 0 |
> 此為不同機制分別達到 0.01-0.02 msec 及 0.02 msec以上的數量
發現此實驗 bloom filter 發揮他的作用，提早發現字串並未在 TST 中，減少執行的時間。而未使用 bloom filter 則會呼叫 `tst_search` 直到最後一個字元才發現不符合。
#### 結論
上面這兩種實驗都是極端的例子，實驗1完全偏向不使用 bloom filter，而實驗2則偏向使用 bloom filter，當然，現實生活中鮮少有這麼極端的應用，但說穿了也只是搜尋的字串存不存在 TST 中的比例多寡而已。不過我認為在現實生活的應用中，bloom filter 的確對於減少執行時間是有幫助的，畢竟不太可能將所有可能會被搜尋的字串預先 insert 到 TST 中。
-------------------------------------------------
## 以 perf 分析 TST 程式碼的執行時期行為並且充分解讀
### [perf](https://zh-blog.logan.tw/2019/07/10/analyze-program-performance-with-perf-events/) 介紹
- Linux 核心內建的系統效能分析工具，主要分為三個部分:
- 在 User Space 的 `perf` 指令
- 在 Kernel Space 負責處理和儲存事件記錄的機制
- 在 Kernel Space 的事件來源：硬體效能計數器、中斷、Page Fault、系統呼叫、KProbe、UProbe、FTrace、Trace Point 等等。
- 硬體效能計數器(PMU):
- 一般的手機或桌上型電腦 CPU 內建的 PMU 通常是若干個[效能計數器（Performance Counter）](https://en.wikipedia.org/wiki/Hardware_performance_counter)取樣指定事件
- 準備工作
```shell=
$ sudo apt-get install linux-tools-generic linux-tools-$(uname -r)
```
:::info
**NOTE:**
`perf` 指令會隨著 Linux 核心版本而有所變動，所以上面的指令同時安裝了 `linux-tools-generic` 與 `linux-tools-$(uname -r)`，其中的 $(uname -r) 會被代換為使用中的 Linux 核心版本。如果你更新了 Ubuntu 的 Linux 核心，需**重新執行**以上指令。
:::
- 常見指令
- `perf list`
- 列出 Linux 核心與硬體支援的事件種類
- `perf stat [-e [events]] [cmd]`
- 執行指定程式。執行結束後，印出各事件的總體統計數據
- 選項 `-e` 用來指定要測量的事件種類。各事件種類以 , 分隔
- `perf record [-e [events]] [-g] [cmd]`
- 執行指定程式。執行過程中，取樣並記錄各事件。這個指令能讓我們能大略知道事件的發生地點。
- 選項 `-e` 用來指定要測量的事件種類。各事件種類以 , 分隔
- 選項 `-g` 讓 perf record 在記錄事件時，同時記錄取樣點的 Stack Trace。
- 選項 `-o` 用來指定一個檔案名稱作為事件記錄儲存位置。預設值為 `perf.data`。
- `perf report [-g graph,0.5,caller]`
- 讀取 `perf record` 的記錄
- 選項 `-g` 用來指定樹狀圖的繪製方式。 `graph,0.5,caller` 代表以呼叫者（Caller）作為父節點，以被呼叫者（Callee）作為子節點。
- 選項 `-i` 用來指定一個檔案名稱作為事件記錄讀取來源。預 設值為 perf.data
:::info
備註：若測量對象沒有安全疑慮，以上所有指令都建議使用 `sudo` 執行
:::
### 分析 TST 程式碼
CPY 機制:
```shell=
$ sudo perf stat --repeat 50 -e cache-misses,cache-references ./test_common --bench CPY
Performance counter stats for './test_common --bench CPY' (50 runs):
1,112,451,175 cache-misses # 39.550 % of all cache refs
( +- 0.86% )
2,812,780,115 cache-references
( +- 0.07% )
11.7365 +- 0.0685 seconds time elapsed ( +- 0.58% )
```
REF 機制:
```shell=
$ sudo perf stat --repeat 50 -e cache-misses,cache-references ./test_common --bench REF
Performance counter stats for './test_common --bench REF' (50 runs):
1,049,437,015 cache-misses # 34.055 % of all cache refs
( +- 2.85% )
3,081,589,827 cache-references
( +- 0.19% )
12.059 +- 0.193 seconds time elapsed ( +- 1.60% )
```
發現兩種機制 cache miss 比例反而 `CRY (39.55%)` 較 `REF (34.055%)` 多，這與作業的講解有些出入，作業講解是說:
> `CPY` 機制在 insert 時，建立 leaf 後會間接呼叫 `malloc` 來保存字串，在這之前的最後一次 `malloc` 是爲了配置該 leaf 的空間。一直 `malloc` 時，heap 也會形同 stack 一般地增長，所以當給定測試條件很規律的狀況下，字串地址與 leaf 的地址很可能都很靠近。
>
> 換言之，CPY 機制在一開始 `p->eqkid` 後，字串有很大可能就在 cache 裡面了，因此 cache miss 機率較低，這就是它相對來說在 prefix-search 上效率比較好的原因。
但整體花費的時間卻是 `CPY (約11.7365sec)`少於 `REF (約12.059sec)`。再者，在我連續觀察兩者的 cache miss 比例時，曾有幾次的 cache miss 比例是由 `CPY` 勝出，不過真的佔少數，綜合上述幾個觀點後我認為有可能是因為 `REF` 機制的 cache miss 比例變動幅度比 `CPY` 來得大，所以造成數次比較中由`CPY` 勝出
但為了釐清 `CPY` 與 `REF` 的 cache miss 比例到底是誰多，因此用 `perf record` 做更進一步函式級別的效能分析，方便我們對程序「熱點」做更精細的分析和優化。
CPY 機制:
```shell=
$ sudo perf record -e cache-misses -g ./test_common --bench CPY
Samples: 37K of event 'cache-misses', Event count (approx.): 774136217
Children Self Command Shared Object Symbol
+ 99.50% 0.00% test_common libc-2.31.so [.] __libc_start_main
+ 99.50% 0.00% test_common test_common [.] main
+ 99.22% 0.02% test_common test_common [.] bench_test
+ 99.14% 0.26% test_common test_common [.] tst_search_prefix
+ 98.88% 98.79% test_common test_common [.] tst_suggest
```
```shell=
| tst_suggest(p->lokid, c, nchr, a, n, max);
0.64 │ movsbl -0xc(%rbp),%esi
0.14 │ mov -0x8(%rbp),%rax
0.23 │ mov 0x8(%rax),%rax
37.96 │ mov -0x10(%rbp),%r8d
0.23 │ mov -0x28(%rbp),%rdi
0.26 │ mov -0x20(%rbp),%rcx
0.05 │ mov -0x18(%rbp),%rdx
0.95 │ mov %r8d,%r9d
1.60 │ mov %rdi,%r8
0.11 │ mov %rax,%rdi
0.04 │ → callq tst_suggest
```
REF 機制:
```shell=
$ sudo perf record -e cache-misses -g ./test_common --bench REF
Samples: 39K of event 'cache-misses', Event count (approx.): 785801109
Children Self Command Shared Object Symbol
+ 99.49% 0.00% test_common libc-2.31.so [.] __libc_start_main
+ 99.48% 0.00% test_common test_common [.] main
+ 99.21% 0.02% test_common test_common [.] bench_test
+ 99.14% 0.24% test_common test_common [.] tst_search_prefix
+ 98.90% 98.81% test_common test_common [.] tst_suggest
```
發現無論是 CPY 或 REF 機制，`tst_suggest` 函式佔的 cache miss 高達98％，因此深入分析到底是 `tst_suggest` 中哪一行程式碼導致的
```shell=
| tst_suggest(p->lokid, c, nchr, a, n, max);
0.54 │ movsbl -0xc(%rbp),%esi
0.18 │ mov -0x8(%rbp),%rax
0.24 │ mov 0x8(%rax),%rax
32.26 │ mov -0x10(%rbp),%r8d
0.24 │ mov -0x28(%rbp),%rdi
0.20 │ mov -0x20(%rbp),%rcx
0.04 │ mov -0x18(%rbp),%rdx
0.88 │ mov %r8d,%r9d
1.44 │ mov %rdi,%r8
0.11 │ mov %rax,%rdi
0.07 │ → callq tst_suggest
```
結果在 `mov -0x10(%rbp),%r8d` 這行指令佔的比例最高
-------------------------------------------------
## 考慮到 CPY 和 REF 這兩種實作機制，思考效能落差的緣故，並且提出後續效能改善機制
在上面 [程式原理](https://hackmd.io/nfsG8OuKQtWIPcfnpfMFFA?view#%E7%A8%8B%E5%BC%8F%E5%8E%9F%E7%90%86) 有提到 `CPY` 與 `REF` 兩種實作機制的不同，
-------------------------------------------------
## 研讀 [Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters](https://arxiv.org/abs/1912.08258) 論文並參閱對應程式碼實作 [xor_singleheader](https://github.com/FastFilter/xor_singleheader)，引入上述 dict 程式碼中，需要比較原有的 bloom filter 和 xor filter 在錯誤率及記憶體開銷
-------------------------------------------------
## 如何縮減頻繁 malloc 帶來的效能衝擊呢
Sign in with Wallet
Connect another wallet