# 2018q3 Homework3(dict)
## 探討實作上 CPY vs REF 的差異
* REF 版本
在進入 test_ref 程式進入點 main 之後,預設是讀取 cities.txt 並進行必要的初始化
* bloom filter
* [bloom_filter structure](https://github.com/posutsai/dict/blob/master/bloom.h#L15) and [bloom_hash structure](https://github.com/posutsai/dict/blob/master/bloom.h#L10)
```C=
typedef unsigned int (*hash_function)(const void *data);
typedef struct bloom_filter *bloom_t;
// 從 bloom_hash 可以知道實作中是以 single linked list
// 串連各個 hash function,而在實作中我們使用了兩種 hash
// function,分別是 jenkins and djb2
struct bloom_hash {
hash_function func;
struct bloom_hash *next;
};
struct bloom_filter {
struct bloom_hash *func; // function list
void *bits; // where we store our 1s and 0s
size_t size;
};
```
* [bloom_create constructor](https://github.com/posutsai/dict/blob/master/bloom.c#L32)
```C=
bloom_t bloom_create(size_t size) {
bloom_t res = calloc(1, sizeof(struct bloom_filter));
res->size = size;
res->bits = malloc(size);
bloom_add_hash(res, djb2);
bloom_add_hash(res, jenkins);
return res;
}
```
* memory pool
在開檔成功後,如果 tst_ins_del 沒有發生錯誤,便會一路讀到 EOF
```C=
// memory pool 透過一開始宣告所需要的記憶體空間,省去需要時每次
// malloc and free 所帶來的成本 memory pool 實作中,固定會有
// 一個 pool 指標指向 pool 的起始位址,另一個 Top 指標指向下一
// 個可插入的單位
char *pool = (char *) malloc(poolsize * sizeof(char));
char *Top = pool;
// 實際把字串塞入 memory pool 使用的是 fscanf,並在每次 while
// loop iteration 之後,把 Top 向後移上個 iteration 已經輸入
// 的那個字串長度
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);
}
void bloom_add(bloom_t filter, const void *item) {
struct bloom_hash *h = filter->func;
uint8_t *bits = filter->bits;
while (h) {
unsigned int hash = h->func(item);
hash %= filter->size;
bits[hash] = 1;
h = h->next;
}
}
```
* CPY 版本
* [main function](https://github.com/posutsai/dict/blob/master/test_cpy.c#L25) 內讀取資料的機制明顯與 REF 版本不同
```C=
// 從以下這段程式碼可以清楚看到,word 一開始先被設定了最長的長度
// 沒有先經過一層外在的記憶體管理就進到 TST 裡
char word[WRDMAX] = "";
while ((rtn = fscanf(fp, "%s", word)) != EOF) {
char *p = word;
if (!tst_ins_del(&root, &p, INS, CPY)) {
fprintf(stderr, "error: memory exhausted, tst_insert.\n");
fclose(fp);
return 1;
}
idx++;
}
```
## 分析效能表現
1. 在以 gnuplot 畫圖之前,勢必要先獲取資料,但在獲取資料上卡了很久,始終不懂單純從 command line 介面,怎麼分析 instruction per cycle,最後查到用 <linux/perf_event.h>,不過時間似乎已經太晚了。
2. 我的分析方法是隨機從 cities.txt 找非 "," 的字串,我在想作業教學上的圖表受到 "," 的影響是很大的,實際上 "," 是會進去 TST 的,且相較於其他可能字串,出現頻率過高,導致分析上的失真。
3. 實驗中,我每次需要查詢一個字串就會 fork 一個 child process 並測量這個 process 的執行時間。
4. 我實作了一個 [cpu_cycles](https://github.com/posutsai/dict/blob/master/measure_ipc.c#L30) 函式,在給的時間區間內計算 child process cpu_cycle
5. 以下為部分紀錄
```
Okha, 0.001148, 7487000
Uruguay, 0.001085, 43227000
Saint-Florent-des-Bois, 0.001074, 54829000
....
```