2024q1 Homework1 (lab0)

contributed by < devarajabc >

開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.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-8265U CPU @ 1.60GHz
    CPU family:          6
    Model:               142
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            11
    CPU max MHz:         3900.0000
    CPU min MHz:         400.0000
    BogoMIPS:            3600.00

開發過程

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)

了解

q_new

不懂就說不懂，不要不懂裝懂說「不太懂」。
改進你的漢語表達。

1.了解

原本不懂要 new 的是哪個東西？是 queue_contex_t 還是element_t 或是單純的 list_head，直到翻閱 qtest.c 才知道 q_new 要新增的是佇列的 head (下圖藍色處)

queue_contex_t *qctx = malloc(sizeof(queue_contex_t));
list_add_tail(&qctx->chain, &chain.head);
qctx->size = 0;
qctx->q = q_new();
qctx->id = chain.size++;

同時程式也說明了如何建立 qctx ，這對於思考如何進行 q_merge 很有幫助

詳閱作業要求！

q_free

利用 list_for_each_entry_safe來走訪每一個節點，再利用 q_release_element 來釋放該節點( element_t )與節點內指向的字串（綠色部分），最後再釋放 head node (藍色部分)

q_insert_head, q_insert_tail

原本是使用 strncpy 以及用 strlen 來判斷長度避免造成記憶體區段錯誤，後來發現函式 strdup 就可以達到所需的功能，而且記憶體配置失敗時會回傳 NULL ，非常方便
不過在 stackoverflow 發現以下敘述

Keeping in mind it's actually not part of the current (C17) ISO C standard itself(a) (it's a POSIX thing), it's effectively doing the same as the following code:

此外在 git commit 的時候一直收到

queue.c:64:5: error: Memory leak: temp [memleak]
	return true;
	^
queue.c:88:5: error: Memory leak: temp [memleak]
	return true;
	^

Fail to pass static analysis.

後來將

 INIT_LIST_HEAD(&(temp->list));
 list_add_tail(&(temp->list), head));

改成

 INIT_LIST_HEAD(&temp->list);
 list_add_tail(&temp->list, head);

就通過 static analysis 了，目前還不知道為什麼

注意看 C 語言運算子的優先順序。

q_remove_head / q_remove_tail

先利用 list_first_entry / list_last_entry 來取出欲移除的節點 removed
接著使用 list_del_init 來將該節點移出佇列
並利用 strncpy 將 removed->value 拷貝到字串 sp 之中
最後要將字串 sp 的最後一元素 sp[bufsize - 1] 指派為 '\0' 。

你該用 ChatGPT 改進你的漢語表達，並避免將自己的專業成長訴諸大語言模型。

我知道錯了

q_size

避免贅字

已刪除

參考作業說明

在範例的基礎上加入 list_empty(head) 來處理佇列為空的情況。

q_delete_mid

利用 list_for_each_entry 與一相反方向走訪的指標 rev_node 來尋找中間點，再利用list_del_init和 q_release_element來刪除節點，以下為部分程式碼：

if(node==rev_node||node->next==rev_node){
    list_del_init(rev_node);
    q_release_element(list_entry(rev_node,element_t,list));
    return true;
}
    rev_node=rev_node->prev;

選擇 rev_node 為要刪除的中間節點而非使用 node 是為了處理 node 數量為偶數的情況

q_delete_dup

程式的執行主要分成兩種情況：

• 目前節點與下一個節點相同：利用 while loop 刪除相同的節點
• 目前節點與下一個節點相異：又可分成兩種可能:
  1. 剛離開 while loop：刪除目前節點
  2. 未曾進入 while loop：什麼都不必做

以下是細節說明：
利用 list_for_each_entry_safe 來走訪每節點，當發現下一個節點與目前節點相等時，就會利用 while loop 不斷走訪並刪除 「目前節點的下一個節點」直到出現相異的節點或是走訪到 head ，因此原先指向「目前節點的下一個節點」的指標 safe 會被改變。

