Try   HackMD

2024q1 Homework1 (lab0)

contributed by < Jimmy01240397 >

Reviewed by jujuegg

  • 不用張貼完整程式碼
  • dudect 的部分可以把詳細實作列出,或者貼出 commit 的連結來參考
  • 我認為可以適當的在程式碼中間加入一點空行,增加可讀性。

工程人員說話要明確,避免說「感覺」
與其談「心法」,不如設想「如果我是你」,我會怎麼做,示範一次給同學看,而且檢討自己哪裡沒做好,從而呼應原本學員的不足處。
軟體工程師要學會說故事,本作業要求學員從良性詳盡的批評開始。繼續檢討!

開發環境

$ gcc --version
gcc (Debian 12.2.0-14) 12.2.0
Copyright (C) 2022 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         40 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  1
  On-line CPU(s) list:   0
Vendor ID:               GenuineIntel
  Model name:            Common KVM processor
    CPU family:          15
    Model:               6
    Thread(s) per core:  1
    Core(s) per socket:  1
    Socket(s):           1
    Stepping:            1
    BogoMIPS:            5999.99

實驗圖表生成程式

python labtest.py config.yml labtest.png

import sys
import matplotlib.pyplot as plt
import subprocess
import yaml
import importlib

with open(sys.argv[1], 'r') as f:
    config = yaml.load(f, Loader=yaml.FullLoader)

data = [[] for a in config['lab']]
size = list(range(int(config['size']['min']), int(config['size']['max']), int(config['size']['step'])))

for a in size:
    for idx, b in enumerate(config['lab']):
        testcase = importlib.import_module(f'testcase.{b["testcasegen"]}').init(a)
        time = subprocess.run(b['command'], input=testcase, stdout=subprocess.PIPE).stdout.decode()
        time = float(time.split('\n')[0])
        data[idx].append(time)

plt.xlabel('size', fontsize=20)
plt.ylabel('time', fontsize=20)

for idx, a in enumerate(data):
    plt.scatter(size, a, c=config['lab'][idx]['color'], alpha=0.5)

plt.savefig(sys.argv[2])

針對佇列操作的程式碼實作

q_new

實作建立一個空的佇列,建立一個 list_head 用來連結佇列的第一個節點以及最後一個節點。

避免過多的中英文混用,已有明確翻譯詞彙者,例如「鏈結串列」(linked list) 和「佇列」(queue),就使用該中文詞彙,英文則留給變數名稱、人名,或者缺乏通用翻譯詞彙的場景。

已修

struct list_head *q_new()
{
    struct list_head *node = malloc(sizeof(struct list_head));
    if (!node)
        return NULL;
    INIT_LIST_HEAD(node);
    return node;
}

q_free

實作佇列的釋放,當佇列被釋放,裡面的所有節點理應被釋放,如果佇列為空的 for 便不會執行,直接釋放佇列本身。

void q_free(struct list_head *l)
{
    if (!l)
        return;
    struct list_head *node, *safe;
    list_for_each_safe (node, safe, l) {
        list_del(node);
        element_t *element = container_of(node, element_t, list);
        e_free(element);
    }
    free(l);
}

q_insert_head 與 q_insert_tail

建立一個新節點並且加入到鏈結串列的頭部或尾部。
考慮到堆疊釋放的情況,因此要對字串做複製。

    if (!head || !s)
        return false;
    element_t *element = e_new(s);
    if (!element)
        return false;
-   list_add(&(element->list), head);
+   list_add_tail(&(element->list), head);
    return true;

考慮到兩者有高度相似,可運用巨集來代替減少重複程式。

/* Base function for insert an element into queue */
#define q_insert_base(head, s, list_add_method) \
    if (!head || !s)                            \
        return false;                           \
    element_t *element = e_new(s);              \
    if (!element)                               \
        return false;                           \
    list_add_method(&(element->list), head);    \
    return true;

/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
    q_insert_base(head, s, list_add);
}

/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    q_insert_base(head, s, list_add_tail);
}

q_remove_head 與 q_remove_tail

從鏈結串列的頭部或尾部移除一個節點。

-   if (!head || head->next == head) return NULL;
-   element_t *element = container_of(head->next, element_t, list);
+   if (!head || head->prev == head) return NULL;
+   element_t *element = container_of(head->prev, element_t, list);
    list_del(&(element->list));
    strncpy(sp, element->value, bufsize - 1);
    sp[bufsize - 1] = '\0';
    return element;

同理,可以運用巨集來代替減少重複程式。

#define q_remove_base(head, sp, bufsize, nextprev)                           \
    if (!head || head->nextprev == head)                                     \
        return NULL; /* When head->next or head->prev == head queue is empty \
                      */                                                     \
    element_t *element = container_of(head->nextprev, element_t, list);      \
    list_del(&(element->list));                                              \
    strncpy(sp, element->value, bufsize - 1);                                \
    sp[bufsize - 1] = '\0';                                                  \
    return element;

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    q_remove_base(head, sp, bufsize, next);
}

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    q_remove_base(head, sp, bufsize, prev);
}

