# 2020q3 Homework (dict)
contributed by < `hankluo6` >
## 環境
```
$ uname -a
Linux hank-VivoBook-ASUSLaptop-X580GD-N580GD 5.4.0-48-generic #52-Ubuntu SMP Thu Sep 10 10:58:49 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --versiongcc (Ubuntu 9.3.0-10ubuntu2) 9.3.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ lscpu
架構： x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 8
On-line CPU(s) list: 0-7
每核心執行緒數： 2
每通訊端核心數： 4
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 158
Model name: Intel(R) Core(TM) i5-8300H CPU @ 2.30GHz
製程： 10
CPU MHz： 2700.405
CPU max MHz: 4000.0000
CPU min MHz: 800.0000
BogoMIPS: 4599.93
虛擬： VT-x
L1d 快取： 128 KiB
L1i 快取： 128 KiB
L2 快取： 1 MiB
L3 快取： 8 MiB
NUMA node0 CPU(s)： 0-7
```
## 視覺化 ternary search tree + bloom filter 的效能表現
設計實驗來分析 bloom filter 對效能的影響，考量到 ternary search tree 為 prefix search，設計出以下實驗：
### 實驗 1：搜尋字串在第一個字元即判斷不在字典內
### 實驗 2：搜尋字串在到中間字元才判斷不在字典內
### 實驗 3：搜尋字串在到結尾字元才判斷不在字典內
可以發現以上三種 bloom filter 效能都比只用 ternary search tree 還好，這是因為我們 hash table 夠大，隨機產生的字串在 hash 之後都能立刻察覺不在字典內。且可以發現 `bloom filter` 不受字元位置影響，但 ternary search tree 卻會因字元位置不同而影響效能。
### 實驗 4：字元位置對 tst 與 bloom filter 的效能差異
從此實驗可以看到，只要搜尋字串不在字典內，使用 bloom filter 都能增加效能。另外，能夠發現此字典建立的 ternary search tree 在不同字元位置增加時，效能還能維持在一定範圍內，推測是因城市間名字差異過大，導致搜尋時很快就能找到 leaf node。但還是有某些常見的 prefix，導致搜尋時可能會 traversal 多次，造成圖上某些特別高點。
## 以 perf 分析 TST 程式碼的執行時期行為
將 bloom filter 的部份從程式碼中移除，使用 `perf record` 來分析 CPY prefix search 的程式熱點：
```
Samples: 3K of event 'cycles', Event count (approx.): 421500000
Overhead Command Shared Object Symbol
47.98% test_common test_common [.] tst_ins_del
13.97% test_common test_common [.] tst_free_all
11.60% test_common test_common [.] main
6.38% test_common libc-2.31.so [.] _int_malloc
3.11% test_common libc-2.31.so [.] _int_free
```
用 `perf diff` 來觀察 CPY 與 REF 的差異：
```
# Event 'cycles'
#
# Baseline Delta Abs Shared Object Symbol
# ........ ......... ................ ................................
#
+14.28% test_common [.] tst_free
0.86% +0.64% libc-2.31.so [.] __strlen_avx2
3.11% -0.46% libc-2.31.so [.] _int_free
0.68% -0.45% test_common [.] 0x00000000000011a4
```
可發現兩者除了 REF 必要的 `tst_free` 外，沒有太大的差異，所以這邊只觀察 CPY 的行為。
`tst_ins_del` 為程式插入跟移除節點呼叫的函式，分析內部實作：
```c
void *tst_ins_del(tst_node **root, const char *s, const int del, const int cpy)
{
...
while ((curr = *pcurr)) {
...
if (diff == 0) {
if (*p++ == 0) {
...
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);
}
if (del)
return (void *) -1;
for (;;) {
...
if (!*root)
*root = *pcurr;
if (cpy) {
...
} else {
...
}
}
pcurr = &(curr->eqkid);
}
}
```
可以看到分支數量極多，前面 `while` 用來尋找插入位置(或將預移除的節點放入 stack 中)，後面 `for` 迴圈則是插入剩下沒存在樹中的字元。觀察 Assembly Code 裡的熱點：
```
Samples: 3K of event 'cycles', 125000 Hz, Event count (approx.): 419750000
tst_ins_del
---------------------------------------------------------------------------------
Percent
│ diff = *p - curr->key; /* get ASCII diff for >, <, = */
│ b3: mov -0x830(%rbp),%rax
0.26 │ movzbl (%rax),%eax
0.39 │ movsbl %al,%edx
1.22 │ mov -0x820(%rbp),%rax
33.42 │ movzbl (%rax),%eax
1.67 │ movsbl %al,%eax
2.06 │ sub %eax,%edx
│ mov %edx,%eax
2.90 │ mov %eax,-0x834(%rb)
```
根據 [隱藏在字典裡的數學](https://hackmd.io/@sysprog/BkE3uSvdN#%E4%BD%BF%E7%94%A8-perf-%E5%88%86%E6%9E%90%E7%A8%8B%E5%BC%8F%E6%95%88%E8%83%BD) 章節中提到 [perf 的偏差問題](https://stackoverflow.com/questions/43794510/linux-perf-reporting-cache-misses-for-unexpected-instruction)，這邊造成熱點的部份應為 `mov -0x820(%rbp),%rax` 這個指令，用來取出 `*p` 的值。分析後可知道此 overhead 應為 cache-misses 造成的，因為此 function 的第一次 deference，故不在 Cache 的機率相當高。
```
Samples: 33 of event 'cache-misses', 125000 Hz, Event count (approx.): 4125000
tst_ins_del
---------------------------------------------------------------------------------
Percent
│ diff = *p - curr->key; /* get ASCII diff for >, <, = */
│ movzbl (%rax),%eax
│ movsbl %al,%edx
│ mov -0x820(%rbp),%rax
│ movzbl (%rax),%eax
62.50 │ movsbl %al,%eax
```
所以程式主要消耗時間的部份是在插入跟移除節點的時候，實際上搜尋所耗的時間相當少，其實從運行時間也能看出此現象：
```
CPY mechanism
ternary_tree, loaded 206849 words in 0.105415 sec
choice: find words matching prefix (at least 1 char): Tai - searched prefix in 0.000184 sec
```
兩者有近千倍的效能差異。
## 考慮到 CPY 和 REF 這兩種實作機制，思考效能落差的緣故，並且提出後續效能改善機制
先執行 `perf test` 來看兩者在硬體上的行為是否有差異：
```
Performance counter stats for './test_common --bench CPY s Tai' (100 runs):
3,778,706 cache-misses # 38.210 % of all cache refs ( +- 0.32% )
9,889,235 cache-references ( +- 0.33% )
587,643,670 instructions # 1.19 insn per cycle ( +- 0.02% )
492,740,152 cycles ( +- 0.07% )
Performance counter stats for './test_common --bench REF s Tai' (100 runs):
3,807,348 cache-misses # 38.754 % of all cache refs ( +- 0.94% )
9,824,456 cache-references ( +- 0.25% )
554,073,126 instructions # 1.12 insn per cycle ( +- 0.00% )
492,670,490 cycles ( +- 0.40% )
```
看不太出來有什麼顯著的差別，只能看出 REF 的 cache-misses 稍微多一些。改從程式碼運行時間觀察：
大部分時間 REF 速度都比 CPY 快。
一開始認為是 locailty 的問題，CPY 因為是使用 malloc 導致其 memory 分配的較分散，進而影響到效能，但觀察 cache-misses 卻發現 CPY 竟然比 REF 還要低。
根據 `perf stat` 中另一個有差距的數據為 instructions，或許是因為 instructions 的數量影響到效能，但不知道如何設計實驗來分析 instruction 數量對效能的影響。
## 研讀 Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters 論文
[論文連結](https://arxiv.org/pdf/1912.08258.pdf)
### Algorithm 1 Membership test
用來檢查該元素是否在 $B$ 當中。
### Algorithm 2 Construction
此部份用來隨機選擇三個 hash function，並經過 Algorithm 3 的檢查確定可以使用後，透過 Algorithm 4 將值存入到 memory 中。
### Algorithm 3 Mapping Step (map)
$S$ 為建立 filter 時的所有元素集合，所有元素 $x \in S$ 經過 3 個 hash function 後會得到 $h_1(x)$, $h_2(x)$, $h_3(x)$。只要集合 $S$ 中的任意兩個元素 $x$ 與 $y$ 中，以下等式成立的話，就是合理的 hash function，回傳 true 到 Algorithm 2。否則，回傳 false 到 Algorithm 2 並重新挑選 3 個 hash function。
$(h_1(x) \neq h_1(y)) \ \vee\ (h_2(x) \neq h_2(y)) \ \vee \ (h_3(x) \neq h_3(y))$
### Algorithm 4 Assigning Step (assign)
將結果存入 $B$ 中，這邊用到第 4 個 hash function: fingerprint 做 XOR。存入到 $B[i]$ 中的為 $B[h_0(x)]\oplus B[h_1(x)]\oplus B[h_2(x)] = \text{fingerprint}(x)$ 的結果，存入的位置 $i$ 為 Algorithm 3 中 push 到 stack 時的位置。
:::info
這邊 $i$ 為 $h_0(x)$, $h_1(x)$, $h_2(x)$ 中的某一個，在論文中使用 **queue** 來儲存要處理的 index，處理完畢後再放入 **stack** 中。這樣在此步驟要處理 pop 出來的 index 上的元素 $x$ 時，該元素對應到的 $B[h_{s\in {0,1,2}}(x)]$ 都只會被處理一次，而不會被後來的元素 $y$ 蓋掉同樣的 $B[h_{s\in {0,1,2}}(x)]$，這是因為每個 pop 出來的 index 皆為在該 set 中的唯一元素。
:::
>an entry in B is modified at most once. After we modify an entry B[i], then
none of the values B[h0(x)], B[h1(x)], B[h2(x)] will ever be modified again.
### Example
$S = \{1, 2, 3\}$
$B = \text{array of 8 bits}$
假設 construction 的 hash function 如下
| $x\in S$ | $h_0(x)$ | $h_1(x)$ | $h_2(x)$ | $\text{fingerprint}(x)$ |
| -------- | -------- | -------- | -------- | ----------------------- |
| 1 | 1 | 4 | 5 | 0 |
| 2 | 1 | 2 | 7 | 1 |
| 3 | 4 | 5 | 7 | 1 |
一開始為 $H$ 為空陣列：
```graphviz
digraph G {
nodesep=.05;
rankdir=LR;
node [shape=record,width=.1,height=.1];
"H" [color=white];
node0 [label = "<f0> 0 |<f1> 1 |<f2> 2 |<f3> 3 |<f4> 4 |<f5> 5 |<f6> 6| <f7> 7",height=2.5];
node [width = 1.5];
node1 [label = "{<n> }"];
node2 [label = "{<n> }"];
node3 [label = "{<n> }"];
node4 [label = "{<n> }"];
node5 [label = "{<n> }"] ;
node6 [label = "{<n> }"] ;
node7 [label = "{<n> }"] ;
node8 [label = "{<n> }"] ;
{ rank=same; "H"; node0 }
node0:f0 -> node1:n;
node0:f1 -> node2:n;
node0:f2 -> node3:n;
node0:f3 -> node4:n;
node0:f4 -> node5:n;
node0:f5 -> node6:n;
node0:f6 -> node7:n;
node0:f7 -> node8:n;
}
```
插入 1, 2, 3 之後：
```graphviz
digraph G {
nodesep=.05;
rankdir=LR;
node [shape=record,width=.1,height=.1];
"H" [color=white];
node0 [label = "<f0> 0 |<f1> 1 |<f2> 2 |<f3> 3 |<f4> 4 |<f5> 5 |<f6> 6| <f7> 7",height=2.5];
node [width = 1.5];
node1 [label = "{<n> }"];
node2 [label = "{<n> 1 | 2}"];
node3 [label = "{<n> 2}"];
node4 [label = "{<n> }"];
node5 [label = "{<n> 1 | 3}"] ;
node6 [label = "{<n> 1 | 3}"] ;
node7 [label = "{<n> }"] ;
node8 [label = "{<n> 2 | 3}"] ;
{ rank=same; "H"; node0 }
node0:f0 -> node1:n;
node0:f1 -> node2:n;
node0:f2 -> node3:n;
node0:f3 -> node4:n;
node0:f4 -> node5:n;
node0:f5 -> node6:n;
node0:f6 -> node7:n;
node0:f7 -> node8:n;
}
```
接著使用 **queue** $Q$ 來 push 只有一個元素的 index，此例中只有 index 2
```graphviz
digraph {
node [shape=plaintext, fontcolor=black, fontsize=18];
"queue Q" [color=white];
node [shape=record, fontcolor=black, fontsize=14 fixedsize=true,width=1];
q [label="2", color=blue, fillcolor=lightblue, style=filled];
{ rank=same; "queue Q"; q }
}
```
進入到 `while` 迴圈，條件為 $Q$ 不為空。做了以下事情：
* 從 $Q$ 中 pop 元素 $i$ 出來
* 宣告 $x$ 為 $H[i]$
* 將 $(x,i)$ pair push 至 stack $\sigma$ 中
* 將所有出現的 $x$ 從 $H$ 中移除
* 如果移除 $x$ 的 index 只剩一個元素，則 push 該 index 至 queue 當中
以下模擬每次迴圈所作的事情：
loop 1:
pop 2 from $Q$
```graphviz
digraph G {
nodesep=.05;
rankdir=LR;
node [shape=record,width=.1,height=.1];
"H" [color=white];
node0 [label = "<f0> 0 |<f1> 1 |<f2> 2 |<f3> 3 |<f4> 4 |<f5> 5 |<f6> 6| <f7> 7",height=2.5];
node [width = 1.5];
node1 [label = "{<n> }"];
node2 [label = "{<n> 1}"];
node3 [label = "{<n> }"];
node4 [label = "{<n> }"];
node5 [label = "{<n> 1 | 3}"] ;
node6 [label = "{<n> 1 | 3}"] ;
node7 [label = "{<n> }"] ;
node8 [label = "{<n> 3}"] ;
{ rank=same; "H"; node0 }
node0:f0 -> node1:n;
node0:f1 -> node2:n;
node0:f2 -> node3:n;
node0:f3 -> node4:n;
node0:f4 -> node5:n;
node0:f5 -> node6:n;
node0:f6 -> node7:n;
node0:f7 -> node8:n;
}
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=black, fontsize=18];
"queue Q" [color=white];
node [shape=plaintext, fontcolor=black, fontsize=18];
"stack S" [color=white];
"queue Q" -> "stack S" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=2];
q [label="<f0>1 | <f1>7", color=blue, fillcolor=lightblue, style=filled];
node [shape=record, fontcolor=black, fontsize=14 fixedsize=true, width=1,];
s [label="(2,2)", color=blue, fillcolor=lightblue, style=filled];
q:f0->s[style=invis];
{ rank=same; "queue Q"; q }
{ rank=same; "stack S"; s }
}
```
loop 2:
pop 1 from $Q$
```graphviz
digraph G {
nodesep=.05;
rankdir=LR;
node [shape=record,width=.1,height=.1];
"H" [color=white];
node0 [label = "<f0> 0 |<f1> 1 |<f2> 2 |<f3> 3 |<f4> 4 |<f5> 5 |<f6> 6| <f7> 7",height=2.5];
node [width = 1.5];
node1 [label = "{<n> }"];
node2 [label = "{<n> }"];
node3 [label = "{<n> }"];
node4 [label = "{<n> }"];
node5 [label = "{<n> 3}"] ;
node6 [label = "{<n> 3}"] ;
node7 [label = "{<n> }"] ;
node8 [label = "{<n> 3}"] ;
{ rank=same; "H"; node0 }
node0:f0 -> node1:n;
node0:f1 -> node2:n;
node0:f2 -> node3:n;
node0:f3 -> node4:n;
node0:f4 -> node5:n;
node0:f5 -> node6:n;
node0:f6 -> node7:n;
node0:f7 -> node8:n;
}
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=black, fontsize=18];
"queue Q" [color=white];
node [shape=plaintext, fontcolor=black, fontsize=18];
"stack S" [color=white];
"queue Q" -> "stack S" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=4];
q [label="<f0>7 | <f1>4 | <f2> 5 | <f3> 7", color=blue, fillcolor=lightblue, style=filled];
node [shape=record, fontcolor=black, fontsize=14 fixedsize=true, width=1,];
s [label="<f0>(2,2) | <f1>(1,1)", color=blue, fillcolor=lightblue, style=filled, width=2];
q:f0->s:f0[style=invis];
{ rank=same; "queue Q"; q }
{ rank=same; "stack S"; s }
}
```
loop 3:
pop 7 from $Q$
```graphviz
digraph G {
nodesep=.05;
rankdir=LR;
node [shape=record,width=.1,height=.1];
"H" [color=white];
node0 [label = "<f0> 0 |<f1> 1 |<f2> 2 |<f3> 3 |<f4> 4 |<f5> 5 |<f6> 6| <f7> 7",height=2.5];
node [width = 1.5];
node1 [label = "{<n> }"];
node2 [label = "{<n> }"];
node3 [label = "{<n> }"];
node4 [label = "{<n> }"];
node5 [label = "{<n> }"] ;
node6 [label = "{<n> }"] ;
node7 [label = "{<n> }"] ;
node8 [label = "{<n> }"] ;
{ rank=same; "H"; node0 }
node0:f0 -> node1:n;
node0:f1 -> node2:n;
node0:f2 -> node3:n;
node0:f3 -> node4:n;
node0:f4 -> node5:n;
node0:f5 -> node6:n;
node0:f6 -> node7:n;
node0:f7 -> node8:n;
}
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=black, fontsize=18];
"queue Q" [color=white];
node [shape=plaintext, fontcolor=black, fontsize=18];
"stack S" [color=white];
"queue Q" -> "stack S" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=3];
q [label="<f0>4 | <f1> 5 | <f2> 7", color=blue, fillcolor=lightblue, style=filled];
node [shape=record, fontcolor=black, fontsize=14 fixedsize=true, width=1,];
s [label="<f0>(2,2) | <f1>(1,1) | <f3>(3,7)", color=blue, fillcolor=lightblue, style=filled, width=3];
q:f0->s:f0[style=invis];
{ rank=same; "queue Q"; q }
{ rank=same; "stack S"; s }
}
```
loop 4~6
pop 4,5,6 from $Q$
**but doing nothing because the condition: ==if the set H[i] contains a single key== in the pseudocode**
因為 stack 的 size 與 元素個數相同，所以此 hash function 是可行的，進入到 Algorithm 4。
初始化陣列 $B$
Algorithm 4 的三次迴圈：
loop 1
pop (7,3) from stack
$$
\begin{align}
B[7]&=\text{fingerpoint}(3)\oplus B[h_0(3)] \oplus B[h_1(3)] \oplus B[h_2(3)]\\
&=\text{fingerpoint}(3)\oplus B[4] \oplus B[5] \oplus B[7]\\
&=1 \oplus 0 \oplus 0 \oplus 0 \\
&=1
\end{align}
$$
loop 2
pop (2,2) from stack
$$
\begin{align}
B[2]&=\text{fingerpoint}(2)\oplus B[h_0(2)] \oplus B[h_1(2)] \oplus B[h_2(2)]\\
&=\text{fingerpoint}(2)\oplus B[1] \oplus B[2] \oplus B[7]\\
&=1 \oplus 0 \oplus 0 \oplus 1 \\
&=0
\end{align}
$$
loop 3
pop (1,1) from stack
$$
\begin{align}
B[1]&=\text{fingerpoint}(1)\oplus B[h_0(1)] \oplus B[h_1(1)] \oplus B[h_2(1)]\\
&=\text{fingerpoint}(1)\oplus B[1] \oplus B[4] \oplus B[5]\\
&=0 \oplus 0 \oplus 0 \oplus 0 \\
&=0
\end{align}
$$
可以看到已經決定後的 $B[x]$，不會在被後面的元素蓋掉。而賦值給 $B[h_{s\in {1,2,3}}(x)]$ 其中一個元素用途是讓 fingerpoint(x) 與 $B[h_0(x)] \oplus B[h_1(x)] \oplus B[h_2(x)]$ 相等。
## 如何縮減頻繁 malloc 帶來的效能衝擊呢？
移除頻繁呼叫的 `calloc()`，改以從 memory pool 中取得所需記憶體。可以使用 free list 來實現 memory pool，此方法能有效的移除不需要的節點空間，減少記憶體碎片化的問題。
:::info
TODO: 實作 free list 並分析效能
:::
## 使用 bloom filter 的專案
[Apache Cassandra](https://en.wikipedia.org/wiki/Apache_Cassandra) 是一套開源分散式 [NoSQL](https://en.wikipedia.org/wiki/NoSQL) 資料庫系統。它最初由 Facebook 開發，用於改善電子郵件系統的搜尋效能的簡單格式資料，集 Google BigTable 的資料模型與 Amazon Dynamo 的完全分散式架構於一身。
Cassandra 是透過將 disk 上的資料 (SSTables) 與 RAM 上的資料 (memtables) 做 merge 來達成資料的讀取。
引入 bloom filter 有兩個好處：
* A Bloom filter can establish that a SSTable does not contain certain partition data.
* A Bloom filter can also find the likelihood that partition data is stored in a SSTable. It speeds up the process of partition key lookup by narrowing the pool of keys.
在資料庫上因為讀取資料耗費的時間較長，使用 bloom filter 可以快速知道資料庫中是否有需要的資料，或是知道哪部份沒有需要的資料，進而縮小搜尋範圍。
延伸閱讀：
* [Cassandra Bloom Filter Source Code](https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/utils/BloomFilter.java)
* [Bigtable: A Distributed Storage System for Structured Data](http://static.googleusercontent.com/media/research.google.com/en//archive/bigtable-osdi06.pdf)
* [How is data read?](https://docs.datastax.com/en/archived/cassandra/3.0/cassandra/dml/dmlAboutReads.html)
* [Cassandra Doc](https://cassandra.apache.org/doc/latest/operating/bloom_filters.html)
###### tags: `linux2020`
Sign in with Wallet
Connect another wallet