Linux Linked-List Queue 實作與排序優化

contributed by < Tonr01 >

開發環境

gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0

架構：                   x86_64
CPU 作業模式：            32-bit, 64-bit
Address sizes:          39 bits physical, 48 bits virtual
Byte Order:             Little Endian
CPU(s):                 16
On-line CPU(s) list:    0-15
供應商識別號：            GenuineIntel
Model name:             11th Gen Intel(R) Core(TM) i7-11800H @ 2.30GHz
    CPU 家族：           6
    型號：               141
    每核心執行緒數：       2
    每通訊端核心數：       8
    Socket(s):          1
    製程：               1
    CPU max MHz:        4600.0000
    CPU min MHz:        800.0000
    BogoMIPS:           4608.00

Virtual machine 建立

建立虛擬機
設定硬碟大小
設定存儲裝置，並選擇下載好的 Ubuntu 版本

Ubuntu磁區分割

Ubuntu Linux 磁碟分割和目錄的類型和定義說明

因為是在虛擬機上分割磁區，不會有 EFI 跟 Bios ，所以都須自己分割出來

安裝必要檔案

作業要求

q_new: 建立新的「空」佇列;
q_free: 釋放佇列所佔用的記憶體;
q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);
q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點;
q_remove_tail: 在佇列尾端 (tail) 移去 (remove) 給定的節點;
q_release_element: 釋放特定節點的記憶體空間;
q_size: 計算目前佇列的節點總量;
q_delete_mid: 移走佇列中間的節點，
- 詳見 LeetCode 2095. Delete the Middle Node of a Linked List
q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點
- 詳見 LeetCode 82. Remove Duplicates from Sorted List II
q_swap: 交換佇列中鄰近的節點
- 詳見 LeetCode 24. Swap Nodes in Pairs
q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
q_reverseK: 類似 q_reverse，但指定每 k 個節點為一組，進行反向順序排列
- 詳見 LeetCode 25. Reverse Nodes in k-Group
q_sort: 以遞增順序來排序鏈結串列的節點
- 參閱 Linked List Sort 得知實作手法;
q_merge: 合併所有已排序的佇列，並合而為一個新的已排序佇列
- 詳見 LeetCode 23. Merge k Sorted Lists
q_descend:
- 參閱 LeetCode 2487. Remove Nodes From Linked List

queue.c 開發過程

q_new

思路

一開始最簡單的想法是，配置記憶體給head，並檢查是否配置成功。

程式碼

出現了 Segmentation fault occurred. You dereferenced a NULL or invalid pointermake ，再看完程式碼的 comment Notice: sometimes, Cppcheck would find the potential NULL pointer bugs 與巨集後，發現我忽略了 pointer 的指向。

struct list_head *q_new()
{
    struct list_head *head =
        (struct list_head *) malloc(sizeof(struct list_head));

    if (!head) {
        free(head);
        return NULL;
    }

    return head;
}

於是加入 INIT_LIST_HEAD(head); ，將 head 的 prev 與 next 都指向自己。

struct list_head *q_new()
{
    struct list_head *head =
        (struct list_head *) malloc(sizeof(struct list_head));

    if (!head) {
        free(head);
        return NULL;
    }

+    INIT_LIST_HEAD(head);

    return head;
}

q_free

思路

一開始先檢查 list 是否存在，若不存在則無須進行 q_free ，再看完 list.h 定義的巨集後，發現 list_for_each_entry_safe 適合用來走訪每個 entry ，再使用 q_release_element(entry); 來釋放該 entry 的 entry->value 及 entry->list ，最後將 head 也釋放掉，釋放整個 list。

程式碼

void q_free(struct list_head *l)
{
    if (!l)
        return;

    element_t *entry, *safe;

    list_for_each_entry_safe (entry, safe, l, list)
        q_release_element(entry);

    free(l);
}

q_insert_head

思路

首先先檢查 list 是否存在，再配置記憶體給新的 entry，並檢查 entry 與 entry->value 的空間是否配置成功，將節點的value值用strdup(s);將s的值複製給它，最後將new_element用list_add加入到list開頭的位置上。