此外在進入 while loop 之前會進行判斷，避免在 entry->list.next 為 head 的情況下使用 list_entry 而造成記憶體區段錯誤。

在第四行將指向「目前節點的下一個節點」的指標儲存在 Next 而非直接用 list_entry 的輸出節果來作為函式 list_del 與函式 q_release_elemen 的輸入，因為執行 list_del 之後的佇列會被改變，直接將 list_entry 的輸出作為 q_release_element 的輸入會破壞佇列的結構。

while (entry->list.next != head &&
    !strcmp(entry->value,
            list_entry(entry->list.next, element_t, list)->value)) {
+    element_t *Next = list_entry(entry->list.next, element_t, list);
-    list_del(entry->list.next)
+    list_del(&Next->list);
-    q_release_element(list_entry(entry->list.next, element_t, list));
+    q_release_element(Next);
}

接著要判斷 safe 是否被改變過，如果是 safe 依然是「目前節點的下一個節點」，代表該節點沒有進去過 while loop ，因此不需要刪除目前節點。

改進你的漢語表達。

已對內容進行更改
還差得遠，要用清晰明確且流暢的漢語書寫，你該展現自己學了二十餘年漢語的能耐。

反之則要刪除該節點，並指派 safe 正確的值，以便 list_for_each_entry_safe 可以繼續運作。

