2024q1 Homework2 (quiz1+2)

第一次測驗

Testing 1 : non-recursive link list quick sort

參考 Optimized QuickSort — C Implementation (Non-Recursive) 來實作非遞迴的 quick sort, 首先為了比較 recursive and non-recursive 的差異，我實作了一個 recursive 版本的 quick sort, 通過實驗數據來比對兩者的差異。
分析 Optimized QuickSort 如何做到 non-recursive 的作法，主要是使用到了 stack 的概念，多了兩個 array 來存放這次需要 begin and end 範圍，以下程式碼為主要的分割概念。

arr[L]=piv; beg[i+1]=L+1; end[i+1]=end[i]; end[i++]=L;

我們以 10 個 node 來做例子，假設第一次的 pivot 實際位於第七個 node, 最一開始的時候我們是檢查 0 ~ 10, 當第一個 pivot 結束後，應該要將他們拆開成 0 ~ 7 and 8 ~ 10, 所以目前的 array 就會變成以下的樣子，直到變成 i 變成 0 後跳出迴圈。

i 迴圈	0	1	2
begin	0	7	?
end	7	10	?

compare times

觀察以下的 swap, 每次 compare 成功就必須做三次的轉換，然而在 optimized quick sort 裡卻只需要兩次的轉換。

int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;

為什麼可以做到只有兩次呢？當一開始的時候我們會將 pivot 設為第一個的值(L)，從 R(lsb) 開始找到替換值，直接覆蓋 L 值，之後再從 R 值開始找到替代值，替代 L, 所以省下的那次是因為我們不是直接找到兩個需要交換的值，再透過 tmp 來交換。

cycle time

透過 dudect 測量的 cycle time 的方式，在程式中插入 x86 rdtscp, 可以計算出精準度較高的 cycle time

uint64_t rdtscp() {
    uint64_t tsc;
    asm volatile ("rdtscp; "          // serializing read of tsc
                  "shl $32,%%rdx; "  // shift higher 32 bits stored in rdx up
                  "or %%rdx,%%rax"   // and or onto rax
                  : "=a"(tsc)        // output to tsc variable
                  :
                  : "%rcx", "%rdx"); // rcx and rdx are clobbered
    return tsc;
}

average 10 times

cycle time	10000	100000
non-recursive	26613060	172404088
recursive	34850950	304100050

實驗中發現的問題
可以發現 non-recursive 的速度快很多，然而 non-recursive 會有 stack 爆炸的問題，使用 valgrind 發現手動調整就可以通過，所以這個以 stack 紀錄範圍的方式說不定可以再優化。

valgrind --leak-check=full --max-stackframe=6400000 ./a.out

link list optimized quick sort

shuffle
我發現這裡使用到了 Fisher-Yates的亂數方法，可以獲取 1 ~ n-1 的隨機數字。一開始很不能明白為什麼不用 mod 可以找到特定範圍的數字，以下 code 的概念使用了分區的方式，我先將 RAND_MAX 分割範圍，然後只要用除法就可以知道這次在哪個範圍，i 的用處就是控制切割範圍大小。

size_t j = i + rand() / (RAND_MAX / (n - i) + 1);

這裡有一段 shuffle 的 code, 可以運用數學的方式交換而不需要多宣告一個參數，但如果數字過大就會有 overflow 的問題。

- int t = array[j];
- array[j] = array[i];
- array[i] = t;
+ array[j] += array[i];
+ array[i] = array[j] - array[i];
+ array[j] -= array[i];

quick sort
假設目前要排列的 link 為以下圖示，首先會選出 pivot 這裡選定為 4.

再來將左邊與右邊分開
begin[i]

begin[i+1]

begin[i+2]

如果不需要比對的時候就會直接將值由大到小的加入到 result list, 排序及完成。

可改進點

pivot 挑選
begin and end 的 array 大小

Testing 2 : Timsort

glossary

run : 切割出的資料
run size : 有幾個資料
run length : 總共的 run 切割數