程式碼

有出現 Test of malloc failure 錯誤訊息，才發現 entry 裡的 entry->value 的空間也可能配置失敗，於是加入配置記憶體的檢查。

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *new_element = malloc(sizeof(element_t));

    if (!new_element)
        return false;

    new_element->value = strdup(s);

    list_add(&new_element->list, head);

    return true;
}

修改後。

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *new_element = malloc(sizeof(element_t));

    if (!new_element)
        return false;

    new_element->value = strdup(s);

+    if (!new_element->value) {
+        free(new_element);
+      return false;
+   }

    list_add(&new_element->list, head);

    return true;
}

q_insert_tail

思路

大致上與 q_insert_head 思路一樣，首先先檢查 list 是否存在，再配置記憶體給新的 entry，並檢查 entry 與 entry->value 的空間是否配置成功，將 entry->value 用 strdup(s); 將s的值複製給它，最後將 new_element 用 list_add_tail 加入到list最後的位置上。

程式碼

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *new_element = malloc(sizeof(element_t));

    if (!new_element)
        return false;

    new_element->value = strdup(s);

    if (!new_element->value) {
        free(new_element);
        return false;
    }

    list_add_tail(&new_element->list, head);

    return true;
}

q_remove_head

思路

一開始先檢查 list 使否存在與 list 是否為空，再使用 list_first_entry 找出第一個 entry 的位置，再使用 list_del_init 將此 entry remove ，並將此 entry 的 prev 與 next 都指向自己，最後將 entry->value 用 strncpy 複製到 sp 裡。

程式碼

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *target = list_first_entry(head, element_t, list);
    list_del_init(&target->list);

    if (sp) {
        strncpy(sp, target->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    return target;
}

q_remove_tail

思路

大致上與 q_remove_head 思路一樣，一開始先檢查 list 使否存在與 list 是否為空，再使用 list_last_entry 找出最後一個 entry 的位置，再使用 list_del_init 將此 entry remove ，並將此 entry 的 prev 與 next 都指向自己，最後將 entry->value 用 strncpy 複製到 sp 裡。

程式碼

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *target = list_last_entry(head, element_t, list);
    list_del_init(&target->list);

    if (sp) {
        strncpy(sp, target->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    return target;
}

q_size

思路

一開始先檢查 list 使否存在與 list 是否為空，再宣告一個節點用 list_for_each 去走訪 list ，並紀錄 list 大小。

程式碼

int q_size(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

    int size = 0;
    struct list_head *li;

    list_for_each (li, head)
        size++;

    return size;
}

q_delete_mid

思路

我的想法是用 two-pointer 的方式實作，首先宣告兩個 pointer pre 與 nex 分別代表 list 的頭跟尾的位置，這兩個 pointer 會一直往中心移動，會有兩種 case

Case 1：Size of list 為奇數 (5個節點)，此時當 pre 與 nex 在同個位置的節點即為中心點。

Case 2：Size of list 為偶數 (6個節點)，此時當 pre 與 nex 交錯時， pre 即為中心點。

用 list_del 將該節點從 list 中分離出來，再用 list_entry 取得 entry 位置，最後釋放該 entry 。

程式碼

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;

    struct list_head *pre = head->prev;
    struct list_head *nex = head->next;

    // Find the middle of list
    do {
        pre = pre->prev;
        nex = nex->next;
    } while (pre != nex && pre != nex->next);

    list_del(pre);
    element_t *target = list_entry(pre, element_t, list);
    q_release_element(target);

    return true;
}

q_delete_dup

思路

先用 list_for_each_entry_safe 去走訪每個元素，分別用 target 與 temp 去紀錄第一個元素與下一個元素，再檢查它們是否相同，若相同，則釋放掉 target，用一個二元變數 dup 去紀錄是否有重複，若 dup == true ，則 target 也為重複的元素，再將其釋放。

在實作時出現 Segmentation fault occurred. You dereferenced a NULL or invalid pointer ，發現是因為在比較時， temp 存取去到 head ，所以加入了 target->list.next != head 去使 temp 不會去存取到 head 。

程式碼

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;

    bool dup = false;
    element_t *target, *temp;

    list_for_each_entry_safe (target, temp, head, list) {
        if (target->list.next != head && !strcmp(target->value, temp->value)) {
            dup = true;
            list_del(&target->list);
            q_release_element(target);
        } else if (dup) {
            dup = false;
            list_del(&target->list);
            q_release_element(target);
        }
    }

    return true;
}