+if (list_entry(entry->list.next, element_t, list) != safe) {
-if (!safe){
    safe = list_entry(entry->list.next, element_t, list);
    list_del_init(&entry->list);
    q_release_element(entry);
}

safe 再其所指向的節點被刪除後，會指向一位置不明、不固定且無法 dereference 的地址而非 NULL，原因不明，甚妙。
所以若使用 safe 是否為 NULL 來判斷是否要刪除該節點，則會在後續的步驟造成記憶體區段錯誤，以下是 valgrind 的輸出結果：

==267663== Invalid read of size 8
==267663==    at 0x10FCB1: q_delete_dup (queue.c:168)
==267663==    by 0x10C093: do_dedup (qtest.c:467)
==267663==    by 0x10E0ED: interpret_cmda (console.c:181)
==267663==    by 0x10E6A2: interpret_cmd (console.c:201)
==267663==    by 0x10F30C: run_console (console.c:691)
==267663==    by 0x10D4DF: main (qtest.c:1288)

q_reverse/q_reverseK/q_swap

參考 yanjiew

1. 利用 list_for_each_safe 走訪每一個節點並用 list_move 把目前節點移到 head，以達到翻轉順序的目的。

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

2. 在撰寫 q_reverseK 的時候一開始誤會題意，以為只要處理前 k 個，還好在 HotMercury 的提醒下才改正，實作如下:
   利用 list_for_each_safe 走訪每個節點並利用 list_move 將其移至 new_head 。
   每經歷 k 個 node 就會更新 new_head 的值，以達到題目的要求，當走訪的節點數量不足 k 時則不會改變 new_head 的值。

list_for_each_safe (node, safe, head) {
        if (!i--) {
            new_head = node->prev;
            i = k - 1;
        }
        list_move(node, new_head);
    }

3. q_swap 是 q_reverseK 的一個特例，用 K = 2 來實踐。

1. 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
2. 改進漢語表達

1.已改正
2.

沒做到的事，不要急著回應。斟酌字句值得佔用你的青春去淬鍊。

q_ascend/q_descend

留意資訊科技詞彙翻譯

將「遍歷」全數更正為「走訪」、「當前」皆更新為「目前」
"queue" 更正為「佇列」、 "linked list" 更正為「鏈接串列」

漢語詞彙不該直接對應到英語，仍該針對情境去調整。

jserv

在走訪的過程中若目前節點大於 min 則會更新 min ，並將用於記錄 node 數量的變數 i 加一 ，反之則將其刪除，細節如下：

if (strcmp(entry->value, min->value) < 0) {
    list_del(&entry->list);
    q_release_element(entry);
} else {
    min = entry;
    i++;
}

而 q_descend 則是把 lish_for_each_safe 改成往 prev 的方向走訪，其他部分則跟 q_ascend 一樣。

這是環狀雙向鏈結串列，何來「右邊」？工程人員說話要精準。

已更正

q_sort, merge_two

參考 yanjiew 和alanjian85 的作法

merge_two 是額外寫的函式，是為了方便 q_sort 和 q_merge 使用而特別獨立出來。
參考 (2023): 第 1 週作業檢討 後決定在 void 前面標註 static .
使用 list_first_entry 來取出兩個佇列的第一個節點來進行比較，之後再依據 descend 的值來決定要插入較大或是較小的節點 。

 if ((descend && strcmp(l->value, r->value) > 0) ||
            (!descend && strcmp(l->value, r->value) <= 0))
            list_move_tail(&l->list, &temp);
        else
            list_move_tail(&r->list, &temp);

在老師的提點之下才發現自己其實根本分不清出 Top-down 和 Bottom-Up 於是便去閱讀 Linux 核心排序實作的演進

使用 Top-down (recursive) merge sort 來實作 q_sort
實作內容如下：

利用 list_for_each_safe 走訪每一個節點

• 若目前節點為佇列的中間節點：
  1. 利用 list_cut_position 將佇列分成兩段並分別放入 q_sort 進行排序
  2. 利用 merge_two 合併已排序好的佇列
  3. 離開迴圈
• 反之則更新反向走訪的指標 rev_node 以利後續判斷是否走訪到中間節點

LIST_HEAD(R);
list_for_each_safe (node, safe, head) {
    if ((node == rev_node || node->next == rev_node) && rev_node != head) {
        list_cut_position(&R, node, head->prev);
        q_sort(&R, descend);
        q_sort(head, descend);
        merge_two(head, &R, descend);
        break;
    }
    rev_node = rev_node->prev;
}

你如何確認目前的測試已涵蓋排序演算法的最差狀況？

確認目前的測試已涵蓋排序演算法的最差狀況

參考 排序測試和效能評估機制

對於 Top-down (recursive) merge sort 而言，不管在最佳、平均、最差的情況下，時間複雜度皆為

$O(n\log n)$ ，差別在於節點間比較的次數，假設有兩個子佇列

$Q_1,Q_2$ ，長度分別為

$n_1,n_2$ ，最差情況下的比較次數

$C_{n1,n2}$ 為

$n_1+n_2-1$ 次，即每一個節點皆被比較過。

$min(n_1,n_2)\le C_{n1,n2}\le n_1+n_2-1$

1. 怎樣的測試資料是最差情況呢？

參考 When Will the Worst Case of Merge Sort Occur? 、2024-03-{19,21} 討論簡記

只要比較次數少於

$n_1+n_2-1$ 次，就不是最差的情況，例如在合併

$Q_1,Q_2$ 的過程中，其中一個子佇列提早被比較完，這樣比較次數就會少於

$n_1+n_2-1$ 次。
因此最差情況的測試資料要確保在每次合併的過程中都會比較到每一個節點。

2. 新增 q_worst_case

commit 16f69b2

先準備一個嚴格遞增的佇列，再使用遞迴的方式將佇列拆成奇數項、偶數項兩個子佇列，直至子佇列只剩一個節點，最後再將所有節點串連起來。

因為在合併兩個交錯排例的子佇列如

$[1,3,5,7],[2,4,6,8]$ 時就能避免其中一個子佇列提早被比較完的情況，然而為了確保每一次的合併都能達到最差的情況，所以要再將

$[1,3,5,7]$ 拆成

$[1,5],[3,7]$ 而

$[1,5]$ 又要再拆成

$[5],[1]$

$...........$
流程如下：

我很好奇

$[5,1,7,3,6,2,8,4]$ 和

$[1,5,3,7,2,6,4,8]$ 會不會造成比較次數的不同

（在最差環境下的表現數據：比較次數、時間、cache miss ratio）
（要確認是否符為合穩定排序，要有數學證明）
（穩定排序的檢測？）

Queue size = 8
l = [a b c d e f g i]
cmd> worst_case
l = [a e c g b f d i]
cmd> list_sort
Comparisons:    17
l = [a b c d e f g i]
Freeing queue

確認目前的排序是否為穩定排序

參考 yenslife 、wiki

穩定排序的定義是：如果一個排序演算法是穩定的，當有兩個相等鍵值的紀錄

$R$ 和

$S$，且在原本的串列中

$R$ 出現在

$S$ 之前，在排序過的串列中

$R$ 也將會是在

$S$ 之前。

所以我使用常數列來判斷 q_sort 是否為穩定排序，若出現任何排列的動作則 q_sort 為不穩頂排序。

仔細檢查之後才發現原本的程式碼錯誤百出，至於為什麼能通過測資還待分析，以下是對程式碼做出的修改

q_merge

失敗的過程可能也值得反覆推敲。

參考你所不知道的 C 語言: linked list 和非連續記憶體 :
naive
直觀地用第一條串列接上剩下的串列，這樣會導致 lists[0] 愈來愈長，立即會遇到的問題是：多數的情況下合併速度會愈來愈慢。

利用 list_first_entry 來找到第一個節點 (queue_context_t) 並用變數 l 來記錄其指標，而 r 則用來記錄「下一個」節點的指標。

在 while loop 中，利用 merge_two 將剩餘的節點都合併到 l 上，合併過後的節點會被移到尾端，若再次造訪則會跳出迴圈 ，這部分是參考自 alanjian85 的作法，但與 alanjian85 的做法不同之處在於是我利用 list_empty(r->q) 來判斷是否造訪過該節點。

改進你的漢語表達。

while (!list_empty(r->q)) {
        merge_two(l->q, r->q, descend);
        list_move_tail(&r->chain, head);
        r = list_entry(l->chain.next, queue_contex_t, chain);
    }

參考 Queue-Mergesort
Queue-Mergesort

---

研讀論文 〈Dude, is my code constant time?〉

參考 jimmylu0303

作者在 Introduction 中介紹了時間攻擊（Timing attack）與其危害，在時間攻擊中，攻擊者會通過分析程式的執行時間差異來推斷出加密過程中使用的密鑰或者其他敏感資訊。

為了防範時間攻擊，工程師會設法讓特定程式的執行時間始終保持恆定 （Constant time），避免因輸入不同而造成執行時間差異，使攻擊者法從該程式的執行時間中獲得有用的資訊。

指出之前手法的缺陷。

然而檢測特定程式是否能維持固定的執行時間絕非易事，作者指出了現行檢測方法的缺點並提出了一套新的測量工具 :

This manual approach can be very time consuming already for moderately sized code bases, and should be repeated for every exact combination of compiler flags being used.

有別於以往的測量方式，作者借用旁路攻擊（Side-channel attack）的概念來測量程式的執行時間，並利用統計學方法對其進行分析，以便判斷該程式是否能在不同的輸入下依然保持恆定的執行時間。

接著作者在 OUR APPROACH: TIMING LEAKAGE DETECTION 中說明了dudect 運作的流程：

1. 測量程式在兩筆不同測試項目下的執行時間
2. 利用統計方法分析該程式是否有維持恆定的執行時間

討論「恆定的執行時間」一詞是否精準。

以下是對流程的細節說明：

1.測量執行時間（Repeatedly measure exeution time）

• 使用兩筆不同類型（class）的測試資料，分別是固定值（fix）和隨機值（random），固定值為一常數，可以用來測試某些特殊臨界情況。
• 利用現代 CPU 提供的 cycle counters 來作為測量依據

不懂就說不懂，沒有「不太懂」這回事。

第三點看不懂 為何可以如此操作

To minimize the effect
of environmental changes in the results, each measurement
corresponds to a randomly chosen class.1 The class assignment
and input preparation tasks are performed prior to the
measurement phase.

2.資料預處理（Apply post-processing）

• 為了避免程式執行的時候受到作業系統本身或其他外在因素干擾而造成測量錯誤，因此在開始統計前會去掉一些極端值
• High-order preprocessing （我不知道這是幹嘛的）

3.進行統計分析（Apply statistical test）

參考 2024-03-{19,21} 討論簡記

改進 dudect 實作

參考 dudect.h, marvin0102, cheezad, HotMercury

發現 lab0-c 中沒有做到 Apply post-processing ，因此在從 dudect.h 中複製了三個函式到 fixture.c 裡面，分別是：

• compare_int64: 比較兩個 64 位元整數的大小。它是給快速排序函式 (qsort) 使用的，以決定排序順序。
• percentile: 計算並返回一個已排序陣列中指定百分位數的值。例如，如果你想找到中位數（即 50% 百分位數），該函式可找到陣列中恰好位於中間位置的值。它首先計算出陣列中對應於所需百分位數的索引位置，然後返回該位置的值。
• prepare_percentiles: 對執行時間進行排序，然後計算一系列特定的百分位數。

使用 qsort 進行排序。

利用特殊的公式計算計算每一個元素的百分位數值

​​​​  1 - (pow(0.5, 10 * (double) (i + 1) / (double) N_MEASURES)), N_MEASURES);

