# 2020q3 Homework1 (lab0)
contributed by < `quantabase13` >
說明
- [作業說明](https://hackmd.io/@sysprog/2020-lab0)
## 作業要求
實作 queue，此 queue 能從 head 處插入 element。
- 需要實現的函式：
- `q_new` - 新增空的 queue
- `q_free` - 清除整個 queue
- `q_insert_head` - 在 queue 的 head 前插入元素
- `q_insert_tail` - 在 queue 的 tail 後插入元素
- `q_remove_head` - 取出並移除 queue 的第一個元素
- `q_size`- 給出 queue 中的元素個數
- `q_reverse`- 反轉整個 queue ，並且只使用原本 queue 中的 element
- `q_sort` - 對 queue 進行遞增排序(時間複雜度：O(nlog(n))
## 實作流程
### queue.h
* 修改 `queue_t`，新增 `size`和 `tail` 這兩個 member
* 從程式碼中的註解可得知 `q_size` 和 `q_insert_tail` 的時間複雜度限制為 O(1)。透過這種方式可以讓 `q_size` 直接返回 `size` 的值 ; 讓 `q_insert_tail` 不需計算 tail 的位置。
```c=
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
/* TODO: You will need to add more fields to this structure
* to efficiently implement q_size and q_insert_tail.
*/
/* TODO: Remove the above comment when you are about to implement. */
list_ele_t *tail;
int size;
} queue_t;
```
### queue.c
* 要點(不含`q_sort`部份)
* 注意 `malloc` 是否有成功分配記憶體
* 注意不再被使用的記憶體要記得 `free`
* 要點( `q_sort` 實作相關)
* merge sort 的實現方式(遞歸或迭代)
* ## `q_size`
```c=
/*
* Return number of elements in queue.
* Return 0 if q is NULL or empty
*/
int q_size(queue_t *q)
{
/* TODO: You need to write the code for this function */
/* Remember: It should operate in O(1) time */
/* TODO: Remove the above comment when you are about to implement. */
if (!q)
return 0;
return q->size;
}
```
`q_size` 確認傳入的 pointer 不為 NULL 後才對其取值。同時透過為 queue_t 加入 size 後可讓所需時間為 O(1)。
* ## q_new
```c=
/*
* Create empty queue.
* Return NULL if could not allocate space.
*/
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* TODO: What if malloc returned NULL? */
if (q) {
q->head = NULL;
q->tail = NULL;
q->size = 0;
}
return q;
}
```
一樣根據程式碼中的註解，在實作中加入對記憶體分配失敗時的處理。
* ## q_free
```c=
/* Free all storage used by queue */
void q_free(queue_t *q)
{
/* TODO: How about freeing the list elements and the strings? */
/* Free queue structure */
list_ele_t *next;
if (!q)
return;
for (list_ele_t *indirect = q->head; indirect != NULL;) {
free(indirect->value);
next = (indirect)->next;
free(indirect);
indirect = next;
}
free(q);
}
```
利用 `next` 和 `indirect` 兩個 pointer 遍歷整個 queue 來釋放記憶體。釋放記憶體的順序為：
1. 元素結構中的 `*char` pointer 指向的記憶體
2. 元素結構佔有的記憶體
3. queue 結構佔有的記憶體
* ## q_insert_head
```c=
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
char *newstr;
int len = strlen(s);
/* TODO: What should you do if the q is NULL? */
if (!q) {
return false;
}
newh = malloc(sizeof(list_ele_t));
if (!newh) {
return false;
}
newstr = malloc(sizeof(char) * len + 1);
if (!newstr) {
free(newh);
return false;
}
for (int i = 0; i < len; i++) {
*(newstr + i) = *(s + i);
}
*(newstr + len) = '\0';
/* Don't forget to allocate space for the string and copy it */
/* What if either call to malloc returns NULL? */
newh->next = q->head;
newh->value = newstr;
q->head = newh;
if (!(q->tail))
q->tail = newh;
(q->size)++;
return true;
}
```
根據傳進來 string 的長度，動態配置記憶體這裡必須要注意 `malloc` 的結果是否成功。為了突顯記憶體分配的問題，作業中的 `malloc` 其實已經被包裝過，在 `harness.h` 檔案中可以看到如下程式碼：
```c=
/* Tested program use our versions of malloc and free */
#define malloc test_malloc
#define free test_free
```
可以得知 `malloc` 在作業裡被替換成 `test_malloc` 。追蹤到 `harness.c` 檔後，可以看到 `test_malloc` 的具體實現：
```c=
/*
* Implementation of application functions
*/
void *test_malloc(size_t size)
{
if (noallocate_mode) {
report_event(MSG_FATAL, "Calls to malloc disallowed");
return NULL;
}
if (fail_allocation()) {
report_event(MSG_WARN, "Malloc returning NULL");
return NULL;
}
block_ele_t *new_block =
malloc(size + sizeof(block_ele_t) + sizeof(size_t));
if (!new_block) {
report_event(MSG_FATAL, "Couldn't allocate any more memory");
error_occurred = true;
}
// cppcheck-suppress nullPointerRedundantCheck
new_block->magic_header = MAGICHEADER;
// cppcheck-suppress nullPointerRedundantCheck
new_block->payload_size = size;
*find_footer(new_block) = MAGICFOOTER;
void *p = (void *) &new_block->payload;
memset(p, FILLCHAR, size);
// cppcheck-suppress nullPointerRedundantCheck
new_block->next = allocated;
// cppcheck-suppress nullPointerRedundantCheck
new_block->prev = NULL;
if (allocated)
allocated->prev = new_block;
allocated = new_block;
allocated_count++;
return p;
}
```
可以看到，在呼叫真正 `malloc` 之前，多了一個 `fail_allocation` 函式。
在 `harness.c` 檔裡同樣可看到 `fail_allocation` 的實現：
```c=
/* Should this allocation fail? */
static bool fail_allocation()
{
double weight = (double) random() / RAND_MAX;
return (weight < 0.01 * fail_probability);
}
```
我們從程式碼中可以得知， `fail_allocation` 代表分配記憶體失敗的機率。在 `harness.c` 檔裡可以看到， `fail_probability` 的值預設為0 。
在作業程式碼中搜尋 `fail_probaility` 時在 `q_test.c` 有找到以下程式碼：
```c=
static void console_init()
{
add_cmd("new", do_new, " | Create new queue");
add_cmd("free", do_free, " | Delete queue");
add_cmd("ih", do_insert_head,
" str [n] | Insert string str at head of queue n times. "
"Generate random string(s) if str equals RAND. (default: n == 1)");
add_cmd("it", do_insert_tail,
" str [n] | Insert string str at tail of queue n times. "
"Generate random string(s) if str equals RAND. (default: n == 1)");
add_cmd("rh", do_remove_head,
" [str] | Remove from head of queue. Optionally compare "
"to expected value str");
add_cmd(
"rhq", do_remove_head_quiet,
" | Remove from head of queue without reporting value.");
add_cmd("reverse", do_reverse, " | Reverse queue");
add_cmd("sort", do_sort, " | Sort queue in ascending order");
add_cmd("size", do_size,
" [n] | Compute queue size n times (default: n == 1)");
add_cmd("show", do_show, " | Show queue contents");
add_param("length", &string_length, "Maximum length of displayed string",
NULL);
add_param("malloc", &fail_probability, "Malloc failure probability percent",
NULL);
add_param("fail", &fail_limit,
"Number of times allow queue operations to return false", NULL);
}
```
再搭配用來測試的腳本，以 `trace-10-malloc.cmd` 的內容為例：
```=
# Test of malloc failure on new
option fail 10
option malloc 50
new
new
new
new
new
new
```
從這些程式碼，我們得知程式執行期間我們可以輸入的命令及參數。以 `option malloc 50` 為例，透過這個命令，能將 `fail_probability` 從原本的 `0` 修改為 `50` 。
* ## q_insert_tail
```c=
bool q_insert_tail(queue_t *q, char *s)
{
/* TODO: You need to write the complete code for this function */
/* Remember: It should operate in O(1) time */
/* TODO: Remove the above comment when you are about to implement. */
list_ele_t *newt;
char *newstr;
int len = strlen(s);
if (!q)
return false;
newt = malloc(sizeof(list_ele_t));
if (!newt) {
return false;
}
newstr = malloc(sizeof(char) * len + 1);
if (!newstr) {
free(newt);
return false;
}
for (int i = 0; i < len; i++) {
*(newstr + i) = *(s + i);
}
*(newstr + len) = '\0';
newt->next = NULL;
newt->value = newstr;
if (!q->tail) {
q->head = newt;
q->tail = newt;
} else {
q->tail->next = newt;
q->tail = newt;
}
(q->size)++;
return true;
}
```
`q_insert_tail` 的實作與 `q_insert_head` 基本相同。
* ## q_remove_head
```c=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
/* TODO: You need to fix up this code. */
/* TODO: Remove the above comment when you are about to implement. */
list_ele_t *tmp;
int i;
if (!q)
return false;
if (q->size == 0)
return false;
if (!sp)
return true;
for (i = 0; (i < bufsize - 1) && (*(q->head->value + i) != '\0'); i++) {
*(sp + i) = *(q->head->value + i);
}
*(sp + i) = '\0';
tmp = q->head;
q->head = q->head->next;
q->size--;
free(tmp->value);
free(tmp);
return true;
}
```
這裡要注意的是 `bufsize` 代表可儲存的最大長度，而非一定要放滿 `bufsize` 的長度。因此在 `for` 迴圈中需要加入來源 `pointer` 指向的 `char` 是否為 `'\0'` 的檢查。
* ## q_reverse
```c=
void q_reverse(queue_t *q)
{
/* TODO: You need to write the code for this function */
/* TODO: Remove the above comment when you are about to implement. */
if (!q)
return;
if (q->size == 0)
return;
list_ele_t *cur = NULL;
list_ele_t *header = q->head;
while (header) {
list_ele_t *next = header->next;
header->next = cur;
cur = header;
header = next;
}
list_ele_t *tmp = q->head;
q->head = q->tail;
q->tail = tmp;
return;
}
```
`q_reverse` 的實現在第一周上課的小考就有出現，畫出各個 `pointer` 指向的變化就能一目了然。
* ## q_sort
`q_sort` 我實作了兩次，第一次是用全遞迴的方式：
```c=
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2);
list_ele_t *mergeSort(list_ele_t *head);
void q_sort(queue_t *q)
{
/* TODO: You need to write the code for this function */
/* TODO: Remove the above comment when you are about to implement. */
if (q == NULL || q->size == 0 || q->size == 1) {
return;
}
q->head = mergeSort(q->head);
while (q->tail->next) {
q->tail = q->tail->next;
}
}
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
if (!l2)
return l1;
if (!l1)
return l2;
if (strcmp(l1->value, l2->value) < 0) {
l1->next = merge(l1->next, l2);
return l1;
} else {
l2->next = merge(l2->next, l1);
return l2;
}
}
list_ele_t *mergeSort(list_ele_t *head)
{
if (!head || !head->next)
return head;
list_ele_t *fast = head->next;
list_ele_t *slow = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
list_ele_t *l1 = mergeSort(head);
list_ele_t *l2 = mergeSort(fast);
return merge(l1, l2);
}
```
全遞迴的版本無法通過 trace-15 ，會出現 `Segmentation fault (core dumped)`的錯誤訊息。
確認過程式碼不會 dereference `NULL pointer` 後，推測是遞迴用到的 stack 空間過多導致。
於是第二次參考[ZhuMon](https://hackmd.io/@ZhuMon/lab0-c#2020q1-Homework1-lab0)，將 `merge` 的部份以迭代實現：
```c=
void mergeSort(list_ele_t **head);
void q_sort(queue_t *q)
{
/* TODO: You need to write the code for this function */
/* TODO: Remove the above comment when you are about to implement. */
if (q == NULL || q->size == 0 || q->size == 1) {
return;
}
mergeSort(&q->head);
while (q->tail->next) {
q->tail = q->tail->next;
}
}
void mergeSort(list_ele_t **head)
{
if (!*head || !(*head)->next)
return;
list_ele_t *l1 = (*head)->next;
list_ele_t *l2 = (*head);
while (l1 && l1->next) {
l2 = l2->next;
l1 = l1->next->next;
}
l1 = l2->next;
l2->next = NULL;
l2 = *head;
mergeSort(&l1);
mergeSort(&l2);
*head = NULL;
list_ele_t **cur = head;
while (l1 && l2) {
if (strcmp(l1->value, l2->value) < 0) {
*cur = l1;
l1 = l1->next;
} else {
*cur = l2;
l2 = l2->next;
}
cur = &(*cur)->next;
}
*cur = l1 ? l1 : l2;
}
```
程式碼利用 `l1` , `l2` 指向等待被 merge 的 linked list 的第一個元素 , 利用 `cur` 這個 pointer to pointer 訪問並修改原本 linked list 元素的 next 欄位
```graphviz
digraph linked_list{
rankdir=LR
node [shape=record];
1 [label="{ <data> 1 | <ref> }"];
3 [label="{ <data> 3 | <ref> }"];
5 [label="{ <data> 5 | <ref> }"];
7 [label="{ <data> 7 | <ref> }"];
cur[label="{ <data> cur }"];
cur -> "1":ref[tailclip=false]
l1 -> 3 [ tailclip=false]
1:ref:c -> 3:data [arrowtail=dot, dir=both, tailclip=false];
3:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false];
5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false];
7:ref:c ->NULL [arrowtail=dot,
dir=both, tailclip=false]
2 [label="{ <data> 2| <ref> }"];
4 [label="{ <data> 4 | <ref> }"];
6 [label="{ <data> 6 | <ref> }"];
8 [label="{ <data> 8 | <ref> }"];
l1 [label="{ <data> l1 }"];
l2 [label="{ <data> l2 }"];
2:ref:f -> 4:data [arrowtail=dot, dir=both, tailclip=false];
4:ref:g -> 6:data [arrowtail=dot, dir=both, tailclip=false];
6:ref:h -> 8:data [arrowtail=dot, dir=both, tailclip=false];
8:ref:8->NULL [arrowtail=dot,
dir=both, tailclip=false]
l2 -> 2 [ tailclip=false]
}
```
```graphviz
digraph linked_list{
rankdir=LR
node [shape=record];
1 [label="{ <data> 1 | <ref> }"];
3 [label="{ <data> 3 | <ref> }"];
5 [label="{ <data> 5 | <ref> }"];
7 [label="{ <data> 7 | <ref> }"];
cur[label="{ <data> cur }"];
cur -> "2":ref[tailclip=false]
l1 -> 3 [ tailclip=false]
1:ref:c -> 2:data [arrowtail=dot, dir=both, tailclip=false];
3:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false];
5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false];
7:ref:c ->NULL [arrowtail=dot,
dir=both, tailclip=false]
2 [label="{ <data> 2| <ref> }"];
4 [label="{ <data> 4 | <ref> }"];
6 [label="{ <data> 6 | <ref> }"];
8 [label="{ <data> 8 | <ref> }"];
l1 [label="{ <data> l1 }"];
l2 [label="{ <data> l2 }"];
2:ref:f -> 4:data [arrowtail=dot, dir=both, tailclip=false];
4:ref:g -> 6:data [arrowtail=dot, dir=both, tailclip=false];
6:ref:h -> 8:data [arrowtail=dot, dir=both, tailclip=false];
8:ref:8->NULL [arrowtail=dot,
dir=both, tailclip=false]
l2 -> 4 [ tailclip=false]
}
```
```graphviz
digraph linked_list{
rankdir=LR
node [shape=record];
1 [label="{ <data> 1 | <ref> }"];
3 [label="{ <data> 3 | <ref> }"];
5 [label="{ <data> 5 | <ref> }"];
7 [label="{ <data> 7 | <ref> }"];
cur[label="{ <data> cur }"];
cur -> "3":ref[tailclip=false]
l1 -> 5 [ tailclip=false]
1:ref:c -> 2:data [arrowtail=dot, dir=both, tailclip=false];
3:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false];
5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false];
7:ref:c ->NULL [arrowtail=dot,
dir=both, tailclip=false]
2 [label="{ <data> 2| <ref> }"];
4 [label="{ <data> 4 | <ref> }"];
6 [label="{ <data> 6 | <ref> }"];
8 [label="{ <data> 8 | <ref> }"];
l1 [label="{ <data> l1 }"];
l2 [label="{ <data> l2 }"];
2:ref:f -> 3:data [arrowtail=dot, dir=both, tailclip=false];
4:ref:g -> 6:data [arrowtail=dot, dir=both, tailclip=false];
6:ref:h -> 8:data [arrowtail=dot, dir=both, tailclip=false];
8:ref:8->NULL [arrowtail=dot,
dir=both, tailclip=false]
l2 -> 4 [ tailclip=false]
}
```
採取部份迭代的方法能順利通過 trace-15 ，但若要從根本上解決問題，程式碼必須全部改成迭代。
## 論文與 simulation 程式碼分析
`is_insert_tail_const` 函式負責分析 `q_insert_tail` 的時間複雜度是不是常數：
```c=
bool is_insert_tail_const(void)
{
bool result = false;
t = malloc(sizeof(t_ctx));
for (int cnt = 0; cnt < test_tries; ++cnt) {
printf("Testing insert_tail...(%d/%d)\n\n", cnt, test_tries);
init_once();
for (int i = 0;
i <
enough_measurements / (number_measurements - drop_size * 2) + 1;
++i)
result = doit(0);
printf("\033[A\033[2K\033[A\033[2K");
if (result == true)
break;
}
free(t);
return result;
}
```
比較重要的是 `init_once` 和 `doit` 兩個函式。
`init_once` 負責待測 `queue` 的初始化，為了避免干擾到真正要進行 `q_insert_tail` 的 `queue` ，會另外生成一個 `queue`:
```c=
static void init_once(void)
{
init_dut();
t_init(t);
}
/* Implement the necessary queue interface to simulation */
void init_dut(void)
{
q = NULL;
}
void t_init(t_ctx *ctx)
{
for (int class = 0; class < 2; class ++) {
ctx->mean[class] = 0.0;
ctx->m2[class] = 0.0;
ctx->n[class] = 0.0;
}
return;
}
```
`doit` 則是包含實際負責測量的函式：
```c=
static bool doit(int mode)
{
int64_t *before_ticks = calloc(number_measurements + 1, sizeof(int64_t));
int64_t *after_ticks = calloc(number_measurements + 1, sizeof(int64_t));
int64_t *exec_times = calloc(number_measurements, sizeof(int64_t));
uint8_t *classes = calloc(number_measurements, sizeof(uint8_t));
uint8_t *input_data =
calloc(number_measurements * chunk_size, sizeof(uint8_t));
if (!before_ticks || !after_ticks || !exec_times || !classes ||
!input_data) {
die();
}
prepare_inputs(input_data, classes);
measure(before_ticks, after_ticks, input_data, mode);
differentiate(exec_times, before_ticks, after_ticks);
update_statistics(exec_times, classes);
bool ret = report();
free(before_ticks);
free(after_ticks);
free(exec_times);
free(classes);
free(input_data);
return ret;
}
```
`prepare_inputs` 負責初始化 `input_data` 、 `classes` 、 `random_string`，其中：
1. `input_data` 有150個數，每個數佔一個 `chunk_size` ，每個數表示對應 `string` 的插入個數。如果 `classes[i]` 對應的值為0(代表 fixed case)，則對應 `input_data` 中第 i 個 chunk 的值(插入個數)也會設為0。
2. `classes`為長度 150 的 array ， array 的第 i 格的值代表第 i 格的 class 。因為只有兩個 class，故只會有 0 、 1 兩種值。
3. `random_string` 存有 150 個 string ，每個 string 長度為7。
```c=
void prepare_inputs(uint8_t *input_data, uint8_t *classes)
{
randombytes(input_data, number_measurements * chunk_size);
for (size_t i = 0; i < number_measurements; i++) {
classes[i] = randombit();
if (classes[i] == 0)
*(uint16_t *) (input_data + i * chunk_size) = 0x00;
}
for (size_t i = 0; i < NR_MEASURE; ++i) {
/* Generate random string */
randombytes((uint8_t *) random_string[i], 7);
random_string[i][7] = 0;
}
}
```
`measure` 負責取得 insert tail 之前和之後的 CPU Cycle 。
另外，在執行 `dut_insert_tail` 前，有先 insert head。從 `random_string` 取出 array ，從 `input_data` 指向的第 i 個 chunk 取出要 insert 的數量 。
```c=
void measure(int64_t *before_ticks,
int64_t *after_ticks,
uint8_t *input_data,
int mode)
{
assert(mode == test_insert_tail || mode == test_size);
if (mode == test_insert_tail) {
for (size_t i = drop_size; i < number_measurements - drop_size; i++) {
char *s = get_random_string();
dut_new();
dut_insert_head(
get_random_string(),
*(uint16_t *) (input_data + i * chunk_size) % 10000);
before_ticks[i] = cpucycles();
dut_insert_tail(s, 1);
after_ticks[i] = cpucycles();
dut_free();
}
} else {
for (size_t i = drop_size; i < number_measurements - drop_size; i++) {
dut_new();
dut_insert_head(
get_random_string(),
*(uint16_t *) (input_data + i * chunk_size) % 10000);
before_ticks[i] = cpucycles();
dut_size(1);
after_ticks[i] = cpucycles();
dut_free();
}
}
}
```
`differentiate` 將其相減後得出 `exe_times` ，送入 `update_statics` ， `update_statics` 會根據第 i 個 measurement 對應的 class (也就是 class [ i ]的值) 進行 t-test。
```c=
static void update_statistics(int64_t *exec_times, uint8_t *classes)
{
for (size_t i = 0; i < number_measurements; i++) {
int64_t difference = exec_times[i];
/* Cpu cycle counter overflowed or dropped measurement */
if (difference <= 0) {
continue;
}
/* do a t-test on the execution time */
t_push(t, difference, classes[i]);
}
}
```
`t_push` 負責計算$\Delta{x}$、$\bar{x}$、$\sum\limits_{i = 0}^N{({x_{i}-\bar{x})}^2}$
```c=
void t_push(t_ctx *ctx, double x, uint8_t class)
{
assert(class == 0 || class == 1);
ctx->n[class]++;
/* Welford method for computing online variance
* in a numerically stable way.
*/
double delta = x - ctx->mean[class];
ctx->mean[class] = ctx->mean[class] + delta / ctx->n[class];
ctx->m2[class] = ctx->m2[class] + delta * (x - ctx->mean[class]);
}
```
`report` 中的 `t_compute` 則會計算出 `t`
$t = \frac{\bar{X_0} - \bar{X_1}}{\sqrt{\frac{Var_0}{N_0} + \frac{Var_1}{N_1}}}$
其中：
$Var_{0} = {\sum\limits_{i = 0}^{N_0}{({x_{i}-\bar{x}_{0})}^2}\over{{N_0}-1}}$
$Var_{1} = {\sum\limits_{i = 0}^{N_1}{({x_{i}-\bar{x}_{1})}^2}\over{{N_1}-1}}$
```c=
double t_compute(t_ctx *ctx)
{
double var[2] = {0.0, 0.0};
var[0] = ctx->m2[0] / (ctx->n[0] - 1);
var[1] = ctx->m2[1] / (ctx->n[1] - 1);
double num = (ctx->mean[0] - ctx->mean[1]);
double den = sqrt(var[0] / ctx->n[0] + var[1] / ctx->n[1]);
double t_value = num / den;
return t_value;
}
```
~~另外，仔細查看 `t_push` 的實作部份會發現，每次計算 ${m_2}$(也就是$\sum\limits_{i = 0}^N{({x_{i}-\bar{x})}^2}$)時，所用的$\bar{x}$都不同，但理論上必須使用全體的$\bar{x}$才符合統計學上的意義。
於是對以下檔案進行修改：~~
後來發現wikipedia 上其實有對 Welford's online algorithm 的仔細敘述，並且還有詳細舉出傳統我認知計算 variance 的方法可能會導致 overflow 的問題。
基於上述，以下的修改實屬多餘。
1. `ttest.h` ：為 `t_ctx` 新增 `sum[2]` 欄位，記錄對應 class 的 total sum 。
```c=
#ifndef DUDECT_TTEST_H
#define DUDECT_TTEST_H
#include <stdint.h>
typedef struct {
double sum[2];/*member added to keep total sums*/
double mean[2];
double m2[2];
double n[2];
} t_ctx;
void t_push(t_ctx *ctx, double x, uint8_t class);
void t_mean(t_ctx *ctx, int64_t *exec_times, uint8_t *classes);/*calculate mean for exec_times*/
double t_compute(t_ctx *ctx);
void t_init(t_ctx *ctx);
#endif
```
2. `ttest.c` : 修改 `t_push` ，只保留計算 $\sum\limits_{i = 0}^N{({x_{i}-\bar{x})}^2}$ 的部份，將計算mean的工作交給新增的 `t_mean`
```c=
/**
* Online Welch's t-test.
*
* Tests whether two populations have same mean.
* This is basically Student's t-test for unequal
* variances and unequal sample sizes.
*
* see https://en.wikipedia.org/wiki/Welch%27s_t-test
*
*/
#include "ttest.h"
#include <assert.h>
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
extern const size_t number_measurements;
void t_push(t_ctx *ctx, double x, uint8_t class)
{
assert(class == 0 || class == 1);
// ctx->n[class]++;
/* Welford method for computing online variance
* in a numerically stable way.
*/
double delta = x - ctx->mean[class];
// ctx->mean[class] = ctx->mean[class] + delta / ctx->n[class];
ctx->m2[class] = ctx->m2[class] + delta * delta /*(x - ctx->mean[class])*/;
}
/*Use t_mean to calculate the "correct" mean for total sum */
void t_mean(t_ctx *ctx, int64_t *exec_times, uint8_t *classes)
{
for (size_t i = 0; i< number_measurements; i++) {
assert(classes[i] == 0 || classes[i] == 1);
ctx->n[classes[i]]++;
ctx->sum[classes[i]] += exec_times[i];
}
ctx->mean[0] = ctx->sum[0] / ctx->n[0];
ctx->mean[1] = ctx->sum[1] / ctx->n[1];
}
```
3.`fixture.c` : 把 `t_mean` 加到程式碼的開頭，一開始就把 mean 給計算出來。
```c=
static void update_statistics(int64_t *exec_times, uint8_t *classes)
{
t_mean(t, exec_times, classes);
for (size_t i = 0; i < number_measurements; i++) {
int64_t difference = exec_times[i];
/* Cpu cycle counter overflowed or dropped measurement */
if (difference <= 0) {
continue;
}
/* do a t-test on the execution time */
t_push(t, difference, classes[i]);
}
}
```
## TODO LIST
* 用 Valgrind 排除 `qtest` 實作的記憶體錯誤
* 用 Massif 視覺化記憶體使用量
* 設計實驗
* 解釋程式的 "simulation" 模式如何以實驗驗證複雜度
Sign in with Wallet
Connect another wallet