# 2018q1 Homework2 (prefix-search)
contributed by < `BodomMoon` >
###### tags `BodomMoon` `prefix-search` `sysprog2018`

[github](https://github.com/bodommoon/prefix-search)、 [作業區](https://hackmd.io/s/BykAwRuKz#)、 [作業要求](https://hackmd.io/s/ByFWoR_tz#%E4%BD%9C%E6%A5%AD%E8%A6%81%E6%B1%82)

## 內容大綱
* 開發環境
* 思考何謂 benchmark
* 實作 benchmark
* 實作 memory pool in REF
* 效能測試及分析
* 研究小結環境

## 開發環境

Architecture:        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-4200M CPU @ 2.50GHz
製程：               3
CPU MHz：            2494.221
CPU max MHz:         3100.0000
CPU min MHz:         800.0000
BogoMIPS:            4988.44
虛擬：               VT-x
L1d 快取：           32K
L1i 快取：           32K
L2 快取：            256K
L3 快取：            3072K
NUMA node0 CPU(s):   0-3

## benchmark 思考
在一開始沒有理解 benchmark 定義時我參考了幾位同學的實作部份：
* bauuuu1021 [github](https://github.com/bauuuu1021/prefix-search)
* 固定的輸入測資
* 執行時會記憶體區塊錯誤
* 修正printf為fprintf
* 讀取 argv 參數比對是否進行 benchmark
>[color=red]想請問一下在什麼情況下會 segmentation fault QQ，可能是有我沒有考慮到的地方
>在想有可能是因為沒有先創一個 **result** 的資料夾來放輸出結果的 txt 檔（應該要寫在 `$make` 裡的抱歉QQ） [name=bauuuu1021]

>有可能喔？我是下載後直接輸入 make bench 然後就爆炸惹。然後你的 memory pool 那樣寫會有覆蓋的問題吧？

* ryanpatiency [github](https://github.com/ryanpatiency/prefix-search)
* ~~缺少 command.txt 根本沒辦法跑QQ~~
* 後來發現要跑一下 gen 就會生出來
* 然後這個同學的作法挺潮的，也很有研究價值
> 根據 ryanpatiency 同學表示在 makefile 中直接 test_cpy.c < command.txt 就可以取代 stdin

* afcidk [github](https://github.com/afcidk/prefix-search)
* 用程式產生固定的輸入測資
* 直接另外在 test_cpy.c 另外寫了一個函式來執行
* 讀取 argv 參數比對是否進行 benchmark

* YuanHaoHo [github](https://github.com/YuanHaoHo/prefix-search)
* 用程式產生固定的輸入測資
* 直接另外在 test_cpy.c 另外寫了一個函式來執行
* 讀取 argv 參數比對是否進行 benchmark
>以上皆為2018/03/31 的測試結果[name=BodomMoon]

但我覺得今天我們是要對 test_cpy.c 進行測試而直接去修改檔案本身取得測試資料的行為我總覺得怪怪的，先不說新增的 bench 相關程式碼會對程式造成多餘不必要的 bench-miss，要是對應到今天要測試的是執行檔而沒原始碼的情況下，這個方法也不適用。

先看看英文的 wikipedia怎樣定義 benchmark 這個行為

> In [computing](https://en.wikipedia.org/wiki/Computing "Computing"), a **benchmark** is the act of running a [computer program](https://en.wikipedia.org/wiki/Computer_program "Computer program"), a set of programs, or other operations, in order to assess the relative **performance** of an object,

如文中所敘提到， test_cpy.c 是我們要測量的「object」那直接用 test_cpy.c 去測試自己是否有點球員兼裁判的概念？

所以整理一下我認為的 benchmark 應該要有符合以下幾點

1. 能夠檢測功能完整性的測資
2. 在對於原始碼進行最小幅度修改的情況下進行
3. 應該為多次大量測試的平均統計

## 實作 benchmark
:::info
1.如何讓程式自動取得 test_cpy 的輸入出
:::
有鑑於在 test_cpy 中大部分的輸出是用 printf 來顯示，輸入是用 scanf 來讀取，為了在不修改程式碼的情況下進行測試我們必須重新導向 test_cpy 的輸入輸出，這時 freopen 可以滿足我們的需求

FILE *freopen(const char *pathname, const char *mode, FILE *stream);

有了這個功能之後我們就可以歸納出以下測試流程
1. MAKE 執行外部測試檔
2. 外部測試檔產生隨機測資 test.txt
3. 外部測試freopen 並將stdio->test.txt stdout->out.txt
4. 外部測試呼叫 test_cpy 進行測試
5. 返回外部測試檔 外部測試檔讀取output.txt 取出clock部份資料並整理為clock.txt
6. MAKE 執行 caculate 計算標準差並取出信賴區間

而在產生隨機測資時我遇到了另外一個問題：
:::info
2.如何對 UTF-8 編碼的文件進行操作
:::
[UTF-8](https://en.wikipedia.org/wiki/UTF-8) 是一種針對[ Unicode ](https://zh.wikipedia.org/wiki/Unicode)的可變長度[字元編碼](https://zh.wikipedia.org/wiki/%E5%AD%97%E5%85%83%E7%B7%A8%E7%A2%BC "字元編碼")，其長度從 1~4 個 byte 不等，故在切割時無法單純以 1 byte char 為單位切割，參考 [在C 程式中處理UTF-8 文字- ITW01](https://itw01.com/GQTGENJ.html) 提到可使用 glib 函式庫處理。

由於 glib 無法用 apt install 安裝，詳細安裝流程可參考 [glib源码安装使用方法- pcat - 博客园](https://www.cnblogs.com/pcat/p/5520317.html) 其中缺少的 [gettext]( https://www.gnu.org/software/gettext/) 可在偉大的 GNU 官網安裝，接著如下就可以自動裁切字串：

    do{
        clock_gettime(CLOCK_REALTIME, &ts);
        if((((int)ts.tv_nsec) >> 2) & 1) {
            strLenth = (((int)ts.tv_nsec) & 6) + 1;
            strLenth = MYMIN(strLenth,(int)g_utf8_strlen(line,-1));
            *(g_utf8_offset_to_pointer (line,(long) strLenth)) = '\0';
            fprintf(output, "s\n");
            fprintf(output, "%s\n", line);
        }
    } while(fscanf(cities, "%s", line) != EOF);

使用 glib 提供的 g_utf8_offset_to_pointer 以及 g_utf8_strlen 就能針對 UTF-8 的文字做字元操作，配合針對 tv_nsec 做位移達到的亂數效果隨機從 cities.txt 擷取長度為 1,3,5,7 的字串作為輸入測試。

>使用此隨機測資也成功找出了在 test_cpy 以及 test_ref 中 LMAX 長度不足的問題，一旦使用者輸入 s A 或是 s B 就會造成陣列位置的 overflow 導致記憶體區塊錯誤無法運行，其他使用固定測資的同學似乎還沒有人發現過這個基本的功能問題。[name=BodomMoon]

測試得出結果如圖
放大一點來看

原本我拿所有測試所得的數據來算帕松分佈的95％信賴區間，但其實看圖就知道這一整個分佈根本不符合帕松，所以想當然的算不出合理的數字。應該要擷取分佈時間在 20~3000 nano second 左右的數據來計算才會比較符合帕松分佈

:::info
未完待續：補完信賴區間的計算
:::

## 實作 memory pool in REF

有鑑於如果 ref 版本只是改為把 malloc 從 tst.c 拔到 test_ref.c 內我覺得太沒勁了，而且跟原版也沒多大區別。所以試著時做了人生中第一個 memory pool 並且參考以下幾位同學並且揚長避短對程式碼做出更好的優化

* bauuuu1021 [github](https://github.com/bauuuu1021/prefix-search)
* 直接對 struct point malloc 一個極大的值，並當作 pool 的空間，卻沒有做類似 initial array 的行為，會有運行錯誤覆蓋指標的問題(實際上也真的沒辦法執行)
* 每次 memAlloc 固定長度的空間給 fscanf 塞，不但造成固定長度的浪費並且不一定會用到(insert 重複的字串時並不會用到該空間)

* tina0405 [hackmd](https://hackmd.io/s/SkEFpwh2-#)
* 正確的先 malloc 一個 pool 出來之後再 calloc 一個極大的值並且將 curren 指過去。但 malloc 的值也是一個極大的區域，這並沒有必要。
* 每次 memAlloc 等同 strlen 的長度(其實這樣會錯誤...因為後面要補 0，所以應該要 strlen+1 的)
* 並沒有 memcpy 讀取到的字串進 memAlloc 的空間李
* 將 ref 中的資料集降低到了 3000
* 這位同學的程式碼編譯根本不會過阿？(喵喵喵？)

>[rex662624](
https://hackmd.io/K4v3wF-8SFudCT2-ckK9Hg?both#) 同學的共筆中也提出了相同的疑問，你的疑點都是對的，的確這是一份不完整的程式碼。
[name=BodomMoon]

如果對一個 struct point m/calloc 空間後，所指向的空間就是 struct 中第一個物件的位置，如果又讓 `current = ptr`，所取得的記憶體位置就會變成這樣：
接著如果塞東西到 current 指向的地方就會變成
然後就全部亂套了，所以為了解決這個問題我們應該要把 current 指向的位置改為 `ptr->current = (char*)ptr + sizeof(pool)`
這樣後續塞東西時就可以放成
但其實邏輯上更完整的作法應該還是先 malloc 一個空間給 struct pointer 本身存放指標再指向 malloc 整個 pool 的大小是比較合理的
> 可是這樣最後在 free 空間時會無法釋放 current 去 malloc 到的空間，所以最後我又改回前面 initial 的寫法了。[詳細實驗請見](https://www.facebook.com/groups/system.software2018/permalink/387876431678525/)[name=BodomMoon]

所以總結以上的過程(感謝[FB各位的協助指教](https://www.facebook.com/groups/system.software2018/permalink/387481195051382/?comment_id=387549355044566&reply_comment_id=387697538363081&notif_id=1523168052308083&notif_t=group_comment&ref=notif))
得出以下程式碼

#include "ref.h"
typedef struct memory_pool {
    char *current;
    char *tail;
}pool;

pool *init (size_t size){
    /*pool *ptr = (pool*)calloc( 1 , sizeof(pool));
    ptr->current =(char*) malloc(size);
    ptr->tail = ptr->current + size;
    因為 free 的問題修正回 initial array 形式的版本*/
    pool *ptr = (pool*)calloc( 1 , size);
    ptr->current = (char*)ptr + sizeof(pool);
    ptr->tail =(char*) ptr + size;
    return ptr;
}

//其實這裡不用用到 pointer to pointer 
char *mpalloc(pool **ptr , size_t size) {
    ptr->current);
    if(((*ptr) -> tail - (*ptr) -> current) > size){
    	char *temp = (*ptr)->current;
    	(*ptr)->current += size;
    	return temp;
    }
    else
	return NULL;
}

pool *mpfreeback(pool **ptr , size_t size) {
    (*ptr)->current -= size;
    memset((*ptr)->current,0,size);
    return (*ptr);
}

void pool_free(pool *p) {
    free(p);
}

int getLarge( pool *ptr){
    return (int)(ptr->tail - ptr ->current);
}//pool remain 124976 size

其實如果把 word 本身 cpy 進 tst.c 確定並非重複字串再 mpalloc 可以省下更多重複的步驟(不用把重複配置的空間 mpfreeback 回去)，但為了保持封裝的完整性故還是分開來寫了。

## 效能測試及分析
首先執行 `make build-cache-test`
(將一個內部只有一堆 q 的檔案當作 stdin 輸入，只測試建立 tree 所需時間)
>p.s:隱藏掉程式輸出在 Makefile 中用 > 將 stdout 重定向到 NULL 即可[name=BodomMoon]

test_cpy：

echo 3 | sudo tee /proc/sys/vm/drop_caches
3
perf stat --repeat 5 \
	-e cache-misses,cache-references,instructions,cycles \
	./test_cpy<test2.txt>-

 Performance counter stats for './test_cpy' (5 runs):

         1,113,531      cache-misses              #   49.015 % of all cache refs      ( +-  0.74% )
         2,271,805      cache-references                                              ( +-  1.13% )
       548,823,125      instructions              #    1.14  insn per cycle           ( +-  0.10% )
       481,906,100      cycles                                                        ( +-  3.10% )

       0.178614806 seconds time elapsed                                          ( +- 12.55% )

test_ref：

echo 3 | sudo tee /proc/sys/vm/drop_caches
3
perf stat --repeat 5 \
	-e cache-misses,cache-references,instructions,cycles \
	./test_ref<test2.txt>-

 Performance counter stats for './test_ref' (5 runs):

         1,056,737      cache-misses              #   46.752 % of all cache refs      ( +-  0.76% )
         2,260,280      cache-references                                              ( +-  0.85% )
       573,642,318      instructions              #    1.16  insn per cycle           ( +-  0.05% )
       492,858,973      cycles                                                        ( +-  1.71% )

       0.176708435 seconds time elapsed                                          ( +-  8.26% )

可以看到雖然 ref 的版本在建立樹上稍微快了一點點，但我覺得完全不能接受，難道我寫了半天的 memory pool 只為了降低 3% 的 cache-miss 嗎？ 難道 memory pool 的功能就只有這樣嗎？

不對，是因為我們沒有把 memory pool 用好用滿！在程式中花了最多記憶體的部份並不是在存放字串的部份，而是建樹的部份。但建樹的部份我們卻都是用 calloc 在執行，而 memory pool 當然能優化這一方面的功能！

if(!cpy){
    if (!(*pcurr =(void*)mpalloc(&ptr, sizeof **pcurr))){
        puts("calloc fail");
        fprintf(stderr, "error: tst_insert(), memory exhausted.\n");
        return NULL;
        }
    }

改完看看結果

echo 3 | sudo tee /proc/sys/vm/drop_caches
3
perf stat --repeat 5 \
	-e cache-misses,cache-references,instructions,cycles \
	./test_ref<test2.txt>-

 Performance counter stats for './test_ref' (5 runs):

           312,439      cache-misses              #   25.010 % of all cache refs      ( +-  2.84% )
         1,249,257      cache-references                                              ( +-  1.87% )
       365,956,502      instructions              #    1.05  insn per cycle           ( +-  0.22% )
       348,319,472      cycles                                                        ( +-  1.12% )

       0.135982024 seconds time elapsed                                          ( +- 15.08% )

建立樹時的 cache-miss 降低了足足有 24％ 少了將近一半，執行速度也快了30％

memory pool 同時還可以增加 search 在查訪節點時的記憶體區域性，增加 cache hit 的機率。在此測試搜尋 120000 筆從 cities.txt 取出的隨機資料：
test_cpy

echo 3 | sudo tee /proc/sys/vm/drop_caches
3
perf stat --repeat 1 \
	-e cache-misses,cache-references,instructions,cycles \
	./test_cpy<test.txt>-

 Performance counter stats for './test_cpy':

        24,625,343      cache-misses              #   34.417 % of all cache refs    
        71,549,933      cache-references                                            
     6,347,964,240      instructions              #    1.09  insn per cycle         
     5,802,380,974      cycles                                                      

       1.987216783 seconds time elapsed

test_ref

echo 3 | sudo tee /proc/sys/vm/drop_caches
3
perf stat --repeat 1 \
	-e cache-misses,cache-references,instructions,cycles \
	./test_ref<test.txt>-

 Performance counter stats for './test_ref':

        16,643,871      cache-misses              #   27.999 % of all cache refs    
        59,443,932      cache-references                                            
     6,163,164,738      instructions              #    1.25  insn per cycle         
     4,942,556,393      cycles                                                      

       1.716825268 seconds time elapsed

cache-miss 也下降到 27%

比較整體搜尋單筆資料的平均時間
**CPY avg = 9685 nanosecond**
**REF avg = 8439 nanosecond**
>平均搜尋時間計算輸出在 avg.txt

接著輸出成圖形看看差距
讓我們放大一點觀察
可以看見 ref 所花的時間曲線更偏左(更少)，分佈更加密集。

## 研究小結
在以上紀錄中我實作並改善了以下幾點：
1. 針對 benchmark 的基準測試並且修復搜尋溢位的錯誤。
2. 新增了 plot,run-cache-test,build-cache-test 等針對不同功能自動測試並生成效能評估數據的指令。
3. 實作 ref 版本並引入 memory pool 改善在搜尋以及新增上的效能表現超過30％。
4. 學習針對非 ASCII 字元進行操作並且使用第三方函式庫

:::info
未完待續：
1. 將之前 [phonebook](https://hackmd.io/1-xapZMWTAm3Y82wCZA9Gw#) 的基礎工作引入，結合霍夫曼編碼的實作增進效能及空間使用率。
2. 研究程式碼的 `tst_traverse_fn` 函式，並思考如何運用這個實作。
3. 利用帕松分布來觀察並取出95％信賴區間，以機率分佈函數來解釋，提出改善猜測精準度的方案。

**exrta 目標: 研究並實作 balanced Ternary Search Tree**
:::
> 希望我有生之年能補完以上實作？
[name=BodomMoon]

## 參考連結

[1]bauuuu1021 [github](https://github.com/bauuuu1021/prefix-search)
[2]ryanpatiency [github](https://github.com/ryanpatiency/prefix-search)
[3]afcidk [github](https://github.com/afcidk/prefix-search)
[4]YuanHaoHo [github](https://github.com/YuanHaoHo/prefix-search)
[5][UTF-8](https://en.wikipedia.org/wiki/UTF-8)
[6][在C 程式中處理UTF-8 文字- ITW01](https://itw01.com/GQTGENJ.html)
[7][glib源码安装使用方法- pcat - 博客园](https://www.cnblogs.com/pcat/p/5520317.html)
[8]tina0405 [hackmd](https://hackmd.io/s/SkEFpwh2-#)