# 2017q3 Homework2 (prefix-search)
contributed by <`tina0405`>

### Reviewed by `ZixinYang`
- 對於程式碼的細節觀察說明得十分完整, 也詳細地記錄了修改程式碼的過程, 對共筆的用心值得學習。
- 實驗以 PDF 的分布曲線來呈現, 結果發現 CPY 的方法不是呈現常態分布, 但較接近柏松分布, 如果作者可以更深入說明這個現象, 也就是 CPY 呈現這個意料之外的結果的原因會更好。
- 還有幾項作業要求尚未完成, 可以再繼續新增內容。
>> 我有將後半段的　poisson 分析補上了，謝謝你。
>> [name=tina0405]
### 開發環境
~~~
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 58
Model name: Intel(R) Core(TM) i5-3230M CPU @ 2.60GHz
Stepping: 9
CPU MHz: 1199.865
CPU max MHz: 3200.0000
CPU min MHz: 1200.0000
BogoMIPS: 5188.68
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 3072K
NUMA node0 CPU(s): 0-3
~~~
### 理解及更改 FIXME 程式碼
* 因為 enum 遞增，所以這邊 INS 和 REF 為 0 ， CPY 和 DEL 為 1
~~~c=
enum { INS, DEL, WRDMAX = 256, STKMAX = 512, LMAX = 1024 };
#define REF INS
#define CPY DEL
~~~
* 在 test_ref.c 裡遇到的第一個 FIXME ，所以先看 tst_ins_del
~~~ c=
while ((rtn = fscanf(fp, "%s", word)) != EOF) {
char *p = word;
/* FIXME: insert reference to each string */
if (!tst_ins_del(&root, &p, INS, CPY)) {
fprintf(stderr, "error: memory exhausted, tst_insert.\n");
fclose(fp);
return 1;
}
idx++;
}
~~~
* 有4個參數 void *tst_ins_del(tst_node **root, char *const *s, const int del, const int cpy)
* 註解上說 ： if 'del' is non-zero deletes 's' from tree
* 所以在 insert 建樹的時候，我們就令 del=0
* 註解上說 ： 'cpy' is non-zero allocate storage for 's', otherwise save pointer to 's'.
* 存入 pointer to 's'
>> 這邊先改變 cpy 的值為 1 ，去探討 allocate storage 和 save pointer 的差別
>>
* 更改 FIXME 的地方 tst_ins_del(&root, &p, INS, REF) 變成 tst_ins_del(&root, &p, INS, REF)
* RUN 完因為結果錯誤，繼續往下看：
~~~
choice: s
find words matching prefix (at least 1 char): Tain
Tain - searched prefix in 0.000009 sec

suggest[0] : Tain
suggest[1] : Tain
suggest[2] : Tain
suggest[3] : Tain
suggest[4] : Tain
suggest[5] : Tain
suggest[6] : Tain
suggest[7] : Tain
suggest[8] : Tain
suggest[9] : Tain
suggest[10] : Tain
suggest[11] : Tain
~~~

* 在 for 裡沒放東西，就是判斷式為 true 一直做迴圈
~~~c=
for (;;)
for (;true;)
~~~
* 裡面的 cpy 只有在 for (;;) 裡出現，
~~~c=
/* Place nodes until end of the string, at end of stign allocate
* space for data, copy data as final eqkid, and return.
*/
if (*p++ == 0) {
if (cpy) { /* allocate storage for 's' */
const char *eqdata = strdup(*s);
if (!eqdata)
return NULL;
curr->eqkid = (tst_node *) eqdata;
return (void *) eqdata;
} else { /* save pointer to 's' (allocated elsewhere) */
curr->eqkid = (tst_node *) *s;
return (void *) *s;
}
}
~~~
>>當 cpy 為 0，先看到 pointer to s 並沒有分配空間，這樣 curr->eqkid 就會直接存 *s
* 發現 line11 有句註解 save pointer to 's' (allocated elsewhere)
* 先分配記憶體空間給他 ref，就可執行，可是這樣就跟 cpy 版一樣了
~~~ c=
if (*p++ == 0) {
const char *eqdata = strdup(*s);
if (cpy) { /* allocate storage for 's' */
if (!eqdata)
return NULL;
curr->eqkid = (tst_node *) eqdata;
return (void *) eqdata;
} else { /* save pointer to 's' (allocated elsewhere) */
curr->eqkid = (tst_node *) eqdata;
return (void *) eqdata;
}
}
~~~
* 發現 line11 有句註解 save pointer to 's' (allocated elsewhere)
* 所以就想說為了修復它，又可以保有 save pointer to 's'，就回傳不一樣的空間就不會重複了
~~~c=
char word2[9400][WRDMAX];
while ((rtn = fscanf(fp, "%s", word2[q])) != EOF) {
char *p = word2[q];
q++;
/* FIXME: insert reference to each string */
if (!tst_ins_del(&root, &p, INS, REF)) {
fprintf(stderr, "error: memory exhausted, tst_insert.\n");
fclose(fp);
return 1;
}
idx++;
}
~~~
* 我這邊利用 Array ，並將資料量減少到 3000 看一下正確性:
* 如此一來 word 就不會重複蓋到
~~~
choice: s
find words matching prefix (at least 1 char): In
In - searched prefix in 0.000055 sec

