# Evaluating and improving the performance of the C program
contributed by < `eddie9712` >

## 開發紀錄：

環境配置：
ubuntu 18.04+cppcheck1.9+valgrind+git

### (1):fork lab0-c

### (2):試著閱讀`C Programming Lab`的內容,並進行修改:
#### 第一次進行 commit 時：
cppcheck 的 static check 時，顯示 strcpy 一種危險的用法

:::danger
1. 文字為主的訊息不要用圖片來展現
2. 中英文以一個半形空白區隔，注意共筆書寫有規範

:notes: jserv
:::

>書寫規範已修改，文字以圖片呈現部份之後會改進
>[name=Eddie][color=blue]

於是將 strcpy 改成 sprintf

=>根據此[網站](https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml)指出

>The strcpy built-in function does not check buffer lengths and may very well overwrite memory zone contiguous to the intended destination. In fact, the whole family of functions is similarly vulnerable: strcpy, strcat and strcmp.

strcpy 會因為沒計算好 buffer 的長度而覆寫到鄰近周圍的記憶體，因此我將需要進行character copy 的部份全部代換成`strncpy`

以下是規格書中對於`strncpy`的形式和描述：

#include <string.h>
char *strncpy(char * restrict s1,const char * restrict s2,size_t n);

> The strncpy function copies not more than n characters (characters that follow a null character are not copied) from the array pointed to by s2 to the array pointed to by s1.

他的用途是將 s2 所指的 memory 中的 character copy 到 s1 所指的 memory 中，而且它會指定 copy 的長度為 n，要是不足長度 n 將會以 null character 填充

#### 第二次的修改：
將所有功能完成(未進行 make test 做測試)，並實做出 q—sort：

此時我使用的是將 **quiz1 的 linked list mergesort** 套入實作之中 ，以下是 quiz1 的 linked list mergesort 內容

list *sort(list *start) {
    if (!start || !start->next)
        return start;
    list *left = start;
    list *right = left->next;
    left->next = NULL;

    left = sort(left);
    right = sort(right);

    for (list *merge = NULL; left || right; ) {
        if (!right || (left && left->data < right->data)) {
            if (!merge) {
                start = merge = left; 
            } else {
                merge->next = left;
                merge = merge->next;
            }
              left = left->next;
        } else {
            if (!merge) {
                start = merge = right;
            } else {
                merge->next = right; 
                merge = merge->next;
            }
            right = right->next;
        }
    }
    return start;
}

完成後顛開始進行 make test 的測試=>
#### 第三次修改：
這時在 trace-06-cmd(truncated string)的測試出現 error ，於是查看測試內容：

並將它和 error output 進行比對發現可能的原因是 `null character` 的問題。
**solve**:
發現是`memmove` 的問題，以下是規格書之中對於`memmove` 的敘述：
>The memmove function copies n characters from the object pointed to by s2 into the object pointed to by s1. Copying takes place as if the n characters from the object pointed to by s2 are first copied into a temporary array of n characters that does not overlap the objects pointed to by s1 and s2, and then the n characters from the temporary array are copied into the object pointed to by s1.

`memmove`會搬移 size 為 n 的 characters 到另一個pointer 所指的 memory 空間，所以它並不會添加 null character 到字串尾，因此將 `remove_head` function 中的 `memmove` 改為 `snprintf`:

執行到 trace-07-cmd(test operation on null queue)
出現了 dereference null pointer 的問題，原來是因為我在某些地方寫了 `if(q->head==NULL)` 在一進入functiion 時，這樣寫會造成說當 q 是NULL，q->head 便無法得知其值，故將此類寫法改進即可

#### 第四次修改：

在執行 **trace-15-cmd、trace-16-cmd** 時無法通過效能測試，這時檢視原來 sort 的程式碼：

void q_sort(queue_t *q)
{
    if (q != NULL) {
        if (q->head != NULL && q->size > 1) {
            list_ele_t *start = q->head;
            q->head = sort(start);
            while (q->tail->next != NULL) {
                q->tail = q->tail->next;
            }
        }
    } else
        return;
}
list_ele_t *sort(list_ele_t *start)
{
    if (!start || !start->next)
        return start;
    list_ele_t *left = start;
    list_ele_t *right = left->next;
    left->next = NULL;

    left = sort(left);
    right = sort(right);

    for (list_ele_t *merge = NULL; left || right;) {
        if (!right || (left && (strcmp(left->value, right->value) <= 0))) {
            if (!merge) {
                start = merge = left;
            } else {
                merge->next = left;
                merge = merge->next;
            }
            left = left->next;
        } else {
            if (!merge) {
                start = merge = right;
            } else {
                merge->next = right;
                merge = merge->next;
            }
            right = right->next;
        }
    }
    return start;
}