為何如此？

（我不知道）

接著將每個元素替換成對應的百分位數值。

最後記得要在 fixture.c 裡面的 doit 中加入 prepare_percentiles(exec_times)
（為什麼？不知道）

---

亂數研究及 shuffle 實作

亂數研究

參考 亂數

如何確認亂數夠亂？

q_shuffle

參考 alanjian85 如何在 qtest 中新增 shuffle 實作、 參考 HotMercury 如何使用 extern 、2024-03-19 討論簡記、Pearson's chi-squared test

在 queue.c 中新增 q_shuffle：

commit1030b5

利用 Fisher–Yates shuffle演算法來實作洗牌（shuffle）

為什麼要用 Fisher–Yates shuffle ？

注意空白字元。

實測與成果

使用 Pearson's chi-squared test 來驗證 q_shuffle
(為何不使用 t-test )?

• $H_0$（虛無假說）: shuffle 的結果發生的機率相同，遵守 Uniform distribution
• $H_1$（對立假說）: shuffle 的結果發生的機率至少有一個不同

列出 diff -u 的結果，不用張貼完整程式碼。

比較亂數產生器

觀察亂數字串的分布，並運用「資訊與熵互補，資訊就是負熵」的觀念，設計一組新的命令或選項，得以在 qtest 切換不同的 PRNG 的實作
參考 由大數法則理解訊息熵的數學意義 、yanjiew1

