Try   HackMD

2021q1 Homework1 (lab0)

contributed by < ccs100203 >

tags: linux2021

實驗環境

$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0

$ lscpu
Architecture:        x86_64
CPU op-mode(s):      32-bit, 64-bit
Byte Order:          Little Endian
CPU(s):              8
On-line CPU(s) list: 0-7
Thread(s) per core:  2
Core(s) per socket:  4
Socket(s):           1
NUMA node(s):        1
Vendor ID:           GenuineIntel
CPU family:          6
Model:               158
Model name:          Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
Stepping:            9
CPU MHz:             2635.475
CPU max MHz:         3800.0000
CPU min MHz:         800.0000
BogoMIPS:            5599.85
Virtualization:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            6144K
NUMA node0 CPU(s):   0-7

作業要求

lab0

詳細閱讀 C Programming Lab ，依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 q_sort 函式。

  • q_new: 創一個空的 queue
  • q_free: 釋放掉一個 queue
  • q_insert_head: 在 head 插入一個 element (LIFO)
  • q_insert_tail: 在 tail 插入一個 element (FIFO), O(1)
  • q_remove_head: 把 head 的 element 移除
  • q_size: return queue 的大小
  • q_reverse: 將 queue 反轉，不配置或釋放任何的 element
  • q_sort: 將 queue 由小排到大, sort by nature sort

開發過程

q_new

檢查 malloc 是否正常運作

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    // if malloc return NULL
    if (q == NULL)
        return NULL;

    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

q_free

要記得先清掉 value

void q_free(queue_t *q)
{
    // NULL queue
    if (q == NULL)
        return;

    for (list_ele_t *tmp = q->head; q->head; tmp = q->head) {
        q->head = q->head->next;
        free(tmp->value);
        free(tmp);
    }
    free(q);
}

q_insert_head

一開始在檢查 malloc 時沒有 free(newh)，導致 make test 時有記憶體未釋放，然後沒有做 memset 的話，會遇到 char* 裡頭塞了怪怪的東西，所以後來就先把他清空了。

bool q_insert_head(queue_t *q, char *s)
{
    // NULL queue
    if (q == NULL)
        return false;

    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    // if malloc fail
    if (newh == NULL)
        return false;
    newh->value = malloc((strlen(s) + 1) * sizeof(char));
    // if malloc fail
    if (newh->value == NULL) {
        free(newh);
        return false;
    }

    memset(newh->value, 0, (strlen(s) + 1) * sizeof(char));
    strncpy(newh->value, s, strlen(s));
    newh->next = q->head;
    q->head = newh;
    q->size++;
    if (q->size == 1)
        q->tail = newh;
    return true;
}

q_insert_tail

跟 insert head 滿像的

bool q_insert_tail(queue_t *q, char *s)
{
    // NULL queue
    if (q == NULL)
        return false;

    list_ele_t *newt;
    newt = malloc(sizeof(list_ele_t));
    // if malloc fail
    if (!newt)
        return false;
    newt->value = malloc((strlen(s) + 1) * sizeof(char));
    // if malloc fail
    if (newt->value == NULL) {
        free(newt);
        return false;
    }

    memset(newt->value, 0, (strlen(s) + 1) * sizeof(char));
    strncpy(newt->value, s, strlen(s));
    newt->next = NULL;
    // if queue is empty
    if (q->size == 0) {
        q->head = newt;
        q->tail = newt;
    } else {
        q->tail->next = newt;
        q->tail = newt;
    }
    q->size++;

    return true;
}

q_remove_head

照著註解的方式去做，一開始 q->size 忘記扣，導致 size 錯誤

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    // NULL or empty queue
    if (q == NULL || q->head == NULL)
        return false;

    if (sp != NULL && q->head->value) {
        memset(sp, 0, bufsize);
        strncpy(sp, q->head->value, bufsize - 1);
    }
    list_ele_t *tmp = q->head;
    q->head = q->head->next;
    free(tmp->value);
    free(tmp);
    q->size--;
    return true;
}

q_size

確認是否為 NULL queue

int q_size(queue_t *q)
{
    return (q == NULL) ? 0 : q->size;
}

q_reverse

用了 prev curr next 三個指標去紀錄目前反轉的位置，一路從頭做到尾

void q_reverse(queue_t *q)
{
    // NULL queue or element < 2
    if (q == NULL || q->size < 2)
        return;

    list_ele_t *prev, *next, *curr;

    prev = NULL;
    next = q->head->next;
    curr = q->head;

    while (curr != NULL) {
        curr->next = prev;
        prev = curr;
        curr = next;
        if (next != NULL)
            next = next->next;
    }
    curr = q->head;
    q->head = q->tail;
    q->tail = curr;
}

探索是否有其他作法
TODO

q_sort

參照 Linkd List Sort 的 merge sort 做更改，起初使用遞迴版本時遇到 stack 爆掉的問題，後來用 iterate 的版本時遇到了不能 malloc 的問題，於是又更改了一下寫法才能通過。

