Linux 核心專題: 紅黑樹實作研究

執行人: LiChiiiii
GitHub
專題解說錄影

:question: 提問清單

• 是否可以 lab0-c 原本的 list-sort 對後續整合的 tree-sort 進行效能比較，並針對結果分析?
• 紅黑樹實作的效能評比部分僅列出實驗數據，並沒有針對圖表進行分析

任務描述

重做第 3 週測驗題 的測驗一及第 4 週測驗題的測驗一，深入理解紅黑樹的實作考量。

TODO: 重做紅黑樹相關測驗題

重做第 3 週測驗題 的測驗一及第 4 週測驗題的測驗一，彙整其他學員的成果，連同延伸問題，比照〈Linux 核心的紅黑樹〉的風格進行報告。

對第 3 週測驗 treesort.c 程式碼的理解

定義一個結構 node_t ，其中 color 代表節點顏色， left 和 right 分別代表紅黑樹的左子節點和右子節點，next 代表在原始陣列中下一個節點， value 代表節點的值。

typedef struct __node {
uintptr_t color;
struct __node *left, *right;
struct __node *next;
long value;
} node_t __attribute__((aligned(sizeof(long))));

定義一個結構 cmap_internal 記錄整個 map 的資訊，有 key, element, map 的 size, 也記錄了 end, most, least 和比較的函式 comparator。

struct cmap_internal {
    node_t *head;

    /* Properties */
    size_t key_size, element_size, size;

    cmap_iter_t it_end, it_most, it_least;

    int (*comparator)(void *, void *);
};

為了節省記憶體空間，這裡把親代節點的位址存在 uintptr_t color 的最高位中。在 64 位元的系統中，考慮到 alignment，記憶體以 8 bytes 為一個單位進行管理，也就是說 node_t 的位址的最後 3 個 bits 一定為 0 ，因此只要對給定的引數 (r) 清除後面 3 個 bits 就可以得到親代節點的位址，並且在引數 (r) 最後一個 bit 存放顏色信息， (r)->color & 1 取出最後一個 bit 。

#define rb_parent(r) ((node_t *) ((r)->color & ~7))
#define rb_color(r) ((color_t) (r)->color & 1)

而在設定顏色時，以 bitwise 操作，若節點是紅色則設定最後一個bit 為 0 ，反之。

#define rb_set_red(r) do { (r)->color &= ~1; } while (0)
#define rb_set_black(r) do { (r)->color |= 1; } while (0)

程式碼內的 cmap_l_l, cmap_l_r, cmap_r_r, cmap_r_l 代表在平衡紅黑樹時會處理的四種情況，並會在 cmap_fix_colors 裡呼叫。

cmap_insert() 是在紅黑樹中插入節點的功能，若比較結果 res 小於零代表往左邊走，否則往右邊走，直到走訪到的節點為 NULL，或迴圈結束，即插入節點。

tree_sort() 會建立一個 map 配置 key 和 element 足夠的空間，接著在 while 迴圈將 list 中的每個節點一個一個插入 map 中。定義 *node 為 map 中擁有最小值的節點，透過 for 迴圈，從最左子開始在紅黑樹找到下一個節點（cmap_next(node) ），由小到大放入 list 中，完成 sort 功能。

void tree_sort(node_t **list)
{
    node_t **record = list;
    cmap_t map = cmap_new(sizeof(long), sizeof(NULL), cmap_cmp_int);
    while (*list) {
        cmap_insert(map, *list, NULL);
        list = &(*list) -> next ;
    }
    node_t *node = cmap_first(map), *first = node;
    for (; node; node = cmap_next(node)) {
        *list = node;
        list = &(*list) -> next ;
    }
    *list = NULL;
    *record = first;
    free(map);
}

將 treesort.c 整合到 lab0-c ，探討 tree sort 的效率

commit f9b2abb

定義結構體