解釋 select 系統呼叫在本程式的使用方式

---

針對 Linux 核心風格的鏈結串列開發 Timsort 排序程式

參考 Timsort 研究與對 Linux 核心貢獻嘗試、Wikipedia: Timsort

使用明確清晰且流暢的漢語表達。

以下是我實作的幾個版本：

1. Timsort_naive commit 103640d

參考 第一週測驗 中使用的版本 、 yanjiew1 、HotMercury、jimmylu890303

此版本使用逐對合併(one-pair-at-a-time) 而非 Galloping mode 且缺乏計算 minrun (最小運行長度)的機制。
此外我看不懂函式指標 list_cmp_func_t cmp 的用法，在
閱讀 Function pointer 後才知道其正確的用法。

參照 C 語言規格書。

參考 jimmylu890303 將 q_tim_sort 加入 qtest ，並使用 jimmylu890303 的測資來測試 q_tim_sort

$ ./qtest < traces/trace-test_tim_sort.cmd 
l = []
l = [jlojw ibobf wojsmiifc bqxdfxw tcqgbze ncfuuzqy ijvzbmtpk ddmwn ggkhinkmv lvvakzhbm zazpevqtq jnxhg vxclmor oaetwm jhrglvn qessrobxy ffdletlf oxzmevgpx yrlejf mxxuxk ftqpbyyxo lsstizr btxxe yfvjr nljrxoag aupsot rmgvx jxrwpyg mzubdze hoypriitx ... ]
l = [aaaatuqw aaabcbj aaabxaxkk aaabzdv aaadre aaadt aaadxb aaaed aaafbdz aaafen aaafofg aaafxxnff aaagdmf aaagfy aaagtibpi aaaguse aaahqwm aaahxzvmi aaaioytq aaaiuyo aaaiw aaaiwpc aaajpqey aaajscy aaakjhvx aaakuqts aaamjce aaanasm aaantzl aaanx ... ]
Delta time = 1.315
Freeing queue