suggest[0] : Incheon,
suggest[1] : Indaiatuba,
suggest[2] : India
suggest[3] : Indiana,
suggest[4] : Indianapolis,
suggest[5] : Indonesia
suggest[6] : Indore,
suggest[7] : Inegeul,
suggest[8] : Ingrāj
suggest[9] : Inisa,
~~~
### 二維矩陣
* 然後測試 ，run 100次 的 cache-miss ，這邊只討論 search， 搜尋的關鍵字是 In
~~~
Performance counter stats for './test_cpy' (100 runs):

2,0842 cache-misses # 39.412 % of all cache refs ( +- 2.44% )
5,2882 cache-references ( +- 0.81% )
1578,7836 instructions # 1.35 insn per cycle ( +- 0.03% )
1169,6138 cycles ( +- 0.41% )

erformance counter stats for './test_ref' (100 runs):

5,7303 cache-misses # 60.791 % of all cache refs ( +- 0.92% )
9,4262 cache-references ( +- 0.78% )
1583,7161 instructions # 1.23 insn per cycle ( +- 0.26% )
1282,9531 cycles ( +- 0.62% )
~~~
* 看來使用動態記憶體分配的 cache-miss 比較少
* 使用 strdup 會先 malloc 一塊記憶體 ， 所以我稱它為動態記憶體分配的版本
~~~c
tina@tina-X550VB:~/Hw/prefix-search$ man strdup
char *strdup(const char *s);
DESCRIPTION
The strdup() function returns a pointer to a new string which is a
duplicate of the string s. Memory for the new string is obtained with
malloc(3), and can be freed with free(3).
~~~
* 然而雖然 array 是連續的記憶體空間，可是每次儲存 word 到三元搜尋樹的最後一筆 ， 再搜尋的時候仍然不是連續的，而且因為還有多給的空間，是浪費的，這樣還不如要用的時候再分配
~~~
o
|-c
|-0
------------+------------
|lokid |eqkid |hikid
o o o
|-a
|-0
----+----
| | | note: any of the lokid or hikid nodes
o can also have pointers to nodes
|-t for words that "cat" or "ca" is
|-0 a partial prefix to.
----+----
| | |
o
|-0
|-1 <== the refcnt is only relevant to the final node
----+----
| | |
NULL o NULL
"cat"
~~~
* 調整回
~~~c=
while ((rtn = fscanf(fp, "%s", word)) != EOF) {
char *p = strdup(word);
/* FIXME: insert reference to each string */
if (!tst_ins_del(&root, &p, INS, REF)) {
fprintf(stderr, "error: memory exhausted, tst_insert.\n");
fclose(fp);
return 1;
}
idx++;
}
~~~

### make bench 時，可對 ternary search tree 的實作做出效能評比，涵蓋建立 tst 和 prefix

- [ ]測試程式碼應該接受 --bench 的執行參數，得以在沒有使用者輸入的前題下，對 tst 程式碼進行效能分析，應涵蓋 cpy 和 ref 兩種途徑 (詳情參閱 tst.h 的程式碼註解)