改寫 treesort.c ，利用 lab0-c 定義的 list_head ，串接每一個 node。
value 的型態從原本的改成 long 改成 char* ，讓排序不限於數字。

struct rb_node {
    uintptr_t color;
    struct rb_node *left, *right;
    char *value;
}__attribute__((aligned(sizeof(long))));

typedef struct __node {
    struct rb_node RBnode;
    struct list_head *list;
} node_t ;

因此改寫 cmap_cmp_int 程式碼，變成 cmap_cmp_str 用以比較字串大小。

static inline int cmap_cmp_str(void *arg0, void *arg1)
{
    char *a = (char *) arg0, *b = (char *) arg1;
    int result = strcmp(a, b);
    return result < 0 ? _CMP_LESS : result > 0 ? _CMP_GREATER : _CMP_EQUAL;
}

可以使用 struct *rb_node 作為走訪節點的通用迭代器。
改寫 cmap_internal 程式碼，用以表示整個 map 的資訊。

struct cmap_internal {
    struct rb_node *head;
    
    /* Properties */
    size_t key_size, element_size, size;
    struct rb_node it_end, it_most, it_least;
    int (*comparator)(void *, void *);
};

建立節點

傳入的參數為定義的結構體 node_t 裡的 list_head 結構，並透過 cmap_create_node() 來初始化 node_t 內的 rb_node。

node_t *list_make_node(struct list_head *list) {
    node_t *node = malloc(sizeof(node_t));
    node->list = list;
    node->RBnode.value = ((element_t *)list_entry(list, element_t, list))->value;
    cmap_create_node(node);
    return node;
}

node_t *cmap_create_node(node_t *node){
    node->RBnode.left = node->RBnode.right = NULL;
    rb_set_parent(&(node->RBnode), NULL);
    rb_set_red(&(node->RBnode));

    return node;
}

釋放 tree 所用到的空間

利用 DFS 方法走所有節點並釋放記憶體。

void tree_free(struct rb_node *node){
    if (!node) 
        return;
    
    tree_free(node->left);
    tree_free(node->right);
    free(container_of(node, node_t, RBnode));
}

節點旋轉及顏色變換的操作

更改 treesort.c 內所有操作紅黑樹節點旋轉及顏色變換之函式的結構體，將 node_t 改成 rb_node。

尋找最小節點

先檢查紅黑樹的根節點 obj->head 是否存在，如果根節點存在，則進入迴圈。迴圈的目的是往左子樹移動，一直到達最左端的節點。返回最左端節點的地址，因為紅黑樹中的節點是通過 struct rb_node 結構嵌入到 node_t 結構中的，所以需要使用 container_of 宏來找到 node_t 結構的起始地址。

node_t *cmap_first(cmap_t obj) {
    struct rb_node *n = obj->head;
    if (!n)
        return NULL;

    while (n->left)
        n = n->left;
    return (node_t *)container_of(n, node_t, RBnode);
}

尋找下一個節點

在紅黑樹中找到給定節點的下一個節點，並以 node_t 結構的指標形式返回。它通過判斷節點的右子節點和父節點的關係來確定下一個節點的位置，並使用 container_of 宏計算出相應的 node_t 結構的指標。

node_t *cmap_next(node_t *node) {
    if (!node)
        return NULL;

    if (node->RBnode.right) {
        node = (node_t *)container_of(node->RBnode.right, node_t, RBnode);
        while (node->RBnode.left)
            node = (node_t *)container_of(node->RBnode.left, node_t, RBnode);
        return node;
    }

    struct rb_node *parent;
    while ((parent = rb_parent(&(node->RBnode))) && &(node->RBnode) == parent->right)
        node = (node_t *)container_of(parent, node_t, RBnode);

    return parent ? (node_t *)container_of(parent, node_t, RBnode) : NULL;
}

插入節點

功能及做法相同，根據新定義的結構體，更改 treesort.c 內cmap_insert() 使用到函式之參數的結構體。