不過在使用 valgrind cachegrind 分析 cache miss ratio 的時候會遇到錯誤，原因未知

valgrind --tool=cachegrind ./qtest -f traces/trace-test_tim_sort.cmd
--293068-- warning: L3 cache found, using its data for the LL simulation.
l = []
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of uzwwcvas failed (1 failures total)
l = [rdsrgsl ... ]
l = [aaaaob aaacxjy aaafv aaaigh aaammvz aaamwqgk aaaxieid aabbitjf aabbzzkd aabie aabjj aaboposi aabtcqhd aabxf aabxw aacajv aaccaz aacpcfed aacpgxxo aacpwe aacqnk aacqt aacvstpm aaczayj aaddhmo aadji aadqu aadshzupc aaduij aaduzhn ... ]
Freeing queue
ERROR: Freed queue, but 1 blocks are still allocated

幻滅是成長的開始

使用明確清晰且流暢的漢語表達。

分析 lib/list_sort.c

參考 Linux 核心專題: 改進 lib/list_sort.c 、 csotaku0926 、kdnvt 、 blueskyson 、 yanjiew1 、bakudr18

（原本的版本有什麼問題？為何需要修改？怎麼修改？）
（merge sort vs. quicksort locality）
原先的版本已經用 DFS 來讓比較次數

$n\ast lo{g}_2(n)-K\ast n+O(1)$ 的領導係數降到理論的極限值（理由做法待補），因此作者著重在一次項的改進。

作者確保兩個子佇列在最糟情況下合併時的長度比為

$2:1$ ，因為當合併兩個大小差異非常大的子佇列的時候比較次數會大大上升（理由、數據待補充）

改進後的效果相當顯著：

This achieves the same average K=1.207 as queue-mergesort, which is 0.2n better then bottom-up, and only 0.04n behind top-down mergesort.

引入至 lab0-c

commit 83a8434

u8 是啥？
unlikely 是啥 ？

    struct list_head *head, **tail = &head;
                      ^

Fail to pass static analysis.

該設計對應的排序測試實驗方案

參考 用效能分析工具比較 list_sort.c 及自己實作的排序、排序測試和效能評估機制、listsort 的說明文件

參考 fennecJ 所使用的方法：

在 q_test 中新增 test_config 來將創造測資
將測試以下幾種情況：

1. random data
2. descending data
3. ascending data
4. ascending, then 3 random exchanges
5. ascending, then 10 random at the end
6. ascending, then randomly replace 1% of elements with random values
7. many duplicates
8. all equal
9. worst case scenario

---

整合 ttt

研讀Linux 核心的浮點數運算

研讀(MCTS) 演算法

針對 ttt 命令的「電腦 vs. 電腦」的對弈模式，引入若干 coroutine

嘗試引入其他快速的 PRNG 實作並比較 MCTS 實作獲得的效益

運用定點數來統計不同 AI 實作機制對系統負載的使用率

改寫既有的 shannon_entropy.c 和 log2_lshift16.h