特性：為了解決日常可能會遇到的排序，通常為非亂序，有一定排序的 list
改良 (相較於 mersge sort)

降低 cache : 會在部分排序完後嘗試合併，減少 cache miss 所造成的成本
降低記憶體開銷 : 只需要配置重疊部分
減少進行合併次數

構思

不看實作嘗試理解及揣測
Timsort 混合 merge sort 以及 insertion sort 且為 stable 的排序演算法，特性是可以有效的處理日常數據 e.g. 大部分以排序的資料。

在 timsort 中會把一次切割的資料稱為 run, 而這個 run 所切割的大小會大大影響效能，我們會先限制一個最小 run length 的大小，在這個 run 裡面會是用 insertion sort 的方式(insertion sort 在資料集少的時候表現好)。

為了達到 balance 的 merge, timsort merge 時會以 stack top 的三個 run 來做 merge 的判斷，且 merge 的判斷都是以相鄰的 run 來合併，這樣可以達到 cache friendly。

如果

X + Y > Z

會作以下 merge

而針對 array 的版本 timsort 為了解決 merge sort 總是會使用額外的空間來合併，提出了一種方法，只須針對重疊的部份作 merge。e.g. [1,2,3,6,10] merge [4,5,7,9,12,14,17] 只須判斷 [4~10] 就可以全部做完，因為剩下的都不會互相影響。

Galloping mode 會設置 minimum galloping threshold 來判斷是否要做 galloping mode, 此機制是每次從一個 run 找到要插入的點，再從被插入的 run 找到對應插入點。 e.g.

$A [1, 2, 3, 7, 8, 9]$
$B [4, 5, 6, 10, 11, 12]$

找到 4 inserted point

$A [1, 2, 3, 4, 7, 8, 9]$
$B [5, 6, 10, 11, 12]$

找到 7 inserted point

$A [1, 2, 3, 4, 5, 6, 7, 8, 9]$
$B [10, 11, 12]$

…依此類推

Timsort 實作遇到的問題

find_run
這裡目前切 run 的方式沒有做過多的處理，只是把已經排好的切成一個 run, 所以需要查閱資料並實作有率的 run 切割。此外這裡有個很有趣的計數方式，因為我們在切 run 的時候只使用到單向鍊結，
，因此可以把 length 用 point 的方式藏在 prev.

head->next->prev = (struct list_head *) len;

merge
與 libsort 的 merge 方式一樣，在看到第 2,3,4 行有注意到，如果

a_{0 - n}

連續n1筆都是小於

b_{0}

, *tail = a 是否等於做白工。