實作時也產生一個疑問是為甚麼 list_del 的無效記憶體位址一定要是 0x00100100 與 0x00200200 而不是其他數字如:0x00100101、0x00200202、0x0 之類的。

這問題很好,你可參見 Linux 核心原始程式的 git log 來解讀。

q_size

實作計算佇列的長度。
由於計算需要迭代計算,如果一次走兩步或許可以加快運行的速度。

所以真的有比較快嗎? 真心發問
雖然迴圈次數減少一半,但是實際上指標還是前進了整個佇列,條件也相對變多,請問真的會比較快嗎?
jujuegg

不要書寫「真心發問」,詳盡提出你的疑慮和佐證,這樣才能有效溝通。

真誠地分享你的專業知識,讓溝通能夠達到共鳴,才是真正展現禮貌的方式。

int q_size(struct list_head *head)
{
    if (!head)
        return -1;
    int size = 0;
    struct list_head *node;
    for (node = head->next; node != head && node->next != head;
         node = node->next->next, size+=2) {
    }
    size += (node != head) & 1;
    return size;
}

實驗

測資產生器

「產生器」不是精準的詞彙,因為你應當有明確的測試計畫,並從數學分析 (或已有的論述) 證實該計畫可行,接著才用程式碼去產生對應的資料輸入。否則,你只是「憑感覺」做事,根本不能算是「工程」。

def init(size):
    return f"""new
ih RAND {size}
size
quit
""".encode()

設定檔

size:
  min: 1000
  max: 100000
  step: 100

lab:
# 一步一步算
- command:
  - "./qtest-normal"
  - "-v"
  - "0"
  color: 'blue'
  testcasegen: 'size'
# 二步二步算
- command:
  - "./qtest"
  - "-v"
  - "0"
  color: 'red'
  testcasegen: 'size'

結果:

  • min: 100 max: 1000 step: 1
    labtest1
  • min: 1000 max: 10000 step: 10
    labtest2
  • min: 1000 max: 100000 step: 100
    labtest3

結論:在 size 高的情況兩步兩步算真的比較快一點點

需要更多的解讀,從電腦科學的基礎學科的角度去陳述,避免說「真的比較快一點點」。

q_delete_mid

參考「你所不知道的 C 語言: linked list 和非連續記憶體」,使用快慢指標並且由於使用環狀鏈結串列因此終止判斷會以 = head 為標準。

for (fast = head->next, slow = head->next;
     fast != head && fast->next != head;
     fast = fast->next->next, slow = slow->next) {
}
list_del(slow);
element_t *element = container_of(slow, element_t, list);
e_free(element);

q_delete_dup

由於 github action 上的 ubuntu 以及我自己的 debian 版本所使用的 glibc 版本皆低於 2.38,而 2.38 後的 strcmp 有做優化,在這之前的 strcmp 都是一個字元做比較,效能不佳。

某些濫用「優化」的語境,根本與「改良」和「改善」無異,那為何不直接講「改良」和「改善」呢?

\(\to\) 資訊科技詞彙翻譯

  • Debian 12.4
$ ldd --version
ldd (Debian GLIBC 2.36-9+deb12u4) 2.36
Copyright (C) 2022 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Written by Roland McGrath and Ulrich Drepper.
  • Ubuntu 22.04.3 LTS
$ ldd --version
ldd (Ubuntu GLIBC 2.35-0ubuntu3.6) 2.35
Copyright (C) 2022 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Written by Roland McGrath and Ulrich Drepper.
  • glibc 2.38 前的 strcmp 實作
int
STRCMP (const char *p1, const char *p2)
{
  const unsigned char *s1 = (const unsigned char *) p1;
  const unsigned char *s2 = (const unsigned char *) p2;
  unsigned char c1, c2;

  do
    {
      c1 = (unsigned char) *s1++;
      c2 = (unsigned char) *s2++;
      if (c1 == '\0')
        return c1 - c2;
    }
  while (c1 == c2);

  return c1 - c2;
}

因此這邊將優化後的 strcmp 做移植,作為 newstrcmp。

list_for_each_safe (node, safe, head) {
    element_t *element = container_of(node, element_t, list);
    if (!check || newstrcmp(check, element->value)) {
        check = element->value;
        continue;
    }
    list_del(node);
    e_free(element);
} 

q_swap

for 迴圈同時使用兩個節點,一次移動兩步,當其中有一個為 head 時停止。

void q_swap(struct list_head *head)
{
    struct list_head *nodea, *nodeb, *safea, *safeb, *tmp = NULL;
    for (nodea = head->next, nodeb = nodea->next,
         safea = nodea->next->next, safeb = nodeb->next->next;
         nodea != head && nodeb != head;
         nodea = safea, nodeb = safeb,
         safea = nodea->next->next, safeb = nodeb->next->next) {
        list_move(nodea, nodeb);
    }
}