q_reverse

思路

想到的方法為逐一將 list 走訪，每走訪一個 entry 就將該 entry 從 list 中分離出來，再加入到 list 的第一個位置。

程式碼

void q_reverse(struct list_head *head)
{
    element_t *entry, *safe;
    list_for_each_entry_safe (entry, safe, head, list)
        list_move(&entry->list, head);
}

q_reversek

思路

作法跟 q_reverse 類似，但不像 q_reverse 總是將節點插入第一個位置，這裡使用一個 pointer insert 指向一組 k 個節點的第一個插入位置，再使用 count 去紀錄走訪的節點數，當走訪的節點數恰 k 個時，將 pointer insert 指向下一組 k 個節點的第一個插入位置，也就是上一組的最後一個節點(目前節點的 prev)。

程式碼

void q_reverseK(struct list_head *head, int k)
{
    if (!head || list_empty(head))
        return;

    struct list_head *node = NULL, *safe = NULL, *insert = head;
    int count = 0;

    list_for_each_safe(node, safe, head) {
        if (k > count) 
            list_move(node, insert);
        else {
            count = 0;
            insert = node->prev;
        }
        count++;
    }    
}

q_swap

思路

q_swap 其實就是 q_reverseK(2) ，於是用q_reverseK 去實作。

程式碼

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    q_reverseK(head, 2);
}

q_descend

思路

從 list 最尾端開始往前做，設 target 為最後一個元素、 prev 為 target 的前一個元素、 size 紀錄 list 中剩餘元素個數。

若後面的元素比前一個元素大，則將前一個元素移出 list。
繼續往前找，直到找到比現在的 target 還大的元素，再將 target 指向此元素。
重複以上步驟直到到 head 為止。

程式碼

在跑測試時，在執行 q_free 後尚有未被刪除的元素，發現因為將元素移出 list 後，並未將其釋放而造成錯誤。

int q_descend(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

    int size = q_size(head);
    struct list_head *target = head->prev, *prev = target->prev;

    while (target->prev !=head) {
        element_t *t = list_entry(target, element_t, list);
        element_t *p = list_entry(prev, element_t, list);

        if (strcmp(p->value, t->value) < 0) {
            list_del_init(&p->list);
            prev = target->prev;
            size--;
        }
        else {
            target = prev;
            prev = target->prev;
        }
    }

    return size;
}

修改後

int q_descend(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

    int size = q_size(head);
    struct list_head *target = head->prev, *prev = target->prev;

    while (target->prev !=head) {
        element_t *t = list_entry(target, element_t, list);
        element_t *p = list_entry(prev, element_t, list);

        if (strcmp(p->value, t->value) < 0) {
-           list_del_init(&p->list);
+           list_del(&p->list);
+           q_release_element(p);
            prev = target->prev;
            size--;
        }
        else {
            target = prev;
            prev = target->prev;
        }
    }

    return size;
}

使用 diff 或 git diff 產生程式碼差異的列表

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

jserv

q_sort

思路

我選擇採用 merge sort，因為 merge sort 為 stable sorting algorithm ，而其最壞的時間複雜度只有 \(O(nlogn)\) ，這裡參考了 Linked List Sort 的實作方法，將 merge sort 分成三個部份，分別是：

mergelist
- 主要是做 merge 的部份，採用非遞迴的方式將兩個 list 以遞增的形式串接在一起。
mergesort
- 主要是做 split 的部份，使用兩個指標，分別是 fast 與 slow ，採用 Floyd Cycle Detection Algorithm ，當較快的指標到達終點時，較慢的指標會恰好在中心位置，並以遞迴的方式將 list 拆解，再呼叫 mergelist 將拆解後的 list 排序並重新組合成一條 list。
q_sort
- 因為採用 Floyd Cycle Detection Algorithm 的方式，所以原本的環狀佇列結構會導致找不到中心位置，於是先將原本的環狀 doubly-linked list 轉換成 singly-linked list，等做完 merge sort 後，再將 singly-linked list 轉回環狀 doubly-linked list。