tree sort

此函式利用紅黑樹將原始鏈表中的元素進行排序，然後重新連結這些元素，使它們按照排序順序形成一個新的鏈表，最後釋放相關的記憶體。
Tree sort 主要分成兩個部分，分別是建立紅黑樹並在走訪樹來將佇列排序。

1. 建立紅黑樹，利用 list.h 裡的 list_for_each 迴圈遍歷傳入指向佇列的 head 指標，將每個節點轉換為 node_t 結構，並插入到 map 紅黑樹中。
   ​​​​void tree_sort(struct list_head *head) {
   ​​​​    cmap_t map = cmap_new(sizeof(long), sizeof(NULL), cmap_cmp_str);
   ​​​​    struct list_head *list;
   ​​​​    list_for_each(list, head) {
   ​​​​        node_t *node = list_make_node(list);
   ​​​​        cmap_insert(map, node, NULL);
   ​​​​    }
   
   ​​​​    ...
   ​​​​}
   

2. 從 map 紅黑樹中取出第一個節點作為起始節點 node ，使用 cmap_next 函式獲取下一個節點 next，並進行以下迴圈遍歷操作：
   • 從原始佇列中移除節點 next->list。
   • 將節點 next->list 插入到 node->list 之前，即將節點按照排序順序插入到佇列中。
   • 更新 node 為 next，以便進行下一輪迴圈。
   ​​​​node_t *node = cmap_first(map);
   ​​​​if (!node) {
   ​​​​    free(map);
   ​​​​    return;
   ​​​​}
   
   ​​​​for (node_t *next = cmap_next(node); next; next = cmap_next(next)) {
   ​​​​    list_del(next->list);
   ​​​​    list_add(next->list, node->list);
   ​​​​    node = next;
   ​​​​}
   

最後釋放記憶體

tree_free(map->head);
free(map);

修改 qtest.c

引入 option，讓 qtest 得以在執行時期切換不同的排序實作，有助於後續分析。
新增條件式 if (is_enable_tree_sort) ，當輸入命令 option tree_sort 1，即可使用 tree_sort 進行排序

bool do_sort(int argc, char *argv[])
{ 
    ...
    if (current && exception_setup(true))
    {
        if (is_enable_tree_sort) {
            tree_sort(current->q);
        } else {
            q_sort(current->q);
        }
    }
    ...
}

並在 console_init 函式中加入對應的 option 的參數

 add_param("tree_sort", 
           &is_enable_tree_sort, "Enable red black tree sort", NULL);

實際執行測試

對數字做排序

cmd> show
Current queue ID: 0
l = [8 7 1 9 4 6 5 3 2]
cmd> option tree_sort 1
cmd> sort
l = [1 2 3 4 5 6 7 8 9]

對字母做排序

cmd> it RAND 5
l = [cajcwse umryjwxb puhyhrinu ziompt kmzif]
cmd> option tree_sort 1
cmd> sort
l = [cajcwse kmzif puhyhrinu umryjwxb ziompt]

隨機產生 10000 筆資料計算 tree sort 排序時間

cmd> it RAND 10000
l = [cytzpsri hmcbl nxrdcxzb wnhiudpi yrmalec bahpslek lnytyc gjuzkk uptwhevm yvcwllv fwxznfpy inhmgmvg gqiwobwgc hykmtpi cdmnkg ujrhylszl kvvojtzb sdcht wzhhm tlrjj qcsidq jhapssga dpejiu gxnvg gsztahcbw twoyuzmpz ikiomm fstavbq rybee txnffxew ... ]
cmd> option tree_sort 1
cmd> time sort
l = [aaekaamj aaery aahlqgqnd aaidup aajsmj aalswiy aaptsp aapzpdfb aavixwyig aaxvzp aaykobgl abdtywi abetyf abgrvq abijuxdii abipvffyr abjlsfaj abjxcgc abkahhy abkaimkpk ablomtzf abohmr abopusld abpnniib abrow abseaup abssul abuco abvnvss abxxl ... ]
Delta time = 0.119

