# 2020q3 Homework3 (dict)
contributed by < `eecheng87` >
###### tags: `進階電腦系統應用2020`
## 研讀 XOR Filter 論文 & Tracing 實做專案
### 工具
在檔案的一開始有定義一些工具：
* `xor_fingerprint`
> Fingerprint-based variants store a fingerprint per key, where a fingerprint is the result of hash
function h
簡單來說就是一種 hash function，但是在這個專案內有多種雜湊的函數，為什麼需要這麼多種？因為相同的 hash 方式會導致 mapping 效果有限，以下引述原文內容：
> The hash functions
h0,h1,h2 are assumed to be independent from the hash function used for the fingerprint.
* `xor_reduce(uint32_t hash, uint32_t n)`
效能版的 modulo 運算，避開 `%` 會用到除法，透過 shift 讓 `hash/(2<<32)` 介於 1~0 之間，因此期望可以公平的產生 0~n 的值，已達到 modulo 的效果。
* `xor_murmur64`
接受一個隨機值(seed)產生一個雜湊值。
### 功能
#### 分配 map 空間
`xor8_allocate` 分配恰當的大小給 `filter`，這個大小根據實驗結果訂成 ⌊1.23 · |S |⌋ + 32(太大會浪費空間，太小則會造成頻繁的 collision)，而實做還有個小細節是 `capacity = capacity / 3 * 3` 使得 `filter` 剛好可以分成三等份，以利往後透過 hash0~3 產生 hash value。
#### construct filter
設定 fingerpoint 的值，使未來呼叫 `xor8_contain` 能透過 exclusive-or aggregate 來檢查 key 是否在 set 內。
首先把所有 key 加到 set 中，加的方式是透過 XOR。接著迭代 set，若該 index 上只有一個 key 就把該 key 加入 Queue 中。
再來是把 Queue 中某 index 上(假設為 h0)只有一個 key 的移出(也要移除其他兩個 index 上(h1, h2)的 key值)。接著再檢查 h1, h2 上是否又只剩一個 key，如果是則加到 Queue 中等下一個回合。一直重複直到 Queue 空了，再檢查 stack 上是否包含所有 key，如果是的話代表 construction 成功，反之失敗，重新開始(第一步驟)。
註: 移除 index 上的 key 是利用 XOR 的特殊性質，假設 `xormask` 上已經有 key1, key2，那 `xormask` 就是 `key1^key2`，如果要移除 `key1` 只需要再做一次 XOR key1，這樣 `xormask` 就會變成 key2。
註: `xor8_get_h0_h1_h2` 會回傳一個 `answer` 裡面紀錄 hash 值和 h0~3 分別該在 index 多少的地方檢查 xormask(每個 iterator 中 filter 有自己的 random seed，所以會根據 key 產生三個 hash index)。
#### 檢查某 key 是否已經存在
要決定一個 key 是否在 set 內需要找到 3 個 fingerprint 來做 exclusive-or aggregate。而這 3 個 fingerprint 的 index 需要透過雜湊得到。這個雜湊的流程是：
* 透過 `xor_mix_split` 得到 tmp hash
* 如果目前要找的 index 在第二或三個 block，則透過 `xor_rotl64` 轉換
* 透過 `xor_reduce` 得到最後的 index
在 Algorithm 1 提到透過檢查 `fingerprint(x)` 和 `B[h0(x)] xor B[h1(x)] xor B[h2(x)]` 是否相同來決定。對應專案：
```cpp=84
f == (filter->fingerprints[h0] ^ filter->fingerprints[h1] ^
filter->fingerprints[h2])
```
之所以可以這樣判斷是因為在建構 filter 時
```cpp
uint8_t * fingerprints0 = filter->fingerprints;
...
size_t stack_size = size;
while (stack_size > 0) {
xor_keyindex_t ki = stack[--stack_size];
uint64_t val = xor_fingerprint(ki.hash);
if(ki.index < blockLength) {
val ^= fingerprints1[xor8_get_h1(ki.hash,filter)] ^ fingerprints2[xor8_get_h2(ki.hash,filter)];
}
...
filter->fingerprints[ki.index] = val;
}
```
假設 `ki.index` 在 `S` 的第三個 block，那 `filter->fingerprints[h3]` 就等於 `xor_fingerprint(ki.hash) ^ fingerprints0[xor8_get_h0(ki.hash,filter)] ^ fingerprints1[xor8_get_h1(ki.hash,filter)]`。可以想成 `fingerprint(h3) = xor_fingerprint(hash) ^ fingerprint(h0) ^ fingerprint(h1)`，那回到檢查是否存在 set 中的判斷式 `xor_fingerprint(hash) == (filter->fingerprints[h0] ^ filter->fingerprints[h1] ^
filter->fingerprints[h2])` 可以發現，兩者是一樣的。
### 效能
#### 建構 filter
[實作的 XOR filter](https://github.com/FastFilter/xor_singleheader/blob/master/include/xorfilter.h) 將 Queue 分成三段避開只有一條 Queue，產生過多 empty。
#### search
在論文中提到用 bloom filter 搜尋時間比較敏感(sensitive)，bloom filter 對搜尋在 set 的資料會花比較久的時間。舉 `dict` 實做的 `bloom_test` 來説：
```cpp
bool bloom_test(bloom_t filter, const void *item)
{
...
while (h) {
...
if (!(bits[hash >> 3] & (0x80 >> (hash & 7)))) {
return false;
}
h = h->next;
}
return true;
}
```
如果要回傳 `true`(item 在 set 內)，那就必須走訪完所有的 hash function。反之，如果已經發現該 item 不在 set 內也不是什麼好事，因為會有 mispredicted branches。
對 XOR Filter 而言就相對穩定，每次 search 花費 3 個 memory access，而且由於硬體的進步，這三次 access 可平行進行。
#### 實驗驗證
##### 搜尋在 set 內的 text
引入 xor filter 至 `dict`，以下為 XOR filter v.s TST search 和 XOR filter v.s bloom filter 的執行速度，以下均尋找『在 set』的字串：
XOR filter v.s TST search
可以看出 XOR filter 表現較好，但直線圖不太直觀，改成 boxplot：
以下是 XOR filter v.s bloom filter 的執行速度的比較：
其實差距真的很小，而且就程式執行來說，『搜尋』並非是整個程式的熱點，即使連續找了 1000 次，仍只佔了 0.06%。
##### 搜尋不在 set 內的 text
又可分為在第一個字元就不一樣或最後一個字元才不一樣。在還沒做實驗前先預測，由於 只有 TST 搜尋是循序的(第一個字元->第二個..)，所以在搜尋不在 set 內的 key 跟第一個不一樣的位置有關係。因此 TST 會因為上述兩種不同情況而產生效能差異。反之，其他兩種 filter 都是把字串內所有字元拿去做 hash，所以和相異字元的位置無關。
以下為設計第一個字元就不在 set 內：
以下為設計直到最後一個字元才不一樣：
從相對關係來看，TST 有些微差距。
##### false positive
測試三千筆不在 set 的資料搜尋，看看 filter 的正確性。
```
iter 2: xor-filter find
iter 776: xor-filter find
iter 873: xor-filter find
iter 888: xor-filter find
iter 972: xor-filter find
iter 1131: bloom-filter find
iter 1189: xor-filter find
iter 1206: bloom-filter find
iter 1212: xor-filter find
iter 1639: bloom-filter find
iter 1641: bloom-filter find
iter 1691: xor-filter find
iter 1788: xor-filter find
iter 1802: xor-filter find
iter 1889: xor-filter find
iter 2000: bloom-filter find
iter 2087: xor-filter find
iter 2113: xor-filter find
iter 2114: xor-filter find
iter 2560: xor-filter find
iter 2697: xor-filter find
```
xor filter 預測錯誤的機率大概是 bloom filter 的三倍。另外還有一件蠻神的事是 xor filter 的 false positive rate 為 17/30%，和文件預測的 0.3%相去不遠。
當然，文件也有提供替代方案，如果需要更高的預測性，使用 `xor16` 系列的 API，這裡測試了 10000 筆，bloom filter 已經 miss 17 次了，但是 xor filter 尚未 miss。
## 提昇 bloom filter 效能
透過 `perf` 觀察程式執行的熱點分佈，試圖找出可改善的地方。由於 bloom filter 主要依賴其搜尋(預測)的功能，所以從 `bloom_test` 開始分析：
```
22.85% 14.41% test_search_per test_search_perf [.] bloom_test
```
接著使用 annotate 來從更底層的角度找瓶頸：
```
25.00 │ mov %eax,-0x14(%rbp) ▒
│ unsigned int hash = h->func(item); ▒
│ mov -0x14(%rbp),%eax ▒
│ mov -0x28(%rbp),%rdx ▒
│ mov 0x10(%rdx),%rcx ▒
│ mov $0x0,%edx ▒
50.00 │ div %rcx ▒
25.00 │ mov %rdx,%rax
```
可以發現在 `bloom_test` 內花了一半的時間在做 `div`，即除法。的確，除法是很貴的運算，`perf` 的結果符合常理。接著開始著手問題，思考如何避免 `bloom_test` 中會用到除法的 modulo 運算。
```cpp
while (h) {
unsigned int hash = h->func(item);
hash %= filter->size;
...
h = h->next;
}
```
modulo 也只是為了能**平均的**分散 hash，所以是否有其他更省力的方式也能達到**公平的**分散呢？當然是有，可參考[文章](https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/)的詳細說明，以下只展示改動的部份：
```cpp
while (h) {
unsigned int hash = h->func(item);
hash = (unsigned int) (((unsigned long) hash * 100000) >> 32);
if (!(bits[hash >> 3] & (0x80 >> (hash & 7)))) {
return false;
}
h = h->next;
}
```
巧妙的用乘法(相對 `div` 之便宜的運算)和 shift(快速的運算，也能達到類似除法的效果)來公平的分配 hash。此外，根據編譯器不同的 optimization，在編譯期間常數的乘法(`hash * 100000`) 很有可能被先算，所以執行期間只需要做 shift，因此期待能達到更快的速度完成搜尋。(p.s. 100000 為 filter 的大小)
### 實驗
以下設計 6 種搜尋方式觀察其搜尋速度，P 代表優化後的 `bloom_test`、Ori 代表原本的 `bloom_test`，而 O1~O3 為編譯最佳化的參數：
可以發現改良後的 `bloom_test` 表現較好(不論最佳化程度)。
### 繼續改善！
或許在某些情況下乘法無法在編譯期間運算，所以為了追求更快的效果，如果我們把 filter 改成 2 的指數，那就可以直接用 shift 完成原本的需求
```cpp
while (h) {
unsigned int hash = h->func(item);
hash = hash >> 16;
if (!(bits[hash >> 3] & (0x80 >> (hash & 7)))) {
return false;
}
h = h->next;
}
```
把 filter 大小由原本的 100000 縮小成 65536，則可將 `(unsigned int) (((unsigned long) hash * 65536) >> 32)` 改成 `(unsigned int) (((unsigned long) hash << 16) >> 32)`，化簡後變 `hash >> 16`。
以下實驗為用 filter 非 2 的指數的 `bloom_test` 和為 2 的指數的 `bloom_test` 來比較效能。前者為 P O1~3，後者為 FP O1~3(Fast Performance)。
可以發現 FP 又比上一個版本的表現更好了！
:::warning
另外要注意，原本的 bloom filter 不能處理資料刪除，所以後來才出現 [Cuckoo Filter](https://en.wikipedia.org/wiki/Cuckoo_filter)，請評估在 dict 的使用情境中，bloom filter 該如何調整，才能具備合理的資料刪除能力，又不失原本的 filtering。
:notes: jserv
:::
Sign in with Wallet
Connect another wallet