2023q1 Homework4 (quiz4)

--- tags: linux kernel, jserv --- # 2023q1 Homework4 (quiz4) contributed by < [`WangHanChi`](https://github.com/WangHanChi) > > [作業要求](https://hackmd.io/@sysprog/linux2023-quiz4) :::info - 測驗一 - [x] 摘錄上述紅黑樹新增和刪除節點操作的程式碼，解釋其原理 - [x] 運用你在第 3 週測驗題提及的延伸問題所開發出的效能評比程式，分析不同 rbtree 實作的效能落差 - [ ] jemalloc 專案的 test/unit/rb.c 對 rbtree API 有更完整的涵蓋，其中 summarize/filter 能夠特化查詢範圍，請自 jemalloc 移植更豐富的 rbtree API 及其實作，並撰寫相關的測試程式 (含效能評比) - [ ] 解讀 Linux 核心的 include/linux/rbtree.h, include/linux/rbtree_types, lib/rbtree.c 運作原理，並探討能否運用上述手法，以縮減 rbtree 節點的佔用空間 - 測驗二 - [ ] 解釋上述程式碼運作原理，應參照論文〈On the Worst-Case Complexity of TimSort〉和〈Merge Strategies: from Merge Sort to TimSort〉 - [ ] BONUS: 針對 Linux 核心原始程式碼的 lib/list_sort.c 和 lib/sort.c，提出 hybrid sorting 的引入和改進方案，並予以實作 - [ ] F9 microkernel 的 kernel/lib/sort.c 用非遞迴的方式實作快速排序，請評估導入 introsort 或更新的 hybrid sort 的效益 - 測驗三 - [x] 解釋上述程式碼運作原理 - [ ] 將測驗 1 對節點的紅色和黑色標注的技巧嵌入到指標變數中 - [ ] Linux 核心的 rbtree 具備 cache 機制 (參見 Red-black Trees (rbtree) in Linux)，探討其原理，並嘗試在測驗 1 或測驗 3 的基礎之上實作 ::: ## 測驗一 ### 理解程式碼經過了老師的一對一面談後，發現自己對於紅黑數的理解完全不足，因此打算重新補足相關知識。會先以老師的書以及教材為主。先從 header [rb.h](https://gist.github.com/jserv/6610eb56bf2486979c8bf6ee8061f71c) 看起，會列出較為複雜或是重要的部份程式碼來筆記，避免自己讀過就忘。 #### RB_MAX_DEPTH ```c #define RB_MAX_DEPTH (sizeof(void *) << 4) ``` 這段程式碼是為了限制存儲紅黑樹時可能出現的問題。通過限制每個節點佔用的最小空間和限制樹的深度 ( 128 個深度)，可以確保樹不會佔用太多的空間，並且可以正常運作。 #### rbtn get & set ```c /* Left accessors */ #define rbtn_left_get(x_type, x_field, x_node) ((x_node)->x_field.left) #define rbtn_left_set(x_type, x_field, x_node, x_left) \ do { \ (x_node)->x_field.left = x_left; \ } while (0) /* Right accessors */ #define rbtn_right_get(x_type, x_field, x_node) \ ((x_type *) (((intptr_t) (x_node)->x_field.right_red) & ~3)) #define rbtn_right_set(x_type, x_field, x_node, x_right) \ do { \ (x_node)->x_field.right_red = \ (x_type *) (((uintptr_t) x_right) | \ (((uintptr_t) (x_node)->x_field.right_red) & 1)); \ } while (0) ``` 這邊主要在設定左右節點的資訊，其中用到了 do-while(0) 語法，可以參見[你所不知道的 C 語言: goto 和流程控制篇](https://hackmd.io/@sysprog/c-control-flow) (dangling else) #### rbtn_rotate ```c /* Internal utility macros */ #define rbtn_rotate_left(x_type, x_field, x_node, r_node) \ do { \ (r_node) = rbtn_right_get(x_type, x_field, (x_node)); \ rbtn_right_set(x_type, x_field, (x_node), \ rbtn_left_get(x_type, x_field, (r_node))); \ rbtn_left_set(x_type, x_field, (r_node), (x_node)); \ } while (0) #define rbtn_rotate_right(x_type, x_field, x_node, r_node) \ do { \ (r_node) = rbtn_left_get(x_type, x_field, (x_node)); \ rbtn_left_set(x_type, x_field, (x_node), \ rbtn_right_get(x_type, x_field, (r_node))); \ rbtn_right_set(x_type, x_field, (r_node), (x_node)); \ } while (0) ``` 再來這邊左旋或是右旋的設定，以右旋來進行舉例，搭配著下面這張圖。 ![](https://i.imgur.com/TwC1obF.png) 右旋的操作可以分成三個部份 1. 取得原先樹親代節點 (70) 的左邊節點 (50) 2. 先取得左邊樹節點 (50) 的右邊節點 (60)，在利用這個節點來設定給原先樹親代節點 (70) 的左邊節點 (60) 3. 最後再設定原先的左邊節點 (50) ，變成新的親代節點，而原本的親代節點變成右邊的節點。左旋的想法也是類似的。透過組合幾個巨集，完成了樹的旋轉操作。 #### rb prototype ```c /* The rb_proto() macro generate function prototypes that correspond to the * functions generated by an equivalently parameterized call to rb_gen(). */ #define rb_proto(x_attr, x_prefix, x_rbt_type, x_type) \ x_attr void x_prefix##new (x_rbt_type * rbtree); \ x_attr x_type *x_prefix##search(x_rbt_type *rbtree, const x_type *key); \ x_attr void x_prefix##insert(x_rbt_type *rbtree, x_type *node); \ x_attr void x_prefix##remove(x_rbt_type *rbtree, x_type *node); \ x_attr void x_prefix##destroy(x_rbt_type *rbtree, \ void (*cb)(x_type *, void *), void *arg); ``` 上面的程式碼是運用到了 [C 語言：前置處理器應用篇 ](https://hackmd.io/@sysprog/c-preprocessor#%E5%89%8D%E7%BD%AE%E8%99%95%E7%90%86%E5%99%A8%E6%98%AF%E5%BE%8C%E4%BE%86%E6%89%8D%E7%B4%8D%E5%85%A5-C-%E8%AA%9E%E8%A8%80%E7%9A%84%E7%89%B9%E5%BE%B5) 這篇裡面的技巧。 - `#``: Stringification/Stringizing (字串化): 讓一個表示式變成字串，在 assert 巨集用到 - `##`: concatenation (連結，接續) 這樣就會使得傳入的 `x_prefix` 可以連接，變成有意義的宣告。像是在 [quiz4 測驗一裡面的 C++ 測試程式碼](https://hackmd.io/@sysprog/linux2023-quiz4) 中，就使用了 ```c rb_gen(static, tree_, tree_t, node_t, link, node_cmp); ``` 來進行命名，也就會使得函式名稱為 `tree_new`, `tree_search` 等等的而其他的參數也可以從下方的註解觀察到 ```c /* Arguments: * * x_attr: * Function attribute for generated functions (e.g., static). * x_prefix: * Prefix for generated functions (e.g., ex_). * x_rb_type: * Type for red-black tree data structure (e.g., ex_t). * x_type: * Type for red-black tree node data structure (e.g., ex_node_t). * x_field: * Name of red-black tree node linkage (e.g., ex_link). */ ``` - x_attr : 函式的屬性 - x_prefix : 函式的前綴 - x_rb_type : 紅黑數結構體的 `typedef` - x_type : 紅黑數節點結構體的 `typedef` - x_field : 紅黑數節點連結的命名 #### rb gen 再來會是比較長的部份，先從註解了結程式碼內容 ```c /*The following API is generated: * * static void * ex_new(ex_t *tree); * Description: Initialize a red-black tree structure. * Args: * tree: Pointer to an uninitialized red-black tree object. * * static ex_node_t * * ex_search(ex_t *tree, const ex_node_t *key); * Description: Search for node that matches key. * Args: * tree: Pointer to an initialized red-black tree object. * key : Search key. * Ret: Node in tree that matches key, or NULL if no match. * * static void * ex_insert(ex_t *tree, ex_node_t *node); * Description: Insert node into tree. * Args: * tree: Pointer to an initialized red-black tree object. * node: Node to be inserted into tree. * * static void * ex_remove(ex_t *tree, ex_node_t *node); * Description: Remove node from tree. * Args: * tree: Pointer to an initialized red-black tree object. * node: Node in tree to be removed. * * static void * ex_destroy(ex_t *tree, void (*cb)(ex_node_t *, void *), void *arg); * Description: Iterate over the tree with post-order traversal, remove * each node, and run the callback if non-null. This is * used for destroying a tree without paying the cost to * rebalance it. The tree must not be otherwise altered * during traversal. * Args: * tree: Pointer to an initialized red-black tree object. * cb : Callback function, which, if non-null, is called for each node * during iteration. There is no way to stop iteration once it * has begun. * arg : Opaque pointer passed to cb(). */ ``` 可以看到它說明了這些巨集程式的描述以及引數，還有他的函式屬性接著會一個註解搭配一段程式碼說明 ##### arguments - header ```c #define rb_gen(x_attr, x_prefix, x_rbt_type, x_type, x_field, x_cmp) ``` - Soucre ```c rb_gen(static, tree_, tree_t, node_t, link, node_cmp); ``` 可以得出 - x_attr -> static - x_prefix -> tree_ - x_rbt_type -> tree_t - x_type -> node_t - x_field -> link - x_cmp -> node_cmp ##### Assuming setup 在註解裡面有些部份是假設我們已經完成的 ```c /* Assuming the following setup: * * typedef struct ex_node_s ex_node_t; * struct ex_node_s { * rb_node(ex_node_t) ex_link; * }; * typedef rb_tree(ex_node_t) ex_t; * rb_gen(static, ex_, ex_t, ex_node_t, ex_link, ex_cmp) ``` 可以從 C++ 測試程式中找到對應的程式碼 ```c++ struct node_; typedef struct node_ node_t; struct node_ { rb_node(node_t) link; int key; }; static int node_cmp(const node_t *a, const node_t *b) { int ret = (a->key > b->key) - (a->key < b->key); if (ret == 0 && a != b) assert(0 && "Duplicates are not allowed in the tree"); return (ret); } typedef rb_tree(node_t) tree_t; rb_gen(static, tree_, tree_t, node_t, link, node_cmp); ``` 可以看到在 `node_t` 這個結構體裡面，透過了巨集 `#define rb_node(x_type) struct { x_type *left, *right_red; }` 來展開變成 `struct { node_t *left, *right_red; }`，並且把它命名為 link 。並且也展開了 `#define rb_tree(node_t) tree_t` 變成 `struct { node_t *root; }`。等待這些程式碼都完成後，就將這些變成引數傳入 `rb_gen` 裡面產生更多的程式碼 ##### tree_path_entry_t - 巨集定義 ```c typedef struct { \ x_type *node; \ int cmp; \ } x_prefix##path_entry_t; ``` 這邊定義了一個結構體，目前無法得知他是用在何處的，要繼續觀察程式碼才能弄清楚。 ##### tree_new - 註解 ```c /* static void * ex_new(ex_t *tree); * Description: Initialize a red-black tree structure. * Args: * tree: Pointer to an uninitialized red-black tree object. * / ``` - 巨集定義 ```c x_attr void x_prefix##new (x_rbt_type * rbtree) \ { \ rb_new(x_type, x_field, rbtree); \ } ``` 這邊通過了巨集設定了 rbtree->root = NULL ##### tree_search - 註解 ```c /* static ex_node_t * * ex_search(ex_t *tree, const ex_node_t *key); * Description: Search for node that matches key. * Args: * tree: Pointer to an initialized red-black tree object. * key : Search key. * Ret: Node in tree that matches key, or NULL if no match. */ ``` - 巨集定義 ```c x_attr x_type *x_prefix##search(x_rbt_type *rbtree, const x_type *key) \ { \ int cmp; \ x_type *ret = rbtree->root; \ while (ret && (cmp = (x_cmp) (key, ret)) != 0) { \ if (cmp < 0) { \ ret = rbtn_left_get(x_type, x_field, ret); \ } else { \ ret = rbtn_right_get(x_type, x_field, ret); \ } \ } \ return ret; \ } ``` 這邊使用了三個數值來進行分類。可以從比較的函式回傳值得到節點的比較結果 `(cmp = (x_cmp) (key, ret))`。以下是三種結果 ``` (a->key > b->key) : ret = (1 - 0) = 1 執行 ret = rbtn_right_get (a->key < b->key) : ret = (0 - 1) = -1 執行 ret = rbtn_left_get (a->key = b->key) : ret = (0 - 0) = 0 跳出 while-loop ``` 根據 key 值找到節點之後就會進行回傳，也有可能沒有找到，就會回傳 NULL。 ##### tree_insert - 註解 ```c /*static void * ex_insert(ex_t *tree, ex_node_t *node); * Description: Insert node into tree. * Args: * tree: Pointer to an initialized red-black tree object. * node: Node to be inserted into tree. */ ``` - 巨集定義 (部份) ```c x_prefix##path_entry_t path[RB_MAX_DEPTH]; \ x_prefix##path_entry_t *pathp; \ rbt_node_new(x_type, x_field, rbtree, node); \ ``` 這邊先宣告了 tree_path_entry_t 的陣列 path 與指標 *pathp 並且使用了跟 `search` 很像的作法，比較了 `node` 與 `pathp->node` 的 key 後再決定往右邊或是左邊尋找。在這邊使用了 `assert(cmp != 0);` 代表了在這棵紅黑樹裡面沒有一個 key 值與要插入的節點 `node` 擁有相同的 key 值。 ```c path->node = rbtree->root; \ for (pathp = path; pathp->node; pathp++) { \ int cmp = pathp->cmp = x_cmp(node, pathp->node); \ assert(cmp != 0); \ if (cmp < 0) { \ pathp[1].node = rbtn_left_get(x_type, x_field, pathp->node); \ } else { \ pathp[1].node = rbtn_right_get(x_type, x_field, pathp->node); \ } \ } ``` 以下面這張圖來舉例。 ![](https://i.imgur.com/fSj3o1r.png) 現在要插入的節點 key 為 `90`。那麼找尋的過程可以寫成下面這樣 1. 先跟 `50` 進行比較，得到 cmp = 1 後，就會往右邊進行下一層的尋找，並且把 cmp 紀錄著 (這就是老師留言說明與 parent 有關的原因) 2. 與 `70` 進行比較，一樣得到了 cmp = 1 後，就會往右邊進行下一層的尋找，並且把 cmp 紀錄著 3. 最後再與 `80` 進行比較，得到 cmp = 1 後，就會往右邊進行下一層的尋找，這時會得到 NULL，並且把 cmp 紀錄著 4. 跳出 for 迴圈，然後把 pathp 指向 node，也就是把插入的點指向了 node。透過這樣的方式，就可以找到插入的路徑了，也難怪會將陣列命名成 `path` 接下來再將陣列 `path` 反向回去可以看到它判斷了每個 `pathp` 的 cmp 值來決定要進到 - `cmp < 0` ```c if (pathp->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; \ AAAA(x_type, x_field, leftleft); \ rbtn_rotate_right(x_type, x_field, cnode, tnode); \ cnode = tnode; \ } \ } ``` 或是 - `cmp > 0` ```c else { \ 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); \ CCCC(x_type, x_field, cnode); \ cnode = tnode; \ } \ } ``` <s> 這邊可以知道 `BBBB` 會是變數的名稱，並且這邊要設定 `tnode` 的顏色，在經過左旋之後，這邊要填入的顏色應該與 `cnode` 原本的顏色相同，並且這邊要填入的是 true 或是 false，因此 `BBBB` 應填 `tred`。 `CCCC` 應該是要將 `cnode` 設定顏色，而它變成了最底部的葉子節點，因此推測 `CCCC` 為 `rbtn_black_set`。 </s> :::warning 不用抄寫答案，只要專注解析程式碼並討論後續改進。 :notes: jserv > 好的，學生會再去參考其他同學的筆記寫法，謝謝老師 ::: 最後再去將樹根節點 root 設定為黑色 ```c rbtree->root = path->node; \ rbtn_black_set(x_type, x_field, rbtree->root); ``` 來遵守紅黑樹規則中的第二點 > 1. All nodes are either red or black > 2. Leaf nodes are black (root’s color) > 3. Leaf nodes do not contain data (NULL) > 4. All non-leaf nodes have two children > 5. If a node is red, both its children are black > 6. When traversing from the root node to a leaf, each path contains the same number of black nodes ##### tree_remove - 註解 ```c /* static void * ex_remove(ex_t *tree, ex_node_t *node); * Description: Remove node from tree. * Args: * tree: Pointer to an initialized red-black tree object. * node: Node in tree to be removed. */ ``` - 巨集定義(部分) ```c ... 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; \ } ... ``` 上面這段程式碼與 `insert` 的找尋路徑的方式相似，但是這邊額外新加了判斷 `cmp == 0` 的狀況，這代表著兩個的 key 值一致，也就是找到了要移除的節點。在 [Red/Black Tree visualization](https://www.cs.usfca.edu/~galles/visualization/RedBlack.html) 上以這棵樹為例 ![](https://i.imgur.com/CgTOWie.png) 假如現在要移除的節點為 `0074` 這個節點，可以得到這個 path 陣列 | node | 0060 | 0072 | 0075 | 0074 | 0073 | | ------- | ---- | ---- | ---- | ---- | ---- | | **cmp** | 1 | 1 | -1 | 0 | -1 | 而在 `cmp == 0` 的時候，會把 `pathp->cmp = 1` ，所以上面 path 陣列會改成 | node | 0060 | 0072 | 0075 | 0074 | 0073 | | ------- | ---- | ---- | ---- | ----- | ---- | | **cmp** | 1 | 1 | -1 | ==1== | -1 | 此時 `pathp` 會是指向 `0074`，而 `left` 會是指向 `0073` 接著會因為 `left` 不等於 NULL，進到 if-statement 裡面，最後會進到這 ```c if (pathp[-1].cmp < 0) { \ rbtn_left_set(x_type, x_field, pathp[-1].node, left); \ } else { \ rbtn_right_set(x_type, x_field, pathp[-1].node, left); \ } \ ``` 接著因為 `pathp[-1]` 是 `0075`，而他的 cmp 是 -1，因此會執行 `rbtn_left_set` 這個巨集使得 `0075` 這個節點的左邊節點變成 `left` 也就是 `0073`，這樣就完成了把 `0074` 移出的動作。接下來就倒回去進行平衡。總共可以分成兩個部份，以 `pathp->cmp < 0` 為條件，在上述的例子中，這個條件是 **True**。就會再進行各個條件判斷 ```c ... if (rbtn_red_get(x_type, x_field, pathp->node)) ... ... if (rightleft && \ rbtn_red_get(x_type, x_field, rightleft)) ``` 可以知道最後會進到迴圈就是下面這段程式碼的部份 ```c for (pathp--; (uintptr_t) pathp >= (uintptr_t) path; pathp--) { \ assert(pathp->cmp != 0); \ if (pathp->cmp < 0) { \ rbtn_left_set(x_type, x_field, pathp->node, pathp[1].node); \ if (rbtn_red_get(x_type, x_field, pathp->node)) { \ x_type *right = \ rbtn_right_get(x_type, x_field, pathp->node); \ x_type *rightleft = rbtn_left_get(x_type, x_field, right); \ x_type *tnode; \ if (rightleft && \ rbtn_red_get(x_type, x_field, rightleft)) { \ /* In the following diagrams, ||, //, and \\ */ \ /* indicate the path to the removed node. */ \ /* */ \ /* || */ \ /* pathp(r) */ \ /* // \ */ \ /* (b) (b) */ \ /* / */ \ /* (r) */ \ /* */ \ rbtn_black_set(x_type, x_field, pathp->node); \ rbtn_rotate_right(x_type, x_field, right, tnode); \ rbtn_right_set(x_type, x_field, pathp->node, tnode); \ rbtn_rotate_left(x_type, x_field, pathp->node, tnode); \ ``` 可以看到上面的圖形就跟這邊的圖形一致。 ![](https://i.imgur.com/XGStm1B.png) 經過這些調整之後，就可以讓樹變回平衡。 ##### tree_destroy - 註解 ```c /* static void * ex_destroy(ex_t *tree, void (*cb)(ex_node_t *, void *), void *arg); * Description: Iterate over the tree with post-order traversal, remove * each node, and run the callback if non-null. This is * used for destroying a tree without paying the cost to * rebalance it. The tree must not be otherwise altered * during traversal. * Args: * tree: Pointer to an initialized red-black tree object. * cb : Callback function, which, if non-null, is called for each node * during iteration. There is no way to stop iteration once it * has begun. * arg : Opaque pointer passed to cb(). */ ``` - 巨集實作 ```c x_attr void x_prefix##destroy_recurse(x_rbt_type *rbtree, x_type *node, \ void (*cb)(x_type *, void *), \ void *arg) \ { \ if (!node) \ return; \ x_prefix##destroy_recurse( \ rbtree, rbtn_left_get(x_type, x_field, node), cb, arg); \ rbtn_left_set(x_type, x_field, (node), NULL); \ x_prefix##destroy_recurse( \ rbtree, rbtn_right_get(x_type, x_field, node), cb, arg); \ rbtn_right_set(x_type, x_field, (node), NULL); \ if (cb) { \ cb(node, arg); \ } \ } \ x_attr void x_prefix##destroy(x_rbt_type *rbtree, \ void (*cb)(x_type *, void *), void *arg) \ { \ x_prefix##destroy_recurse(rbtree, rbtree->root, cb, arg); \ rbtree->root = NULL; \ } ``` 可以看到這段程式碼在 Remove 節點的方法是使用遞迴的方式來執行的，它會先將根節點左半邊的全部節點清完後，設置根節點的左節點為 NULL，右邊也是一樣的方法。而這邊的 cb 是函式指標，代表著 callback function，如果傳進來的參數不為 NULL 的，它就會去呼叫 `cb` 並執行相對應的功能，而 arg 是 cb 函式的額外參數。 ### 比較紅黑樹效能 #### 實作 priority queue 並與 STL 的版本進行比較 :::warning 這項實驗設計不恰當之處是: 1. C++ STL 使用 rbtree 的場景是 map 和 set，而其 priority queue 大多是 heap 結構或其變形，因此這就成為不同類型的資料結構比較 2. 輸入資料分布不足以涵蓋 rbtree 特性 :notes: jserv > 學生設計這個實驗原先是發想自 [quiz3/problem2 延伸問題 1](https://hackmd.io/@sysprog/linux2023-quiz3) ，想與 quiz3/problem1 的紅黑樹與 AVL 樹實作的 priority queue 進行比較，只是後者的實作尚未完成，因此想先知道跟 C++ STL 的 priority queue相差多少，才會有這個實驗。經過老師的題點後，學生會著重於 quiz3 與 quiz4 的紅黑樹比較的，謝謝老師。 ::: Priority queue 可以有多種的實作方式，例如利用 heap 等等的方式，參見〈[Priority Queue：Intro](http://alrightchiu.github.io/SecondRound/priority-queueintrojian-jie.html)〉，我利用此題的紅黑樹實作了簡單的 priority queue，並與 C++ STL 提供的 Priority queue 進行插入與移除節點的比較 Pirority queue 的實作 API 比較少，而因此我的類別如下 ```cpp class pq { private: /* to store node */ tree_t tree; /* to record tree size */ int count; public: /* constructor */ pq(tree_t t, int s); /* destructor */ ~pq(); /* to check the pq is empty or not*/ bool empty(); /* to remove node */ void pop(); /* to insert node */ void push(int data); /* return the tree size */ int size(); /* to get the top of the tree */ int top(); } ``` - 資料由小到大順序排列以 10 萬筆資料到 100 萬筆資料 | data 數 | my_pq(第一次) | my_pq(第二次) | my_pq(第三次) | my_pq(平均) | | ------- | ------------- | ------------- |:------------- | ----------- | | 100000 | 0.03006 | 0.02919 | 0.031959 | 0.03028 | | 200000 | 0.03993 | 0.036198 | 0.056237 | 0.044121 | | 400000 | 0.050892 | 0.068313 | 0.070066 | 0.063090 | | 600000 | 0.085633 | 0.098455 | 0.087791 | 0.090626 | | 800000 | 0.124831 | 0.108754 | 0.110198 | 0.114594 | | 1000000 | 0.149021 | 0.149008 | 0.124445 | 0.140824 | | data 數 | stl_pq(第一次) | stl_pq(第二次) | stl_pq(第三次) | stl_pq(平均) | | ------- | -------------- | -------------- |:-------------- | ------------ | | 100000 | 0.001908 | 0.002878 | 0.001651 | 0.002145 | | 200000 | 0.002524 | 0.002429 | 0.003418 | 0.002790 | | 400000 | 0.006056 | 0.004783 | 0.004756 | 0.005198 | | 600000 | 0.007759 | 0.008056 | 0.010521 | 0.008778 | | 800000 | 0.009296 | 0.009366 | 0.009465 | 0.009375 | | 1000000 | 0.011264 | 0.011689 | 0.011261 | 0.011404 | ![](https://i.imgur.com/ohAN2Ac.png) #### 兩種紅黑樹實作比較接下來將比較兩種不同的紅黑樹實作，分別進行插入節點的比較，而節點的會分成順序排序的節點還有亂數排序的節點兩種資料及進行比較，主要的操作內容會是插入所有節點之後，確保樹是平衡的。 :::spoiler 原先命名不佳的部份以下實驗稱 [quiz3 中紅黑樹](https://gist.github.com/jserv/920766d1fd893d0efd66ac7fdaf23401)為 Original，而 [quiz4 中的紅黑樹](https://gist.github.com/jserv/6610eb56bf2486979c8bf6ee8061f71c)為 Innovative ::: 以下實驗稱 [quiz3 中紅黑樹](https://gist.github.com/jserv/920766d1fd893d0efd66ac7fdaf23401)為 rbt-3nodes，而 [quiz4 中的紅黑樹](https://gist.github.com/jserv/6610eb56bf2486979c8bf6ee8061f71c)為 rbt-2nodes - 亂數排序 | data 數 | rbt-3nodes(第一次) | rbt-3nodes(第二次) | rbt-3nodes(第三次) | rbt-3nodes(平均) | | ------- | ---------------- | ---------------- |---------------- | -------------- | | 10000 | 0.002138 | 0.002149 | 0.002102 | 0.002130 | | 40000 | 0.009702 | 0.009803 | 0.008167 | 0.009224 | | 70000 | 0.014931 | 0.016541 | 0.014661 | 0.015378 | | 100000 | 0.021267 | 0.020736 | 0.020204 | 0.020735 | | data 數 | rbt-2nodes(第一次) | rbt-2nodes(第二次) | rbt-2nodes(第三次) | rbt-2nodes(平均) | | ------- | ------------------ | ------------------ |------------------ | ---------------- | | 10000 | 0.000807 | 0.000798 | 0.000825 | 0.000812 | | 40000 | 0.003777 | 0.003751 | 0.003738 | 0.003755 | | 70000 | 0.007339 | 0.005851 | 0.006031 | 0.006407 | | 100000 | 0.008507 | 0.009132 | 0.009699 | 0.009113 | :::spoiler 命名不佳的圖片 ![](https://i.imgur.com/dw6BTaQ.png) ::: ![](https://i.imgur.com/9y3UnhL.png) 為了了解為何效能究竟會差距如此大，使用 perf 來進行分析，這邊所使用的插入資料集都是亂數排序的，而這個實驗要採用插入亂數的原因在於，假如插入連續的數值的話，就會導致整顆紅黑樹的平衡性可能會受到嚴重影響，導致性能下降。例如插入連續數值會導致頻繁的旋轉操作，進而降低插入的效率。 - rbt-3nodes ``` Performance counter stats for './testing' (10 runs): 1,313,449 cache-misses # 31.320 % of all cache refs ( +- 1.09% ) 4,182,720 cache-references ( +- 0.81% ) 98,541,507 instructions # 1.07 insn per cycle ( +- 0.59% ) 92,258,935 cycles ( +- 1.14% ) 0.023043 +- 0.000468 seconds time elapsed ( +- 2.03% ) ``` - rbt-2nodes ``` Performance counter stats for './pq' (10 runs): 128,824 cache-misses # 7.182 % of all cache refs ( +- 4.10% ) 1,779,453 cache-references ( +- 1.19% ) 93,405,918 instructions # 2.49 insn per cycle ( +- 0.03% ) 37,767,058 cycles ( +- 0.58% ) 0.011277 +- 0.000737 seconds time elapsed ( +- 6.54% ) ``` 可以看到在 quiz4 中所設計的紅黑樹在 cache-misses 的部份明顯的小於 quiz3 中的紅黑樹，因此在差不多的 instructions 總數下， quiz4 的 rbt-2nodes 版紅黑樹的 IPC性能明顯優於 quiz3 版的。這樣的結果也符合實作的預期，精簡了紅黑樹節點所佔用的空間，也符合老師的說明。 > 考慮到 cacheline 在 x86(-64) 架構為 64 bytes，能夠放入 cache 的節點數量因為這樣的記憶體佈局 (memory layout)，變得更多，且紀錄 cmp 的成本相對低並對 cache 友善。 :::warning TODO: 引入 [rb-bench](https://github.com/jserv/rb-bench) 進行評比和分析 :notes: jserv ::: --- ## 測驗二 --- ## 測驗三 ### 分析程式碼該程式的走訪是以迭代的方式來進行的，而第一題的走訪是以遞迴來進行的。 ```c=255 static int sum_subtree(node_t *node) { int result = 0; while (node) { node_t *pre; if (!rbtn_left_get(node_t, link, node)) goto do_print; for (pre = rbtn_left_get(node_t, link, node); rbtn_right_get(node_t, link, pre) && rbtn_right_get(node_t, link, pre) != node; pre = rbtn_right_get(node_t, link, pre)) { } if (!rbtn_right_get(node_t, link, pre)) { rbtn_right_get(node_t, link, pre) = node; node = rbtn_left_get(node_t, link, node); } else { rbtn_right_get(node_t, link, pre) = NULL; do_print: result += node->value; printf("value: %d\n", node->value); node = rbtn_right_get(node_t, link, node); } } return result; } ``` ![](https://i.imgur.com/nheLnjb.png) 以上面這棵樹為例，在第一次的 while-loop 會把 node 從 `0004` 移動到 `0002` ，在藉由下一次的 while-loop，找到 `0001`，就會移動到第 273 行的 do_print 這個 label，關於這些 goto 的使用方法可以參考 [你所不知道的 C 語言: goto 和流程控制篇](https://hackmd.io/@sysprog/c-control-flow)。因為這些節點在進行插入的時候就已經進行排序了，所以印出節點的時候必定是按照比較的函式 (在此例是用 node_less，比小的函式)的順序印出。因此就會得到這樣的輸出 ```shell $ ./rbi 1 2 3 4 5 6 7 8 9 10 11 12 lookup(11): OK value: 1 value: 2 value: 3 value: 4 value: 5 value: 6 value: 7 value: 8 value: 9 value: 10 value: 11 value: 12 sum: 78 ``` ### 加入測驗題一所用的技巧若要將測驗 1 對節點的紅色和黑色標注的技巧嵌入到指標變數中，需要修改結構以及一些巨集。如以下所示 ```c /* Node structure */ #define rb_node(x_type) \ struct { \ x_type *left, *right_red; \ } ``` 將結構體換成測驗題一的形式，將顏色標注嵌入到 `右邊節點的指標變數當中` 接著引入及修改巨集成測驗題一的形式最後需要修改 `sum_subtree` 這個函式 ```diff ... if (!rbtn_right_get(node_t, link, pre)) { - rbtn_right_get(node_t, link, pre) = node; + rbtn_right_set(node_t, link, pre, node); node = rbtn_left_get(node_t, link, node); } else { - rbtn_right_get(node_t, link, pre) = NULL; + rbtn_right_set(node_t, link, pre, NULL); do_print: result += node->value; ... ``` --- ## 參考資料 - [linux]([torvalds/linux](https://github.com/torvalds/linux)) - [RBT Visualizations](https://www.cs.usfca.edu/~galles/visualization/RedBlack.html)