2023q1 Homework1 (quiz1)

contributed by < WangHanChi >

作業要求

測驗一

解釋上述程式碼運作原理

這個部份的程式定義了新的結構體 item

#include <stdint.h>
#include "list.h"

struct item {                         
    uint16_t i;
    struct list_head list;
};

這個程式比較了 item 中的 i 這個值，並且回傳值為參數1 - 參數2

static inline int cmpint(const void *p1, const void *p2)
{
    const uint16_t *i1 = (const uint16_t *) p1;
    const uint16_t *i2 = (const uint16_t *) p2;
    return *i1 - *i2;
}

以下的程式碼進行了 quick_sort

首先設定了兩個 head 並且初始化，一個放 less ，另一個放 greater
設定一個 pivot ，作為比較大小的基準
走訪所有的鏈結串列，並且逐一比較大小
對二條鏈結串列排序
最後將其接起來

static void list_sort(struct list_head *head)
{
    if (list_empty(head) || list_is_singular(head))
        return;

    struct list_head list_less, list_greater;
    INIT_LIST_HEAD(&list_less);
    INIT_LIST_HEAD(&list_greater);

    struct item *pivot = list_first_entry(head, AAA, BBB);
    list_del(&pivot->list);

    struct item *itm = NULL, *is = NULL;
    list_for_each_entry_safe(itm, is, head, list) {
        if (cmpint(&itm->i, &pivot->i) < 0)
            list_move(&itm->list, &list_less);
        else
            list_move(&itm->list, &list_greater);
    }

    list_sort(&list_less);
    list_sort(&list_greater);

    list_add(&pivot->list, head);
    list_splice(&list_less, head);
    list_splice_tail(&list_greater, head);
}

由 list_first_entry 的定義可以知道，AAA 需要填入的 type 也就是 struct item，而 BBB 會需要填入的就是 member ，接下來 CCC 會是需要走訪所有 list 的迴圈函式，又因為會需要移動節點，所以選擇使用 list_for_each_entry_safe 。而至於 quick sort 的 for-loop 會將點分配給基準值 less 區 與 greater 區 ，所以 DDD 與 EEE 都會是移動節點的巨集，所以就會是使用 list_move_tail 到最尾端。最後要把 greater 區 移動到鏈結串列的尾巴，所以選用 list_splice_tail。

~~> AAA = struct item > BBB = list > CCC = list_for_each_entry_safe > DDD = list_move_tail > EEE = list_move_tail > FFF = list_splice_tail~~

著重在程式碼和其原理，不用貼出參考答案。隨堂測驗是引導學員「誠實面對自己」的手段，我們不該拘泥於其形式。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

提出程式碼的可改進地方並實作

由程式碼可以看出 pivot 的選選擇相當的重要，若是選擇不當的話，可能會造成 less 區 與 greater 區 失衡。例如選到 pivot 是最小值的時候，會使得這次遞迴無效。

為了解決上述的問題，目前有兩種解決方法

使用老師所說的 Hybrid Sort
改善 pivot 的選擇

測驗二

解釋上方程式碼運作原理，指出設計和實作的缺失

此題為延續上題，改成使用非遞迴的版本

可以看到下面的 stack 會先被初始化後再把 head 以及整條鏈結串列都放進這個 stack 裡面

struct list_head stack[MAX_DEPTH];
for (int i = 0; i < MAX_DEPTH; i++)
    INIT_LIST_HEAD(&stack[i]);
int top = -1;
list_splice_init(head, &stack[++top]);

接著利用 list.h 中提供的函式把 stack 頂端的節點放入 partition 中

INIT_LIST_HEAD(&partition);
list_splice_init(&stack[top--], &partition);

分別建立出 less 區 與 greater 區 分別儲存比 pivot 大跟小的節點。而這邊 pivot 的選擇就跟測驗 1 的選擇方法一致

