2020q1 Homework3 (quiz3)

contributed by < StevenChen8759 >

注意共筆書寫格式規範！

jserv

tags: linux2020

quiz3內容說明

:Camera: 測驗一 - XOR Linked List

XOR Linked List 之排序實作填答與原理

• 程式碼實作敬請參閱我的github -> list_xor.c
• 串列是如何透過XOR的運算找到上一節點 or 下一節點的位址？
  • 欲找到串列中某一節點 A 的上一節點，必須先知道 A 之下一節點的位址，並將該位址與 A->addr 內之值做XOR運算，所得結果即是上一節點的位址。尋找下一節點的方式相同，但其方向相反。即：A之下一節點位址 = XOR( A之上一節點位址, A->addr )，如下列範例所示：

用 GraphViz 重新製圖

jserv

• list_xor.c 中的填答如下：

#define LL1 XOR(merge->addr, left)  // LL1 Select (h)
#define LL2 merge                   // LL2 Select (c)
#define RR1 XOR(merge->addr, right) // RR1 Select (i)
#define RR2 merge                   // RR2 Select (c)

• 參考此處實現的分割方法，會將 list 分割成下圖之格式，並逐一合併：
  
• 在每一次合併的第一個 for iteration 中，因為串列頭的 addr 欄位之位址必恰為該節點之下一節點的位址 (此處以 right 為例子， left 亦同)，因為 right->addr = XOR( 0, right->next) = right->next，故我們可直接讀取 right->addr 的值得知 right->next 的位址，並利用指標 next 指向下一節點的位址。此時我們可透過 XOR(right, right->addr) 取得 right 之後二節點的位址，並暫存在 next->addr 欄位。

        list *next = right->addr;
        if (next)
            next->addr = XOR(right, next->addr);

• 因為此時 merge 指向 NULL ，故將指標 start 以及 merge 指向 right ， 又因 right 之前一節點位址為空，故指派 right->addr 為 NULL，在完成以上串列走訪之後，將 right 移動至串列的下一個位置，即 next 所指向之節點。

        if (!merge) {
                start = merge = right;
                merge->addr = NULL;
        }

         right = next;

• 在每一次合併的第二個 for iteration 起， right 會恆指向子串列尚未走訪的第一個節點，而 merge 恆指向此時 right 指向節點的前一節點，這樣才能在串列進行合併時， 修改 right 前一節點的 addr 欄位，使其可透過 XOR 操作找到合併的節點。

        /* 修改 merge 節點的 addr 欄位，由前一節點位址 XOR 下一節點位址得到 */
        merge->addr = XOR(merge->addr, right);
        /* 將前一節點的位址暫存在 right 之 addr 欄位內 */
        right->addr = merge;
        /* 修改 merge 指標以供下一次的 addr 計算 */
        merge = right;

• 在此處我們利用了 right 的欄位 addr 暫存前一節點的位址，待下一輪的 for iteration 決定下一個合併的節點後，再計算實際的 addr 值。
• 在最後一個 for iteration 中，left 與 right 皆指向 NULL，因此只要直接指派合併串列尾端節點的 addr 欄位為其前一節點的位址即可。
• 綜合以上分析，最終的程式碼實作如下：

