2023q1 Homework4 (quiz4)

contributed by < yanjiew1 >

實驗環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
    CPU family:          6
    Model:               142
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            10
    CPU max MHz:         3400.0000
    CPU min MHz:         400.0000
    BogoMIPS:            3600.00

紅黑樹研究

Linux 核心的紅黑樹 裡面提到了左傾紅黑樹，但 Eddie Kohler 教授在〈Left-Leaning Red-Black Trees Considered Harmful 〉指出左傾紅黑樹的疑慮。故希望能實作傳統紅黑樹和左傾紅黑樹，並進行效能分析研究。

我也有發現 Robert Sedgewick 教授的〈Left-leaning Red-Black Trees〉的描述中，在移除節點步驟，其在往下走訪與往上修正時，都會進行旋轉，猜測可能會對效能有影響。此外也不確定 Eddie Kohler 教授做的實驗是用 2-3 樹版本的實作還是 2-3-4 樹版本的實作。

目前會把研究成果放在這篇文章內。但因時間有限，會先完成其他作業。

TODO: 利用 rb-bench 來比較 FreeBSD 和 jemalloc 在內的紅黑樹實作的效能表現。

jserv

另外在 quiz4 中的紅黑樹，因為沒有親代節點指標，但又是實作非遞迴呼叫，故使用了 path 來存走訪路徑，類似堆疊操作。但先前作業在排序演算法實驗中，手動加入堆疊操作不一定會比用遞迴呼叫有效率，故可以嘗試以遞迴呼叫重新實作取代模擬堆疊操作來比較效能。

而在沒有親代節點指標情況下，走訪也會是個問題。故想嘗試引入引線二元樹的方式，看看能不能在沒有親代節點指標時，也能輕易走訪下一個或上一個中序 (in-order) 節點。

Timsort 研究

Timsort 是結合 Mergesort 和 Insertion sort 的排序演算法。

在這裡要探討 Timsort 對 Mergesort 的改進。以及如何修改 Timsort 使它能在非連續記憶體的 linked list 中有效率運作。

從排序時額外空間使用量、排序所需的比較次數，來探索 Timsort 對 Mergesort 的改進。

研究結果會放在這裡： Timsort 研究與對 Linux 核心貢獻嘗試