發現 quiz1 所給予的 mergesort algorithm 的performance 很差約為 T(n)=T(n-1)+O(n),所以我針對partition 的部份做改進=>將 partition 改成一次將linked list 切成兩半

void q_sort(queue_t *q)
{
    if (q != NULL) {
        if (q->head != NULL && q->size > 1) {
            list_ele_t *start = q->head;
             q->head = sort(start); 
            while (q->tail->next != NULL) {
                q->tail = q->tail->next;
              }
        }
    } else
        return;
}
list_ele_t *sort(list_ele_t *start)
{
    if((start==NULL)||(start->next==NULL))
         return start;
    list_ele_t *head = start;
    list_ele_t *fast;
    list_ele_t *slow;
    list_ele_t *front;
    list_ele_t *back;
    slow = head;
    fast = head->next;
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }
    front = head;  // partition the linked list into two sublists
    back = slow->next;
    slow->next = NULL;

    front = sort(front);
    back = sort(back);

    head = SortedMerge(front, back);
    return head;
}
list_ele_t *SortedMerge(list_ele_t *a, list_ele_t *b)
{
    list_ele_t *result = NULL;

    if (a == NULL)
        return b;
    else if (b == NULL)
        return a;
    if (strcmp(a->value, b->value) <= 0) {
        result = a;
        result->next = SortedMerge(a->next, b);
    } else {
        result = b;
        result->next = SortedMerge(a, b->next);
    }
    return result;
}

在重新跑一次 **make test**，結果通過了 **trace-16-cmd** 但仍沒有通過 trace-15 的效能測試
**solve**:

發現原因是 "**Mergesort**" 這個 function 之中用到了recursive 導致 merge 這個動作脫離了 O(n) 的時間複雜度，所以就將它改寫成 iterative version

void q_sort(queue_t *q)
{
    if (q != NULL) {
        if (q->head != NULL && q->size > 1) {
            list_ele_t *start = q->head;
            q->head = sort(start);
            while (q->tail->next != NULL) {
                q->tail = q->tail->next;
            }
        }
    } else
        return;
}
list_ele_t *sort(list_ele_t *start)
{
    if ((start == NULL) || (start->next == NULL))
        return start;
    list_ele_t *head = start;
    list_ele_t *fast;
    list_ele_t *slow;
    list_ele_t *front;
    list_ele_t *back;
    slow = head;
    fast = head->next;
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }
    front = head;  // partition the linked list into two sublists
    back = slow->next;
    slow->next = NULL;
    front = sort(front);
    back = sort(back);
    if (front == NULL)  // iterative version
        return back;
    if (back == NULL)
        return front;
    list_ele_t *merge;
    if (strcmp(front->value, back->value) <= 0) {
        merge = front;
        head = front;
        front = front->next;
    } else {
        merge = back;
        head = back;
        back = back->next;
    }
    while ((front != NULL) && (back != NULL)) {
        if (strcmp(front->value, back->value) <= 0) {
            merge->next = front;
            merge = merge->next;
            front = front->next;
        } else {
            merge->next = back;
            merge = merge->next;
            back = back->next;
        }
    }
    if (front == NULL)  // merge the remain part
        merge->next = back;
    else if (back == NULL)
        merge->next = front;
    return head;
}

成功：

#### 將sorting 時的compare function 改成 nature sort:

### (3)使用valgrind 進行記憶體分析：
執行：`make valgrind`
並無發現有記憶體錯誤

接著利用massif 分析：

使用之前須在`.valgrindrc` 之中的`--show-leak-kinds=all` 加上`memcheck`：

為了使數據的顯示可以視覺化，可以使用massifg
=>參考[此頁](http://ottoshare.blogspot.com/2012/03/valgrind.html)，或者也可以使用官方推薦的[massif-visualizer](https://github.com/KDE/massif-visualizer)

#### 用 valgrind massif 觀察 "simulation" 的結果：

實驗設計：我準備用以下的命令進行測試 qtest 的 valgrind 測試，然後觀察記憶體使用=>
將實驗分成三組：
(1)insert head 後 remove head

new
ih RAND 10
rh    //10 times
free
quit

(2)insert head 後做 reverse

new
ih RAND 10
reverse
free
quit

(3)insert 後用不須 allocate 記憶體的 remove head

new
ih RAND 10
rhq //10 times
free
quit

以下為 massif-visualizer 的結果:
(1):
(2):
(3):

從上面三者的記憶體使用來看，因為 malloc 是負責動態記憶體分配，所以可以介由 heap size 的變化來觀察，當使用的 remove 是需要 malloc 空間的 rh heap size 的變化明顯(鋸齒狀變化大)，當執行的是完全不用 allocate 新空間的reverse (無鋸齒狀變化)，第三個是 rhq，因為這個 remove head 傳入的 buffsize 是零，所以他不會有多於的空間去紀錄 remove 掉的資料，所以鋸齒狀變化小。