list *sort(list *start)
{
    /* Return while input is equal or less than 1 element */
    if (!start || !start->addr)
        return start;

    /* Divide -> Cut to two sublist */
    list *left = start, *right = start->addr;
    left->addr = NULL; 			// Left sublist with 1 element only
    right->addr = XOR(right->addr, left);     // Right sublist with n-1 elements

    /* Conquer -> Sort each sublist */
    left = sort(left);   // Sort left list
    right = sort(right); // Sort right list

    /* Combine - List Merging */
    // loop: merge start with NULL, repeat until left and right are both NULL
    for (list *merge = NULL; left || right;) {
    
        // [Right is NULL] OR [left is not NULL and left data is smaller than right data]
        if (!right || (left && left->data < right->data)) {
            
            list *next = left->addr;  // Let next points to addr field of left (Fetch next node address of right)
            // Next is not NULL, Calculate next two node after right, and store in the addr field of next 
            if (next)
                next->addr = XOR(left, next->addr);

            // Merge pointer is initially NULL, assign merged list start pointer and store the previous node address of the node which merge points to 
            if (!merge) {
                start = merge = left;
                merge->addr = NULL;
            // Merge is not null, calculate merge->addr and do pointer assignment
            } else {
                merge->addr = XOR(merge->addr, left);  // Calculte real bit mask, with previous value of merge and current node which left points to
                left->addr = merge;   // Store previous node address to left->addr for merge calculation in the next run
                merge = left;       // Pointer assignment for element to do merge in the next run
            }
            left = next;  // Current node in the leftlist is traversed, move to next position
            
        // [Right is NOT NULL] AND [left is NULL OR left data is bigger than or equal to right data]
        } else {
            list *next = right->addr;
            if (next)
                next->addr = XOR(right, next->addr);

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

    return start;
}

XOR Linked List 之實作可改進之處

• 觀察我們在 insert 的實作，可發現函式會操作傳入指標指向新增插入的元素。如下圖所示：
  
• 但若要在串列中間之某節點後方插入資料，則我們必須對範例串列做以下修改：
  
• 因此我們必須讓 insert 函式能夠知道插入節點的前一節點或後一節點，才能計算出正確的 addr (如同 sort 函式內的指標操作技巧)，但目前的實現僅允許在串列的頭或尾插入元素，因為我們並無法透過傳入單一指標至 insert 函式，計算出前一節點的位址。
• 解決方法：利用兩個指標操作 XOR Linked List ，這兩個指標必須同時指向兩個相鄰的節點，透過兩個指標的協同操作，即可克服上述的操作障礙，如同上述 sort 函式內，以 merge 與 left 或 right 指標之實作。

XOR Linked List 針對 Merge Sort 的效能改善 - 子串列分割

• 觀察 list_xor.c 中函式 sort 的實現，可以發現在 sublist 的分割上，左邊的 list 永遠只有一個元素，而右邊的 list 恆分割到
  $n-1$ 個元素，假設每一次的 Merge 耗費
  $O(n)$，則可基於此分割方式做下列複雜度分析：
  • $T(n)=T(n-1)+O(n)$
  • $T(n)=n+(n-1)+...+1$
  • $T(n)={\displaystyle \frac{n\cdot (n+1)}{2}}=O(n^2)$
• 透過上列分析，我們可以發現這樣的分割方式並無法得到 Merge Sort 原有的
  $O(n\log n)$ 時間複雜度。故我們需在串列的分治策略上做一些調整。
• 改善的 Merge Sort 分治策略如下：
  • 將 list 之 head 與 tail 額外記錄，並同時傳入 sort 函式內。
  • 同時由 head 與 tail 出發，同時往中間移動，直到兩指標相碰時停止，由相碰之位址分割成左右子串列。
  • 遞迴呼叫 sort 函式，以完成左右子串列之排序。
  • 最後透過指標操作，將左右子串列合併成已排序的串列。
• 透過上述方法，可保證兩個分割出來的子串列是平均分割的，此處同樣假設每一次的 Merge 耗費
  $O(n)$，可得以下時間複雜度分析：
  • $T(n)=2\cdot T({\displaystyle \frac{n}{2}})+O(n)$
  • $T(n)=O(n\log n)$ <By Master Theorem>

XOR Linked List 針對 Merge Sort 的效能改善 - Locality 優化

• 首先，我們先回顧 XOR Linked list 的結構宣告：

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

• XOR Linked list 的一個節點的大小為 8 Bytes
  • int 佔用 4 Bytes
  • addr 佔用 4 Bytes
• 透過 lscpu 查看 Cache 的配置 (註: CPU 為 Intel Core i5-5200u @ 2.20GHz)

$ lscpu | grep cache
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              3072K

• 在此 CPU 中 L1 data cache 配置了
  $32KB$，假設忽略快取碰撞、指標存取與其他程序造成的影響，則在串列長度在
  ${\displaystyle \frac{32768}{8}}=4096$ 個以下時，可使用 in-place 排序方法進行排序，因為善用了元素存取上的 空間區域性 (Spatial Locality)，除了加速排序實際所需時間以外，亦可減少 Merge sort 重複遞迴呼叫所造成的效能負擔。
• 但在實際的配置上並不會這麼理想，故我們仍需在考量實際執行情形後，向下調整串列的實際最小長度，並不會恰等於
  $4096$。

透過 XOR Linked List 改善 lab0-c 中 harness.c 之實作效能

• 觀察 harness.c 中的 link list 結構，每一個節點皆使用了兩個指標，分別指向該節點的前一元素與後一元素。

typedef struct BELE {
    struct BELE *next, *prev;
    size_t payload_size;
    size_t magic_header; /* Marker to see if block seems legitimate */
    unsigned char payload[0];
    /* Also place magic number at tail of every block */
} block_ele_t;

• 我們可透過 XOR linked list 節省節點內的一個指標存放空間，但需同時修改 insert 、 delete 與 traverse 等操作以符合原有功能，且執行上述操作時，需兩個指標協同操作，才能讓指標正確地指向串列內各個節點的元素。

:Camera: 測驗二 - Linked List with Insertion Sort via Pointer to Pointer

實作分析與填答

• 考慮以下 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;
}

請補完程式碼。

• 參考上列程式碼，我們先分析 Insert via Pointer to Pointer 的實作中「指標的指標」link 的特性，如下所示：
  • link 將會指向一個「指向 list 節點的指標」
  • *link 即是代表存取上述「指向 list 節點的指標」
  • *link->data 則代表存取「指標 *link 所指向的 list 節點中」，該「list 節點的 data 欄位值」。
    
    
• 觀察上述程式中的 insert 函式，可發現最開始從 head 開始走訪，直到 list 中某節點之值不小於欲插入 list 的節點之值跳離，或是 list 走訪到終點時跳離。
• 在向下一個節點走訪時，應將 Pointer to Pointer 指向現時節點的 next 指標，才能正確地存取下一個節點。
• 最後，操作該節點的相關指標，完成 list 節點之插入。
• 除此之外，考量編譯器的設計機制上的不同 (如: 最佳化機制、運算子優先權…等) ，在基於 Pointer to Pointer 之 list 存取順序上，應嚴格遵守下列順序：
  1. 對 Pointer to Pointer 做取值運算，取得其所指向的 Pointer
  2. 取出的 Pointer 指向 list 中之某一 node ，透過 Arrow Operator 取出所需欄位值進行相關操作。
• 故根據上述分析與考量，填答AA與BB之值：
  • AA 應選 <C> (*link)->data < newt->data
  • BB 應選 <A> link = &(*link)->next

兩種實現的效能分析與實作限制

• 首先，我們實作時間的量測機制，由函式 insert 呼叫前起算，至返回值為止。

   int ins_count;
   struct node *ptr = NULL;

   trun = clock();
   insert(ptr);
   trun = clock() - trun;

   trun = clock();
   insert_ptp(ptr);
   trun = clock() - trun;

• 透過檔案操作輸出 clk_normal.csv 與 clk_ptp.csv 兩檔案，並透過 gnuplot 繪製成圖。
• 插入100個元素的效能比較:
  
  
• 插入1000個元素的效能比較:
  
  
• 插入10000個元素的效能比較:
  
  
• 在插入元素時，我們可以觀察到有幾次插入所耗的 clock cycle 特別地高，可以合理推論這是受到了 快取失誤 (Cache Miss) 的影響。
• 除此之外，因為操作 Pointer to Pointer，因此在插入10000個的元素時，其執行所需 Clock Cycle 較傳統方法略少一些；在插入100000個的元素時，其差異更加顯著，如下圖所示：
  
  

在 Linux Kernel 中之應用 - 紅黑樹操作

• 在 bfq-wf2q.c 的函式 bfq_insert ，以及 rbtree.h 中的 rb_link_node 函式中使用了 Pointer to Pointer 進行紅黑樹操作，其目的在於利用存取 Pointer to Pointer 的 時間區域性 (temporal locality)，因為存放 Pointer to Pointer 的位址是固定的，因此得以讓我們在大量的節點元素操作下，使更改 Pointer to Pointer 所指向的指標時產生的讀寫操作能夠透過快取記憶體增速。
• 在此紅黑樹的實作中，以演算法分析的角度而言，紅黑樹因為具有 自平衡 (Self Balancing) 的特性，因此其效能已優於一般的二元搜尋樹，但在此處的設計中，更善用快取加速的優勢，使大量資料的操作下有更佳的效能。