## Linux 核心專題: 改進 ksort
> 執行人: yu-hsiennn
> [專題解說錄影](https://youtu.be/t_CDw4y1h14)
### Reviewed by `Lccgth`
>kernel threads 在小到中等規模的資料集上表現良好，提供了最快的處理時間。然而，在更大的資料集上，不帶 flag 的 CMWQ 表現出更佳的效率
為什麼 kernel threads 在更大的資料集上，不帶 flag 的 CMWQ 表現出更佳的效率?
:::danger
注意用語：
數據集 -> 資料集
:::
### Reviewd by `mesohandsome`
Lomuto's quicksort 程式碼有錯誤，for 迴圈少了 `}`。
## 任務簡介
重作第六次作業的 ksort，強調 workqueue / CMWQ / kernel thread 對於任務分配的效率 (CPU utilization)。
## TODO: 回覆自我檢查清單
> 依據第六次作業規範
- [x] 研讀前述 ==Linux 效能分析== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 → 從中也該理解為何不希望在虛擬機器中進行實驗;
- [ ] 閱讀〈[Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module)〉並對照 Linux 核心原始程式碼 (v6.1+)，解釋 `insmod` 後，Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)、`MODULE_LICENSE` 巨集指定的授權條款又對核心有什麼影響 (GPL 與否對於可用的符號列表有關)，以及藉由 [strace](https://man7.org/linux/man-pages/man1/strace.1.html) 追蹤 Linux 核心的掛載，涉及哪些系統呼叫和子系統？
- [x] 閱讀《[The Linux Kernel Module Programming Guide](https://sysprog21.github.io/lkmpg/)》(LKMPG) 並解釋 [simrupt](https://github.com/sysprog21/simrupt) 程式碼裡頭的 mutex lock 的使用方式，並探討能否改寫為 [lock-free](https://hackmd.io/@sysprog/concurrency-lockfree);
- `read_lock`: 在讀取操作期間，同步對 `rx_fifo` kernel FIFO 緩衝區做訪問，確保只有一個執行緒可以從緩衝區讀取資料，防止資料損壞。
- `producer_lock`: 在 workqueue 處理程序內同步，將數據插入到 `rx_fifo` FIFO 中。防止多個生產者同時向 FIFO 插入資料。
- `consumer_lock`: 保護 `fast_buf` 環狀緩衝區的訪問，確保一次只有一個消費者可以進入。
- [ ] 探討 Timsort, Pattern Defeating Quicksort (pdqsort) 及 Linux 核心 [lib/sort.c](https://github.com/torvalds/linux/blob/master/lib/sort.c) 在排序過程中的平均比較次數，並提供對應的數學證明;
- [x] 研讀 [CMWQ (Concurrency Managed Workqueue)](https://docs.kernel.org/core-api/workqueue.html) 文件，對照 [simrupt](https://github.com/sysprog21/simrupt) 專案的執行表現，留意到 worker-pools 類型可指定 "Bound" 來分配及限制特定 worker 執行於指定的 CPU，Linux 核心如何做到？CMWQ 關聯的 worker thread 又如何與 CPU 排程器互動？
> Why CMWQ?
>
> 早期 Linux 的工作佇列提供了兩種主要類型：單執行緒工作佇列（ST wq）和多執行緒工作佇列（MT wq）。ST wq 使用單一的工作執行緒來處理所有的工作項目，而 MT wq 為每個 CPU 都配置了一個工作執行緒，以提高並行性。隨著時間推移，越來越多的系統使用了 MT wq，加上 CPU 核心數的不斷增加，導致一些系統在啟動時就達到了預設的 32k PID 上限。
>
> 儘管 MT wq 消耗了大量資源，其提供的並行性，效果仍然未達到預期。無論是 ST wq 還是 MT wq，這種限制都存在，只不過在 MT wq 上表現較為緩和。每個工作佇列都有自己的獨立 worker pool；在 MT wq 中，每個 CPU 只分配到一個，而 ST wq 在整個系統中只有一個 context。這導致 work item 需要爭奪極為有限的執行 context，進而引發多種問題，例如在單一執行中 context 容易出現 deadlock。
>
> 並行性的提供與資源使用之間的矛盾迫使使用者作出不必要的妥協。例如，libata 選擇使用單執行緒工作佇列來輪詢 PIOs，從而接受了一個不必要的限制：無法同時處理兩個輪詢 PIOs。因為多執行緒工作佇列的並行性仍不足以滿足需求，需要更高並行性的用戶，如 async 或 fscache，最終不得不自行開發 thread pool。
>
> 每個綁定實際 CPU 的工作池通過與調度器的整合來管理並行性。當工作者喚醒或進入睡眠時，工作池會更新可運行工作者的數量，從而保持工作項目持續處理，避免 CPU 閒置。系統旨在**用最少的工作者維持必要的執行頻寬，且會暫時保留但最終終止不活動的工作者**。
>
> 對於不綁定 CPU 的工作佇列，其後台支援池的數量可以動態調整。使用者可以通過 apply_workqueue_attrs() 自訂工作佇列的屬性，系統將自動創建相應的工作池。此外，進展保證機制依賴於能夠在需要時創建新的工作者，特別是在內存壓力下，某些工作項目會被分配到有專門救援工作者的工作佇列上，以防止因執行 context 耗盡導致的 deadlock。
- [ ] 解釋 `xoroshiro128+` 的原理 (對照〈[Scrambled Linear Pseudorandom Number Generators](https://arxiv.org/pdf/1805.01407.pdf)〉論文)，並利用 [ksort](https://github.com/sysprog21/ksort) 提供的 `xoro` 核心模組，比較 Linux 核心內建的 `/dev/random` 及 `/dev/urandom` 的速度，說明 `xoroshiro128+` 是否有速度的優勢？其弱點又是什麼？
- [x] 解釋 [ksort](https://github.com/sysprog21/ksort) 如何運用 CMWQ 達到並行的排序;
### [ksort](https://github.com/sysprog21/ksort)
#### What's workqueue?
通過呼叫 workqueue 的介面就能建立核心執行緒。並且可以根據目前系統 CPU 的個數建立執行緒的數量，使得執行緒處理能夠並行化。
```c
#include <linux/workqueue.h>
struct workqueue_struct *create_workqueue(const char *name);
```
所獲得的工作佇列，對系統上的每個處理器各有一個專屬執行緒。
```c
DECLARE_WORK(name,void (*function)(void*),void *data);
INIT_WORK(struct work_struct *work,void (*function)(void*),void *data);
```
DECLARE_WORK 為靜態初始化，會在編譯時期做好 work_struct 的初始化。
:::danger
注意書寫規範：
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
:::
```c
// example for DECLARE_WORK
#include <linux/init.h> // Needed for __init and __exit macros
#include <linux/module.h> // Needed by all modules
#include <linux/workqueue.h> // Required for work_struct and related functions
// Function that will be executed by the workqueue
void my_work_function(struct work_struct *work)
{
printk(KERN_INFO "Executing my_work_function\n");
}
// Declaring and initializing the work item statically
DECLARE_WORK(my_work, my_work_function);
// Module initialization function
static int __init my_module_init(void)
{
printk(KERN_INFO "Module loaded, scheduling work\n");
// Schedule the work to be executed
schedule_work(&my_work);
return 0;
}
// Module cleanup function
static void __exit my_module_exit(void)
{
printk(KERN_INFO "Module unloaded\n");
flush_scheduled_work(); // Ensure all scheduled work has finished
}
module_init(my_module_init);
module_exit(my_module_exit);
MODULE_LICENSE("GPL");
MODULE_AUTHOR("yu-hsien");
MODULE_DESCRIPTION("A simple example of using DECLARE_WORK");
```
`INIT_WORK` 為動態初始化，會在執行時期執行。
```c
// example for INIT_WORK
#include <linux/init.h>
#include <linux/module.h>
#include <linux/slab.h> // For dynamic memory allocation
#include <linux/workqueue.h>
struct work_struct *my_dynamic_work;
// Work handler function
void my_dynamic_work_function(struct work_struct *work)
{
printk(KERN_INFO "Dynamic work executed\n");
}
// Module initialization function
static int __init my_module_init(void)
{
printk(KERN_INFO "Module loaded, initializing dynamic work\n");
// Allocate memory for the work_struct
my_dynamic_work = kmalloc(sizeof(struct work_struct), GFP_KERNEL);
if (!my_dynamic_work)
return -ENOMEM;
// Initialize the dynamically allocated work_struct
INIT_WORK(my_dynamic_work, my_dynamic_work_function);
// Schedule the work
schedule_work(my_dynamic_work);
return 0;
}
// Module cleanup function
static void __exit my_module_exit(void)
{
printk(KERN_INFO "Cleaning up module\n");
if (my_dynamic_work) {
cancel_work_sync(
my_dynamic_work); // Ensure the work is not currently running
kfree(my_dynamic_work); // Free the allocated memory
}
}
module_init(my_module_init);
module_exit(my_module_exit);
MODULE_LICENSE("GPL");
MODULE_AUTHOR("yu-hsien");
MODULE_DESCRIPTION(
"An example of using INIT_WORK with dynamically allocated work_struct");
```
Makefile
```Makefile
obj-m += init_work_ex.o \
declare_work_ex.o
all:
make -C /lib/modules/$(shell uname -r)/build M=$(PWD) modules
clean:
make -C /lib/modules/$(shell uname -r)/build M=$(PWD) clean
```
用 `make` 編譯後，掛載二個核心模組，再執行 `dmesg | tail` 可得輸出：
```
[261931.853758] Module loaded, initializing dynamic work
[261931.853896] Dynamic work executed
[262921.150709] Module loaded, scheduling work
[262921.150853] Executing my_work_function
```
確認掛載成功後，我們可以利用 `nm` 來觀察變數的宣告方式
```shell
$ nm init_work_ex.ko | grep 'my_dynamic_work'
0000000000000000 B my_dynamic_work
0000000000000010 T my_dynamic_work_function
0000000000000000 T __pfx_my_dynamic_work_function
$ nm declare_work_ex.ko | grep 'my_work'
0000000000000000 D my_work
0000000000000010 T my_work_function
0000000000000000 T __pfx_my_work_function
```
對於 `declare_work_ex.ko` 和 `init_work_ex.ko` 中的符號類型 `D` 和 `B` 的理解如下：
1. D (Data section)：表示該變數已經初始化，位於初始化資料段中。declare_work_ex.ko 中的 my_work 使用 D 標記，這表示這是一個在編譯時期就已經初始化的靜態 work_struct，這符合 `DECLARE_WORK` 的行為，即在宣告時就完成初始化。
3. B (BSS section)：表示該變數未初始化，位於 BSS 段，這是用來存放程序中未初始化的全域變數和靜態變數的區域。init_work_ex.ko 中的 my_dynamic_work 使用 B 標記，這表示它是一個在 BSS 段的變數（可能是一個指向 work_struct 的指針），這通常指向一塊動態分配的記憶體（即使該指針本身是靜態分配的）。
---
#### [Engineering a Sort Function](https://cs.fit.edu/~pkc/classes/writing/papers/bentley93engineering.pdf)
ksort 採用的 quicksort 即是從這篇論文中所實作出來的。
##### 動機
現有的快速排序 (Quicksort) 實作在某些情況下表現不佳，特別是在非隨機輸入下效能可能變得很差，例如可能需要 $O(n^2)$ 來排序某些特定陣列配置。
##### 思考過程
在快速排序的最初版本時，是由 `Lomuto` 所提出來的，具體作法如下。選擇第 `1` 個元素當作 `pivot`，而若陣列已經做好排序(大到小或小到大)，會導致時間複雜度提升到 $O(n^2)$
:::danger
注意書寫規範：
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
:::
```c
// Lomuto's quicksort
void iqsort0(int *a, int n) {
int i, j;
if (n <= 1) return;
for (i = 1, j = 0; i < n; i++) {
if (a[i] < a[0])
swap(++j, i, a);
swap(0, j, a);
iqsort0(a, j);
iqsort0(a + j + 1, n - j - 1);
}
```
為了解決快速排序在面對已經排序或接近排序的陣列時性能下降的問題，改良版快速排序採取了隨機選擇 pivot 的策略。透過隨機產生一個索引並與陣列的第一個元素交換來實作，這樣 pivot 就被放在了陣列的開始位置。
而分割則採取兩個指標 `i` 和 `j`，其中 `i` 指向陣列的第二個元素（因為第一個元素是 pivot ），而 `j` 指向陣列的最後一個元素
1. `i` 指標從底部開始，向上尋找直到找到一個大於或等於 pivot 值的元素停下來
2. `j` 指標從頂部開始，向下尋找直到找到一個小於或等於 pivot 值的元素停下來
3. 檢查這兩個指標 `i` 和 `j` 是否已經交叉。如果沒有交叉（即 `i < j`），則交換這兩個位置的值，然後繼續進行上述兩個搜索步驟；如果交叉了（即 `i > j`），則將 j 位置的元素與 pivot（陣列的第一個元素）交換。
```c
// Program 3
void iqsort1(int *a, int n) {
int i, j, pivot_index, pivot;
if (n <= 1) return;
srand(time(NULL));
pivot_index = rand() % n;
swap(&a[0], &a[pivot_index]);
pivot = a[0];
i = 1;
j = n - 1;
// Partitioning step
while (i <= j) {
while (i <= j && a[i] <= pivot) i++;
while (i <= j && a[j] > pivot) j--;
if (i < j) {
swap(&a[i], &a[j]);
}
}
swap(&a[0], &a[j]);
iqsort1(a, j);
iqsort1(a + j + 1, n - j - 1);
}
```
切割完後如下圖所示:
作者進一步增強了排序功能的通用性和靈活性。這個版本的快速排序不再僅僅針對整數資料，而是可以處理任何類型的資料。函式接受一個 `char *a` 參數，這是指向資料的指標，其中的元素可以是任何資料型態。
- `es` 表示陣列中每個元素的大小（以 Byte 為單位）
- `cmp` 比較函式，允許用戶自定義比較的行為
```c
// Program 4
void iqsort1(char *a, int n, int es, int (*cmp)())
{
int j;
char *pi, *pj, *pn;
if (n <= 1) return;
pi = a + (rand() % n) * es;
swap(a, pi, es);
pi = a;
pj = pn = a + n * es;
for (;;) {
do pi += es; while (pi < pn && cmp(pi, a) < 0);
do pj -= es; while (cmp(pj, a) > 0);
if (pj < pi) break;
swap(pi, pj, es);
}
swap(a, pj, es);
j = (pj - a) / es;
qsort1(a, j, es, cmp);
qsort1(a + (j + 1) * es, n - j - 1, es, cmp);
}
```
為了進一步提升快速排序的效率並減少最壞情況下的性能下降，作者採用了 Tukey 的 `ninther` 方法來選擇中位數作為 pivot。這個方法是一個擴展的 **median of three** 技巧，它基於更大範圍的樣本來估計中位數，具體而言，是從三個不同的位置各取三個元素，再從這九個元素中選出中位數。雖然它比以往的 `median of three` 多了將近 12 次的比較次數，但對於大陣列來說成本不會很大，也能找到更加準確的中位數，不過對於小陣列可能就不是那麼友善了，所以作者經過實驗後來決定是否要用 `ninther` ，以下的數值是作者經過測試所統計出來的。
:::danger
提供數學推理和證明。
:::
- [Ninther](https://en.wikipedia.org/wiki/Median#Ninther) 方法: 先將原先的陣列切分成 3 部分(這邊會切成左，中，右)，並在每個子陣列中找尋其 `median of three`，找到後再比較較這三個子陣列中位數的中位數，來避免選到最糟的 `pivot` 的情況。
```c
static char *med3(char *a, char *b, char *c, int (*cmp)())
{ return cmp(a, b) < 0 ?
(cmp(b, c) < 0 ? b : cmp(a, c) < 0 ? c : a)
: (cmp(b, c) > 0 ? b : cmp(a, c) > 0 ? c : a);
}
// ninther
pm = a + (n / 2) * es; /* Small arrays, middle element */
if (n > 7) {
pl = a;
pn = a + (n - 1) * es;
if (n > 40) { /* Big arrays, pseudomedian of 9 */
s = (n / 8) * es;
pl = med3(pl, pl + s, pl + 2 * s, cmp);
pm = med3(pm - s, pm, pm + s, cmp);
pn = med3(pn - 2 * s, pn - s, pn, cmp);
}
pm = med3(pl, pm, pn, cmp); /* Mid-size, med of 3 */
}
```
`median of three` 示意圖如下 (平均比較次數: $\frac{8}{3}$)
在 `Program 3, 4` 中，當面對含有許多重複值的陣列時，其分割方法導致效率顯著下降。這是因為這些方法在處理重複值時可能會引起不必要的比較和交換操作，特別是當這些重複值佔據了大部分陣列時。相比之下，第七版的 quicksort 採用了所謂的 **fat partition** 方法，這種方法有效地將陣列分割成三部分：
- 數值小於 `pivot`
- 數值等於 `pivot`
- 數值大於 `pivot`
```c
void iqsort2(int *x, int n)
{
int a, b, c, d, l, h, s, v;
if (n <= 1) return;
v = x[rand() % n];
a = b = 0;
c = d = n - 1;
for (;;) {
while (b <= c && x[b] <= v) {
if (x[b] == v) iswap(a++, b, x);
b++;
}
while (c >= b && x[c] >= v) {
if (x[c] == v) iswap(d--, c, x);
c--;
}
if (b > c) break;
iswap(b++, c--, x);
}
s = min(a, b - a);
for(l = 0, h = b - s; s; s--) iswap(l++, h++, x);
s = min(d - c, n - 1 - d);
for(l = b, h = n - s; s; s--) iswap(l++, h++, x);
iqsort2(x, b - a);
iqsort2(x + n - (d - c), d - c);
}
```
示意圖如下:
最後，來看 ksort 是怎麼運作的:
可以發現到 sort_impl.c 中的 `qsort_algo` 有用到兩個標籤:
- `top`: 會先判斷要排序的長度是否小於 `7`，是則直接做插入排序，反之則作上述的排序方式，其中
```c
if (swap_cnt == 0) { /* Switch to insertion sort */
r = 1 + n / 4; /* n >= 7, so r >= 2 */
for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
for (pl = pm; pl > (char *) a && CMP(thunk, pl - es, pl) > 0;
pl -= es) {
q_swap(pl, pl - es);
if (++swap_cnt > r)
goto nevermind;
}
return;
}
```
這個判斷式用於決定要不要提前使用插入排序，要進入有兩個條件:
1. 子序列不能有值與 `pivot` 相同
2. 子序列已經可以被切分成兩半不須經過交換
ex.
```graphviz
digraph {
node[shape=record];
graph[pencolor=transparent];
rankdir=LR;
"Pivot"[shape=none];
"pc"[shape=none];
"pb"[shape=none];
"Pivot" -> 5 -> 3 -> 1 -> 2 -> 4 -> 8 -> 9
"pc" -> 9
"pb" -> 3
}
```
```graphviz
digraph {
node[shape=record];
graph[pencolor=transparent];
rankdir=LR;
"Pivot"[shape=none];
"pc"[shape=none];
"pb"[shape=none];
"Pivot" -> 5 -> 3 -> 1 -> 2 -> 4 -> 8 -> 9
"pc" -> 8
"pb" -> 9
}
```
3. 但若交換次數太多會在切回原先的排序方式
- `nevermind`: 會先計算分段大小，若兩側的數量都大於 `100`，則會分配一個新的 `qsort` 結構，並將它排入對列進行並行處理，而若其小於 `100` 且大於 `0`，會將左側分段採取地回方式來排序，右側分段採取 goto <s>跳轉</s> 到 `top` 來處理。
:::danger
注意用語：
* jump 是「跳躍」，而非「跳轉」，這操作沒有「轉」
$\to$ 教育部重編國語詞典的「[轉](https://dict.revised.moe.edu.tw/dictView.jsp?ID=8114)」解釋。
:::
## TODO: 依據第六次作業規範，重作 ksort
> 適度彙整其他學員的成果並予以重現，比較自己實作的表現。要確保排序結果正確。
## TODO: 改進並行的資料排序效能
> 在 ksort 的基礎，提出得以改善並行的資料排序效能的方案，並予以充分實作，要考慮到 workqueue / CMWQ / kernel thread 對於任務分配的效率 (CPU utilization)。
首先，我們再 sort_mod.c 上面加了以下的函式:
```c
void start_measure(void)
{
measure_start = ktime_get();
}
void end_measure(void)
{
measure_end = ktime_get();
printk(KERN_INFO "Duration on CPU: %llu ns\n", smp_processor_id(), ktime_to_ns(ktime_sub(measure_end, measure_start)));
}
```
為了測量不同情況下的執行時間，我們採用了三種不同的方法：
1. `workqueue = alloc_workqueue("sortq", 0, WQ_MAX_ACTIVE);`
workqueue 的第二個參數是 0 ，代表沒有對 CPU 有特定行為的指示。
2. `workqueue = alloc_workqueue("sortq", WQ_CPU_INTENSIVE | WQ_MEM_RECLAIM, WQ_MAX_ACTIVE);`
- `WQ_CPU_INTENSIVE`: 被設置此 flag 的 workqueue 中的 work 是特別消耗 CPU 資源的。具體的影響是，這些 workqueue 中的 work item 將歸 scheduler 管理，相關的 work item 不會阻止同一 worker-pools 中的其他 work item 被執行。
- `WQ_MEM_RECLAIM`: kernel 將預先考慮此狀況讓建立的 workqueue 可以無視記憶體的壓力來建立 rescuer thread 以避免 deadlock 的發生。
3. kernel threads
```c
int thread_function(void *data)
{
sort_data(data, 1024 / sizeof(int));
return 0;
}
struct task_struct *task;
task = kthread_run(thread_function, sort_buffer, "sort_thread");
if (IS_ERR(task)) {
kfree(sort_buffer);
return PTR_ERR(task);
}
```
我們利用 kernel threads 來執行排序，其中 IS_ERR(task) 用於，若創建失敗會回傳 true ，我們須將提前結束任務的分配，並通過 PTR_ERR(task) 來告知使用者錯誤原因為何。
:::spoiler
[Workqueue](https://docs.kernel.org/core-api/workqueue.html)
[Linux 核心設計: Concurrency Managed Workqueue(CMWQ)](https://hackmd.io/@RinHizakura/H1PKDev6h)
:::
接著，利用 python script 來產生資料
```python
def generate_data(num_files, num_integers):
for i in range(num_files):
data = [random.randint(0, 10000) for _ in range(num_integers)]
file_path = os.path.join(data_dir, f'data_{num_integers}_{i+1}.txt')
with open(file_path, 'w') as f:
f.write('\n'.join(map(str, data)))
```
有了資料後，我們還會用到 `perf` 來觀測，故需安裝 `perf`，安裝後，再利用批次檔來執行先前產生的資料
```sh
DEVICE="/dev/sort"
DATA_FILE_PREFIX="data/data_10000_"
RESULTS_FILE="kernel_threads_10000_results.txt"
echo "Performance Test Results" > $RESULTS_FILE
for i in $(seq 1 10); do
DATA_FILE="${DATA_FILE_PREFIX}${i}.txt"
echo "Running test for $DATA_FILE" >> $RESULTS_FILE
sudo perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./user "$DEVICE" "$DATA_FILE" &>> $RESULTS_FILE
if [ $? -ne 0 ]; then
echo "Test failed for $DATA_FILE" >> $RESULTS_FILE
exit 1
fi
echo "" >> $RESULTS_FILE
done
echo "All tests completed successfully." >> $RESULTS_FILE
```
並且修改 `user.c`
```c
#define N_ELEMENTS 10000
int main(int argc, char *argv[]) {
if (argc != 3) {
fprintf(stderr, "Usage: %s <device_path> <data_file>\n", argv[0]);
return -1;
}
const char *device_path = argv[1];
const char *data_file = argv[2];
int fd = open(device_path, O_RDWR);
...
```
使其可以對應上先前的批次檔。
並依序執行以下命令
```shell
$ make insmod
$ gcc -o user user.c
# Clear the Kernel Message Buffer
$ sudo dmesg -c
$ chmod +x run_tests.sh
$ ./run_tests.sh
# Capture specific module output
$ sudo dmesg | grep "Duration on CPU"
$ make clean
```
#### 結果
100 筆資料的排序 5 次的平均時間:
| | CMWQ(no flag) | CMWQ(two flag) | kernel threads |
| ----- | ------ | ------ | ------ |
| data1 | 3.2 ns | 3.2 ns | 3.8 ns |
| data2 | 4.2 ns | 4.2 ns | 4 ns |
| data3 | 0.4 ns | 5.2 ns | 3.6 ns |
| data4 | 3.6 ns | 4.4 ns | 4.4 ns |
| data5 | 6.2 ns | 5.2 ns | 2.2 ns |
| data6 | 7 ns | 6 ns | 2 ns |
| data7 | 3.2 ns | 5.2 ns | 3 ns |
| data8 | 4.8 ns | 4.6 ns | 4.4 ns |
| data9 | 7 ns | 4 ns | 3 ns |
| data10 | 7 ns | 2 ns | 3.8 ns |
| **Average** | 4.66 ns | 4.4 ns | 3.42 ns |
1000 筆資料的排序 5 次的平均時間:
| | CMWQ(no flag) | CMWQ(two flag) | kernel threads |
| ----- | ------ | ------ | ------ |
| data1 | 3.6 ns | 2.8 ns | 3.8 ns |
| data2 | 6 ns | 4.4 ns | 3.8 ns |
| data3 | 4.6 ns | 3.6 ns | 4 ns |
| data4 | 4.2 ns | 0.6 ns | 3.2 ns |
| data5 | 3.6 ns | 6.2 ns | 2.2 ns |
| data6 | 2.4 ns | 0.4 ns | 4.6 ns |
| data7 | 3 ns | 6.2 ns | 4 ns |
| data8 | 3.4 ns | 5.4 ns | 3 ns |
| data9 | 3.2 ns | 5.6 ns | 2.4 ns |
| data10 | 1 ns | 0 ns | 1.8 ns |
| **Average** | 3.4 ns | 3.48 ns | 3.28 ns |
10000 筆資料的排序 5 次的平均時間:
| | CMWQ(no flag) | CMWQ(two flag) | kernel threads |
| ----- | ------ | ------ | ------ |
| data1 | 3.4 ns | 3.4 ns | 4.4 ns |
| data2 | 0.6 ns | 4.2 ns | 4.6 ns |
| data3 | 2.6 ns | 4.6 ns | 3.4 ns |
| data4 | 3.2 ns | 5.8 ns | 4.8 ns |
| data5 | 5.2 ns | 3 ns | 3.6 ns |
| data6 | 2.6 ns | 3.6 ns | 5 ns |
| data7 | 3.6 ns | 4.4 ns | 4.4 ns |
| data8 | 2.6 ns | 3.6 ns | 4.6 ns |
| data9 | 3.2 ns | 3 ns | 4.6 ns |
| data10 | 4.4 ns | 3.2 ns | 3.4 ns |
| **Average** | 3.02 ns | 3.76 ns | 4.28 ns |
在處理不同規模的資料集時，kernel threads 在小到中等規模的資料集上表現良好，提供了最快的處理時間。然而，在更大的資料集上，不帶 flag 的 CMWQ 表現出更佳的效率
:::danger
使用 gnuplot 製圖，並留意資料範圍。
:::
> [commit 336a10d](https://github.com/yu-hsiennn/ksort/commit/336a10dfbe3056e20770c7dee861604d5a841cd1)
Sign in with Wallet
Connect another wallet