2018q3 Homework3 (dict)

tags: GOGOGOGOGOGOG

作業目標

• 在 GitHub 上 fork dict，研讀並修改 Makefile 以允許 $ make plot 時，視覺化 ternary search tree + bloom filter 的效能表現。注意，需要設計實驗，允許不同的字串輸入並探討 TST 回應的統計分佈
  • 要考慮到 prefix search 的特性還有詞彙的涵蓋率
  • 限用 gnuplot 來製圖
  • 參閱 Hash Table Benchmarks
• 以 perf 分析 TST 程式碼的執行時期行為並且充分解讀
• 考慮到 CPY 和 REF 這兩種實作機制，思考效能落差的緣故，並且提出後續效能改善機制
  • 充分量化並以現代處理器架構的行為解讀
  • 注意：這兩者都該加入 Bloom filter，而且分析具體效益 (原有程式存在若干缺陷，也該指出並修正)

事前準備

• 首先先將perf進行安裝，輸入sudo apt-get install linux-tools-common 系統便會開始自行安裝，但要注意的點是安裝的檔案版本不同的問題，老師所給的指令$ sudo apt-get install linux-tools-3.16.0-50-generic linux-cloud-tools-3.16.0-50-generic 其版本不一定適用於每個人，需要根據提示字元進行安裝。
• 由於這次需要自行設定makefile所以需要開啟權限，透過指令sudo sh -c " echo -1 >/proc/sys/kernel/perf_event_paranoid" 來開啟權限。
• 可以參考這篇 https://hackmd.io/s/Skwp-alOg# 非常詳盡的解說了gnuplot的使用，但這次作業scripts已經都寫好了，需要更改的部份不多。
• 關於如何編譯Makefile: https://hackmd.io/c/rJKbX1pFZ/https%3A%2F%2Fhackmd.io%2Fs%2FSySTMXPv

了解Trie和Ternary search tree (TST)

Trie

Trie ，又叫做前綴樹或是字典樹，是一個動態配置或關聯性配置的資料結構，用來保存關聯數組，常用在 string。 而當運用在 string 時， Trie 中每個節點由一個字元組成。

• Trie樹的基本性質可以歸納為：

  • 根節點不包含字元，除了根節點外的每個節點只包含一個字元。
  • 從根節點到某一個節點，路徑上經過的字符連接起來，為該節點對應的字符串。
  • 每個節點的所有子節點都有相同的前綴字串。
  • 不是所有的節點都有對應的值，只有葉子節點和部分內部節點所對應的 key 才有相關的值。

• Trie 的應用： 主要在 bioinformatics ， information retrieval

Ternary Search Tree (TST) 介紹

Trie 樹的結構，它的實現簡單但空間效率低。如果要支持26個英文字母，每個節點就要保存26個指針，假如還要加入標點符號、區分大小寫，內存用量就會急劇上升，以至於不可行。

因為 trie 的節點數組中保存的空指針，佔用了太多內存，因此考慮改用其他數據結構去代替，像是用 hash map。但是管理成千上萬個 hash map 不是什麼好主意，而且它還會使數據的相對順序信息丟失，所以使用 Ternary Tree 替代 trie。

• Binary Search Tree 查詢與建表時間是 O(log2n)，但是在最糟的情況下時間複雜度可能轉為 O(n)，除了要儲存的字串外不須另外分配空間。

• Trie 的時間複雜度是 O(n)，能夠實現前者難以做到的 prefix-search，缺點是會有大量的空指針表，造成空間開銷過大。

• Ternary Search Tree，是一種 trie（亦稱 prefix-tree) 的結構，並且它結合字典樹的時間效率和 BST 的空間效率優點。

  • 每個節點 (Node) 最多有三個子分支，以及一個 Key
  • Key 用來記錄 Keys 中的其中一個字元 (包括 EndOfString)。
  • low ：用來指向比當前的 Node 的 Key 小 的 Node。
  • equal ：用來指向與當前的 Node 的 Key 一樣大 的 Node。
  • high ：用來指向比當前的 Node 的 Key 大 的 Node。

• Ternary Search Tree 的應用:

  • spell check: Ternary Search Tree 可以當作字典來存儲所有的單詞。一旦在編輯器中輸入單詞，可以在Ternary Search Tree中並行搜索單詞以檢查正確的拼寫。
  • Auto-completion: 使用搜索引擎進行搜索時，它會提供自動完成（Auto-complete）功能，讓用戶更加容易查找到相關的信息；假如：我們在Google中輸入ternar，它會提示與ternar的相關搜索信息。
    
    
    Google根據我們的輸入ternar，提示了ternary，ternary search tree等等搜索信息，自動完成（Auto-complete）功能的實現的核心思想三叉搜索樹。
    對於Web應用程序來說，自動完成（Auto-complete）的繁重處理工作絕大部分要交給服務器去完成。很多時候，自動完成（Auto-complete）的備選項數目巨大，不適宜一下子全都下載到客戶端。相反，三叉樹搜索是保存在服務器上的，客戶端把用戶已經輸入的單詞前綴送到服務器上作查詢，然後服務器根據三叉搜索樹算法獲取相應數據列表，最後把候選的數據列表返回給客戶端。
    

