Try   HackMD

2023q1 Homework3 (quiz3)

contributed by < hankTaro >

測驗一

延伸問題:

  1. 指出 treesort.c 程式碼的缺失並改進
  2. 利用 Linux 核心的 list.h 標頭檔改寫並整合進第一次作業的實驗程式碼中,探討 Tree sort 的效率
  3. 研讀 Linux 核心的 Red–black tree 程式碼,比較給定的 treesort.c 實作手法,指出後者的改進空間並予以實作

此紅黑樹節點架構將顏色與親代節點的資料存在同個空間,藉由透過 __attribute__((aligned(sizeof(long)))) 對齊到 sizeof(long),這樣指標最低 3 個位元是沒有使用到的,便可將此位置用於儲存顏色(但是儲存顏色只需要用到 1 bit)

long 所需的位元數為 4,所以對齊後最小的三位元會固定不動
e.g. 00001000 -> 00010000 -> 00011000 -> 00100000 -> 00101000
你所不知道的 C 語言:記憶體管理、對齊及硬體特性

這裡對將變數名取為 color 頗為不滿,若將其命名為 parent_color 會更容易閱讀理解,並避免混淆

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

並且定義巨集以便取出親代節點的位置與節點顏色

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

#define rb_set_parent(r, p)                         \
    do {                                            \
        (r)->color = rb_color(r) | (uintptr_t) (p); \
    } while (0)
#define rb_set_red(r) \
    do {              \
        (r)->color & ~7;         \
    } while (0)
#define rb_set_black(r) \
    do {                \
        (r)->color | 1;           \
    } while (0)

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;
    }
    // 找出 tree 中最小的值(也就是不停的往左側尋訪)
    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);
}

int res = obj->comparator(&node->value, &cur->value); 中的 res ,是 obj->comparator (一個比較函數,由 cmap_new, assign 進去的),當 &node->value 大於 &cur->value 時回傳 1,反之回傳 -1 ,相等回傳 0 ,隨後便利用 res 辨別相對大小,將此 node 放在 NIL 的位置(leaf),

static bool cmap_insert(cmap_t obj, node_t *node, void *value)
{
    cmap_create_node(node);

    obj->size++;

    if (!obj->head) {
        /* Just insert the node in as the new head. */
        obj->head = node;
        rb_set_black(obj->head);

        /* Calibrate the tree to properly assign pointers. */
        cmap_calibrate(obj);
        return true;
    }

    /* Traverse the tree until we hit the end or find a side that is NULL */
    for (node_t *cur = obj->head;;) {
        int res = obj->comparator(&node->value, &cur->value);
        if (!res) /* If the key matches something else, don't insert */
            assert(0 && "not support repetitive value");

        if (res < 0) { //若  node 比現在這個點小,則檢查 cur 左側有沒有節點,若沒有就將 node 放入 cur 的左側,反之則將 cur 變為其左側節點重複判斷
            if (!cur->left) {
                cur->left = node;
                rb_set_parent(node, cur);
                cmap_fix_colors(obj, node);
                break;
            }
            cur->cur->left;
        } else {
            if (!cur->right) {
                cur->right = node;
                rb_set_parent(node, cur);
                cmap_fix_colors(obj, node);
                break;
            }
            cur->cur->right;
        }
    }

    cmap_calibrate(obj);
    return true;
}

cmap_new 的必要性,因為只有在 tree_sort 中呼叫過一次,內容也只是將固定傳入數值 assign 進結構中

引入 list.h

struct __node 中的 struct __node *next;struct list_head list; 替換

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

main 中的 list_make_node 改為使用 list_add

int main(int argc, char** argv)
{
    size_t count = 100;

    int* test_arr = malloc(sizeof(int) * count);

    for (int i = 0; i < count; ++i)
        test_arr[i] = i;
    shuffle(test_arr, count);

    /*node_t* list = NULL;*/
    LIST_HEAD(list);

    while (count--) {
        list_make_node(list, test_arr[count]);
    }
    tree_sort(&list);
    assert(list_is_ordered(list));

    list_free(&list);
    free(test_arr);
    return 0;
}
static inline void list_make_node(struct list_head* head, int n)
{
    node_t* node = malloc(sizeof(node_t));
    node->value = n;
    list_add(node->list, head);
}

使用 list_for_each_entrylist_move_tail 省去使用 list = &(*list)->next;,並且更改 cmap_nextcmap_first 資料回傳型態