q_reverse

一個一個的把 head->prev 移到 head->next 後面。

void q_reverse(struct list_head *head)
{
    if (!head)
        return;
    for (struct list_head *node = head, *move = head->prev; node != move;
         node = move, move = head->prev) {
        list_move(move, node);
    }
}

q_reverseK

從頭迭代 k 次並把這個範圍的節點取出來另外存成一個鏈結串列以後做一次 q_reverse 再放回來原來的位置。

for (first = head->next, last = first; first != head;
     first = lastnext, last = first) {
    for (int i = 0; i < k - 1 && last != head; i++, last = last->next) {
    }
    if (last == head)
        return;
    firstprev = first->prev;
    lastnext = last->next;
    lastnext->prev = firstprev;
    firstprev->next = lastnext;
    tmphead.next = first;
    first->prev = &tmphead;
    tmphead.prev = last;
    last->next = &tmphead;
    q_reverse(&tmphead);
    list_splice(&tmphead, firstprev);
}

q_ascend 與 q_descend

從後面往前迭代,當出現大於/小於前一個節點時,便刪除該節點。

for (node = head->prev, safe = node->prev; node != head;
     node = safe, safe = node->prev) {
    element = container_of(node, element_t, list);
    if (check && newstrcmp(check, element->value) op 0) {
        list_del(node);
        e_free(element);
        continue;
    }
    check = element->value;
    len++;
}

q_sort

參考 Linux 核心的鏈結串列排序 並且閱讀 lib/list_sort.c,這邊採用 Queue-Mergesort。

先寫一個巨集來處理合併兩個列表

#define mergelist(nodea, nodeb, mergeadd, mergesplice, mergehead)              \
    {                                                                          \
        struct list_head *lastnode = nodeb, *safe, **pnode;                    \
        while (nodea && nodeb) {                                               \
            element_t *elementa = container_of(nodea, element_t, list),        \
                      *elementb = container_of(nodeb, element_t, list);        \
            bool cmpresult = ((!descend) * 2 - 1) *                            \
                                 newstrcmp(elementa->value, elementb->value) < \
                             0;                                                \
            pnode = cmpresult ? &nodea : &nodeb;                               \
            safe = (*pnode)->next;                                             \
            lastnode = cmpresult ? nodeb : nodea;                              \
            mergeadd(*pnode, mergehead);                                       \
            *pnode = safe;                                                     \
        }                                                                      \
        mergesplice(lastnode, mergehead);                                      \
    }

sort 總共有兩個階段,第一個階段是將 list 移到 pending 並且對部分節點做合併,第二階段是將所有 pending 做合併。

第一階段的每個迴圈先做 count++ 接著判斷是否做合併最後將原本的 pending 放到 list 上並且 list 成為新 pending 然後切到下一個 list。當需要合併時,對 countffs 得到需要對哪兩個列表做合併,使用 mergelist 處理合併,最後更新 *ppending

第二階段時先對 head 做初始化,並且使用 mergelisthead 與目前的 pending 做合併。

q_merge

每兩個鏈結串列一組做合併,遇到長度為 0 就跳過,持續到只有一條鏈結串列有東西為止。

do {
    count = 0;
    mergehead = NULL;
    list_for_each_safe (node, safe, head) {
        queue_contex_t *queue = container_of(node, queue_contex_t, chain);
        if (!queue->q || (!queue->size && queue->q != head->next)) {
            continue;
        }
        count++;
        if (mergehead) {
            mergehead->q->prev->next = NULL;
            queue->q->prev->next = NULL;
            struct list_head *nodea = mergehead->q->next,
                             *nodeb = queue->q->next;
            INIT_LIST_HEAD(mergehead->q);
            INIT_LIST_HEAD(queue->q);
            mergehead->size = 0;
            queue->size = 0;
            mergelist(nodea, nodeb, descend, queuemergeadd,
                      queuemergesplice, mergehead);
            queue = NULL;
            count--;
        }
        mergehead = queue;
    }
} while (count > 1);

當你選定合併排序,現有的測試案例要如何涵蓋合併排序的最差狀況呢?

研讀論文〈Dude, is my code constant time?〉並改進 lab0-c 的 dudect

dudect 原始程式搭配對照。

  • dudect_main <-> doit
  • prepare_inputs <-> prepare_inputs
  • measure <-> measure
  • update_statistics <-> update_statistics
  • report <-> report

其中缺少 percentile 相關用來去除極端值的程式碼。將該功能寫入即可。

指出論文和實作的出入之處,尚有其他!

prepare_inputs(input_data, classes);
bool ret = measure(before_ticks, after_ticks, input_data, mode);
differentiate(exec_times, before_ticks, after_ticks);
+prepare_percentiles(exec_times);
update_statistics(exec_times, classes);
ret &= report();