if (cmp(priv, a, b) <= 0) {
    *tail = a;
    tail = &a->next;
    a = a->next;
    if (!a) {
        *tail = b;
        break;
    }

merge_at
把自己跟前一條 list 做 merge
merge_collapse
依照 stak_size 來決定合併的方式，先假設 A, B, C, D, E 為 stack 目前紀錄的長度且有順序的概念。
這樣可以確保鄰近的 list 會先 merge 且 merge 間的 length 不會差太多。

- if (n >= 3 且 A <= B + C) || (n >= 4 且 A <= B + C)
    - if (A < C) 做 B 的 merge
    - else 做 C 的 merge
- else (n >=2 且 A <= B)
    - 做 B 的 merge

嘗試改良切割 run

目前完全是依據當前有多少連續上升或下降的方式切割，而現在要注意的點有以下：切割出的總數量因該小於 2 的冪，且長度不能太短。思考：如何分割是可以達到較佳的效果？站在 merge 的角度要讓 merge 的兩個 run 長度差不多。

insertion sort 在 64 個值以下會有較佳的效能，而 run size 也要小於等於 2 的冪，如何作到？

根據 Minimum run size run length 在 32 ~ 64 會有較佳的表現，這裡有提到一個方法，首先提取 msb 的 6 個 bit, 如果後面還有就 + 1 這樣就可以得到 minimim run size, 原理是：6 個 bit 代表我們要取 32 ~ 64 的範圍，而在 2 進位中假設

0 b 10

的第 1 位元代表由兩的第 0 位元組成，所以就可以確保 merge 時是兩兩相似長度合併且會 <= 2 的冪，再來是加入 insertion sort 來處理 run 內部的排序。

如何找到對應的 6 位 MSB 可以搭配 GCC Built-in function __builtin_clz

Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

uint64_t mask = (1ULL << 6) - 1;
uin64_t num_bits = 64 - __builtin_clzll(total_length);
int min_size = (total_length >> (num_bits - 6)) & mask;
min_size += !!(total_length & mask << (num_bits-6));

timsort_test 方式

在 check_list 中發現實作了測試 stable 的方式，這是我以前在測試時不會想到要考慮正確性的點，透過加入額外 seq 的方式可以檢查最後排序的結果是否 stable，這裡還有個思考點：是否可以在排序時就檢查？

int unstable = 0;
list_for_each_entry_safe (entry, safe, head, list) {
    if (entry->list.next != head) {
        if (entry->val == safe->val && entry->seq > safe->seq)
            unstable++;
    }
}

在產生亂數的地方看到了一段註解 Assume ASLR
ASLR 是一種安全機制，通常在操作系統中使用，它會隨機地改變程序的內存地址佈局，增加攻擊者對特定記憶體位置進行攻擊的難度，所以使用的 main 每次位置都會不一樣。

實驗設計

minimal run size 調整大小的影響。

第二次測驗

Testing 1

目標是利用 preorder 加上 inorder 做出 unique 的數列，並加以測試。
e.g.

Input : preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

這邊注意到 struct hlist 成員有 *next 以及 **prev, 為了了解原因參考了Linux 核心的 hash table 實作，因此在這裡整理我的理解。
為什麼要以 **pprev 的方式而不是 doubly link list? 因為我們可以透過控制 prev 達到不用再將 list_head 傳入當 function 就可以處理刪除 first node 的例外處理。

struct hlist_head {
    struct hlist_node *first;
};
struct hlist_node {
    struct hlist_node *next, **pprev;
};

buildTree

動態建立跟 inorder 數量一樣的 hlist_head : in_heads
將對應 hash key 插入 in_head
呼叫 dfs

dfs
這是一個遞迴搜尋法，因為 preorder 的第一個元素及為 root 所以先設定好 root, 使用 find 找到對應 index(從這裡可以知道 hash 是為了加速查找，不用走過整個 link list), 接下來討論 left and right 該怎麼接上。

left : 根據從 in_head 找到的 index 限制下次的左邊範圍，
right : 限制右邊的範圍

以下面的例子來說，index 為 1 ,所以下次左邊的範圍會被限制在 1~1 間，右邊則會被限制在 2~4 之間
preorder 選中第一個當作 root

inorder 分別分出屬於左子樹 or 右子樹。

在 Linux 核心的 cgroups 相關原始程式碼，找出 pre-order walk 程式碼並探討

cgroups ： control groups
patch of cgroups writeback support
我在閱讀 fsync syscall 時為了瞭解 write back 的流程注意到 Writeback and control groups, 把資料從 memory 寫入 persistent device 是一件棘手的事，kernel 必須在 dirty pages 與 limited I/O bandwidth 間平衡，以下提出為什麼需要使用 cgroups.

There is a "magical function" called balance_dirty_pages() that will, if need be, throttle processes dirtying a lot of pages in order to match the rate at which pages are being dirtied and the rate at which they can be cleaned. It works reasonably well in current kernels, but it only operates globally; it is not equipped to deal with control groups

然而 block controller 與 memory controller 並不能好好協調

Writeback is clearly related to both memory use and I/O bandwidth, but the control-group mechanism offers no way to enable controllers to work together

我總結一下這邊的問題，如果有不對的地方請幫我指正
block control 並不能得到 memory control 的資訊，因此並不會去執行特定 control group 的資料，這樣會影響 global dirty-page watermarks

kernel 中有兩個 struct 會參與 write back backing_dev_info 知道寫入 device 以及追蹤 IO bandwith, bdi_writeback 設定回寫。因此為了解決上述問題，將更多的資訊從 backing_dev_info 移到 bdi_writeback. 更多資訊可以從 commit 52ebea749aaed195245701a8f90a23d672c7a933 取得。

balance_dirty_pages() is changed to use the per-group bdi_writeback structure, as are other pieces of the writeback-control mechanism. Tejun described it as being mostly "a giant plumbing job.

在 submit_bio 裡面做的第一件事就跟 cgroup 有關西，不過還有待理解。

blk_qc_t submit_bio(struct bio *bio)
{
	if (blkcg_punt_bio_submit(bio))
		return BLK_QC_T_NONE;

可改進點

目前是把 indorder 數量當作 hash table 的預設空間大小，且還有可能發生碰撞，所以其實不需要 hash table 只需要用 index 當作 key 就好，但如果當測資很大時，array 沒那麼大時，就可以構思 hash table 的大小的設計。

Testing 2

分析 LRU 實作，會將目前最久沒用的 cache 剔除，這裡維護兩種 list, doubly link list and hlist, 在這裡 list 維護所有的 cache, 會形成一條長鍊，所以可以簡單的插入以及剔除，而如果我們想從這條長鍊找到對應的 node 將會付出很大的成本，這時候 hlist 就派上用場，可以很容易的找到資料。

lRUCacheCreate

初始化內部成員 list_head and hlist_head

lRUCacheFree

釋放所有 cache

lRUCacheGet

這裡會將回傳對應 key 值的 value, 且 list_move 會將此次的 node 移到 list_head 的頭，這樣便可以達成 LRU 的需求。

lRUCachePut

想要將值放入 cache, 有兩種情況，如果 cache 存在則移到 MSB 位置，否則查看是否還有空間，如果沒空間還要額外做剔除 cache 的動作，接下來再將新的 cache 放入 list and hlist.

在 Linux 核心找出 LRU 相關程式碼並探討

linux kernel 5.14.1

先觀察 struct page 首先注意到用到了大量的 union 這表示這個 struct 被用到很多不同的場景

/**
 * @lru: Pageout list, eg. active_list protected by
 * lruvec->lru_lock.  Sometimes used as a generic list
 * by the page owner.
 */
struct list_head lru;

當發生 page fault 時，會伴隨發生踢除 page cache 的行為。

Testing 3

find n_th bit
此 macro 在 linux kernel 中的 bitmap.h 中出現，主要的目的是設定一個 mask 從低位元開始的 nbits 都是1 其他都是 0, e.g. 輸入3 得到 0b11. 0UL 右移會以 0 的方式補其左邊，而為什麼 nbit 要加上負號，假設輸入 3 表示應該右移 64 - 3 位, 因為負號是

\sim n b i t + 1

也就是

- 3 + 1

所以

64 - 1 - 3 - 1 = 61

剛好是需要右移的量。
這裡的 >> 證實了 unsign shift 是以 logical shift 的方式補齊

找資料輔助說明

#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))

以下的code 參考 GCC built-in functions 是用來

#define small_const_nbits(nbits) \
    (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0)

find_nth_bit

2024q1 Homework2 (quiz1+2)

第一次測驗

Testing 1 : non-recursive link list quick sort

compare times

cycle time

link list optimized quick sort

可改進點

Testing 2 : Timsort

構思

Timsort 實作遇到的問題

嘗試改良切割 run

timsort_test 方式

實驗設計

第二次測驗

Testing 1

在 Linux 核心的 cgroups 相關原始程式碼，找出 pre-order walk 程式碼並探討

可改進點

Testing 2

在 Linux 核心找出 LRU 相關程式碼並探討

Testing 3

Read more

2024q1 Homework5

2024q1 Homework6 (integration)

2024q1 Homework4

2024q1 Homework1 (lab0)