if (!list_empty(&partition) && !list_is_singular(&partition)) {
        struct list_head list_less, list_greater;
        INIT_LIST_HEAD(&list_less);
        INIT_LIST_HEAD(&list_greater);
        struct item *pivot =
            list_first_entry(&partition, struct item, list);
        list_del(&pivot->list);
        INIT_LIST_HEAD(&pivot->list);

這邊也跟測驗 1 的方法一致，走訪所有的節點，再分成 less 區 與 greater 區，因此 GGGG 也會是 list_for_each_entry_safe

struct item *itm = NULL, *is = NULL;
GGGG (itm, is, &partition, list) {
list_del(&itm->list);
if (cmpint(&itm->i, &pivot->i) < 0)
    list_move(&itm->list, &list_less);
else
    list_move(&itm->list, &list_greater);
}

下面這行程式碼的功能是將 pivot 插在 list_less 的後面，所以 HHHH 應該使用 list_move_tail 。再來是檢查 less 區 與 greater 區是否為空，若不是空的就將其加入 stack 中，所以 IIII 與 JJJJ 都要填入 &stack[++top]

HHHH (&pivot->list, &list_less);
if (!list_empty(&list_greater))
    list_splice_tail(&list_greater, IIII);
if (!list_empty(&list_less))
list_splice_tail(&list_less, JJJJ);

這邊探討的是假如 partition 只剩下一個節點的情況應該要怎麼處理，可以看到他在這邊將 partition 加到 stack 中後，執行了 while-loop，這邊我想不透為何要這樣執行，因此參考 yanjiew1，發現是要將 stack top 上的 list 節點移除，所以 KKKK 應該要填入的是 &stack[top--]。

else {
    top++;
    list_splice_tail(&partition, &stack[top]);
    while (top >= 0 && list_is_singular(&stack[top])) {
        struct item *tmp =
            list_first_entry(&stack[top], struct item, list);
        list_del(&tmp->list);
        INIT_LIST_HEAD(KKKK);
        list_add_tail(&tmp->list, head);
    }
}

提出程式碼的可改進地方並實作

目前觀察到的問題為

程式碼一開始所定義的 MAX_DEPTH 只有 512，因此若是要處理節點數超過 512 個的鏈結串列就會超出界線，或是遇到了 Worst case (例如從 257 到 1 的序列)，所設定的 stack 就會發生 buffer overflow

比較測驗 `1` 和測驗 `2` 的程式碼

測驗 1 (遞迴版本)

因為要在 lab0-c 這個專案下執行，所以需要修改一些部份才能夠正常執行，我將修改的程式碼放在這裡了，然後也會使用 lab0-c 內部的 time 以及 perf 工具才進行效能的測試

次數	第一次	第二次	第三次	平均
10萬筆	0.027	0.026	0.027	0.027
20萬筆	0.069	0.074	0.070	0.071
30萬筆	0.145	0.149	0.143	0.146
40萬筆	0.257	0.248	0.248	0.251
50萬筆	0.368	0.381	0.376	0.375
60萬筆	0.485	0.455	0.460	0.467
70萬筆	0.598	0.589	0.592	0.593
80萬筆	0.722	0.739	0.715	0.725
90萬筆	0.804	0.810	0.814	0.809
100萬筆	0.985	0.943	0.930	0.953

善用 gnuplot 製圖。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

好的，學生會多練習 gnuplot 並在下方附上效能比對圖

測驗 2 (非遞迴版本)

同樣也是修改了一些部份，使其可以在lab0-c 這個專案下執行，將檔案放在這邊

次數	第一次	第二次	第三次	平均
10萬筆	0.033	0.034	0.033	0.033
20萬筆	0.083	0.086	0.088	0.086
30萬筆	0.183	0.163	0.173	0.173
40萬筆	0.281	0.320	0.315	0.305
50萬筆	0.404	0.408	0.391	0.401
60萬筆	0.574	0.588	0.528	0.563
70萬筆	0.650	0.651	0.626	0.642
80萬筆	0.803	0.779	0.829	0.804
90萬筆	0.935	0.921	0.951	0.936
100萬筆	1.025	1.076	1.006	1.036

效能比較

從上方的詳細數據或是下方的圖表看出非遞迴的版本從 10 萬 筆資料後的效能已經落後遞迴的版本了，為了確保完整，因此我嘗試先從資料筆數更低的部份觀察

資料 (10 萬筆 ~ 100 萬筆)，曲線越靠近右下方越好

圖例不清楚的圖

資料 (1 萬筆 ~ 10 萬筆)，曲線越靠近右下方越好

圖例不清楚的圖

可以從上面的兩張圖片觀察到，不論在資料量多少的情況下，非遞迴的版本花費的時間總是比遞迴的版本還要多，因此打算用 perf 工具來深入觀察，以下測試是在資料比數為 50 萬筆的時候

遞迴版本

 Performance counter stats for './qtest -f traces/trace-sort.cmd' (10 runs):

        24,990,278      cache-misses              #   32.899 % of all cache refs      ( +-  0.52% )
        75,427,362      cache-references                                              ( +-  0.41% )
     2,412,927,383      instructions              #    0.90  insn per cycle           ( +-  0.08% )
     2,703,750,725      cycles                                                        ( +-  0.45% )

           0.57981 +- 0.00242 seconds time elapsed  ( +-  0.42% )

非遞迴版本

 Performance counter stats for './qtest -f traces/trace-sort.cmd' (10 runs):

        30,481,432      cache-misses              #   34.391 % of all cache refs      ( +-  0.61% )
        89,248,407      cache-references                                              ( +-  0.84% )
     2,819,848,018      instructions              #    0.96  insn per cycle           ( +-  0.18% )
     2,983,632,953      cycles                                                        ( +-  0.49% )

           0.63051 +- 0.00329 seconds time elapsed  ( +-  0.52% )

從 cache-misses 以及 instructions 的數量就可以發現，非遞迴版的執行速度比起遞迴版的還要慢是相當正常的。因為在指令的部份，非遞迴版本就已經多許多了，在相同的電腦環境之下，是很難超越遞迴版本的。

圖例的單位應採 SI prefix，亦即 K, M, G 等等，避免用「萬」。
座標軸的文字用英語書寫。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

已修正, 謝謝老師

不好的圖

提出效能改進方案，特別是避免依賴 `MAX_DEPTH`

測驗三

解釋上述程式碼運作原理，指出其實作缺陷並改進

首先可以看到下面的程式碼

定義了 xor_node_t 與 xor_list_t 這兩個結構體，其中，可以把 xor_list_t 這個看作是整個 xor_linked_list 的 head 節點，它當中包含了 head, tail 與 count ，用來儲存這條 xor_linked_list 的所有資訊。

再來看到 XOR_COMP 這個巨集，可以知道會是通過 Exclusive or (^) 這樣的位元運算所得到下一個地址的，所以 LLLL 會是 (uintptr_t)(a) ^ (uintptr_t)(b)

typedef struct _xorlist_node {
    struct _xorlist_node *cmp;
} xor_node_t;

typedef struct _xor_list_struct {
    xor_node_t head, tail;
    uint32_t count;
} xor_list_t;

#define XOR_COMP(a, b) ((xor_node_t *) (LLLL))

下面這段程式碼就是運用了剛剛所定義好的巨集，並且搭配 assert 這個功能來進行實作的
接下來先在終端機輸入

$ man assert

來取得第一手 assert 的資料

assert

ASSERT(3) Linux Programmer's Manual ASSERT(3)

NAME
assert - abort the program if assertion is false

SYNOPSIS
#include <assert.h>

   void assert(scalar expression);

DESCRIPTION
This macro can help programmers find bugs in their programs, or handle exceptional cases via a crash that will produce limited debugging output.

   If  expression is false (i.e., compares equal to zero), assert() prints an error message to standard error and terminates the program by calling abort(3).  The error message
   includes the name of the file and function containing the assert() call, the source code line number of the call, and the text of the argument; something like:

       prog: some_file.c:16: some_func: Assertion `val == 0' failed.

   If the macro NDEBUG is defined at the moment <assert.h> was last included, the macro assert() generates no code, and hence does nothing at all.  It is not recommended to de‐
   fine NDEBUG if using assert() to detect error conditions since the software may behave non-deterministically.

RETURN VALUE
No value is returned.

ATTRIBUTES
For an explanation of the terms used in this section, see attributes(7).

   ┌──────────┬───────────────┬─────────┐
   │Interface │ Attribute     │ Value   │
   ├──────────┼───────────────┼─────────┤
   │assert()  │ Thread safety │ MT-Safe │
   └──────────┴───────────────┴─────────┘

CONFORMING TO
POSIX.1-2001, POSIX.1-2008, C89, C99. In C89, expression is required to be of type int and undefined behavior results if it is not, but in C99 it may have any scalar type.

BUGS
assert() is implemented as a macro; if the expression tested has side-effects, program behavior will be different depending on whether NDEBUG is defined. This may create
Heisenbugs which go away when debugging is turned on.

SEE ALSO
abort(3), assert_perror(3), exit(3)

COLOPHON
This page is part of release 5.10 of the Linux man-pages project. A description of the project, information about reporting bugs, and the latest version of this page, can
be found at https://www.kernel.org/doc/man-pages/.

GNU 2017-09-15 ASSERT(3)

可以確保 assert 中的敘述必定為 ture ，否則就會中斷程式並且報錯，因此運用在這個函式中，就可以得到 n1 && n2 必定有值，再去回傳 XOR_COMP 這個巨集的執行結果

static inline xor_node_t *address_of(xor_node_t *n1, xor_node_t *n2)
{
    assert(n1 && n2);
    return XOR_COMP(n1, n2);
}

這邊定義了許多風格近似於 list.h 的巨集，包括了 container_of 等等的
可以發現到這邊找尋下一個節點的方式都是透過剛剛所定義好的 address_of

#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

#define xorlist_for_each(node, rp, rn, list)                        \
    for (rp = &(list)->head, node = rp->cmp; node != &(list)->tail; \
         rn = address_of(rp, node->cmp), rp = node, node = rn)

#define xorlist_for_each_prev(node, rp, rn, list)                   \
    for (rp = &(list)->tail, node = rp->cmp; node != &(list)->head; \
         rn = address_of(rp, node->cmp), rp = node, node = rn)

#define xorlist_for_each_from(node, pos1, pos2, rp, rn, list) \
    for (rp = pos2, node = pos1; node != &(list)->tail;       \
         rn = address_of(rp, node->cmp), rp = node, node = rn)

#define xorlist_for_each_from_prev(node, pos1, pos2, rp, rn, list) \
    for (rp = pos1, node = pos2; node != &(list)->head;            \
         rn = address_of(rp, node->cmp), rp = node, node = rn)

這邊使用了老師所提到的 C 語言前置處理器，詳情可以參考你所不知道的 C 語言：前置處理器應用篇。 xorlist_delete_prototype 巨集的作用是定義一個名為 _xorlist_delete_##name 的函數，這個函數接受一個名為 node 的 xor_node_t 指標參數。這個函數在實現時會被用來從一個 xor_linked_list 中刪除給定節點。xorlist_delete_call 巨集的作用是展開為 _xorlist_delete_##name ，這裡的 name 是在之前定義 xorlist_delete_prototype 巨集時傳入的。

/* Note that when the delete function success is must return 0. */
#define xorlist_delete_prototype(name, node) \
    int _xorlist_delete_##name(xor_node_t *node)

#define xorlist_delete_call(name) _xorlist_delete_##name

下面的函式與巨集主要在初始化節點，功能相似於 INIT_LIST_HEAD 及 LIST_HEAD

static inline xor_node_t *xornode_init(xor_node_t *n)
{
    assert(n);
    n->cmp = NULL;
    return n;
}

#define XORNODE_INIT(n) \
    do {                \
        (n).cmp = NULL; \
    } while (0)

#define XORLIST_INIT(h)           \
    do {                          \
        (h).head.cmp = &(h).tail; \
        (h).tail.cmp = &(h).head; \
        (h).count = 0;            \
    } while (0)

這個函式的命名其實沒有很明確，他是把節點新增到 head 的下一個，若是改叫做 xorlist_add_head 會明確很多

int xorlist_add(xor_list_t *list, xor_node_t *n)
{
    xor_node_t *real_next;

    if (!n)
        return ENOMEM;

    xor_node_t *real_prev = &list->head;
    xor_node_t *node = real_prev->cmp;
    if (node == &list->tail)
        real_next = &list->tail;
    else
        real_next = node;
    real_prev->cmp = n;
    n->cmp = XOR_COMP(real_prev, real_next);
    real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, real_next->cmp));
    list->count++;

    return 0;
}

xorlist_add_head 的步驟可以分成目前只有兩個節點以及三個節點以上
首先先從只有兩個節點的部份開始:

原本鏈結串列只有兩個節點

Address	A	B
特別名稱	head	tail
cmp	B	A

插入一個節點 C，需要改變的是 A 與 B 的 cmp 以及 C 的 cmp 是從 A^B 而來的

Address	A	C	B
特別名稱	head	node 1	tail
cmp	B C	$A \oplus B$	A C

接著插入節點 D，修改加入節點的前一個節點以及後一個節點的 cmp 以及重新指派新插入節點的 cmp

Address	A	D	C	B
特別名稱	head	node 2	node 1	tail
cmp	C D	$A \oplus C$	$D \oplus B$	C

由此發現，插入節點主要就是修改插入節點前後的 cmp 以及自己的 cmp
可以再插入一個節點來驗證此發現

插入節點 E ，並套用上述結論，發現可以適用!

Address	A	E	D	C	B
特別名稱	head	node 3	node 2	node 1	tail
cmp	D E	$A \oplus D$	$E \oplus C$	$D \oplus B$	C

在上述 XOR linked list 的基礎，實作測驗 1 和 2 提及的快速排序演算法

Reference

gnuplot 語法解說和示範

2023q1 Homework1 (quiz1)

測驗一

解釋上述程式碼運作原理

提出程式碼的可改進地方並實作

測驗二

解釋上方程式碼運作原理，指出設計和實作的缺失

提出程式碼的可改進地方並實作

比較測驗 1 和測驗 2 的程式碼

測驗 1 (遞迴版本)

測驗 2 (非遞迴版本)

效能比較

提出效能改進方案，特別是避免依賴 MAX_DEPTH

測驗三

解釋上述程式碼運作原理，指出其實作缺陷並改進

在上述 XOR linked list 的基礎，實作測驗 1 和 2 提及的快速排序演算法

Reference

Read more

2023q1 Homework1 (lab0)

cm4hbm

2023q1 Homework3 (fibdrv)

rbtmalloc 開發紀錄

比較測驗 `1` 和測驗 `2` 的程式碼

提出效能改進方案，特別是避免依賴 `MAX_DEPTH`