注意連字號的位置，書寫為 "doubly-linked list"

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv
👌 (以修改)

程式碼

mergelist

struct list_head *mergelist(struct list_head *l1, struct list_head *l2)
{
    struct list_head temp;
    struct list_head *t = &temp;

    while (l1 && l2) {
        element_t *ele1 = list_entry(l1, element_t, list);
        element_t *ele2 = list_entry(l2, element_t, list);
        if (strcmp(ele1->value, ele2->value) < 0) {
            t->next = l1;
            t = t->next;
            l1 = l1->next;
        } else {
            t->next = l2;
            t = t->next;
            l2 = l2->next;
        }
    }

    // Connect the remain list
    if (l1)
        t->next = l1;
    if (l2)
        t->next = l2;

    return temp.next;
}

mergesort

struct list_head *mergesort(struct list_head *head)
{
    if (!head->next)
        return head;

    struct list_head *fast = head->next;
    struct list_head *slow = head;

    // split list
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // Fast is the middle of list
    fast = slow->next;
    slow->next = NULL;

    struct list_head *left = mergesort(head);
    struct list_head *right = mergesort(fast);

    // Merge sorted left and sorted right
    return mergelist(left, right);
}

q_sort

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    // Turn the list into Singly linked list
    head->prev->next = NULL;
    head->next = mergesort(head->next);

    // Turn the list into doubly circular linked list
    struct list_head *temp = head, *next = head->next;
    while (next) {
        next->prev = temp;
        temp = next;
        next = next->next;
    }
    temp->next = head;
    head->prev = temp;

q_merge

思路

一開始有兩種想法，第一種是使用 mergelist 迭代的將兩條 list 合併成一條，但因為 mergelist 實作的關係，輸入需要是沒有 head 的兩條 list ，所以在迭代前都需要先對 list head 做處理，而在合併後還須將 list 變回 doubly-linked list，以上步驟會讓程式碼變得較為冗長。於是採用第二種方法，第二種為先將所有 list 串接在一起，再對這條 list 做 q_sort ，這樣一來就無須對 head 做變更，整體程式碼可以較為簡短。

cur 表示第一條 queue， temp 為指向下一條佇列的指標，迭代的將後面的佇列連接到第一條佇列後面，最後再對這條佇列做 q_sort ，最後回傳佇列長度。

程式碼

int q_merge(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

    queue_contex_t *cur = list_entry(head->next, queue_contex_t, chain);

    for (struct list_head *temp = head->next->next; temp != head;
         temp = temp->next) {
        queue_contex_t *t = list_entry(temp, queue_contex_t, chain);
        list_splice_init(t->q, cur->q);
    }

    q_sort(cur->q);
    return q_size(cur->q);
}

引入 list_sort.c 比較自己的 sort.c 效能差異

引入`list_sort` 檔案及修改

首先引入 list_sort.h ，刪除不必要的 header 。

/* SPDX-License-Identifier: GPL-2.0 */
#ifndef _LINUX_LIST_SORT_H
#define _LINUX_LIST_SORT_H

#include <stdint.h>
#include "list.h"

list_sort.c 使到兩個巨集 likely 與 unlikely，定義於<linux/compiler.h>，將其定義加入 list_sort.h 中，在 merge_final 函式中宣告了 u8 count = 0; ，將其改成 uint_8 count = 0; 。

# define likely(x)	__builtin_expect(!!(x), 1)
# define unlikely(x)	__builtin_expect(!!(x), 0)

最後是將 list_sort.o 寫入 makefile 裡。

OBJS := qtest.o report.o console.o harness.o queue.o list_sort.o\
        random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
        shannon_entropy.o \
        linenoise.o web.o

在 qtest 中先複製一份 do_sort 給 list_sort 使用，在 list_sort.h 中有定義函式，於是需要自己實作，這個函式是用來比較字串大小，回傳值為 int 。

typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *,
		const struct list_head *, const struct list_head *);

所以在 qtest 中加入 cmp 函式實作。

int cmp(void *priv, const struct list_head *list1, const struct list_head *list2)
{
    element_t *list1_entry = list_entry(list1, element_t, list);
    element_t *list2_entry = list_entry(list2, element_t, list);
    return strcmp(list1_entry->value, list2_entry->value)   ;
}

在 qtest 中的命令 mysort 與 list_sort 都能正常執行。

效能比較

這裡用 qtest 中的 time 進行時間的比較，有三種測資，分別用命令 RAND 加入100000、300000、500000筆隨機資料給 queue 。

測試指令

加入自己寫的 trace-mysort.cmd 與 trace-list_sort.cmd 到測試資料中， ./qtest -v 3 -f traces/trace-list_sort.cmd 會執行以下命令。

option fail 0
option malloc 0
new
ih RAND 100000/300000/500000
time mysort/list_sort
free

my_sort

測試次數	100000筆	300000筆	500000筆
1	0.042	0.196	0.407
2	0.041	0.194	0.419
3	0.042	0.200	0.430
average	0.0417	0.1967	0.4187

list_sort

測試次數	100000筆	300000筆	500000筆
1	0.041	0.170	0.368
2	0.043	0.170	0.388
3	0.039	0.171	0.364
average	0.041	0.1703	0.3733

效能差距

	100000筆	300000筆	500000筆
效能差距	2%	14%	11%

因為測試資料都是隨機生成的，加上測試次數不多，所以以 Perf 來分析效能。

測試方式不足以反映出上述實作的特性。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv
👌 (以修改)

以 Linux 效能分析工具: Perf 來分析效能

環境安裝

$ cat "/boot/config-`uname -r`" | grep "PERF_EVENT"

用此指令確認是否安裝 perf。

$ uname -r
5.19.0-43-generic

確認 kernel 版本。

$ sudo apt-get install linux-tools-5.19.0-43-generic linux-cloud-tools-5.19.0-43-generic

安裝 perf。

$ cat /proc/sys/kernel/perf_event_paranoid

確認 perf 權限。

2 : 不允許任何量測。但部份用來查看或分析已存在的紀錄的指令仍可使用，如 perf ls、perf report、perf timechart、 perf trace。
1 : 不允許 CPU events data。但可以使用 perf stat、perf record 並取得 Kernel profiling data。
0 : 不允許 raw tracepoint access。但可以使用 perf stat、perf record 並取得 CPU events data。
-1: 權限全開。

$ sudo sh -c " echo -1 > /proc/sys/kernel/perf_event_paranoid"

將權限全開

$ sudo sh -c " echo 0 > /proc/sys/kernel/kptr_restrict"

最後如果要檢測 cache miss event，需要先取消 kernel pointer 的禁用。

測試指令

使用./qtest -v 3 -f traces/trace-list_sort.cmd 會執行以下命令，這裡以500000筆隨機資料做測試。

option fail 0
option malloc 0
new
ih RAND 500000
time mysort/list_sort
free

執行 perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./qtest -f traces/trace-mysort.cmd ，會執行5次上述命令，再去觀察其效能。

my_sort

Performance counter stats for './qtest -f traces/trace-mysort.cmd' (5 runs):

        16,049,539      cache-misses              #   48.666 % of all cache refs      ( +-  0.18% )
        32,954,397      cache-references                                              ( +-  0.04% )
     2,203,807,317      instructions              #    0.74  insn per cycle           ( +-  0.00% )
     2,958,082,501      cycles                                                        ( +-  0.37% )

           0.65370 +- 0.00448 seconds time elapsed  ( +-  0.69% )

list_sort

Performance counter stats for './qtest -f traces/trace-list_sort.cmd' (5 runs):

        14,022,127      cache-misses              #   54.505 % of all cache refs      ( +-  0.43% )
        25,688,333      cache-references                                              ( +-  0.10% )
     2,251,606,244      instructions              #    0.81  insn per cycle           ( +-  0.00% )
     2,867,416,957      cycles                                                        ( +-  0.90% )

           0.61738 +- 0.00504 seconds time elapsed  ( +-  0.82% )