reference: [Ternary Search Tree 的應用]
(http://www.cnblogs.com/rush/archive/2012/12/30/2839996.html)

TST的實作程式碼：

首先一樣的fork本次的作業，並且進行git clone https://github.com/GOGOGOGOGOGOG/dict.git 但要注意的點是本次作業除了要git init 以外，需要先安裝pref等等套件才可以執行。

• 了解Makefile：

TESTS = test_cpy test_ref

TEST_DATA = s Calva

CFLAGS = -O0 -Wall -Werror -g

...
test:  $(TESTS)
	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)
				

 bench: $(TESTS)
	@for test in $(TESTS); do\
		./$$test --bench $(TEST_DATA); \
	done
 output.txt: test calculate
	./calculate

plot: output.txt bench_cpy.txt bench_ref.txt
	gnuplot scripts/runtime.gp
	eog runtime.png
	gnuplot scripts/runtime3.gp
	eog runtime3.png
	gnuplot scripts/runtimept.gp
	eog runtime2.png 
			

calculate: calculate.c
	$(CC) $(CFLAGS_common) $^ -o $@

 
clean:
	$(RM) $(TESTS) $(OBJS)
	$(RM) $(deps)
	rm -f  bench_cpy.txt bench_ref.txt ref.txt cpy.txt output.txt caculate

-include $(deps)

前半部份為：

• TESTS 是進行test_cpy和test_ref的程式碼，也就是進行make後的所產生的執行碼。
• TEST_DATA 測試的字串，原本為 Tai 但未來滿足作業需求進行實驗，我改成了Calva，下面會解釋實驗流程。
• CFLAGS 代表 GCC 編譯時用的參數。
• 後半部份的TEST 輸入 make test 會使用 pref 去測試 test_cpy 和 test_ref 總共會測試100次。
• make bench 則會對兩個執行檔 test_cpy 和 test_ref 進行檢測。
• make clean 會對執行檔和txt檔進行清除。

make plot的執行與建構：

• 在著手進行make plot 之前我們必須先整理清楚各個GNU的.gp檔所需要的內容是什麼，例如：runtime.gp 是需要output.txt 而 runtime3.gp 則是需要test_cpy.txt 等等…
  （ 關於如何生成bench_cpy.txt bench_ref.txt ref.txt cpy.txt output.txt 我會在後面的bug標題進行說明。）

plot

plot: output.txt bench_cpy.txt bench_ref.txt
	gnuplot scripts/runtime.gp
	eog runtime.png
	gnuplot scripts/runtime3.gp
	eog runtime3.png
	gnuplot scripts/runtimept.gp
	eog runtime2.png 
			

在第一行中代表的是輸入plot指令後需要的檔案，分別為bench_cpy.txt bench_ref.txt 和 output.txt 而指令 gnuplot scripts/runtime.gp 則是執行gnuplot該gp檔的程序，eog runtime.png 則是顯示圖形。執行畫面如下：
首先鍵入指令make plot 後，輸入完密碼開始進行檢測並紀錄執行時間。

執行完成後會產生三張圖形：分別是cpy和ref的執行時間比;cpy的搜尋效率;ref和cpy的搜尋效率對照，如圖：

字串實驗的實現與紀錄

本次作業的要求：
視覺化 ternary search tree + bloom filter 的效能表現。注意，需要設計實驗，允許不同的字串輸入並探討 TST 回應的統計分佈。於是我做了以下實驗，其得到的結果是：ref的執行效率低於cpy並且會隨著輸入字串的增加越來越明顯，如同我上述所提到的我將測試的字串改為Calva 但其實我一開始是從字串C 開始進行實驗然後再逐一增加字串數量，例如增加為Ca 等等…測試的結果如下

增加為Ca

增加為Cal

增加為Calv

增加為Calva

可以發現雙方的執行時間從0.38秒的差距拉開到0.47秒，可知ref和cpy的效率的確是差了一些。

探討造成此現象可能的原因？

10/15 將runtime.gp作修改：

reset                                                                           
set ylabel 'time(sec)'
set style fill solid
set key center top 
set title 'perfomance comparison'
set term png enhanced font 'Verdana,10'
set output 'runtime.png'

plot [:][y=0:5.000]'output.txt' using 2:xtic(1) with histogram title 'cpy', \
'' using 3:xtic(1) with histogram title 'ref' , \
'' using ($0-0.500):(0.110):2 with labels title ' ' textcolor lt 1, \
'' using ($0-0.500):(0.320):3 with labels title ' ' textcolor lt 2,

Bug的問題與解決：

首先比較容易發現的bug在test_cpy.c和test_ref.c之間的差異，執行完程式碼後會發現無法生成ref的文字檔，其原因是在於test_ref.c中程式碼少了輸出txt檔的程式碼：如下：

if (argc == 2 && strcmp(argv[1], "--bench1") == 0) {
        int stat = bench_test(root, BENCH_TEST_FILE, LMAX);
        tst_free_all(root);
        return stat;
    }

    FILE *output;
    output = fopen("ref.txt", "a");
    if (output != NULL) {
        fprintf(output, "%.6f\n", t2 - t1);
        fclose(output);
    } else
        printf("open file error\n");