tree_sort 平均五次下來為 0.134 s

參考 willwillhi1 的作法

對第 4 週測驗 LLRBT 程式碼的理解

在測驗一提供的程式碼中定義

#define rb_node(x_type)
    struct{
        x_type *left, *right_red;
    }

這裡的 rb_node 定義了紅黑樹中的節點結構，其中 x_type 是節點的數據類型。該結構包含了 left 和 right_red 兩個成員指標。
left 指向節點的左子節點，而 right_red 指向節點的右子節點，同時它的最低有效位（Least Significant Bit）儲存節點的顏色信息（紅色或黑色），以此原理精簡紅黑樹節點佔用的空間。

typedef rb_tree(node_t) tree_t;
rb_gen(static, tree_, tree_t, node_t, link, node_cmp);

對照 rb.h 之巨集的使用，展開 rb_gen(static, ex_, ex_t, ex_node_t, ex_link, ex_cmp) 巨集可以得到插入、刪除等功能之函式。

新增節點操作 tree_insert()

將巨集 x_attr void x_prefix##insert(x_rbt_type *rbtree, x_type *node) 展開為 static void tree_insert (tree_t *rbtree, node_t *node) ，此函式將新節點插入紅黑樹中，主要有三個步驟：

1. 根據節點的比較結果遞迴查找插入位置
2. 依次從下往上檢查是否需要旋轉
3. 將根節點設為黑色。

舉個例子來說，現在有一個紅黑樹。

我們想插入新的節點 3，會先用 BST 的概念尋找插入的位置。

1. 3 與 7 比較，紀錄 cmp = -1 ，並往左進行下一層尋找。
2. 3 與 2 比較，紀錄 cmp = 1 ，並往右進行下一層尋找。
3. 3 與 5 比較，紀錄 cmp = -1 ，並往左進行下一層尋找，得到 NULL 跳出迴圈，把插入位置指向此節點，也就是 pathp->node = node 。

由於在尋找插入的位置的過程中，有依序紀錄經過每個節點及其 cmp 至名為 path 的陣列，因此當找到插入位置的同時，也得到了以下陣列 path 。

接下來將 pathp 反向回去，判斷每個 pathp 的 cmp 值來檢查是否需要旋轉。
如果 cmp < 0 ，且出現左邊狀況則進行旋轉成下圖右側。

x_type *left = pathp[1].node;                           
rbtn_left_set(x_type, x_field, cnode, left);            
if (!rbtn_red_get(x_type, x_field, left))               
    return;                                             
x_type *leftleft = rbtn_left_get(x_type, x_field, left);
if (leftleft && rbtn_red_get(x_type, x_field, leftleft)) {     
    /* Fix up 4-node. */    
    x_type *tnode;                                     
    rbtn_black_set(x_type, x_field, leftleft);                   
    rbtn_rotate_right(x_type, x_field, cnode, tnode);   
    cnode = tnode;                                      
}                   

如果 cmp >= 0 ，

1. 出現左邊狀況則進行顏色轉換設定成下圖右側。

2. 出現左邊狀況則進行旋轉成下圖右側。這邊是為了滿足 LLRBT 的左傾條件。

x_type *right = pathp[1].node;   
rbtn_right_set(x_type, x_field, cnode, right);  
if (!rbtn_red_get(x_type, x_field, right)) 
    return;        
x_type *left = rbtn_left_get(x_type, x_field, cnode);  
if (left && rbtn_red_get(x_type, x_field, left)) {  
    /* Split 4-node. */    
    rbtn_black_set(x_type, x_field, left); 
    rbtn_black_set(x_type, x_field, right);     
    rbtn_red_set(x_type, x_field, cnode);          
} else { 
    /* Lean left. */    
    x_type *tnode;          
    bool tred = rbtn_red_get(x_type, x_field, cnode); 
    rbtn_rotate_left(x_type, x_field, cnode, tnode);    
    rbtn_color_set(x_type, x_field, tnode, BBBB);  
    rbtn_red_set(x_type, x_field, cnode);    
    cnode = tnode;        
}                   