效能

event data	my_sort	list_sort
cache-misses	16,049,539	14,022,127
cache-references	32,954,397	25,688,333
instructions	2,203,807,317	2,251,606,244
cycles	2,958,082,501	2,867,416,95

花費時間

測試次數	my_sort 花費時間	list_sort 花費時間
1	0.357	0.398
2	0.361	0.412
3	0.362	0.407
4	0.364	0.411
5	0.365	0.402
average	0.3618	0.406

可以看出 list_sort 的 cache-misses 比 my_sort 少很多， list_sort 所需的 instructions 與 cycles 都比 my_sort 少， my_sort 只能達到 list_sort 的 89% 效能 (0.3618/0.406 = 0.89) 。

在 qtest 提供新的命令並實作 shuffle

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

先用 q_size 取得佇列的大小 len。
隨機從 0 ~ (len - 1) 中抽出一個數字 random，抽到的數字為節點的位置，再將該節點加到佇列最後位置。
隨著 len 大小變小，直到所有的節點都已經被抽到過，shuffle 就結束。

shuffle 流程

len	random	queue	result
0–5	5	A B C D E F	F
0–4	3	A B C D E	F D
0–3	1	A B C E	F D B
0–2	1	A C E	F D B C
0–1	0	A E	F D B C A
0–0	0	E	F D B C A E

shuffle 實作

len 為佇列的大小，random 為隨機數，也同時代表被抽到的節點位置，將 node 移動到第 random 個節點位置，再將該節點移動到佇列最後的位置，當每個節點都做過一輪就結束。

void shuffle(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    int len = q_size(head);

    while (len) {
        int random = rand() % len;
        struct list_head *node = head->next;

        while (random) {
            node = node->next;
            random--;
        }

        list_move_tail(node, head);
        len--;
    }
}

將 shuffle 加入到 qtest 裡面，這裡的 do_shuffle 是參考 do_reverse 的實作，因為這兩個函式都是用來改變佇列的位置。

bool do_shuffle(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }

    if (!current || !current->q)
        report(3, "Warning: Calling shuffle on null queue");
    error_check();

    set_noallocate_mode(true);
    if (current && exception_setup(true))
        shuffle(current->q);
    exception_cancel();

    set_noallocate_mode(false);
    q_show(3);
    return !error_check();
}

執行結果

# do 5 times shuffle
l = []
l = [A]
l = [A B]
l = [A B C]
l = [A B C D]
l = [A B C D E]
l = [A B C D E F]
# shuffle
l = [E F D C B A]
l = [B A F E C D]
l = [E F B C A D]
l = [C F D E A B]
l = [B D F A E C]
l = NULL
Freeing queue

研讀論文〈Dude, is my code constant time?〉，解釋本程式的 “simulation” 模式

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

Introduction

這篇論文主要闡述提供了一個新的工具 dudect ，可以不限定任何平台去檢測部份的程式碼是否達到 constant time ，提供 leakage detection 的方法。

Leakage detection

這個方法會先去測量兩種不同的輸入的執行時間，並用統計學去判定這兩種執行時間的差異性，其中一種輸入為固定的數值，另一種為隨機數值。在進行統計分析前會先裁掉極值，這些極值可能是測量的誤差或是程式執行被中斷導致。

Statistical test

這裡採用 Welch's t-test ，為 Student's t-test 的改編版， Welch's t-test 處理兩個樣本間不同的標準差與樣本大小會比較可靠，這個方法會去計算兩個樣本的均值是否相等，並計算出 t 值。其中 \(\bar{X}\) 為樣本均值， \(s_{\bar{X}}\) 為標準差。

Pre-processing

這裡提到的預處理指的是在進行統計分析前裁剪掉極值的動作，而裁剪的方法為裁剪掉大於 \(p\) 百分比的測量值。這部份也就是 simulation 的缺陷，因為沒有將極值裁剪掉，導致影響到測量的速度。

解釋 Simulation 模式