- [ ]GNU Make 的技巧
* 參考 [Makefile header 檔的相依性檢查](https://yodalee.blogspot.tw/2017/04/makefile-header.html)
* 參考 [Makefile 語法和示範](https://hackmd.io/s/SySTMXPvl#)
* 參考 [Automatic-Prerequisites](https://www.gnu.org/software/make/manual/html_node/Automatic-Prerequisites.html)

* it must remake main.o whenever defs.h changes.
~~~
main.o: defs
~~~
* 使用 -M 後，也就是只要 main.c 和 defs.h 改變，就要重新 make main.o
~~~
cc -M main.c 會轉變成 main.o : main.c defs.h
~~~

* 使用 -MM ，不想要產生 dependency 包含 system library 的 header
~~~
-MM
Like -M but do not mention header files that are found in system header directories
~~~
---

* 在還沒寫測試檔前想要跑 100 次，輸入是一個問題，所以我參考 [argc 和 argv](http://crasseux.com/books/ctutorial/argc-and-argv.html)
~~~=
//這邊的相依檔是 test_cpy test_ref
bench: $(TESTS)
perf stat --repeat 100 \
-e cache-misses,cache-references,instructions,cycles \
./test_cpy --bench s In
perf stat --repeat 100 \
-e cache-misses,cache-references,instructions,cycles \
./test_ref --bench s In
~~~

* 這邊我再將程式內限制，一定要收到 4 個參數，才會啟動 b_flag 參數輸入，不然一律都手動輸入
~~~c=
if ((argc == 4) && !strcmp("--bench", argv[1])
b_flag = 1;
~~~
:::danger
為什麼 argc 要等於 4 的時候才允許 `--bench` 參數實際發揮作用呢？
:notes: jserv
:::

>>一開始因為想要確保有在 Makefile 裡輸入 choice 和想搜尋的資料，但我突然想到 case q 不用輸入城市
>> [name=tina0405]

> 適度分析程式碼行為，並從「歸納」過的表現去闡述 argc/argv 的設計考量。以這個案例來說，不管 `--bench` 後面有多少參數，都沒有處理的必要
> [name="jserv"][color=red]
* 解釋：
* argc stands for "argument count" （個數）
* The name of the variable argv stands for "argument vector" ，A vector is a one-dimensional array

vector 因為是一個一維陣列所以上面的例子來說：
| ./test_ref | --bench | s |In|
| :--------: | :--------: | :--------: | :--------: |
| argv[0] | argv[1] | argv[2] | argv[3]|

* 參考了以上意見後，我覺得新的方向應該是如同作業要求去分析 prefix search ，而不是著墨於參數的限制
* 所以將 tst_search_prefix 獨立出來學習 clz 去分析它的 cycle 數
* 因為希望有別於我之前將參數寫死在 Makefile 的情況， 我利用 cities.txt 已有程式來搜尋 ， 但可以控制搜尋字的長度 ：
~~~c=
#define PREFIX_SIZE 3
char search_word[PREFIX_SIZE] = "";

while (fscanf(in, "%s", word) != EOF) {
strncpy(search_word, word, PREFIX_SIZE);
get_cycles(&timec_high1, &timec_low1);
tst_search_prefix(root, search_word, sgl, &sidx, LMAX);
get_cycles_end(&timec_high2, &timec_low2);
timec = diff_in_cycles(timec_high1, timec_low1, timec_high2, timec_low2);
fprintf(out, "%d %lu\n", i, timec);
i++;
}
~~~
* 在 file 裡指印兩個數是因為，我在利用 gnuplot 畫圖時取 column 時，比較方便，再把 cpy 和 ref 的 cycle 情形，利用 gnuplot 畫出來：
### 實作 Memory pool
* 在找尋 cache-miss 的降低方法時 ，參考了 [ierosodin 的 phonebook 作業](https://hackmd.io/s/SJ4uqs9Yx#)

* 原理參考 [wiki](https://en.wikipedia.org/wiki/Memory_pool)：
* memory pool also called fixed-size blocks allocation, is the use of pools for memory management that allows dynamic memory allocation comparable to malloc
* 簡易的 momory pool 至少要涵蓋 memory 的 allocate / access / free

* 一開始我直接用二維矩陣測試，目的是希望連續記憶體可以降低 cache-miss 結果從原本的 (CPY)39.412 % -> (REF)60.791 %
* 原因就出在於一開始的考量不周全，我直接使用 char word2[9400][WRDMAX] 的空間給每一個 word ，沒用完的部份就造成記憶體破碎 （memory fragmentation）
* 只要我先 create 一個連續的記憶體空間，我需要多少空間裝 word 就分配給他剛好的大小，就可以保有我連續記憶體空間的想法並解決我一開始二維矩陣的問題了。

* 因為我在參考 ierosodin 的 HACKMD 上的程式碼時，我發現我這邊並沒有使用到 head 因此拿掉了
* malloc 和 calloc 的不同差在有無初始化，[參考](https://www.programiz.com/c-programming/c-dynamic-memory-allocation) ：

| malloc() | calloc() |
| -------- | -------- |
| Allocates requested size of bytes and returns a pointer first byte of allocated |Allocates space for an array elements, initializes to zero and then returns a pointer to memory |

~~~c=
typedef struct pool{
char *next;
char *tail;
} MEMPOOL;

MEMPOOL *pool_initial(size_t size)
{
MEMPOOL *p = (MEMPOOL *)malloc(size);
p->next = (char *) calloc(1, size);
p->tail = p->next + size;
return p;
}

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

void *pool_access(MEMPOOL *p, size_t size)
{
if( p->tail - p->next < size )
return NULL;
void *tmp = (void*)p->next;
p->next += size;
return tmp;
}
~~~
* 結果在搜尋時的 cache-miss 下降了：
~~~
ina@tina-X550VB:~/Hw/prefix-search$ make cache-test |grep perf
perf stat --repeat 100 \

Performance counter stats for './test_cpy s In' (100 runs):

1,8797 cache-misses # 35.540 % of all cache refs ( +- 3.13% )
5,2890 cache-references ( +- 0.77% )
1573,7959 instructions # 1.36 insn per cycle ( +- 0.02% )
1154,9756 cycles ( +- 0.36% )

0.005854204 seconds time elapsed ( +- 3.06% )

perf stat --repeat 100 \

Performance counter stats for './test_ref s In' (100 runs):

4440 cache-misses # 24.746 % of all cache refs ( +- 3.20% )
1,7943 cache-references ( +- 0.98% )
622,2836 instructions # 1.18 insn per cycle ( +- 0.16% )
529,3465 cycles ( +- 0.53% )

0.002717278 seconds time elapsed ( +- 2.99% )
~~~
* REF 的 cycle 數目也下降了很多

### 分析資料
* 透過統計模型，取出 95% 信賴區間
* 先參考了 [什麼是信賴區間](https://www.google.com.tw/url?sa=t&rct=j&q=&esrc=s&source=web&cd=3&cad=rja&uact=8&ved=0ahUKEwjsu7n_mvXWAhWDLpQKHRSIAhwQFggvMAI&url=http%3A%2F%2Fmathcenter.ck.tp.edu.tw%2FMCenter%2FCtrl%2FePaper%2FePaperOpenFileX.ashx%3FautoKey%3D11&usg=AOvVaw21XaaaLhBpJhrKO84sJF6n) 和 [wiki](https://zh.wikipedia.org/wiki/%E6%AD%A3%E6%80%81%E5%88%86%E5%B8%83)
* 95％信賴區間是從樣本數據計算出來的一個區間，保證在所有樣本當中，有95％會把真正的母體參數包含在區間之中。
* 所以如果以鐘形曲線來看 ， 我們會很容易的知道資料的密集與散佈與否
* 圖形上第一個數為平均，第二個數為標準差的平方，我們稱以下圖形為機率密度函數 “PDF”（Probability Density Function）

* 雖然不一定每種統計數據都是常態分佈，但只要資料是常態分佈，機率密度函數就會成鐘形曲線，這是我們所希望的，因為排除掉忽大忽小的個案，才可以掌握資訊的正確性
* 於是我先把我原本的之前做的 CPY 和 REF（Memory pool 版本）用統計的方式重畫 ， X-axis 是 cycles 數， Y-axis 是到目前為止已累積多少筆相同 cycle 數的資料
* CPY 分析分佈

* REF( Memory pool 版本 ) 分析分佈

* 轉換圖表 X-Y 的數據後我們可以很明顯的看出 REF 資料密集程度遠大於 CPY ，不只在 count 累積的數目，也在 cycles 的 range 有很大的差異
* 這並不是機率密度函數的圖，只是先單純做資料分析的分佈
* 計算平均與標準差：
標準差 $\sigma=\sqrt{\dfrac{1}{N}\cdot\sum_{k=1}^{N}(X_i-\overline{x})^2}$
* CPY 平均 ： 5974.116 cycles
CPY 標準差 ： 5908.070
* REF 平均 ： 65.885 cycles
REF 標準差 ： 9.854
* 帶入機率密度函數公式：
$f(x) = {1 \over \sigma\sqrt{2\pi} }\,e^{- {{(x-\mu )^2 \over 2\sigma^2}}}$
* 把 x 帶入後，在常態分佈下資料會長這樣 ，這邊要特別注意是因為我們判定資料型態像常態分佈才用這個公式算出理想的模型，像其實我認為 CPY 太分散了其實並不像常態分佈所以才會在算 95% 信賴區間（平均加減 2 倍標準差）時出現負數， REF 長的比較常態分佈 ， 所以我再假設他們是常態分佈下才能做以下的鐘形曲線圖
* probability 總和為1，因為資料量大，所以如果愈分散每個 cycles 分到的機率愈小
* REF_PDF ideal model ：

* 真實情況
* REF_PDF real model ：

* 當然希望做出來的實驗愈符合常態分佈愈好 ， 但真實情況常常如上圖，不是非常符合， 但我們想要拿取資料時還是可以將出現機率很小且不符合 95 % 信賴區間的數值拿掉不考量。
* CPY_PDF real model ：
* CPY 除了非常不符合常態分佈以外，還有一個更糟糕的情況，我們出現機率少的數值竟然佔大多數，可見資料是十分分散的，所以這邊我們不能取 95% 信賴間，因此得重新分析 CPY_PDF。

* Poisson distribution
* 參考 [Statistics The Poisson Distribution ](https://www.umass.edu/wsp/resources/poisson/), [統計應用小小傳](http://www.agron.ntu.edu.tw/biostat/Poisson.html) ，[wiki](https://en.wikipedia.org/wiki/Poisson_distribution)
* 上禮拜的課程中提到的卜瓦松分布，剛好有 CPY 的特性
* The fundamental trait of the Poisson is its asymmetry，and this trait it preserves at any value of ${\lambda }$
* 有別於我們一般常態分佈的對稱性，不對稱性剛好是卜瓦松分布的特色
* x 軸代的 k 是 index ， y 軸則是代入 k 後的機率
* Probability of events for a Poisson distribution：
P ( k events in interval ) = $e^{-\lambda}\cdot\dfrac{{\lambda}^k}{k!}$
* 他只需要一個參數 ： 單位時間平均事件發生次數 λ
* 要判定一個統計是否可以做出 Poisson distribution 必須要有以下特點：
(1) the event is something that can be counted in whole numbers
(2) occurrences are independent
(3) the average frequency of occurrence for the time period is known
(4) it is possible to count how many events have occurred

* $\lambda$ 代 $\frac{1}{\mu}$ : 這邊的意思拿 CPY 來說就是平均每 5974.116 個 cycle 可以完成一次搜尋

* 但是為了做圖方便所以將 5974.116 (cycles) 為一個單位時間，這樣 $\lambda$ 代 1
* 放大版

* ｉｄｅａｌ　為階梯狀的原因是因為　5974.116（ｃｙｃｌｅｓ） 為一個單位，然後公式裏面又有　ｋ　階層，所以在小數的部份會被忽略，但　ｒｅａｌ　的部份又是　1個　ｃｙｃｌｅ　為單位，我認為這樣是不好的製圖方式，我應該要以　5974.116（ｃｙｃｌｅｓ）　為單位製圖才比較容易觀察差異

* 以　5974.116（ｃｙｃｌｅｓ） 為一個單位製圖
* 這樣看來就可以確定　ＣＰＹ　比起　Ｎｏｒｍａｌ distribution　確實比較像　Poisson distribution　
* 代入　Poisson　的　95%　confidence interval
* 參考 [How to calculate a confidence level for a Poisson distribution?](https://stats.stackexchange.com/questions/15371/how-to-calculate-a-confidence-level-for-a-poisson-distribution)
* 兩者的 95% 信賴區間
* CPY　= 5477.26　～　6947.76 (cycles)
* ＲＥＦ（+ｍｅｍｏｒｙ　ｐｏｏｌ） ＝　46.177　～　85.593 (cycles)