將此程式碼輸入後即可產生bench_ref.txt 除此之外也要記得執行calculate.c檔來產生output.txt
不過最讓我好奇的還是：

尋找 search "A" 發生 Segfault 的原因

如圖：

會發現在輸入A後會出現segfault的狀況，後來發現其問題是出在 tst.c檔中：

void tst_suggest(const tst_node *p, 
                 const char c,
                 const size_t nchr,
                 char **a,
                 int *n, 
                 const int max)
{
    if (!p || *n == max)
       return;
    tst_suggest(p->lokid, c, nchr, a, n, max);
    if (p->key)
        tst_suggest(p->eqkid, c, nchr, a, n, max);
    else if (*(((char *) p->eqkid) + nchr - 1) == c)
        a[(*n)++] = (char *) p->eqkid;
    tst_suggest(p->hikid, c, nchr, a, n, max);
}

參考了：（https://hackmd.io/nLSb34t0SE2V-56Gxi7ErA?both# ）之後才發現原來是因為，*n不斷的滿足條件進入遞迴（return）當進行到330行時，程式早已經不符合原來的設定了，*n的持續增加會造成存取到不正確的記憶體。需要將程式修改成：

else if (*(((char *) p->eqkid) + nchr - 1) == c && *n != max)

即可修復這個bug。

10/16 新增關於輸入功能cpy和ref之間的效率比較

• 修改runtimebox裡的gp內容，如下：

reset
set xlabel 'test'
set ylabel 'time(microsec)'
set title 'perfomance comparison(add)'
set term png enhanced font 'Verdana,10'
set output 'addruntime.png'
set format x "%10.0f"
set xtic 10
set xtics rotate by 45 right

plot [:300][:]'cpy.txt'  title 'cpy_ add',\
'ref.txt'  title 'ref_ add'

• 圖形顯示
  
  

可以看到cpy和ref在輸入功能中仍舊是cpy的速度較快，其中原因我想也來自於cpy和ref存取的方式不同，前者是用TST不過後者是用bloom filter，但關於本次作業要求要兩個都加入bloom filter還是不懂。
10/17更新： ref還使用了bloom filter去搜尋字串所以可能是因為這樣，在時間上才會高於cpy。

關於coredumped的問題

時間不夠待補上 對ref進行perf分析時，會導致coredumped，如圖：

為什麼執行perf會導致test_ref coredumped呢？是不是內部還有bug？待用gdb去做檢測。

Linux perf效能分析

10/19更新：
在test_cpy新增bloom_filter進行測試：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "bloom.h"
#include "bench.c"
#include "tst.h"
/** constants insert, delete, max word(s) & stack nodes */
enum { INS, DEL, WRDMAX = 256, STKMAX = 512, LMAX = 1024 };
#define REF INS
#define CPY DEL
long poolsize = 2000000 * WRDMAX;
#define BENCH_TEST_FILE "bench_cpy.txt"
#define TableSize 5000000
/* simple trim '\n' from end of buffer filled by fgets */
static void rmcrlf(char *s)
{
    size_t len = strlen(s);
    if (len && s[len - 1] == '\n')
        s[--len] = 0;
}

#define IN_FILE "cities.txt"

int main(int argc, char **argv)
{
    char word[WRDMAX] = "";
    char *sgl[LMAX] = {NULL};
    tst_node *root = NULL, *res = NULL;
    int rtn = 0, idx = 0, sidx = 0;
    FILE *fp = fopen(IN_FILE, "r");
    double t1, t2;

    if (!fp) { /* prompt, open, validate file for reading */
        fprintf(stderr, "error: file open failed '%s'.\n", argv[1]);
        return 1;
    }
    t1 = tvgetf();

    bloom_t bloom = bloom_create(TableSize);

    /* memory pool */
    char *pool = (char *) malloc(poolsize * sizeof(char));
    char *Top = pool;
    while ((rtn = fscanf(fp, "%s", Top)) != EOF) {
        char *p = Top;
        /* insert reference to each string */
        if (!tst_ins_del(&root, &p, INS, REF)) { /* fail to insert */
            fprintf(stderr, "error: memory exhausted, tst_insert.\n");
            fclose(fp);
            return 1;
        } else { /* update bloom filter */
            bloom_add(bloom, Top);
        }
        idx++;
        Top += (strlen(Top) + 1);
        // break;
    }
    t2 = tvgetf();
    fclose(fp);
    printf("ternary_tree, loaded %d words in %.6f sec\n", idx, t2 - t1);

後來經過討論後，發現原來 test_ref是代表tst加上bloom_filter，而test_cpy則是只有tst而已，而在之前的圖形中，之所以ref需要的時間會比cpy還的長的原因是因為bloom_filter需要建立還有更新的時間，再兩者都加入bloom_filter後所產生的搜尋圖形和新增圖形之比較如下：

由上圖可知，兩者所需的時間是差不多的。

提問：

上面的圖形是關於新增功能的比較，但不太清楚過程中的波動是因為什麼原因造成的？