最後將根節點設為黑色。

刪除節點操作 tree_remove()

將巨集 x_attr void x_prefix##remove(x_rbt_type *rbtree, x_type *node) 展開為 static void tree_remove(tree_t *rbtree, node_t *node) ，此函式用於刪除紅黑樹中的節點，跟 tree_insert() 一樣的方式去尋找要刪除的節點，只是額外加上 if(cmp==0) ，若條件式成立，則表示找到要刪除的節點，接著就是找出節點的 successor ，來為交換做準備。
舉個例子來說，現在有一個紅黑樹，我想刪除節點 2。

可以得到這個 path 陣列。

在 cmp == 0 時，代表找到想刪除的節點，也就是找到節點 2，會設定 pathp->cmp = 1 ，並尋找此節點的 successor 。

if (cmp == 0) {
/* Find node's successor, in preparation for swap. */    
    pathp->cmp = 1;                                       
    nodep = pathp;                                           
    for (pathp++; pathp->node; pathp++) {                     
        pathp->cmp = -1;                                     
        pathp[1].node = rbtn_left_get(x_type, x_field, pathp->node);                                
    }                                                         
    break;
} 

因此 path 陣列會變成

接著確定要拿來替代的節點 pathp->node 不是欲刪除的節點後，將兩者的顏色和左右子樹及在 path 陣列中的位置交換。
此時紅黑樹會變成

nodep 的 node 指向後繼者節點（successor node），pathp 的 node 指向要刪除的節點，path 陣列會變成

最後移除 pathp->node，移除掉欲刪除的節點。
若欲刪除節點是紅色，則可以直接移除，不影響樹的平衡（如上述範例）；若欲刪除節點是黑色，則沿著 path 陣列反向走訪經過的節點，並根據狀態作出平衡。

兩種紅黑樹實作方式比較

特徵	Tree Sort	LLRBT
節點結構	包含左子節點、右子節點和親代節點的指標	包含左子節點和右子節點的指標，無親代節點直接紀錄
節點操作方式	通過節點的親代指標直接獲取和操作親代節點	使用額外的路徑陣列追蹤操作路徑並對紅黑樹進行平衡
空間佔用	需要額外的指標記錄親代節點，佔用更多的內存空間	不需要額外的指標記錄親代節點，節省內存空間
平衡操作複雜度	平衡操作相對較簡單，直接通過指標修改節點的親代關係	平衡操作較複雜，需要使用陣列記錄路徑並進行調整
適用場景	操作和追蹤節點的親代關係較為頻繁的場景	節點操作和平衡操作頻率較低的場景

上述程式碼已整合進 rv32emu:

• map.h
• map.c
• test-map.c

撰寫測試/效能評比程式碼時，可對照運用。
:notes: jserv

TODO: 紅黑樹實作的效能評比

利用 rb-bench，分析不同紅黑樹實作手法的差異，應當考慮更大的資料範圍

對照 rbtree_bench

使用 rb-bench

依序執行

make all
./rb-bench > reports/test-linux-emag.xml
./plot.py reports/test-linux-emag.xml reports/test-linux-emag.png

得到以下這張圖

在 test.h 宣告一變數 small_set_size，代表測試中的小型數據集大小，預設 small_set_size = 128 （上圖），接著我們更改數據集大小觀察圖表。
當small_set_size = 256 時得到下圖

當small_set_size = 512 時得到下圖

分析不同紅黑樹實作手法的差異

在 SmallSetLinear 情況下，發現 FreeBSD 的效能最好

應予以解讀並說明應用場景。
:notes: jserv