首先在 trace-17-complexity.cmd 會先執行 option simulation 1 ，先開啟 simulation mode ，再呼叫 it, ih, rh, rt 四個函式。以呼叫 ih 為例，在 qtest 中會執行 bool do_ih 函式。

if (simulation) {
        if (argc != 1) {
            report(1, "%s does not need arguments in simulation mode", argv[0]);
            return false;
        }
        bool ok = is_insert_head_const();
        if (!ok) {
            report(1,
                   "ERROR: Probably not constant time or wrong implementation");
            return false;
        }
        report(1, "Probably constant time");
        return ok;
    }

可以看到決定執行時間是否為 constant time 且程式正確執行，由函式 is_insert_head_const 決定，此函式在 fixture.h 定義。

bool is_##op##_const(void) { return test_const(#op, DUT(op)); }

在 fixture.c 中 is_##op##_const 會回傳函式 test_const 的結果 result ， result 為函式 doit 的回傳值。

result = doit(mode);

其中 result 由兩個函式的回傳值做 AND 而來， measure(), report()。

static bool doit(int mode)
{
    ...
    bool ret = measure(before_ticks, after_ticks, input_data, mode);
    ...
    ret &= report();
    ...
    return ret;
}

首先為函式measure ，主要對四種模式 it, ih, rh, rt 進行執行正確性的判定，判定依據為執行完該函式，其改變後的佇列大小是否正確。

if (before_size != after_size - 1)
    return false;

再來是函式 report ，主要是用來判定執行時間是否為 constant time 。

/* Definitely not constant time */
if (max_t > t_threshold_bananas)
    return false;

/* Probably not constant time. */
if (max_t > t_threshold_moderate)
    return false;

/* For the moment, maybe constant time. */
return true;

解決 Simulation 實作的缺陷

首先將參數 \(p\) 百分比 percentiles 加入到宣告中，但因為作者有多宣告了一種結構，而 Simulation 實作是將宣告直接寫在函式中，於是這裡將 percentiles 在 t_context_t 結構中宣告。

/* 作者宣告 */ 
typedef struct {
  int64_t *ticks;
  int64_t *exec_times;
  uint8_t *input_data;
  uint8_t *classes;
  dudect_config_t *config;
  ttest_ctx_t *ttest_ctxs[DUDECT_TESTS];
  int64_t *percentiles;  <------
} dudect_ctx_t;

typedef struct {
    double mean[2];
    double m2[2];
    double n[2];
+   int64_t *percentiles;
} t_context_t;

再將相關程式引入到專案中，詳細修改在 commit 中。

測試結果

加入了 percentiles 的實作後，測試都能在 constant time 內完成。

---	Trace		Points
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---	TOTAL		5/5

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.

Linux Linked-List Queue 實作與排序優化

開發環境

Virtual machine 建立

Ubuntu磁區分割

安裝必要檔案

作業要求

queue.c 開發過程

q_new

思路

程式碼

q_free

思路

程式碼

q_insert_head

思路

程式碼

q_insert_tail

思路

程式碼

q_remove_head

思路

程式碼

q_remove_tail

思路

程式碼

q_size

思路

程式碼

q_delete_mid

思路

程式碼

q_delete_dup

思路

程式碼

q_reverse

思路

程式碼

q_reversek

思路

程式碼

q_swap

思路

程式碼

q_descend

思路

程式碼

q_sort

思路

程式碼

q_merge

思路

程式碼

引入 list_sort.c 比較自己的 sort.c 效能差異

引入list_sort 檔案及修改

效能比較

測試指令

my_sort

list_sort

效能差距

以 Linux 效能分析工具: Perf 來分析效能

環境安裝

測試指令

my_sort

list_sort

效能

花費時間

在 qtest 提供新的命令並實作 shuffle

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

shuffle 流程

shuffle 實作

執行結果

研讀論文〈Dude, is my code constant time?〉，解釋本程式的 “simulation” 模式

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

Introduction

Leakage detection

Statistical test

Pre-processing

解釋 Simulation 模式

解決 Simulation 實作的缺陷

測試結果

引入`list_sort` 檔案及修改