# 2023q1 Homework4 (quiz4)
contributed by < [Chiwawachiwawa](https://github.com/Chiwawachiwawa) >
## 測驗一
### 解釋並且補全上述程式碼
#### 插入 insert
```c
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); \
} \
} \
pathp->node = node;
```
此段程式碼用於尋找新節點應該插入的位址。它使用 cmp 來進行比較，並藉由 for 迴圈來選擇是往左邊還是往右邊尋找，直到找到最終的插入點。在這個過程中，有三種情況需要考慮：
1. 若新節點的值比目前節點的值小，則插入到目前節點的左子樹中。即 `pathp[1].node(new node)->node` 的左子樹。
2. 若新節點的值比目前節點的值大，則插入到目前節點的右子樹中。即 `pathp[1].node(new node)->node` 的右子樹。
3. 當 `pathp->node` 為 `NULL` 時，表示已找到最終的插入點，此時將新節點插入到這個位置即可。即 `pathp->node` 存放目前查找到的節點。
```c
for (pathp--; (uintptr_t) pathp >= (uintptr_t) path; pathp--) {
...
```
這段程式碼可分為幾個步驟。在確定好插入位置後，我們需要處理幾個情況。因為插入新節點後，需要對已插入的樹進行調整，以符合紅黑樹的定義。觀察程式碼，這次實作範例使用的是左傾紅黑樹 (LLRBT)。
:::warning
判斷的依據是什麼？
:notes: jserv
:::
:::info
:::
最後，我們將處理好的樹的節點顏色設定為黑色。
```c
rbtree->root = path->node;
rbtn_black_set(x_type, x_field, rbtree->root);
```
#### 刪除 remove
### 閱讀以下文章
Jemalloc:
jemalloc 最大的優勢還是其強大的 scalability，
對於 lock contention 是其最大的解決議題，其中我們來嘗試探討紅黑樹相關內容，
由於紅黑樹對平衡性的要求沒有 AVL 樹高，因此頻繁插入和刪除節點時，觸發平衡調整
的次數更少，平衡調整的過程也更易收斂。
我們來觀察插入以及刪除的相關程式碼
結構:
### 當插入時會有幾個情形進行討論
1.插入的紅色節點在左邊時:
case 1 : parent = black
直接完成
case 2 : parent = red
這樣會產生連續兩個紅色節點相連，這時我們需要將 `node->left->left` 的節點轉為黑色， `node->left` 轉為新的 node，並且還是維持紅色，因為我們要確保 `node->left` 的 parent_node 為黑色，調整之後:
```c
left_node = new_node(red)
left->left->node = left_node(black)
root(black) = right_node(black)
```
接下來，程式進行<s>回朔</s> [回溯](https://dict.revised.moe.edu.tw/dictView.jsp?ID=85125)，因為新的 root 被改為 red。
當插入的節點(red)在右邊時:
case 1 : `(parent = NULL || black) && (parent == black)`
我們這個情況要進行左旋，調整後:
```c
new_node = new_parent
old_parent_color = black
old_parent = left_child && color = red
```
case 2 : `parent->left_node = NULL && (color == black)` 以這個條件下為前提，當 `parent_node color == red`
同樣進行左旋
調整後:
```c
new_node = new_parent
old_parent = left_child, color = red
do next loop...
```
下一個情況我們就會遇到前面提過的 case (`root->left && root->left->left = red`)(第一段的 case 2)。
case 3 : p`arent_node->left && color == red`
我們需要將 left&right_color set black，並且將 `parent_node` 的 color 改為 red 。
因為 parent_node 被改了顏色，所以我們需要一直進行回溯，直到我們遇到黑色的節點。
### 當刪除時會有幾個情形進行討論
如果刪除的節點為紅色，因為不會影響到平衡，故直接刪除即可，反之，則我們需要一直進行回溯，並且恢復平衡(路徑上的黑色節點要一樣)，重複此動作，直至數量平衡。
接下來我們來看看刪除的相關程式:
```c
for (pathp = path; pathp->node != NULL; pathp++) { int cmp = pathp->cmp = a_cmp(node, pathp->node);...
```
if (cmp < 0)
這個情況我們做這一步就可以了
```c
pathp[1].node = rbtn_left_get(a_type, a_field, \
pathp->node)
```
但是
if (cmp == 0)
這時我們需要將後續的節點保存下來以便做處理
```c
pathp->cmp = 1;
nodep = pathp;
for (pathp++; pathp->node != NULL;
pathp++) {
pathp->cmp = -1;
pathp[1].node = rbtn_left_get(a_type, a_field,pathp->node);
}
break;
}
}
```
`if (pathp->node != node)`
用最後一個靠近的節點的 child 來代替此節點，並保存替代節點的顏色
```c
bool tred = rbtn_red_get(a_type, a_field, pathp->node);
```
然後把替代節點重新著色
```c
rbtn_color_set(a_type, a_field, pathp->node,
rbtn_red_get(a_type, a_field, node));
```
接下來跳過一些單純的部分，我想著重講一段我個人認為不好閱讀懂的地方
```c
if (rbtn_red_get(a_type, a_field, pathp->node)) {
assert(pathp[-1].cmp < 0);
rbtn_left_set(a_type, a_field, pathp[-1].node, NULL);
return;
}
```
這裡 `pathp->node` 就是需要刪除的節點，但是它的顏色經由上述忽略的程式碼可以看出，已經被替換他的節點顏色所取代，而且他在這顆紅黑數裡面的位置也被移除了，在 path 堆疊的位置也被置換到了頂端，
而這邊 assert 是指沒有右節點為紅色的紅黑樹，只有左節點為紅色節點的紅黑樹，那這時如果，右節點為紅色，插入時左節點為紅色，則他們同時需要變為黑色，如果左節點為空或是為黑色，則我們需要進行左旋，因此，這段程式碼，是用來確保紅色的節點只存在左邊的子節點，所以它 `parent` 的 `cmp < 0`。
在講解完一些比較難的地方之後，我要接這來對比 Linux 核心之中的一些優劣
這邊用到老師提供的專案 [rb-bench](https://github.com/jserv/rb-bench)。
### [rb-bench](https://github.com/jserv/rb-bench)
進行 `make image` 會得到一張效能統計圖片
可以看到，在小單位測試樣本的情況下，我們會發現 "Linux" 的效能竟然不是最好的，不論線性還是隨機情況下輸入。
### 探討原因(觀察 FreeBSD 的 tree)
在SmallSetLinear情況下，我發現 FreeBSD 的效能最好，因此繼續閱讀相關內容。
### (FreeBSD,Linux,Jemalloc)共同使用到的功能：
在 test.h 之中，可以看出如何使用 random 機制來生成隨機數的。
首先觀察各個樹插入的相關議題。
### 研讀 FreeBSD 實作
FreeBSD `rb_tree` structures
```c
struct name { \
struct type *sph_root; /* root of the tree */ \
}
#define SPLAY_INITIALIZER(root) \
{ NULL }
#define SPLAY_INIT(root) do { \
(root)->sph_root = NULL; \
} while (/*CONSTCOND*/ 0)
#define SPLAY_ENTRY(type) \
struct { \
struct type *spe_left; /* left element */ \
struct type *spe_right; /* right element */ \
}
```
閱讀插入相關函式
#### `RB_INSERT` FreeBSD vs. Linux
```c
name##_RB_INSERT(struct name *head, struct type *elm) \
{ \
struct type *tmp; \
struct type **tmpp = &RB_ROOT(head); \
struct type *parent = NULL; \
\
while ((tmp = *tmpp) != NULL) { \
parent = tmp; \
__typeof(cmp(NULL, NULL)) comp = (cmp)(elm, parent); \
if (comp < 0) \
tmpp = &RB_LEFT(parent, field); \
else if (comp > 0) \
tmpp = &RB_RIGHT(parent, field); \
else \
return (parent); \
} \
return (name##_RB_INSERT_FINISH(head, parent, tmpp, elm)); \
}
```
我們先判斷 root 是否為空，如果不是的話，就進入 while 進行實作，
這邊我有一個問題，為何在 linux 之中，第一堂課有提到，
通常在判斷條件的情況下，會將 `(tmp = *tmpp) = NULL`放在前端，
那為何在這個程式裡面遇到這種情況（？
因此我想測試一下以下程式
```c
name##_RB_INSERT(struct name *head, struct type *elm)
{
struct type *tmp;
struct type **tmpp = RB_ROOT(head);
struct type *parent = NULL;
if (!(tmp = *tmpp)){
return(name##_RB_INSERT_FINISH(head, parent, tmpp, elm))
}
parent = tmp;
__typeof(cmp(NULL, NULL)) comp = (cmp)(elm, parent); \
if (comp < 0) \
tmpp = &RB_LEFT(parent, field); \插入左子
else if (comp > 0) \
tmpp = &RB_RIGHT(parent, field); \插入右子
else \
return (parent); \已經存在了
}
```
接下來我們探討一下為何 FreeBSD 的效率會高於 Linux 核心因此我要對照 Linux 核心近似於 `RB_LEFT` 的功能
#### `RB_LEFT`
```c
RB_LEFT(elm, field) _RB_LINK(elm, _RB_L, field)
```
#### `RB_LINK`
```c
_RB_LINK(elm, dir, field) (elm)->field.rbe_link[dir]
```
在 Linux 核心的插入過程中，
我發現，在 linux 之中關於插入的函式，比 `RB_INSERT` 多的實在是太多了，
但是 linux 的插入在我看來是直觀非常多的，
但是由於 FreeBSD 效能比較好，因此我決定按照他的風格來改寫一些 linux 上面的實作，
我觀察到呼叫流程，我發現 FreeBSD 對於紅黑樹的平衡有一些與 linux 的實作有一些不同的地方，他是額外獨立出一個函式來進行處理，在 insert 之中來透過 _RB_INSERT_FINISH 來進行呼叫
`if ((_RB_BITS(gpar) & _RB_LR) == 0)`
在我的初步閱讀下，我發現 BSD 紅黑樹十分注重「高度」，基本上對於樹結構的調整也是圍繞著這個議題打轉
我們可以看到：
`/* the rank of the tree rooted at elm grew */`
因為在 `_RB_INSERT_COLOR` 的開頭有提到 The balance criterion "the rank of any leaf 因此在插入所有的節點時 ，不論其出身(一視同仁的味道飄出來了)，它使用來進行平衡的原理是利用紅黑樹要求所有的 leaf 到 root 所有的黑色節點都有一樣的數量，來進行平衡。
這邊我要收回我前面說的，
linux kernel 的程式碼直觀多了QQ
在這個過程中，我發現，雖然我對 `_RB_INSERT_COLOR` 還是沒有很了解，但是在`_RB_INSERT_FINISH` 以及其他函式，沒有很多的 node swap 操作。
接下來比對一下 FreeBSD 之餘 Linux 並且試著找出為何會在一些情況下優於其的因素。
也許問題不出在這邊，但我們先觀察一下。
我著重比較的地方為 `rb_insert_color`
因為我發現， linux 與 FreeBSD 對於判斷祖輩節點的顏色，判斷當前節點位於的位置，等等方式有所不同，
我先統整一下。
### how Linux red_black_tree works
### 對比
Linux:
`rb_set_parent_color`
```c
static inline void rb_set_parent_color(struct rb_node *rb,
struct rb_node *p, int color)
{
rb->__rb_parent_color = (unsigned long)p | color;
}
```
FreeBSD:
`_RB_INSERT_COLOR`
我們可以看到， FreeBSD 用來判斷插入節點對於樹高影響的方式為：
這邊利用 RB_BITS(gpar(有可能為1.2.3)) 來對 elmdir(判斷是在 parent 節點的左邊還是右邊) 做判斷，
判斷的重點為將兩者做 bitwise-AND 操作
#### 旋轉(rotation)
老師上課提供的教材有提到，
在紅黑樹操作中，旋轉是需要教高成本的操作，
因此我需要判斷兩個東西，
第一個是 linux 以及 FreeBSD 做一個旋轉所需的成本，
並且分析他們在各個情況下進行旋轉的次數。
FreeBSD:
```c
#define RB_ROTATE(elm, tmp, dir, field) do { \
if ((_RB_LINK(elm, dir ^ _RB_LR, field) = \
_RB_LINK(tmp, dir, field)) != NULL) \
RB_SET_PARENT(_RB_LINK(tmp, dir, field), elm, field); \
_RB_LINK(tmp, dir, field) = (elm); \
RB_SET_PARENT(elm, tmp, field); \
} while (/*CONSTCOND*/ 0)
```
插入`_RB_INSERT_COLOR`:
這邊被 vscode 坑了一把，註解上面的圖片跑板了...因此在詳細閱讀完以後，我重新復原了它
not valid case1:
```
parent parent
/ \ / \
element n1 ----> child n1
/ \ / \
n2 child element n4
/ \ / \
n3 n4 n2 n3
```
not valid case2:
```
parent child
/ \ / \
child n1 ----> n2 parent
/ \ / \
n2 n3 n3 n1
```
**依據我的理解，每次 call 這個函式最多會呼叫兩次 rotation 功能**
刪除`_RB_REMOVE_COLOR`:
case1:
```
parent parent
/ \ / \
element sibline -----> element element*
/ \ / \
element* n1 n2 sibline
/ \ / \
n2 n3 n3 n1
```
case2:
```
parent element
/ \ / \
n1 element -----> parent n3
/ \ / \
n2 n3 n1 n2
```
這邊我們不能分開看，
要將兩個情況做結合，
當一顆不平衡的樹進入這個函式中時，我們會需要將述作最後的平衡，在最差的情況下，
我們需要額外多做一次 case 1，
最後將 sibline 這棵子樹提取上來。
閱讀〈[Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree)〉相關的例子後，我發現 Linux 有一個寫法跟 FreeBSD 不同。
接下來我們進行單獨討論。
### remove
remove的情況跟前者差不多
### 遇到的問題
我目前遇到的問題是，我找不到兩者明顯的效能差異所在(在對比了兩者對於自平衡相關的操作，我還找不到顯著的效能差異)
目前只能看到結果，
但如果想要提昇 linux，或是題目上面的程式效率，
FreeBSD 版本的紅黑樹必定有值得學習參考的地方，
### 不同情境下的議題
我目前想要了解的是，在 FreeBSD 上的實作，能看到他是將盡量規避一些進入 `_RB_INSERT_FINISH` 之中的 `rb_insert_color` 而刪除亦然，
有跟老師討論中提到，FreeBSD 的寫法在於將一些需要左右旋轉的函式獨立出來，並且加入了 `spy_tree`，在一般的演算法書籍中有提到，這種樹的時間複雜度不甚理想(在數字體量上夠大時)，但目前我們在 `RB_BRANCH` 這項專案之中，我們需要的場景需要的數字量不超過 128 個。
其他也很類似的場景中，我們不一定需要有多大的計算量，
因為 Jserv 老師有提到，紅黑樹對 cache 不是那麼的友好，
所以我需要探討出，在 128 數量以下的操作中，我們需要付出哪些代價來執行紅黑樹，
並且，在 freebsd 之中的實作，他有一些相對 linux 小的支出，
目前我的探討方向有三個點。
#### 1.找出為何 rb_tree 對 cache 不友善
在我查詢了很多篇 CSDN 上面的資源，都沒得到很滿意的答案，
但是我在 jemalloc 的 GitHub 上面看到 [issue #2043](https://github.com/jemalloc/jemalloc/issues/2043)，提到一些關於為何 red-black tree 對於 cache 來說並不是特別友善的原因 cache miss ，甚至在討論中用到了 "terrible"
那為何會有 cache miss 呢？
以 Linux 核心為範例，當我們在判斷何時需要 ROTATE 時，
會需要讀取至少一個點的顏色，
~~而且不需要其他節點相關的資訊，~~
~~那這樣必定會遭遇一次 cache miss，~~(沒有什麼一定不一定...)
經過我的查證與理解，我發現我錯了。
紅黑樹產生 cache miss 是因為各個節點不但不連續存儲在一起，並且使用了很多的間接指標。
這樣的情況下更容易造成所需的東西並不在 cache 之中，
我們來看看 Linux 核心之中相關的案例，
如同以下幾個案例：
`tmp = gparent->rb_right;`
在 kernel 之中，我們時常使用到下面這個函式，但是它對 cache 並不是那麼的友好，
因為據我的想法，它涉及到了寫入的操作，
在一些情況下會有可能造成我們在 cache 讀取時發生 miss (這邊說發生錯誤我認為並不嚴謹)。
```c
static inline void rb_set_parent_color(struct rb_node *rb,
struct rb_node *p, int color)
{
rb->__rb_parent_color = (unsigned long)p | color;
}
```
但是其中的 element 資料我們其實不需要，但是我們有可能會遇到 cache miss ，花費了額外的時間與資源來進行查找出一段我們不需要的資訊。
我要來比較兩者之間的優劣，
#### FreeBSD:
插入：
這邊可以藉由上述部份程式碼看到，我們的 `rb_insert` 並不是像 Linux 一樣，逐步執行下去，而世界由多個函數來組成，盡可能的避免一些會造成 cache missing 的情況。
刪除：
todo...
#### Linux:
插入：
我們需要一直執行 `__rb_insert` 裡面有一個 while loop ，直到我們給定的 parent 為黑色(進入 `!parent` 的情況)，
在這個 while loop 中，
雖然不是每一個場景下都需要進行到 case 1～case 3
(這邊不另行解釋， chatGPT 逐行解說比我強多了)，
但是我發現，在這過程中，
我們需要不停的重複指派 `tmp` 還有 `gpar` ，並且每次變更內容時，都是用新的節點來當做指定值，這樣很有可能會造成我們的 cache miss 問題。
刪除：
刪除亦然，並且更糟糕的是，我們會需要不停的去檢查刪去後各個節點的情況，這是必會需要更頻繁的指定不同的值給我們的 parent 或是 gparent。
#### 2.splay_tree 為何會出現在 FreeBSD 的紅黑樹實作之中？
觀察到當最近被存取的節點很可能在未來再次被存取時，[splay tree](https://en.wikipedia.org/wiki/Splay_tree) 的表現會優於紅黑樹，並且對於需要快速查詢的應用，其效能也相當不錯。其操作方式可以參考〈[Splay tree 圖解與實作](https://blog.csdn.net/u014634338/article/details/49586689)〉。
儘管根據教科書《Fundamentals of Data Structures in C》的描述，這種樹的效能相對較差，但在以上情況下，它確實具有某些優勢。接下來，我將分析其操作方式和旋轉方式，並試著將其與我們先前提到的三種不同實現紅黑樹進行比較。
特點：建立在 locality 之上
其時間複雜度為 $O(m \times \log n)$，$m$ 即是操作次數，當我們操作 $m$ 次，可以保證每次都是 $O(logn)$
原理為：
在每次的操作之後，都會將剛存取到的節點旋轉到根節點，為的是要加速我們後續的操作，具體加速的理論是，當需要重複存取某些節點時，他們會很靠近我們的樹根，進而減少存取所需的時間，並且，一些會需要被頻繁存取的節點，會被靠攏在樹根附近，減少需要旋轉的次數，也可以節省一些成本。
**提問：說到底，它這樣也是為了減少 cache miss 嘛？**
旋轉：
以下圖片摘自上篇提及的 CSDN 文章
左旋
右旋
伸展：逐層 vs 雙層
逐層：
當某個 `node v` 被訪問後，通過左旋以及右旋，使其上升至 root (這邊我的理解是，當我們存取某個節點時，它會逐步的靠近我們的 `root`，有利我們後續的存取)
雙層：
由於上述的方法雖然簡單，但是有一個致命的問題，存取時採用逐層伸展的策略，最壞情況為$O(n)$，這樣會使我們的時間複雜度變為$O(mn)$，這是我們不樂見的，
因此開發者做出了一個改良過的方法，
重點為每次操作時向上調整兩層，
具體方式展示如下
這個方法的優點為，它可以有效的減少整棵樹的高度，
這也是一個很好的方法來減少左傾樹的高度(在完全左傾的情況下，可以直接使高度減半！)
從這個樹(高度為15)
轉換為(高度為7)
缺點：
這種樹的缺點也是十分明顯的，
第一，它不是一個嚴格的自平衡樹。
第二，即使它只有唯讀情況下，自身結構仍然有可能會被改變，並且這個過程是很吃資源的(畢竟我們一直在上面討論怎麼不要進行旋轉，以免造成 cache miss 等等麻煩)。
第三，他有可能會成為一條 linked list ，這個情況下毫無優勢可言，並且會造成這案例的情形是很常見的，只要在有順序的(原文說是當 sequence 的方式進行)情形下輸入數組便會造成！
#### 3.FreeBSD 為何需要將一些函適合外打包出來而非如同 linux 的作法。
進一步觀察第一點，我們可發現之所以這樣做，可能是為了減少讀取親代節點的次數，進而減少 cache miss，在特定情況下形成 cache-friendly 的資料結構。然而，這裡存在一個問題：在 GitHub 上的 issue 討論串和 jemalloc 的官方文件中宣稱此方式是對 cache 友善的，但是要如何定義一個資料結構是 cache-friendly 呢？實際上，即使使用此方式，仍然無法避免許多 cache miss。
> 參見 [Red-black trees are pretty much terrible for performance](https://news.ycombinator.com/item?id=13263664)
#### 效能比較與測量
我在使用 make images 之後，發現只有 .png 檔案有被 modify，但是 make all 並沒有實際更新我們的 XML 檔案，目前正在解決相關問題，
這邊遇到一個問題卡了，我在寫完 `test.h` 想要進行 `make inti` 時，會遇到一些錯誤訊息，這邊 debug 了很久...
```
undefined reference to `test_rbtree_llrb'
...
...
```
這邊與老師討論到一些不同的情境，我需要修改一些測量方法
像是非連續性插入或是刪除，加入更多的測量數字體量等等...
### 如何使用 rb_bench
閱讀 `test.h`
我改寫了部分內容
先講一下老師提供的使用方法，以免出現跟我一樣蠢的失誤(以下)，
:::warning
~~我發現無法使用 `test.h` 來產生 XML 裡面的數據，這邊我要好好處理一下。~~
:::
一定要執行以下步驟來使用我們的專案：
step1:
`make all`
step2:
`刪去 report/XXX.png`
step3:
執行`./rb-bench > reports/test-linux-emag.xml `（這個過程很久，慢慢等）
step4:
執行`./plot.py reports/test-linux-emag.xml reports/test-linux-emag.png`
一直 `make` 是沒有結果的( trace code 功力好弱...)，
像是原始情況使用 128 我們就會得到 128 個數據在每一組，
在我的版本之中，
128
256
512(大概跑了30分鐘)
這邊可以看到，噪音變得非常多...
老師有說要優化這個問題，需要忽略我們的 outlier
1024(天荒地老...)
可以看到我們遇到了跟作業0一樣的情況，當數量被放很大時(其實也還好)，有一些需要額外刪去的因素，會影響我們測試的準確性
這邊出現了一個很有趣的現象，當我們的測試數量往上提升之後，Linux 竟然有較好的性能(跟 FreeBSD 相比的話)
為何呢?
### 非連續插入以及刪除
那個...我使用了順序插入並且隨機再次插入，結果我們可以看到一個很神奇的圖片
修改一下 `plot.py` 使得我們的結果更好看。
很明顯這個修改並沒有什麼意義
我們只能試圖從中看出，
Sign in with Wallet
Connect another wallet