HackMD
2025q1 Homework1 (lab0)
contributed by <weiso131>
開發環境
$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ lscpu
架構： x86_64
CPU 作業模式： 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
供應商識別號： GenuineIntel
Model name: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz
CPU 家族： 6
型號： 140
每核心執行緒數： 2
每通訊端核心數： 4
Socket(s): 1
製程： 1
CPU(s) scaling MHz: 19%
CPU max MHz: 4700.0000
CPU min MHz: 400.0000
BogoMIPS: 5606.40
開發過程
q_new
當函式遇到記憶體分配失敗時，應回傳 NULL。
根據 C 語言標準（7.20.3）：
若無法分配記憶體，則回傳空指標（NULL）。
可以根據 malloc 的結果，決定是否對物件進行初始化，最後直接回傳物件指標。
q_free
此函式的目標是釋放佇列所佔用的所有記憶體。
可以使用 list.h 提供的 list_for_each_entry_safe 來走訪所有節點，並使用 q_release_element 釋放它們，最後再釋放 list_head。
q_insert_head / q_insert_tail
這兩個函式分別負責在佇列的頭部或尾部插入一個節點，並將輸入的字串 s 複製到節點的 value 成員。
如果記憶體分配失敗或佇列為 NULL，則回傳 false。
字串複製
- 使用
strlen計算字串長度。 - 為
value成員分配長度 +1 的記憶體空間。 - 使用
strncpy將輸入字串s複製過去。
插入頭/尾
使用 list.h 提供的 list_add 或 list_add_tail 即可完成此操作。
共用函式 __q_insert
由於 q_insert_head 與 q_insert_tail 具有相似功能，可以建立一個通用函式，透過傳入 list_add 或 list_add_tail 來決定插入的位置。
q_remove_head / q_remove_tail
此函式負責從佇列的頭部或尾部移除一個元素，並回傳該元素。
如果佇列為 NULL 或為空，則回傳 NULL。
若 sp 不為 NULL，則將元素的 value 字串最多 bufsize - 1 個字元複製到 sp 中。
實作流程
- 確認佇列不為
NULL且不為空，這可透過list.h提供的list_empty來檢查。 - 若符合條件，則使用
list_del移除元素。 - 若
sp不為NULL，則執行字串複製。
q_size
實作一個函式回傳佇列的元素數量。
可以利用 list_for_each 走訪整個佇列來計算元素個數。
q_delete_mid
實作一個函式刪除佇列中間的元素。
這裡使用快慢指標來尋找中間節點。
相比其他方法，這種方式具有更好的時間局部性。
q_delete_dup
實作一個函式能刪除所有重複的元素。
- 輸入的佇列必須是已排序的。
- 若成功執行回傳
true。 - 若佇列為
NULL或空，則直接回傳false。 - 若佇列只有一個元素，則直接回傳
true。
此函式會走訪整個串列的所有節點。
若當前節點與下一個節點相同，則刪除當前節點，並標記下一個節點為刪除目標。
若其後的節點不同，則刪除標記的節點。
q_swap
實作一個函式，使佇列中的元素兩兩交換。
觀察可發現，q_reverseK(head, 2) 即可實現該功能。
參考 2025-02-25 問答簡記
q_reverse
實作一個函式，使佇列中的元素顛倒排列。
__reverse
額外實作一個函式處理顛倒排列的功能，以便與 q_reverseK 共用。
使用兩個 list_head 指標 start 和 next。
next 被設為 head->next，然後交換這兩個節點的關係。
重複此過程，直到 start 走到 end。
在 q_reverse 中，start 與 end 皆設為佇列的 head，因為起點與終點都是 head。
void __reverse(struct list_head *start, struct list_head *end)
{
struct list_head *next = start->next, *prev = NULL;
do {
prev = start;
start->prev = next;
start = next;
next = next->next;
start->next = prev;
} while (start != end);
}
q_reverseK
實作一個函式，使佇列中的元素每 K 個進行顛倒排列。
顛倒操作
我實作了一個函式 __reverse_k，專門負責處理此功能。
該函式接受目標區間的起點 start 和終點 end 作為輸入，並利用 __reverse 來執行顛倒操作。
顛倒後，還需調整節點的鏈結關係，使 end 移至前方，start 移至後方，具體操作如下：
struct list_head *l = start->prev, *r = end->next;
__reverse(start, end);
l->next = end;
end->prev = l;
r->prev = start;
start->next = r;
取得需要進行顛倒操作的區間
使用兩個指標 start 和 end 來標記區間的起點與終點，並每次將這兩個指標移動 K 步。
為了實現 K 步移動的功能，我實作了一個函式 __move_k，其主要功能如下：
- 負責將指標向前移動 K 步。
- 回傳實際移動的步數。
- 若未滿 K 步，則表示途中遇到了
head，可用來判斷何時終止迴圈。
由於在 __reverse_k 執行完顛倒操作後，start 和 end 在佇列上的位置將與原本相反，因此需要事先儲存下一個 start 和 end，以便在迴圈結束時進行更新。
void q_reverseK(struct list_head *head, int k)
{
if (head == NULL || list_empty(head) || list_is_singular(head))
return;
struct list_head *start = head->next, *end = head;
int i = __move_k(head, &end, k);
while (i == k) {
struct list_head *next_start = start, *next_end = end;
__move_k(head, &next_start, k);
i = __move_k(head, &next_end, k);
__reverse_k(start, end);
start = next_start;
end = next_end;
}
}
q_sort
此函式使用合併排序法來對鍊結串列進行排序。
在排序開始前，會先解除環狀鍊結串列的狀態，使頭尾不再指向 head。
排序完成後，則會重新將頭尾接回。
__merge
我額外實作了 __merge 來合併兩個已排序的鍊結串列。
該函式的參數如下：
l、r：分別代表兩個鍊結串列。decend：用來決定排序方式。
此實作參考了linked list 和非連續記憶體 中 MergeTwoList 的方法，並嘗試使用間接指標來簡化邏輯。
以下是幾個優化設計：
- 使用
tmp儲存目前元素的下一項指標，即&(*tmp)->next，可避免head為NULL時的特判。 indir用於存放當前優先度較高的串列開頭元素。- 為了維護雙向鏈結的特性，使用
last來儲存上一個元素的位址。
struct list_head *__merge(struct list_head *l, struct list_head *r, bool decend)
{
struct list_head *head = NULL, **tmp = &head, *last = head;
while (l != NULL && r != NULL) {
char *l_value = list_entry(l, element_t, list)->value,
*r_value = list_entry(r, element_t, list)->value;
struct list_head **indir =
((strcmp(l_value, r_value) > 0) == decend) ? &l : &r;
(*indir)->prev = last;
*tmp = *indir;
last = *tmp;
*indir = (*indir)->next;
tmp = &(*tmp)->next;
}
struct list_head *tail = (l != NULL) ? l : r;
*tmp = tail;
tail->prev = last;
return head;
}
__merge_sort
此外，我也實作了 __merge_sort 來遞迴處理鍊結串列的切分，並透過 __merge 進行合併。
此函式的參數如下：
l：鍊結串列的head。decend：決定排序方式。
若 l 為 NULL 或 l->next 為 NULL，則直接回傳 l。
q_ascend / q_descend
實作函式 q_ascend 和 q_descend，與元素右側（next 之後）的元素比較，若較小/較大則刪除，最終使佇列形成遞增/遞減序列。
該函式回傳一個 int，代表剩餘元素數量。
- 若佇列為
NULL或為空，則直接回傳0。 - 若佇列只有一個元素，則直接回傳
1。
由於兩個函式的功能類似，我額外實作了一個函式 __monotonic 來統一實現其功能。
該函式透過改變 decend 參數的 true 或 false，來決定是遞增或遞減。
此函式需與右側所有元素進行比較，因此可以反向走訪所有節點，紀錄當前的最小/最大值，並與目前元素進行比較。（目前的 list.h API 並未提供反向走訪功能）
for (struct list_head *node = (head)->prev, *safe = node->prev;
node != (head); node = safe, safe = node->prev) {
element_t *entry = list_entry(node, element_t, list);
int cmp = strcmp(entry->value, last);
if ((cmp < 0) != descend || cmp == 0) {
last = entry->value;
count++;
} else {
list_del(&entry->list);
q_release_element(entry);
}
}
q_merge
實作一個函式，將多條已排序的佇列合併至第一條佇列中。
- 函式應回傳合併後佇列的長度。
- 若 head 為 NULL 或 chain 為空，則直接回傳 0。
舊的實作方法
與 q_sort 相同，合併過程使用 __merge，因此須先解除鏈結串列的環狀結構，待所有佇列合併完成後再接回。
採用兩兩合併的方式，此方法能使各佇列長度較為均衡，相較於逐一合併，通常能提升效能。
int q_merge(struct list_head *head, bool descend)
{
if (head == NULL || list_empty(head))
return 0;
int chain_size = q_size(head), cnt = 0, chain_cnt = 0;
struct list_head *chain[1000];
struct list_head *q_head = list_first_entry(head, queue_contex_t, chain)->q;
queue_contex_t *chain_entry = NULL;
list_for_each_entry (chain_entry, head, chain) {
chain[chain_cnt] = chain_entry->q->next;
__cut_head(chain_entry->q);
INIT_LIST_HEAD(chain_entry->q);
cnt += chain_entry->size;
chain_cnt++;
}
for (int i = 1; i < chain_size; i = i << 1)
for (int j = 0; j < chain_size; j += i << 1)
chain[j] = __merge(chain[j], chain[j + i], descend);
__link_head(q_head, chain[0]);
return cnt;
}
重新實作
舊的實作方式需要在 stack 上建立一個大小為 1000 的陣列來儲存多條佇列，這會帶來兩個問題：
- 佔用過多的 stack 空間
- 若佇列數量超過 1000，將導致錯誤
新的實作方式參考了 Linux 核心的做法，利用 list_head 的 next 指標來維護單向鏈結串列，合併的部分則直接使用 list_sort 中的 merge 演算法。
根據實驗結果， list_sort 的 merge 函式看似隴長，但它其實比原本透過間接指標儲存比較結果的方式，效能高了將近一倍。
與 list_sort 的概念類似，在合併過程中，list_head 的 prev 指標則被用來維護佇列的前後關係。
使用兩個 struct list_head 物件 r0 和 r1，分別代表待合併的佇列與合併後的結果。
反覆執行合併操作並交換 r0 與 r1，直到 r0 只剩一條佇列且 r1 為空，即代表合併完成。
此方法與舊方法一樣是採用兩兩合併以維持良好的合併效率，但它能夠處理任意數量的佇列，且不會因為佇列數量增加而額外佔用更多記憶體。
使用 merge_final
JeffBla 提到我的 q_merge 其實可以利用 merge_final 提高效率，對此我進行了實驗並進行 t-test
✅ Welch's t-test 結果：
t 值：19.7091
p 值：0.0000 （顯著）
Cohen's d 效果量：0.8814
效能提升倍率：1.0545
不出意外的效能確實提高了
亂數+論文閱讀
在 qtest 提供新的命令 shuffle
實作 Fisher–Yates shuffle
- 初始化
struct list_head *new_node = head， 讓它儲存最後一個被抽到的節點 struct list_head *old_node儲存這輪被抽到的節點new_node = new_node->prev， 代表被抽到的節點增加- 若
old_node == new_node直接進入下一輪 - 利用自訂的函式
__entry_swap()， 交換old_node與new_node的entry value
亂度驗證程式
使用作業說明提供的程式來進行測試
然而，由於字串加法本身不是 1000000 會耗費非常多的時間
因此我將資料蒐集的程式進行了一些調整
nums = []
test_count = 1000000
t_count = 1000
i_char = ['1', '2', '3', '4']
for t in range(t_count):
if t % 100 == 0:
print(f"testing {t}/{t_count}")
# 測試 shuffle 次數
input = f"new\nit {i_char[0]}\nit {i_char[1]}\nit {i_char[2]}\nit {i_char[3]}\n"
for i in range(test_count // t_count):
input += "shuffle\n"
input += "free\nquit\n"
# 取得 stdout 的 shuffle 結果
command='./qtest -v 3'
clist = command.split()
completedProcess = subprocess.run(clist, capture_output=True, text=True, input=input)
s = completedProcess.stdout
startIdx = s.find(f"l = [{i_char[0]} {i_char[1]} {i_char[2]} {i_char[3]}]")
for i in result:
nums.append(i.split())
i_char = nums[len(nums) - 1]
- 將 1000000 分成 1000 次執行，避免對超長的字串做字串加法花費大量時間
i_char儲存上一輪最後一次shuffle的結果，確保與原本的程式效果相同
驗證自己實作的 Fisher–Yates shuffle
測試結果
Expectation: 41666
Observation: {'1234': 41478, '1243': 41641, '1324': 41868, '1342': 41911, '1423': 41819, '1432': 41891, '2134': 41827, '2143': 41549, '2314': 41984, '2341': 41397, '2413': 41918, '2431': 41421, '3124': 41629, '3142': 41389, '3214': 41694, '3241': 41686, '3412': 41694, '3421': 41560, '4123': 41741, '4132': 41988, '4213': 41533, '4231': 41472, '4312': 41520, '4321': 41390}
chi square sum: 21.621561944991118
分析
1234 總共有 24 種組合，只要知道其中 23 組的資料就能得到最後 1 組的，因此自由度為 23
以 0.05 作為顯著水準查表得
Dude, is my code constant time?
論文閱讀
本篇論文透過統計方法探討程式是否能夠在常數時間內完成任務，以此避免時序攻擊。
研究中使用兩種不同類別的輸入數據來測量程式的執行時間：
- random class：每次測量時隨機選擇輸入數據。
- fix class：固定輸入為某個常數值。
接著，記錄程式在這兩種類別下的 CPU 執行時間，並利用 Welch’s t-test 來檢驗程式是否具有常數時間執行特性。
Lab0 實作
在終端機輸入以下指令：
./qtest
cmd> option simulation 1
cmd> new
l = []
cmd> it
可能會顯示：
ERROR: Probably not constant time or wrong implementation
在 qtest.c 搜尋此訊息，可以發現當 simulation 設為 1 時，程式會根據 pos 來執行 is_insert_tail_const() 或 is_insert_head_const()。
這兩個函式由 dudect/fixture.h 定義的巨集封裝，真正的測試函式則實作於 dudect/fixture.c 中的 test_const()。
該函式的核心邏輯由 doit() 負責，它的主要目標是驗證測試函式是否為常數時間運行。
主要函式解析
prepare_inputs()
doit() 執行的第一個函式，負責隨機初始化 classes 與 input_data。
此步驟對應論文中 Step 1: Measure execution time 的 (c) Environmental conditions，其主要作用如下：
- 隨機排列 fix 與 random 的順序（fix 設為 0，random 設為 1）。
- 決定測試類別與輸入數據，分為以下兩種情況：
- fix:
input_data[i] = 0 - random:
input_data[i] = 隨機整數
- fix:
measure()
此函式負責測量 CPU 執行時間，具體步驟如下：
- 根據
input_data內容，在佇列中插入一定數量的隨機字串（類別 0 不會插入字串）。 - 執行目標測試函式，並在執行前後記錄 CPU 時間。
differentiate()
該函式計算函式實際消耗的時間，並將結果記錄到 exec_times 中。
update_statistics()
利用 t_push() 蒐集測試數據，並記錄各類別的數量、平均值及偏差平方和 (
report()
在 t_compute() 中，根據 Welch’s t-test 公式：
計算 t 值，並與 t_threshold_bananas 及 t_threshold_moderate 進行比較。
若結果顯示
q_insert_head/q_insert_tail 非常數時間問題
在 make test 中，插入節點的功能總是被認為不是常數時間完成
在實際追蹤測試程式之前，我原本以為可能跟 strncpy 有關
然而不管在 fix 還是 random 類別，字串的長度都是隨機的
後來我受到 rota1001 開發紀錄的提示，得知了問題出在 malloc
實驗
我在能穩定通過測試的 q_remove_head 中加入原先不存在的記憶體分配
char *trash = malloc(sizeof(char) * 10);
if (trash) {
free(trash);
}
再執行 qtest 並輸入以下命令
cmd> new
cmd> option simulation 1
cmd> rh
最後得到
ERROR: Probably not constant time or wrong implementation
紀錄測試的類別與時間，利用 python 畫出的累積百分比圖如下
- 加入記憶體分配之前
- 加入記憶體分配之後
malloc重用釋放記憶體的特性
參考你所不知道的 C 語言：記憶體管理、對齊及硬體特性
malloc 在分配記憶體時，會先嘗試從 bin 尋找是否有合適的區塊可直接使用
來加速記憶體分配
我就猜測，現在遇到的 malloc 問題是否與此有關連
可能 input_data 較小時能直接從 bin 取得合適的區快來加速分配
input_data 較大時，開始進行測量的時候 bin 裡面已經沒有任何可用區塊
於是我在 constant.c 的 measure 函式中，在開始測量時間之前
先在佇列的頭插入一個節點再釋放
dut_insert_head(get_random_string(), 1);
element_t *e = q_remove_head(l, NULL, 0);
q_release_element(e);
觀察這是否能解決 malloc 的問題
然而
cmd> new
l = []
cmd> option simulation 1
cmd> it
Probably constant time
cmd> it
Probably constant time
cmd> it
Probably constant time
cmd> it
ERROR: Probably not constant time or wrong implementation
這個方法雖然增加了通過機率，但沒能完全解決 malloc 的問題
下方累積百分比圖也顯示了，此操作並非完全有效(讓兩個類別的曲線在低於 60% 前重合)
-
加上操作之前
-
加上操作之後
malloc 時間與 input_data 的關聯
參考 rota1001 開發紀錄
提到 input_data 與 malloc 時間呈現正相關
於是我在 dudect/constant.c 做以下更改並實驗，紀錄 input_data 與 exec_times
- dut_insert_head(
- get_random_string(),
- *(uint16_t *) (input_data + i * CHUNK_SIZE) % 10000);
+ element_t *big_trash = malloc(sizeof(element_t) * (*(uint16_t *) (input_data + i * CHUNK_SIZE) % 10000));
int before_size = q_size(l);
before_ticks[i] = cpucycles();
- dut_insert_tail(s, 1);
+ char *trash = strdup(s);
after_ticks[i] = cpucycles();
int after_size = q_size(l);
+ free(trash);
+ free(big_trash);
dut_free();
- if (before_size != after_size - 1)
+ if (before_size != after_size)
可發現 malloc 時間確實與 input_data 呈現正相關
於是將 input_data 的上限調成 1000
- *(uint16_t *) (input_data + i * CHUNK_SIZE) % 10000);
+ *(uint16_t *) (input_data + i * CHUNK_SIZE) % 1000);
它能夠通過了測試
而對於非常數時間的實作也能確實的辨認出來
- 常數時間實作
- 非常數時間實作(從第一項走訪直到找到最後一項再進行操作)
至於這是否真的代表能防範 side-channel attack
我原本對此有些質疑
然而，在跟 rota1001 討論之後，他提出以下論點
在實驗中可得知只要記憶體的佔用量增加， malloc 的速度就會慢慢下降
這跟佇列內實際存在多少元素不完全有關係
因此，攻擊者無法藉由 side-channel attack 確切得知佇列內的元素數量
移除DROP_SIZE
DROP_SIZE
在追蹤這段程式碼的時候，我發現了一個奇怪的問題
在 fixture.c 進行統計量計算與更新 (differentiate 與 update_statistics)時，其範圍是從 0 到 N_MEASURES
然而在 constant.c 測量數據的時候，其範圍是從 DROP_SIZE 到 N_MEASURES - DROP_SIZE
這可能會導致會在計算 t 值的時候，會計算到根本不是測量數據的數值
然而當初發現時嘗試藉由修改來解決 q_insert 問題不成
就認為它可能沒有實際影響，因此沒將這次修改提交
q_remove_head 問題
當我將 Input_data 的上限調整為 1000 (參考:malloc 時間與 input_data 的關聯) ，在本地端拿到測試程式的滿分並推送至 github 上之後，發現 github 上的測試只拿到 95 分，看詳細紀錄才發現，我的 q_remove_head 功能每次都不能通過測試，這在本地端的測試中從未發生過。
提交修改
在3月4號上課前，我跟 Ian-Yen 與 rota1001 討論 q_remove_head 的問題，在過程中 Ian-Yen 提起了 DROP_SIZE 的問題，這才知道認為那個 DROP_SIZE 的功能很奇怪的不只我，現在的就該思考，應該要統一使用 DROP_SIZE ， 還是統一移除。
在經過一番討論之後，認為如果要將數據移除，應該要先根據 exec_time 做排序再去除極端值，因此最後選擇了將 DROP_SIZE 全數移除。
而在提交此次修改後，我成功的在 github 上的測試程式拿到 100 ，獲得卡比一隻。
然而，在之後的 github action ，仍然可見到同樣的問題再次發生
其結果仍存在不確定因素
Linux 核心的鏈結串列排序
程式碼閱讀
第一階段合併
尋找 count 二進位表示式 第一個0
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
這段程式會反覆執行直到 bits 的最低位變成0
- bits 作為下方判斷式的條件
- tail 作為下方合併的位置依據
若 bits 到最高位都是 1 (像是: 1, 3, 7)，在迴圈執行完畢後會變成0， 此時就不會滿足下方的判斷條件
相反情況的話， bits 在迴圈執行完畢後不為 0，滿足下方的判斷條件，此時 tail 會指向需要進行合併的第一項
以 8 個元素為例子:
| count | count 二進位 | bits 二進位表達式 | 是否合併 | 合併後狀態 |
|---|---|---|---|---|
| 0 | 0 | 0 | 否 | |
| 1 | 1 | 0 | 否 | 1 |
| 2 | 10 | 10 | 是 | 2 |
| 3 | 11 | 0 | 否 | 2 -> 1 |
| 4 | 100 | 100 | 是 | 2 -> 2 |
| 5 | 101 | 10 | 是 | 4 -> 1 |
| 6 | 110 | 110 | 是 | 4 -> 2 |
| 7 | 111 | 0 | 否 | 4 -> 2 -> 1 |
| 8 | 1000 | 1000 | 是 | 4 -> 2 -> 2 |
likely 巨集
這個巨集定義在 linux/include/linux/compiler.h 裡面
相關程式如下
void ftrace_likely_update(struct ftrace_likely_data *f, int val,
int expect, int is_constant);
#if defined(CONFIG_TRACE_BRANCH_PROFILING) \
&& !defined(DISABLE_BRANCH_PROFILING) && !defined(__CHECKER__)
#define likely_notrace(x) __builtin_expect(!!(x), 1)
#define unlikely_notrace(x) __builtin_expect(!!(x), 0)
#define __branch_check__(x, expect, is_constant) ({ \
long ______r; \
static struct ftrace_likely_data \
__aligned(4) \
__section("_ftrace_annotated_branch") \
______f = { \
.data.func = __func__, \
.data.file = __FILE__, \
.data.line = __LINE__, \
}; \
______r = __builtin_expect(!!(x), expect); \
ftrace_likely_update(&______f, ______r, \
expect, is_constant); \
______r; \
})
/*
* Using __builtin_constant_p(x) to ignore cases where the return
* value is always the same. This idea is taken from a similar patch
* written by Daniel Walker.
*/
# ifndef likely
# define likely(x) (__branch_check__(x, 1, __builtin_constant_p(x)))
# endif
# ifndef unlikely
# define unlikely(x) (__branch_check__(x, 0, __builtin_constant_p(x)))
# endif
可得知 likely 背後有個 __branch_check__ 巨集
由於我真的看不懂這段程式碼，我選擇將其複製，要 chatGPT 解釋並附上規格書資料
這才知道這是 GCC 提供的擴充功能
You may use __builtin_expect to provide the compiler with branch prediction information.
The return value is the value of exp, which should be an integral expression. The semantics of the built-in are that it is expected that exp == c. For example:
if (__builtin_expect (x, 0))
foo ();
這說明了這個函式用來提供編譯器 exp 出現機率較高的值，來幫助做編譯優化。最後仍會回傳 exp ，對應到原始碼， ___r 就是 x 。
A compound statement enclosed in parentheses may appear as an expression in GNU C. This allows you to use loops, switches, and local variables within an expression.
The last thing in the compound statement should be an expression followed by a semicolon; the value of this subexpression serves as the value of the entire construct.
這說明了這個語法可以定義一個表達式包含任何需要的東西，而這個表達是的最後一條語句則代表整個表達式的值。
對應到原始碼， ___r 即是最後的值。
結論就是，這個巨集主要是幫助編譯器優化，不影響遠本的值。
merge 函式
這邊其實我不太理解為什麼不用一個間接指標儲存比較結果來將程式碼簡潔化
此外，最後將尾巴接上的方法，可以藉由轉型與位元運算來節省分支
我的想法實作出來如下
struct list_head *one_way_merge(struct list_head *l,
struct list_head *r,
bool descend)
{
struct list_head *new_head = NULL, **tmp = &new_head, **indir = NULL;
while (l != NULL && r != NULL) {
char *l_value = list_entry(l, element_t, list)->value,
*r_value = list_entry(r, element_t, list)->value;
indir = ((strcmp(l_value, r_value) > 0) == descend) ? &l : &r;
*tmp = *indir;
tmp = &(*tmp)->next;
*indir = (*indir)->next;
}
*tmp = (struct list_head *) ((uintptr_t) l | (uintptr_t) r);
return new_head;
}
第二階段合併
將多個佇列合併到 list ， 最後會剩下兩個佇列: list 和 pending ， 交由 merge_final 做最後的合併
將佇列恢復成雙向環狀鍊結串列
原始碼的作法是 final_merge 合併最後兩個佇列，同時維護雙向的特性，後面再用迴圈尋找尾巴的位置，維護環狀特性
我自己的作法是在第二階段合併時就把佇列合併完成，最後再跑迴圈維護雙向特性並找到尾巴，最後再接上 head 維護環狀特性。我認為這個作法少了一個迴圈另外尋找尾巴，應該要更快，之後會做實驗比較。
實驗
數據蒐集方法
計錄排序的 cpu 時間
在 q_test.c 做以下更改，儲存使用的 cpu 時間到 output.csv
if (current && exception_setup(true)) {
+ int64_t _start = cpucycles();
q_sort(current->q, descend);
+ int64_t _end = cpucycles();
+ FILE *file = fopen("output.csv", "a"); // 以附加模式 (append) 開啟檔案
+ if (file == NULL) {
+ perror("無法開啟檔案");
+ exit(EXIT_FAILURE);
+ }
+ fprintf(file, "%ld\n", _end - _start); // 將文字寫入檔案
+ fclose(file); // 關閉檔案
}
數據蒐集腳本
import subprocess
# shuffle 的所有結果
nums = []
t_count = 1000
_input = f"new\nih RAND {100000}\nsort\nfree\n"
# 取得 stdout 的 shuffle 結果
for i in range(t_count):
if (i % 100 == 0):
print(i + 1)
command='./qtest -v 3'
clist = command.split()
completedProcess = subprocess.run(clist, capture_output=True, text=True, input=_input)
completedProcess = subprocess.run(clist, capture_output=True, text=True, input="quit\n")
比較原本的 top-down 實作與模仿 list_sort 的實作
由於差距明顯，不使用 t-test 去檢定平均是否不同
在作業說明中有提到， top-down mergesort 雖然會需要遞迴或額外的記憶體做 user stack，但它有最少的 average case、worst case 的 comparison 次數
而 list_sort 的實作屬於 Bottom-up mergesort，有著各種變形中最多的比較次數
merge 使用 linux 核心的實作
參考 rota1001 的開發紀錄，有提到利用間接指標儲存比較結果的方法，相較 linux 核心的方法耗費時間
將 linux 核心的 merge 做點修改
- static struct list_head *merge(void *priv, list_cmp_func_t cmp,
- struct list_head *a, struct list_head *b)
+ struct list_head *linux_merge(struct list_head *a,
+ struct list_head *b,
+ bool descend)
...
+ char *l_value = list_entry(a, element_t, list)->value,
+ *r_value = list_entry(b, element_t, list)->value;
- if (cmp(priv, a, b) <= 0) {
+ if ((strcmp(l_value, r_value) > 0) == descend) {
...
接著進行實驗
由於差距明顯，不使用 t-test 去檢定平均是否不同
沒想到 merge 方法的差距能造成如此明顯的差距
使用 perf 執行數據蒐集腳本 (只蒐集 100 個)，觀察不同合併方法對效能的影響
-
linux 原本的 merge
- 組合語言
- 組合語言
-
使用間接指標儲存比較結果
- clock cycle
- cache miss
- clock cycle
上方結果能明顯看出， q_sort 函式的佔用量都是 1.4% 左右，然而，兩種合併方法的佔用時間相差了一倍，與上方累積百分比圖的結果吻合
觀察組合語言指令的佔用時間，間接指標儲存比較值的方法
mov -0x8(%rbp),%rsi
mov -0x8(%rbx),%rdi
也就是將 l_value 與 r_value 作為參數傳遞時
花了更多的時間
使用 linux 的 final_merge 與否
使用作業二自訂記憶體配置器 的 t test 程式
輸出
✅ Welch's t-test 結果：
t 值：73.2370
p 值：0.0000 （顯著）
Cohen's d 效果量：3.2759
效能提升倍率：1.3971
如 lib/list_sort.c 的註解
Combine final list merge with restoration of standard doubly-linkedlist structure. This approach duplicates code from merge(), but
runs faster than the tidier alternatives of either a separate final
prev-link restoration pass, or maintaining the prev links
throughout.
使用 final_merge 比起額外執行一次還原 prev 鍊結串列的方法快
重新觀察程式碼，發現 merge_final 的作法是一邊進行 merge 一邊維護 prev ， 並且用 tail 儲存最後一個被維護到的節點 ， 最後在從 tail 往後維護。
這樣的作法比起額外執行一次還原 prev 鍊結串列的方法，可減少重新存取節點的次數。在鍊結串列很長的時候，如果在合併完成後再重新存取節點維護 prev ，有可能因為節點的資料已經不在 cache 裡面，造成 cache-miss 導致速度下降，可以藉由 perf 工具觀察相關函式的 cache-miss 次數。
- 有 final merge
- 沒有 final merge
- 查看 cache miss 最多的位置，正是在重新維護 prev 的程式
- 查看 cache miss 最多的位置，正是在重新維護 prev 的程式
提交修改
在我嘗試推測這個實驗結果的解釋原因之後，想到昨天有跟 JeffBla 討論這件事情，打開 discord 想告訴他我的想法，結果發現他稍早已經傳訊息給我，說的就是這件事情，這讓我更確信這個想法是對的，之後也在 perf 的結果得到驗證。
此外，他也發現我的 q_merge 其實可以利用 merge_final 提高效率，對此我進行了實驗。