void tree_sort(struct list_head **list)
{
    struct list_head **record = list;
    cmap_t map = cmap_new(sizeof(long), sizeof(NULL), cmap_cmp_int);
    node_t *it;
    list_for_each_entry(it, *list, list) {
        cmap_insert(map, it, NULL);
    }

    struct list_head* node = cmap_first(map);
    for (; node; node = cmap_next(node)) {
        list_move_tail(node, *list);
    }
    free(map);
}

測驗二

答案

IIII = node->parent_balance & ~7
JJJJ = node->parent_balance & 3
KKKK = node->parent_balance & 3
LLLL = node->parent_balance & ~7
MMMM = avl_rotate_right
NNNN = avl_rotate_leftright

程式碼講解

AVL tree 這裡也利用 AVL_NODE_ALIGNED 做 data alignment ,將 balance 值存於 adress 的末兩位中,剛好 balance 只有三種可能,平衡、左傾或右傾,故可以使用 2 bits 空間進行保存

要注意的是,這裡左傾與右傾是指,兩邊最大高度差為 1,因為當兩邊高度差為 2 時,就會進行平衡,並且求出新的 balance ,所以這邊 Balance Factor 只會有 -1, 0, 1 的狀況

// 用於對應是平衡、左傾還是右傾(Balance Factor 為 0, -1, 1)
enum avl_node_balance { AVL_NEUTRAL = 0, AVL_LEFT, AVL_RIGHT, };
#define AVL_NODE_ALIGNED __attribute__((aligned(sizeof(unsigned long))))

...

struct avl_node {
    unsigned long parent_balance;
    struct avl_node *left, *right;
} AVL_NODE_ALIGNED;

呼叫 avl_insert 的情況下,是已經找到此 node 在樹中的位置,並且 parent 已將此節點設為他的 child,故呼叫 avl_link_node 建立出一個 left right 都是 NULL 的新節點,並且是平衡的,再將 parent 的位置存入

static inline void avl_link_node(struct avl_node *node,
                                 struct avl_node *parent,
                                 struct avl_node **avl_link)
{
    avl_set_parent_balance(node, parent, AVL_NEUTRAL);
    node->left = NULL;
    node->right = NULL;

    *avl_link = node;
}


static inline void avl_insert(struct avl_node *node,
                              struct avl_node *parent,
                              struct avl_node **avl_link,
                              struct avl_root *root)
{
    avl_link_node(node, parent, avl_link);
    avl_insert_balance(node, root);
}

當 node 插入後,便開始沿著 parent 的路徑依序平衡,可以將情況分為一下幾種:

  • case 1:
    • node 平衡,在 parent 的左側,parent 右傾
    • node 平衡,在 parent 的右側,parent 左傾
  • case 2:
    • node 平衡,parent 平衡
  • case 3:
    • node 不平衡

在 case 1 中只需要將 parent 設為平衡
在 case 2 中只需要依據 node 是插入在左側還是右側,將 parent 設為右傾或左傾

case 3 需要進行旋轉以平衡兩側高度,並且要同時對 node 與 parent 做判斷,可以分為 4 種類型

  • LL 型:
    • 狀況: parent 與 node 均為左傾
    • 處理方法: 對 parent 進行右旋
  • LR 型:
    • 狀況: parent 左傾,node 右傾
    • 處理方法: node 進行左旋後,對 parent 進行右旋
  • RR 型:
    • 狀況: parent 與 node 均為右傾
    • 處理方法: parent 進行左旋
  • RL 型:
    • 狀況: parent 右傾,node 左傾
    • 處理方法: node 進行右旋後,對 parent 進行左旋

要注意插入新節點還沒平衡前,新節點的 parent 的 balance 尚未更新,並且新節點必定平衡,所以第一次平衡不可能會進行旋轉

新節點的 parent 只受新節點在其左還右,以改變其平衡狀態

node 為平衡或左傾時,都算做 L

LL 型:

LR 型:


RR 型:

RL 型:

