2020q3 Homework (dict)

# 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：搜尋字串在第一個字元即判斷不在字典內 ![](https://i.imgur.com/z8gZfbk.png) ### 實驗 2：搜尋字串在到中間字元才判斷不在字典內 ![](https://i.imgur.com/IelMykq.png) ### 實驗 3：搜尋字串在到結尾字元才判斷不在字典內 ![](https://i.imgur.com/xvDyowQ.png) 可以發現以上三種 bloom filter 效能都比只用 ternary search tree 還好，這是因為我們 hash table 夠大，隨機產生的字串在 hash 之後都能立刻察覺不在字典內。且可以發現 `bloom filter` 不受字元位置影響，但 ternary search tree 卻會因字元位置不同而影響效能。 ### 實驗 4：字元位置對 tst 與 bloom filter 的效能差異 ![](https://i.imgur.com/LvrgA42.png) 從此實驗可以看到，只要搜尋字串不在字典內，使用 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 稍微多一些。改從程式碼運行時間觀察： ![](https://i.imgur.com/2l5qlZ2.png) 大部分時間 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`

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.