2020q1 第 3 週測驗題

tags: linux2020

目的: 檢驗學員對 linked list 和非連續記憶體操作, bitwise 操作, 指標操作 的認知

作答表單

---

測驗 1

XOR 運算特性:

• $A\oplus A=0$
• $A\oplus 0=A$
• $A\oplus 1=\mathrm{\neg }A$
• $(A\oplus B)\oplus B=A$

以下程式碼是個 XOR linked list 的實作，在這樣的資料結構可表示為:

       1    2    3    4
data  HAT  CAT  EAT  BAT
link   2    2    6    3

要往下一格移動時，我們需要前一格在哪和這一格的位置。例如我們現在在 HAT (1), 已知前一格是 (0)，那麼下一格就是 link(1) XOR 0 = 2 XOR 0 = 2，也就是 CAT。繼續，現在位於 CAT (2)，前一格在 (1)，於是下一格就是 link(2) XOR 1 = 2 XOR 1 = 3，亦即 EAT，依此類推。只要當找出來的下一格是 (0) 就結束。

#include <stdint.h>

typedef struct __list list;
struct __list {
    int data;
    struct __list *addr;
};

#define XOR(a, b) ((list *) ((uintptr_t) (a) ^ (uintptr_t) (b)))

void insert_node(list **l, int d) {
    list *tmp = malloc(sizeof(list));
    tmp->data = d;

    if (!(*l)) {
        tmp->addr = NULL;
    } else {
        (*l)->addr = XOR(tmp, (*l)->addr);
        tmp->addr = *l;
    }
    *l = tmp;
}

void delete_list(list *l) {
    while (l) {
        list *next = l->addr;
        if (next)
            next->addr = XOR(next->addr, l);
        free(l);
        l = next;
    }
}

在 __list 結構體內雖僅有一個 struct __list *addr 指標型態的物件，但卻可實作雙向的 linked list，就是憑藉著上述的實作技巧。XOR linked list 的優勢很顯著，對空間的佔用更為精簡:

隨著資料處理量的增長，效益更明顯:

與尋常作法相比，佔用的儲存空間比值會趨近

$67\mathrm{\%}$。

接著我們嘗試撰寫針對 XOR linked list 的排序程式，採用遞增順序:

list *sort(list *start)
{
    if (!start || !start->addr)
        return start;

    list *left = start, *right = start->addr;
    left->addr = NULL;
    right->addr = XOR(right->addr, left);

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

    for (list *merge = NULL; left || right;) {
        if (!right || (left && left->data < right->data)) {
            list *next = left->addr;
            if (next)
                next->addr = XOR(left, next->addr);

            if (!merge) {
                start = merge = left;
                merge->addr = NULL;
            } else {
                merge->addr = LL1;
                left->addr = LL2;
                merge = left;
            }
            left = next;
        } else {
            list *next = right->addr;
            if (next)
                next->addr = XOR(right, next->addr);

            if (!merge) {
                start = merge = right;
                merge->addr = NULL;
            } else {
                merge->addr = RR1;
                right->addr = RR2;
                merge = right;
            }
            right = next;
        }
    }

    return start;
}

請補完上述排序程式碼。

作答區

LL1 = ?

• (a) right
• (b) left
• (c) merge
• (d) XOR(merge, left)
• (e) XOR(merge, right)
• (f) XOR(merge, left->addr)
• (g) XOR(merge, right->addr)
• (h) XOR(merge->addr, left)
• (i) XOR(merge->addr, right)

LL2 = ?

• (a) right
• (b) left
• (c) merge
• (d) XOR(merge, left)
• (e) XOR(merge, right)
• (f) XOR(merge, left->addr)
• (g) XOR(merge, right->addr)
• (h) XOR(merge->addr, left)
• (i) XOR(merge->addr, right)

RR1 = ?

• (a) right
• (b) left
• (c) merge
• (d) XOR(merge, left)
• (e) XOR(merge, right)
• (f) XOR(merge, left->addr)
• (g) XOR(merge, right->addr)
• (h) XOR(merge->addr, left)
• (i) XOR(merge->addr, right)

RR2 = ?

• (a) right
• (b) left
• (c) merge
• (d) XOR(merge, left)
• (e) XOR(merge, right)
• (f) XOR(merge, left->addr)
• (g) XOR(merge, right->addr)
• (h) XOR(merge->addr, left)
• (i) XOR(merge->addr, right)

延伸問題:

1. 解釋上述 XOR linked list 排序實作的原理，並指出其中可改進之處;
2. 在 Wikipedia 關於合併排序的詞目中，談及 Optimizing merge sort，我們可知道一種最佳化策略是：在子序列大小達到
   $S$ 時就不再繼續分割，此時這個
   $S$ 為可完整放進處理器 cache 中的元素數量。每個大小為
   $S$ 的子序列，都透過適用於小規模 in-place (即不需要額外配置記憶體) 排序演算法（如插入排序或泡沫排序）進行排序，以減少在記憶體內交換特定區域的次數。在小型子序列排序完畢後，再以典型的遞迴型合併排序完剩下的部份。
   若可找到一個恰當的
   $S$， 便能有效的同時利用到插入排序和合併排序的優點，並減少原始的合併排序當中 locality 不好的影響。請觀察你的硬體組態 (如 L1 data cache 的容量和行為)，以上述策略實作效率更好的 XOR linked list 排序程式。過程中應該充分量化數據並進行視覺化處理。
3. 修改 lab0-c 裡頭的 harness.c，將原本內部使用的 doubly-linked list 換為 XOR linked list，觀察記憶體佔用率的變化，可設計頻繁的 test_malloc / test_free 呼叫交錯情境。

---

測驗 2

考慮以下 singly-linked list 程式:

#include <stddef.h>
struct node {
    int data;
    struct node *next;
} *head;

void insert(struct node *newt) {
    struct node *node = head, *prev = NULL;
    while (node != NULL && node->data < newt->data) {
        prev = node;
        node = node->next;
    }
    newt->next = node;
    if (prev == NULL)
        head = newt;
    else
        prev->next = newt;
}

可透過以下 pointer to pointer 改寫 insert 函式，功能等價但更簡潔，如下:

void insert(struct node *newt)
{
    struct node **link = &head;
    while (*link && AA)
        BB;
    newt->next = *link;
    *link = newt;
}

請補完程式碼。

作答區

AA = ?

• (a) (link)->data < newt->data
• (b) *link->data < newt->data
• (c) (*link)->data < newt->data
• (d) **link->data < newt->data

BB = ?

• (a) link = &(*link)->next
• (b) *link = *link->next
• (c) (*link) = (*link)->next
• (d) link = (*link)->next

延伸問題:

1. 解釋程式運作原理、對執行時間的影響 (考慮到 branch predictor 行為)，和指出其實作限制;
2. 在 Linux 核心找出運用類似的手法的程式碼並解說
   • 提示: 可參見 bfq_insert 和 rb_link_node 操作 red-black tree 的手法

---