void avl_insert_balance(struct avl_node *node, struct avl_root *root)
{
    struct avl_node *parent;

    /* go tree upwards and fix the nodes on the way */
    while ((parent = avl_parent(node))) {
        if (avl_is_right_child(node)) {
            switch (avl_balance(parent)) {
            default:
            case AVL_RIGHT:
                /* compensate double right balance by rotation
                 * and stop afterwards
                 */
                switch (avl_balance(node)) {
                default:
                case AVL_RIGHT:
                case AVL_NEUTRAL:
                    avl_rotate_left(node, parent, root);
                    break;
                case AVL_LEFT:
                    avl_rotate_rightleft(node, parent, root);
                    break;
                }

                parent = NULL;
                break;
            case AVL_NEUTRAL:
                /* mark balance as right and continue upwards */
                avl_set_balance(parent, AVL_RIGHT);
                break;
            case AVL_LEFT:
                /* new right child + left leaning == balanced
                 * nothing to propagate upwards after that
                 */
                avl_set_balance(parent, AVL_NEUTRAL);
                parent = NULL;
                break;
            }
        } else {
            switch (avl_balance(parent)) {
            default:
            case AVL_RIGHT:
                /* new left child + right leaning == balanced
                 * nothing to propagate upwards after that
                 */
                avl_set_balance(parent, AVL_NEUTRAL);
                parent = NULL;
                break;
            case AVL_NEUTRAL:
                /* mark balance as left and continue upwards */
                avl_set_balance(parent, AVL_LEFT);
                break;
            case AVL_LEFT:
                /* compensate double left balance by rotation
                 * and stop afterwards
                 */
                switch (avl_balance(node)) {
                default:
                case AVL_LEFT:
                case AVL_NEUTRAL:
                    avl_rotate_right(node, parent, root);
                    break;
                case AVL_RIGHT:
                    avl_rotate_leftright(node, parent, root);
                    break;
                }

                parent = NULL;
                break;
            }
        }

        if (!parent)
            break;

        node = parent;
    }
}

而進入旋轉後,需要根據親代節點的平衡狀況去設置調整後的平衡狀況
依序分別為:

  • LL 型: 右旋
  • LR 型: 先左旋再右旋
  • RR 型: 左旋
  • RL 型: 先右旋再左旋
static struct avl_node *avl_rotate_right(struct avl_node *node,
                                         struct avl_node *parent,
                                         struct avl_root *root)
{
    enum avl_node_balance balance_parent, balance_node;
    struct avl_node *tmp;

    switch (avl_balance(node)) {
    case AVL_NEUTRAL:
        balance_parent = AVL_LEFT;
        balance_node = AVL_RIGHT;
        break;
    default:
    /* AVL_RIGHT is not allowed */
    case AVL_LEFT:
        balance_parent = AVL_NEUTRAL;
        balance_node = AVL_NEUTRAL;
        break;
    }

    /* rotate right */
    tmp = parent->left;
    parent->left = tmp->right;
    tmp->right = parent;

    avl_rotate_switch_parents(tmp, parent, parent->left, root, balance_node,
                              balance_parent);

    return tmp;
}

此方法對應的是 LL 型,由於此情況 node 不可能右傾,因為右傾則會成為 LR 型, 故只需要考慮 node 為平衡以及左旋的狀況,當 node 為平衡時,代表其左右側都不為 NIL(因為第一次平衡不可能會進行旋轉,故發生選轉的節點必定有子節點),所以其右側節點會成為其親節點的左側節點

node 為紅色節點







graphname

NODE 為平衡時


n01

A



n02

B



n01--n02




n03

C



n01--n03




n04

D



n02--n04




n05

E



n02--n05










graphname

旋轉後


n01

B



n02

D



n01--n02




n03

A



n01--n03




n05

E



n03--n05




n04

C



n03--n04




故 node 在旋轉後會右傾,而 parent 會左傾,故更新平衡狀態,隨後進行節點的移動與連結

而 RL/LR 型則是先對 node 做相對應的旋轉,使其變為 RR 或 LL 型,再用同樣的方式對 parent 旋轉,並更新平衡狀態,概念相同這裡就不多做贅述

Linux 核心 rb_tree 替代 AVL_tree 之因素

目前Linux 核心中的 AVL tree ,逐漸被紅黑樹替代,AVL tree 相較於 RBT 的劣勢在於,當節點數量較大時,可能需要一直旋轉直到 root ,在大多數情況下,RBT 的效率會比 AVL tree 好

在考慮是否要用 RBT 取代 AVL tree 以前,必須先行了解 linux 核心的同步機制之一 RCU,以及 linux 的鎖定機制 seqlock(short for sequence lock),因為要將 AVL tree 用 RBT 取待,需要確保 RBT 支援 RCU ,否則在多執行上效率不彰

在使用 RCU 的狀況下,RBT 可使用較少的函式達成,同時使用較少的變數

(TODO)利用 rb_tree 替代 AVL_tree 之實作

延伸問題:

  1. 解釋上述程式碼運作原理,並比較用紅黑樹實作的 priority queue,應提供完整的測試程式和效能分析
  2. Linux 核心也有 AVL tree 的身影,但陸續被紅黑樹替代,請揣摩 Linux 核心開發者的考慮因素,並搭配 git log 來解讀

    見 commit b145425

  3. 研讀 Linux 核心原始程式碼,指出曾經/現在使用 AVL tree 的部分,對照 Linux 核心的 rbtree.h,探究是否可用後者替換,從而爭取到貢獻程式碼到 Linux 核心的機會