在舊版的寫法中，會遇到一開始 head 不知道要放什麼，所以需要在 5~13 行去提前判斷 head 應該要放什麼，在新版中改為用一個 pointer to pointer tmp 去指著 head，就可以在做 while 時把 node 直接放進 tmp 並同時把第一個 node 給 head，隨後只需要把 tmp 一直往後接就可以把 list 串起來。

舊版




































list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
    list_ele_t *temp = NULL, *q = NULL;
    // init the nodes
    if (strnatcmp(l1->value, l2->value) < 0) {
        q = l1;
        temp = l1;
        l1 = l1->next;
    } else {
        q = l2;
        temp = l2;
        l2 = l2->next;
    }

    // sort and connect two list
    while (l1 && l2) {
        if (strnatcmp(l1->value, l2->value) < 0) {
            temp->next = l1;
            temp = temp->next;
            l1 = l1->next;
        } else {
            temp->next = l2;
            temp = temp->next;
            l2 = l2->next;
        }
    }

    // connect remaining node
    if (l1)
        temp->next = l1;
    if (l2)
        temp->next = l2;

    return q;
}

新版



























list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
    list_ele_t *head = NULL;
    list_ele_t **tmp = &head;

    // sort and connect two list
    // don't move head, use tmp traverse all list
    while (l1 && l2) {
        if (strnatcmp(l1->value, l2->value) < 0) {
            *tmp = l1;
            l1 = l1->next;
        } else {
            *tmp = l2;
            l2 = l2->next;
        }
        tmp = &((*tmp)->next);
    }

    // connect remaining node
    if (l1)
        *tmp = l1;
    if (l2)
        *tmp = l2;

    return head;
}

list_ele_t *mergeSortList(list_ele_t *head)
{
    // merge sort
    if (!head || !head->next)
        return head;

    list_ele_t *fast = head->next;
    list_ele_t *slow = head;

    // split list, find the middle of list
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow->next;
    slow->next = NULL;

    // sort each list
    list_ele_t *l1 = mergeSortList(head);
    list_ele_t *l2 = mergeSortList(fast);

    // merge sorted l1 and sorted l2
    return merge(l1, l2);
}

一開始忘記 update q->tail 導致錯誤

void q_sort(queue_t *q)
{
    // NULL queue or element < 2
    if (q == NULL || q->size < 2)
        return;
    q->head = mergeSortList(q->head);

    // update q->tail pointer
    list_ele_t *tmp = q->head;
    while (tmp->next) {
        tmp = tmp->next;
    }
    q->tail = tmp;
}

Valgrind

  • massif 實驗

寫 q_free 時，沒注意到 value 的釋放而導致錯誤，這邊試試看沒有釋放 value，明顯看出在最後的差別

new
ih RAND 10000
sort
free
quit
  • 有 free value

  • 沒有 free value

Dude, is my code constant time?

  • Dude, is my code constant time?

  • Measure execution time

    • 分出 fix-vs -random 兩種不同 class
    • 利用現代 CPU 的 cycle counters，可精準測量執行時間
    • 為了降低環境影響，每次測量的 class 隨機，且會在測量之前將 input 做好

  • post-processing

    • Cropping: 排除因為 OS 或其他無關因素導致的極端值
    • Higher-order preprocessing: 根據不同的 statistical test 做出不同調整

  • dudect 相關

    • constant.c 的 measure
      分為 test_size 與 test_insert_tail 兩個 mode，測試是不是 O(1)
      先在 insert_head 放入 get_random_string 得到的隨機 string，之後做 test 時會前後 call cpucycles 放入 after_ticks 跟 before_ticks ，之後相減就可以得到 cycle 數量
    












    ​​​​ 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();
​​​​    }
​​​​}
    • fixture.c: 判斷是否在誤差範圍內
      test_tries 代表整體測試的次數
      在 10000 筆之中，使用 500 與 10 兩個 threshold，如果差距在 5% 以上則代表整個程式完全不符合 constant time
      未搞懂 threshold 如何設置
    










    ​​​​#define enough_measurements 10000
​​​​#define test_tries 10
​​​​#define t_threshold_bananas 500   
​​​​#define t_threshold_moderate 10 
​​​​if (max_t > t_threshold_bananas) {
​​​​    return false;
​​​​} else if (max_t > t_threshold_moderate) {
​​​​    return false;
​​​​} else { /* max_t < t_threshold_moderate */
​​​​    return true;
​​​​}

2021/02/24
在 cppcheck 2.3 dev 會遇到 unmatchedSuppression 的問題，
無法解讀 pre-commit.hook 內 suppresses 新增的 nullPointerRedundantCheck，
我將 cppcheck 的版本降為 1.9 後解決此問題。

提交 pull request 來改進 Cppcheck 相關操作？
:notes: jserv

Last changed by 
 
ccs100203
Still learning...
0
1623
Published on HackMD