# 2018q3 Homework3 (dict)
contributed by <[`pjchiou`](https://github.com/pjchiou)>
---
## 實驗環境
```
架構： x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
每核心執行緒數： 2
每通訊端核心數： 2
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 60
Model name: Intel(R) Core(TM) i5-4200H CPU @ 2.80GHz
製程： 3
CPU MHz： 2607.673
CPU max MHz: 3400.0000
CPU min MHz: 800.0000
BogoMIPS: 5587.04
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 3072K
NUMA node0 CPU(s)： 0-3
```
```
$ cat /etc/os-release
NAME="Ubuntu"
VERSION="18.04.1 LTS (Bionic Beaver)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 18.04.1 LTS"
VERSION_ID="18.04"
HOME_URL="https://www.ubuntu.com/"
SUPPORT_URL="https://help.ubuntu.com/"
BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/"
PRIVACY_POLICY_URL="https://www.ubuntu.com/
legal/terms-and-policies/privacy-policy"
VERSION_CODENAME=bionic
UBUNTU_CODENAME=bionic
$ cat /proc/version
Linux version 4.16.0-041600-generic (kernel@kathleen)
(gcc version 7.2.0 (Ubuntu 7.2.0-8ubuntu3.2))
#201804012230 SMP Sun Apr 1 22:31:39 UTC 2018
```
---
## outline
- 測試檔
- 了解 `cpy` 與 `ref` 兩個版本的差異
- `cpy` 版本中的自動測試
- tst 加 bloom filter(也就是 ref 版本)
- cpy 與 ref 兩版本效能落差的緣故
- 後續改善
---
## 測試檔
資料夾內有一個 cities.txt 就是輸入檔，其中一段內容如下
```=1
...
Moxa, Germany
Monticello, Missouri, United States
Sassen, Germany
Lückenburg, Germany
...
```
以 #3 為例，在程式內會拆成 `Monticello,` 、 `Missouri,` 、 `United` 、 `States` 等四個字串，可想而知這個測試檔一定
- 很多字串是 `,` 結尾，不過這個特性對我沒什麼用，要小心 find 的時候別找錯。
- 國家會出現很多次。
此外
- case-sensitive 。
- 注意 #5 ，不是只有 26 個英文字出現，還會有其它歐洲國家的字母。
---
## 了解 `cpy` 與 `ref` 兩個版本的差異
test_cpy.c 沒有 #include"bloom.h" ，明顯這個版本沒有用到 bloom filter ，而 bloom filter 一個特性就是，==如果 bloom filter 說字串存在，不一定真的存在；若說字串不在，就 100% 真的不存在。==
由這個程式的各個功能來看兩者的差異。
:::warning
雖然我們的 structure 宣告成這樣，但在最後一個結點時 key 存的是 `\0` ，而 eqkid 會直接指向該字串而不是 struct tst_node 物件。
```clike=1
typedef struct tst_node {
char key;
unsigned refcnt;
struct tst_node *lokid;
struct tst_node *eqkid;
struct tst_node *hikid;
} tst_node;
```
:::
- 一開始插入字串時，要注意作業的示意圖內並沒有畫出字串結尾符號 `\0` ，如果我們先插入 `aa` 再插入 `aaa` ，結構應該要變下圖
```graphviz
digraph cpy{
a [label="a"]
aa [label="a"]
char [label="\\0"]
emp [label="NULL"]
eq [label="a|a",shape=record]
aaa [label="a"]
aaaend [label="\\0"]
lemp [label="NULL"]
aaastr [label="a|a|a",shape=record]
remp [label="NULL"]
a -> aa
aa -> char
char -> emp
char -> eq:nw
char -> aaa
aaa -> aaaend
aaaend -> lemp
aaaend -> aaastr:nw
aaaend -> remp
}
```
:::info
cpy 版本會 malloc 新的空間去存字串， ref 版卻是直接指向 memory pool 中的一塊空間，這應該就是這麼命名的原因?
:::
- 新增部分，多了以下判斷，如果存在就不會真的插入 tst 內。這跟程式一開始加入所有字串時是兩件事，一開始沒有做這個判斷，會確實把所有的字串都插入 tst 。
```clike=1
...
if (bloom_test(bloom, Top) == 1) /* if detected by filter, skip */
res = NULL;
else { /* update via tree traversal and bloom filter */
bloom_add(bloom, Top);
res = tst_ins_del(&root, &p, INS, REF);
}
...
```
- 搜尋部份，先用 bloom filter 判斷後，再真的下去找。
```clike=1=1
if (bloom_test(bloom, word) == 1) {
t2 = tvgetf();
printf(" Bloomfilter found %s in %.6f sec.\n", word, t2 - t1);
printf(
" Probability of false positives:%lf\n",
pow(1 - exp(-(double) HashNumber /
(double) ((double) TableSize / (double) idx)),
HashNumber));
t1 = tvgetf();
res = tst_search(root, word);
t2 = tvgetf();
if (res)
printf(" ----------\n Tree found %s in %.6f sec.\n",
(char *) res, t2 - t1);
else
printf(" ----------\n %s not found by tree.\n", word);
} else
printf(" %s not found by bloom filter.\n", word);
```
- 搜尋字首、刪除字串的部分一樣
- 結束時 cpy 版本會多去 free 自行 malloc 用來存字串的空間；而 ref 版本只要 free 結點自身所占的空間。
---
## `cpy` 版本中的自動測試
從程式碼可以看出，輸入 `./test_cpy --bench` ，可以直接再讀取一次測試檔，取每筆資料的前三個字元做為 prefix_search 的輸入。
但這個程式我覺得有個地方怪怪的，在 #3 處 `prefix` 的長度是 3 ，但在下方 #27 使用 strncpy(prefix, word, 3); ，不就會使 prefix 這個字串內沒有結尾符號 `\0` ?
```clike=1
int bench_test(const tst_node *root, char *out_file, const int max)
{
char prefix[3] = "";
char word[WORDMAX] = "";
char **sgl;
FILE *fp = fopen(out_file, "w");
FILE *dict = fopen(DICT_FILE, "r");
int idx = 0, sidx = 0;
double t1, t2;
if (!fp || !dict) {
if (fp) {
fprintf(stderr, "error: file open failed in '%s'.\n", DICT_FILE);
fclose(fp);
}
if (dict) {
fprintf(stderr, "error: file open failed in '%s'.\n", out_file);
fclose(dict);
}
return 1;
}
sgl = (char **) malloc(sizeof(char *) * max);
while (fscanf(dict, "%s", word) != EOF) {
if (strlen(word) < 4)
continue;
strncpy(prefix, word, 3);
t1 = tvgetf();
tst_search_prefix(root, prefix, sgl, &sidx, max);
t2 = tvgetf();
fprintf(fp, "%d %f sec\n", idx, (t2 - t1) * 1000000);
idx++;
}
fclose(fp);
fclose(dict);
return 0;
}
```
因此先將 prefix長度改為 4 ，之後輸入 `./test_cpy --bench` ，得到 bench_cpy.txt 這個檔案，記錄了將每個字串前三個字元拿來做 prefix search 所需時間，另外發現 scripts 資料夾內的 `runtime3.gp` 就是拿來畫圖的檔案，不過這個檔案只有過濾前 12500 筆資料，我把限制範圍的部分拿掉後，改為下方指令
```
reset
set xlabel 'prefix'
set ylabel 'time(sec)'
set title 'perfomance comparison'
set term png enhanced font 'Verdana,10'
set output 'runtime3.png'
set format x "%10.0f"
set xtic 1200
set xtics rotate by 45 right
plot 'bench_cpy.txt' using 1:2 with points title 'cpy',\
```
畫出來以後如下圖。
x 軸糊成一糰，不過沒差。搜尋的時間會和以下兩個因素有關
- 插入的順序影響 tst 整體結構，會導致有些搜尋要走很遠。
- 同樣開頭的字串太多，導致某結點下方很大一串。
看一下是不是這樣，改一下 bench_test #31 使其輸出搜尋的字首
```clike
fprintf(fp, "%d %s %f sec\n", idx, prefix, (t2 - t1) * 1000000);
```
然候寫一個[小程式](https://github.com/pjchiou/dict/blob/master/analysis/analysis.c)來看是否**同樣開頭太多會導致搜尋時間變長**，這個程式會輸出 4 個欄位
|prefix|出現次數|總搜尋時間|平均時間|
|:-:|:-:|:-:|:-:|
用以下指令依平均時間排序後
```
sort -g -k 4,4 output.txt > sort.txt
```
以下是其片段，一共有 6126 種字首，字首是 `San` 開頭花最多時間，其有 1036 個字串(其中可能有重複)，平均 735.9229 微秒，但 `San` 並非是出現最多次的字首。
```
Itx 1 0.238419 0.238419
Uno 2 0.715256 0.357628
Bch 1 0.476837 0.476837
DhÅ 1 0.476837 0.476837
Fki 1 0.476837 0.476837
Geà 1 0.476837 0.476837
Gzy 1 0.476837 0.476837
InÄ 1 0.476837 0.476837
Itr 1 0.476837 0.476837
...
Mon 1050 343904.972088 327.528545
Con 537 179635.524740 334.516806
Mos 82 31693.458558 386.505592
Chi 1745 681142.091729 390.339308
Can 1017 452615.737909 445.049890
Ban 353 161922.693256 458.704513
Cai 44 22166.252135 503.778458
Sai 1258 655490.398387 521.057550
Man 495 328909.635538 664.463910
San 1036 762416.124335 735.922900
```
以出現次數 vs. 平均秒數畫圖得到下圖
非常集中在左下角，放大來看看
只能說不常出現的字首在搜尋上會相對快得多，如果以 (x=50,y=50) 分成四個象限，一、三象限是我們預期的狀況，但出現在二、四象限的點也不在少數，看來 ==tst 整體結構的影響是很大的==。
---
## tst 加 bloom filter
從這邊之前都還沒有對 bloom filter 做說明與分析，先簡單用個例子說明一下 bloom filter 在做什麼。
bloom filter 是一個存有 `0` 或 `1` 的陣列，假設今天我有一個長度為 10 的 bloom filter 如下圖
```graphviz
digraph bloom{
node [shape=record]
filter [label="0|0|0|0|0|0|0|0|0|0"]
}
```
在程式開始時，把字串逐步加入 tst 之中，同時我們更新這個 bloom filter 內的值，利用 hash function 把字串轉成 0~9 之間的整數，然後把對應 bloom filter 中的值改為 1 。
假設今天我的 bloom filter 有兩個 hash function ，而我要插入兩個字串 `hello` 與 `world` ，這兩個字串經過我的 hash function 後，分別會得到兩個整數，假設是 `hello` 會得到 (0,5) ， `world` 得到 (0,3) ，我就更新 bloom filter 為下圖。
```graphviz
digraph bloom{
node [shape=record]
filter [label="1|0|0|1|0|1|0|0|0|0"]
}
```
接著，如果我要判斷一個字串 `test` 是否在我們的 tst 當中，我們把 `test` 也透過同樣的 hash function 計算後得 (5,1) ，分別去看 bloom filter 內這兩個位置是否都是 `1` ，如果是的話，有可能 `test` 在 tst 中，其中有一個不是 `1` 的話，`test` 必不在 tst 中。
這樣的機制我們可以知道以下特性
- bloom filter 愈長，誤判機率愈低。
- hash function 出來的結果愈平均愈好。
- 這個對 prefix search 沒用， hash function 的設計可能使 `hello` = (0,3) ； `hel` = (1,4) ，截然不同的結果。
- 判斷時間複雜度為 O(1) ，只要經過常數個 hash function運算加上常數次判斷是否為 `1` 。
接著看看 `ref` 版本內 find 是怎麼做的
```clike=1
...
printf("find word in tree: ");
if (!fgets(word, sizeof word, stdin)) {
fprintf(stderr, "error: insufficient input.\n");
break;
}
rmcrlf(word);
t1 = tvgetf();
if (bloom_test(bloom, word) == 1) {
t2 = tvgetf();
printf(" Bloomfilter found %s in %.6f sec.\n", word, t2 - t1);
printf(
" Probability of false positives:%lf\n",
pow(1 - exp(-(double) HashNumber /
(double) ((double) TableSize / (double) idx)),
HashNumber));
t1 = tvgetf();
res = tst_search(root, word);
t2 = tvgetf();
if (res)
printf(" ----------\n Tree found %s in %.6f sec.\n",
(char *) res, t2 - t1);
else
printf(" ----------\n %s not found by tree.\n", word);
} else
printf(" %s not found by bloom filter.\n", word);
break;
...
```
可以看到在 #10 有先用 bloom filter 找一次， #19 真的進到 tst 去找字串是否存在。這兩個時間的差異，就是 bloom filter 帶來的效益，以下再把輸入檔讀入一次， find 每一個字串。
先在 bench.c 中加入一版給 bloom filter 用的測試。跟原版的很像，但要注意這裡是 find ，而不是 prefix search 。
**最前面記得 #include "bloom.h"**
```clike=1
int bench_test_bloom(const tst_node *root, char *out_file, bloom_t filter)
{
char word[WORDMAX] = "";
int idx = 0;
double t1, t2;
FILE *fp = fopen(out_file, "w");
FILE *dict = fopen(DICT_FILE, "r");
tst_node *res;
if (!fp || !dict) {
if (fp) {
fprintf(stderr, "error: file open failed in '%s'.\n", DICT_FILE);
fclose(fp);
}
if (dict) {
fprintf(stderr, "error: file open failed in '%s'.\n", out_file);
fclose(dict);
}
return 1;
}
while (fscanf(dict, "%s", word) != EOF) {
t1 = tvgetf();
if (bloom_test(filter, word) == 1) {
t2 = tvgetf();
fprintf(fp, "%d %s %f ", idx++, word, (t2 - t1) * 100000);
t1 = tvgetf();
res = tst_search(root, word);
t2 = tvgetf();
if (res)
fprintf(fp, "%f\n", (t2 - t1) * 1000000);
else
printf("Error.\n");
} else
printf("Error, it's impossible can not find string.\n");
}
fclose(fp);
fclose(dict);
return (0);
}
```
在 test_ref.c 加入一小段
```clike=1
if (argc == 2 && strcmp(argv[1], "--bench") == 0) {
int stat = bench_test_bloom(root, "bench_ref.txt", bloom);
tst_free(root);
return stat;
}
```
相較於 tst ， bloom filter 幾乎是緊貼著 0 的線。
接下來畫張圖， X 軸是字串序號 ， Y 軸是 (tst 需要的時間 - bloom filter 需要的時間)
小於零的部分代表 tst 搜尋比 bloom filter 還要快，果然大部分字串的搜尋用 bloom filter 都會快上許多，但不見得一定正確。
---
## cpy 與 ref 兩版本效能落差的緣故
首先，透過程式碼我們看到 ref 的版本有使用 bloom filter 而 cpy 版沒有。但這並非我要討論的主因， bloom filter 在搜尋上比 tst 快是很正常的(多數情況下)，把這個程式看成是一個字典，我想知道的是建立起這個字典要花多少時間。
這兩個在建立起字典的機制有一點不一樣
- cpy
1. 逐個把字串插入 tst
2. 為每一個字串 malloc 一塊空間
- ref
1. 建立 bloom filter
2. 先 malloc 一塊很大的 memory pool 。預設是 $2000000*256*sizeof(char)$
3. 逐個把字串的存進這個 memory pool 與 tst 中，然後在 tst 之中每個字串的最後一個節點會指向這個 memory pool 存該字串的位置。
4. 更新 bloom filter
:::info
test_ref.c 之中最後忘記 free 這個 memory pool 了，因此我在最後加上 free(pool)
:::
可以看出 ref 版在前置的準備上步驟較多，先看看這兩個流程的效能差了多少。眼尖的網友應該有發現每次執行 test_cpy 時都會把建立起字典的時間寫入 cpy.txt 中，我們在 test_ref 也做一個這樣的機制。
```clike=1
FILE *output;
output = fopen("ref.txt", "a");
if (output != NULL) {
fprintf(output, "%.6f\n", t2 - t1);
fclose(output);
} else
printf("open file error\n");
```
==記得把 cpy.txt 先砍掉==
然後我們用 `make test` ，這已經準備好了，不用自己寫，可以得到 cpy.txt 與 ref.txt 。
避免我自己忘了刪 cpy.txt 我改了 Makefile 的這段，#2 加入刪除的部分。
```=1
test: $(TESTS)
rm cpy.txt ref.txt;
echo 3 | sudo tee /proc/sys/vm/drop_caches;
perf stat --repeat 100 \
-e cache-misses,cache-references,instructions,cycles \
./test_cpy --bench $(TEST_DATA)
perf stat --repeat 100 \
-e cache-misses,cache-references,instructions,cycles \
./test_ref --bench $(TEST_DATA)
```
然後發現 calculate.c 就是計算兩者 100 次平均時間的程式，編繹後執行得到 output.txt ，用 scripts/runtime.gp 畫成圖
cpy 版大約是 ref 版的 78% 。
接下來我們把 bloom filter 也加到 cpy 版中，這下子兩者的差異就只有 ==cpy 版把字串存在破碎的記憶體中，ref 版存在連續的記憶體中==
- cpy
1. 建立 bloom filter
2. 逐個把字串插入 tst
3. 為每一個字串 malloc 一塊空間
4. 更新 bloom filter
- ref
1. 建立 bloom filter
2. 先 malloc 一塊很大的 memory pool 。預設是 $2000000*256*sizeof(char)$
3. 逐個把字串的存進這個 memory pool 與 tst 中，然後在 tst 之中每個字串的最後一個節點會指向這個 memory pool 存該字串的位置。
4. 更新 bloom filter
再 `make test` 一次，然後 `./calculate` 、 `gnuplot scripts/runtime.gp` 。
相當接近，原本以為頻繁 malloc 的成本很高，以下有查了關於 memory pool 的資料。
- [wiki pedia](https://en.wikipedia.org/wiki/Memory_pool)
- [Pros and Cons](http://www.modernescpp.com/index.php/pros-and-cons-of-the-various-memory-management-strategies)
這裡面有提到 memory pool 要避免 memory fragment 的產生，memory fragment 會導致記憶體利用效率低落，試想假設今天我要 malloc(100) 而記憶體內現在所有的連續可用空間都小於 100 bytes ，這時候勢必得先 sbrk(100) 。
:::info
:question:
在 [wikipedia](https://en.wikipedia.org/wiki/Fragmentation_(computing)#Performance_degradation) 有提到 memory fragment 是會造成效能影響，讀取連續的記憶體會較快，但在我的實驗中看不出來，是因為尺度的關係?還是因為程式的這一堆 malloc 都接著做，所以看不出影響?
:::
---
## 後續改善
- ref 版本的 memory pool 大小應該要隨測資大小變動。
- tst 在找字串的時候，效能與其結構相關，我猜想與其**深度**有關，如果先對資料做某種排序，再建立起 tst ，使這個結構最淺，或許會對效能有改善。
Sign in with Wallet
Connect another wallet