測驗三

uint64_t log2_64(uint64_t v)
{
    unsigned r;
    uint64_t t, tt, ttt;

    ttt = v >> 32;
    if (ttt) {
        tt = ttt >> 16;
        if (tt) {
            t = tt >> 8;
            if (t) {
                r = 56 + log_table_256[t];
            } else {
                r = 48 + log_table_256[tt];
            }
        } else {
            t = ttt >> 8;
            if (t) {
                r = 40 + log_table_256[t];
            } else {
                r = 32 + log_table_256[ttt];
            }
        }
    } else {
        tt = v >> 16;
        if (tt) {
            t = tt >> 8;
            if (t) {
                r = 24 + log_table_256[t];
            } else {
                r = 16 + log_table_256[tt];
            }
        } else {
            t = v >> 8;
            if (t) {
                r = 8 + log_table_256[t];
            } else {
                r = 0 + log_table_256[v];
            }
        }
    }
    return r;
}
unsigned int bucket_number(uint64_t x)
{
    uint64_t mask111 = (1 << (N_BITS + 1)) - 1;
    uint64_t mask011 = (1 << (N_BITS)) - 1; /* one 1 less */

    unsigned char leq = ((x & mask111) < N_BUCKETS);
    /* leq (less or equal) is 0 or 1. */

    return (leq * (x & mask111)) +
           ((1 - leq) * ((x >> (N_BITS + 1)) & mask011));
    /* 'x >> (N_BITS + 1)' : take different set of bits -> better uniformity.
     * '... & mask011' guarantees that the result is less or equal N_BUCKETS.
     */
}

__builtin_clzl 求出左側0數量就可以求出小於 x 的

n=log2x
最大位元 - 左側0數量 - 1 = 右側到最大 1 之間的 0 數量 = n

延伸問題:

  1. 解釋 Linear feedback shift register (LFSR) 的運作原理,搭配在 Linux 核心原始程式碼中,用 git loggrep 找出 LFSR 的應用案例
  2. 解釋上述程式碼運作的原理
  3. 在 Linux 核心原始程式碼中找到
    log2(x)
    的實作 (整數),要涵蓋不同的整數型態寬度,以及是否能運用微處理器提供的指令來加速。也從 Linux 核心找出整數
    log2(x)
    的應用案例並解說。
  4. lab0-c 提供類似的實作 log2_lshift16.h,解釋其原理並嘗試改進其效能

測驗四

運作原理

此程式欲求出

log2(x) 並向上取整

int ceil_log2(uint32_t x) { uint32_t r, shift; x--; r = (x > 0xFFFF) << 4; x >>= r; shift = (x > 0xFF) << 3; x >>= shift; r |= shift; shift = (x > 0xF) << 2; x >>= shift; r |= shift; shift = (x > 0x3) << 1; x >>= shift; return (r | shift | x >> 1) + 1; }

log2(x) 的改念就是看最高有效位元的位置,因為在二進位中,位元的位置為冪運算的上標,所以只要知道 x 最左側的 1 後有幾個位元,就可以求出
log2(x)

在第 5 行中,將 x-- 是為了將

2n 型態的數值最大值降低一位元,確保無條件進位時的答案正確

6~15 行都是在求最高有效位的位置,最後在 return (r | shift | x >> 1) + 1; 無條件向上取整

改進程式碼,使其得以處理 x = 0 的狀況,並仍是 branchless

由於

log2(x) 需要求出最高有效位元右側有幾個位元,便可使用 __builtin_clz 函式,求出最高有效位元左側有幾個 0 ,在用最大位元數減去,便可得到其值共佔多少位元,由於要向上取整,故在運算前 x - 1,這樣
2n
型態算出的值會剛好是其減 1 前右側位元數,而不是
2n
型態算出的值會是無條件進位後的位元數

另外輸入有機會為 0,故使用 assert 檢查,並達成 branchless

int ceil_log2(uint32_t x)
{
    assert(x != 0 && "log2(0) is undefined !\n");
    return 32 - __builtin_clz(x - 1);
}

(TODO)Linux 核心中 ceil 和 log2 的組合案例

TODO:

  1. 解釋上述程式碼運作原理
  2. 改進程式碼,使其得以處理 x = 0 的狀況,並仍是 branchless
  3. 在 Linux 核心原始程式碼找出 ceil 和 log2 的組合 (類似的形式),並解說應用案例 (提示: 在 Linux 核心排程器就有)