2024q1 Homework1 (lab0)

contributed by <jychen0611 >

Reviewed by jimmy01240397

1. 善用巨集展開以減少重複的程式碼，例如：
   ​​​​#define q_remove_base(head, sp, bufsize, from)                \
   ​​​​    if (!head || list_empty(head))                            \
   ​​​​        return NULL;                                          \
   ​​​​    element_t *tmp = list_first_entry(head, element_t, list); \
   ​​​​    strncpy(sp, tmp->value, bufsize);                         \
   ​​​​    sp[bufsize - 1] = '\0';                                   \
   ​​​​    list_del(&tmp->list);                                     \
   ​​​​    return tmp;
   ​​​​    
   ​​​​element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
   ​​​​{
   ​​​​    q_remove_base(head, sp, bufsize, first);
   ​​​​}
   
   ​​​​element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
   ​​​​{
   ​​​​    q_remove_base(head, sp, bufsize, last);
   ​​​​}
   

   • q_insert_head
   • q_insert_tail
   • q_remove_head
   • q_remove_tail
   • q_ascend
   • q_descend

:monkey: commit e674e7b

Add multiple sets of function macros

[What?] 採納 jimmy01240397 的建議將同類型的函式寫成巨集 [Why?] 原程式碼存在重複性極高的函式，可用巨集整合之 [How?] 以下依函式類型兩兩說明

(1) q_insert_head 和 q_insert_tail

使用巨集 q_insert_base 利用 to 判別是 q_insert_head 還是 q_insert_tail 使用，若傳入 head ，則表 q_insert_head ，需使用 list_add。反之則使用 list_add_tail。

+#define q_insert_base(head, sp, to)                                 \
    .
    .
+   !strcmp(to, "head") ? list_add(&tmp->list, head) : list_add_tail(&tmp->list, head); \

(2) q_remove_head 和 q_remove_tail

使用巨集 q_remove_base 利用 from 判別是 q_remove_head 還是 q_remove_tail 使用，若傳入 first ，則表 q_remove_head ，需使用 list_first_entry。反之則使用 list_last_entry。

#define q_remove_base(head, sp, bufsize, from)                \
    .
    .
+   element_t *tmp = !strcmp(from, "first") ? list_first_entry(head, element_t, list) : list_last_entry(head, element_t, list); \

(3) q_ascend 和 q_descend

使用巨集 q_scend_base 利用 dir 判別是 q_ascend 還是 q_descend 使用，若傳入 ascend ，則表 q_ascend ，需使用 strcmp(cur, t->value) >= 0。反之則使用 strcmp(cur, t->value) <= 0。

+#define q_scend_base(head, dir)                                 \
   .
   .
+       if (strcmp(dir, "ascend") ? strcmp(cur, t->value) >= 0 : strcmp(cur, t->value) <= 0) {\

2. 刪除部分非必要的分支
   • PR

:monkey: commit b003cdc

Merge pull request #1 from chumytest/master

[What?] 接受 jimmy01240397 的 pull request [Why?] 原程式碼不夠精簡，且有多餘判斷式 [How?] 以下依不同函式更動逐一說明

(1) q_delete_mid

在此無須檢查節點數量是否只有一個。若只有一個節點，則 slow 會指到這個節點，且不會進入 while 迴圈，最終會刪除 slow 所指的這個唯一的節點。

-    if (list_is_singular(head)) {
-        struct list_head *del = head->next;
-        list_del(del);
-        q_release_element(list_entry(del, element_t, list));
-    }

(2) q_delete_dup

新增變數 nowdel 表當前是否需刪除該節點，以簡化判斷式敘述。

-    bool del = false;
+    bool del = false, nowdel = false;

使用 del 紀錄 nowdel 的先前狀態，以刪除最後一個重複節點。

    list_for_each_safe (l, r, head) {
        element_t *nl = list_entry(l, element_t, list);
        element_t *nr = list_entry(r, element_t, list);
-        if (l->next != head && !strcmp(nl->value, nr->value)) {
-            list_del(l);
-            q_release_element(nl);
-            del = true;
-        } else if (del) {
+        nowdel = r != head && !strcmp(nl->value, nr->value);
+        if (nowdel || del) {
            list_del(l);
            q_release_element(nl);
-            del = false;
+            del = nowdel;
        }
    }

(3) merge (用於 q_sort)

以 ((descend * 2) - 1) * strcmp(l->value, r->value) > 0 判斷要優先將 left 的 element 放入佇列尾端，還是將 right 的 element 放入佇列尾端。 ((descend * 2) - 1) 此處理方式可使 descend 值從原本的 0/1 表示轉成 -1/+1 表示。 因此

• ((descend * 2) - 1)為 +1 表 descend
• ((descend * 2) - 1)為 -1 表 ascend

eg. 若 strcmp(l->value, r->value) > 0 (l>r) 且 ((descend * 2) - 1)為 +1 (descend)，則優先放入 left 的 element。

     while (!list_empty(left) && !list_empty(right)) {
        element_t *l = list_entry(left->next, element_t, list);
        element_t *r = list_entry(right->next, element_t, list);
-        if (descend) {
-            if (strcmp(l->value, r->value) > 0) {
-                list_move_tail(left->next, head);
-            } else {
-                list_move_tail(right->next, head);
-            }
+        if (((descend * 2) - 1) * strcmp(l->value, r->value) > 0) {
+            list_move_tail(left->next, head);
        } else {
-            if (strcmp(l->value, r->value) < 0) {
-                list_move_tail(left->next, head);
-            } else {
-                list_move_tail(right->next, head);
-            }
+            list_move_tail(right->next, head);
        }
    }

最後是微幅調整，將!list_empty(left) 代換成 list_empty(left) ，list_splice_tail(left, head) 也隨之替換成 list_splice_tail(right, head)

-    if (!list_empty(left))
-        list_splice_tail(left, head);
-    else
+    if (list_empty(left))
        list_splice_tail(right, head);
+    else
+        list_splice_tail(left, head);

(4) q_merge

新增變數 tmphead 作為 head->next 的替代放入 list_for_each 的第二個輸入，待進入迴圈後，再將 tmphead 改為 head 。 其用意為使 node 初始化為 head->next->next ，這樣便能跳過第一個佇列，不必額外去檢查當前是否為第一個佇列。 刪除 if (list_empty(another_q->q)) continue; 不會影響程式運作，不需要做此額外判斷。

-    struct list_head *tmp;
-    list_for_each (tmp, head) {
-        if (tmp == head->next) {
-            continue;
-        }
+    struct list_head *tmp, *tmphead = head->next;

+    list_for_each (tmp, tmphead) {
+        tmphead = head;
        queue_contex_t *another_q = list_entry(tmp, queue_contex_t, chain);
-        if (list_empty(another_q->q))
-            continue;
        len += another_q->size;
        list_splice_init(another_q->q, first_q->q);
    }

然而我在修改 commit message 時遭遇以下問題 新增的 nowdel 被系統指出範圍可以縮減，且初始化 nowdel 為 false 並無實質意義

elian@elian-System-Product-Name:~/linux2024/lab0-c$ git rebase -i 2808dbedc22d4577bd0ecbd28862b6fb28fdefaa
queue.c:156:23: style: The scope of the variable 'nowdel' can be reduced. [variableScope]
    bool del = false, nowdel = false;
                      ^
queue.c:156:30: style: Variable 'nowdel' is assigned a value that is never used. [unreadVariable]
    bool del = false, nowdel = false;
                             ^

Fail to pass static analysis.

於是我做了以下修改

:monkey: commit 7d17d45

Correct the variable

[What?] 修正變數 nowdel 的宣告方式 [Why?] nowdel 被系統指出範圍可以縮減，且初始化 nowdel 為 false 並無實質意義 [How?] 把 nowdel 宣告在 list_for_each_safe 迴圈內

-   bool nowdel = false;
    list_for_each_safe (l, r, head) {
        element_t *nl = list_entry(l, element_t, list);
        element_t *nr = list_entry(r, element_t, list);
-       nowdel = r != head && !strcmp(nl->value, nr->value);
+       bool nowdel = r != head && !strcmp(nl->value, nr->value);
        if (nowdel|| del) {
            list_del(l);
            q_release_element(nl);
            del = nowdel;
        }
    }

經修改後，程式可正常 push 上去，但唯獨 pull request 的 commit message 無法做修改，仍會有上述問題。 待解

3. q_merge：直接將所有已經排序完成的鏈結串列接上再重新排序有點不太 優雅，應該有效能更好的解決方式。

用字務必精準，既然說他人不好，那就提供好的做法給同學看。 :notes: jserv

:monkey: commit 0db6def

Improve the efficiency of q_merge

[What?] 撰寫 merge_with_first_q 函式，使其他佇列能和第一個佇列兩兩合併，以改善 q_merge 效能。 [Why?] 比起直接將所有已經排序完成的鏈結串列接上再重新排序，有效能更好的解決方式。 [How?] 在 merge_with_first_q 函式中，使用佇列標頭變數 tmp_head 存放已排序的節點，其排序過程似 merge 函式，最終將排序好的節點接回第一個佇列。

    list_for_each (tmp, tmphead) {
        tmphead = head;
        queue_contex_t *another_q = list_entry(tmp, queue_contex_t, chain);
        len += another_q->size;
-       list_splice_init(another_q->q, first_q->q);
+       merge_with_first_q(another_q->q, first_q->q, descend);
    }
-   q_sort(first_q->q, descend);

Reviewed by Kuanch

• 未完成 lib/list_sort.c 的效能測量，這部分實作不困難，使用 perf 及準備小規模獨立的測試即可，可參考 q_sort 與 list_sort 效能比較，亦可透過 dudect/cpucycles.h僅計算 cycle 數

:monkey: commit 2a8d392

比較自己實作的 merge sort 和 Linux 核心程式碼之間效能落差

• 研讀論文〈Dude, is my code constant time?〉我傾向至少將程式碼一一和文章對應，譬如它是如何計算執行時間、怎麼做後處理、如何計算統計量等等，再針對其中有興趣的程式碼深入探討；或參考 vax-r，他以記錄自身的問題以及解答撰寫本節

:monkey: commit e9eab10

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

• Git 部分，commit message 有落實 Why?What?How? 很難得，向你看齊

開發環境

$ 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:         46 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  32
  On-line CPU(s) list:   0-31
Vendor ID:               GenuineIntel
  Model name:            13th Gen Intel(R) Core(TM) i9-13900K
    CPU family:          6
    Model:               183
    Thread(s) per core:  2
    Core(s) per socket:  24
    Socket(s):           1
    Stepping:            1
    CPU max MHz:         5800.0000
    CPU min MHz:         800.0000
    BogoMIPS:            5990.40

針對佇列操作的程式碼實作

依據上述指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 $ make test 自動評分系統的所有項目。

• :warning: 在提交程式變更前，務必詳閱 如何寫好 Git Commit Message
• 詳閱「你所不知道的 C 語言: linked list 和非連續記憶體」並應用裡頭提及的手法，例如 pointer to pointer (指向某個指標的指標，或說 indirect pointer)，讓程式碼更精簡且有效
• 參閱「2023 年 Linux 核心設計/實作課程第一次作業檢討」，留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心

結構體

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

typedef struct {
    char *value;
    struct list_head list;
} element_t;

q_new

:monkey: commit 0bf802e

Implement q_new

[What?] 初始化一個雙向環狀佇列 [Why?] 此功能可初始化一個標頭指標 h 以串接之後新增的節點 [How?] 宣告一個 struct list_head *h 並使用 malloc 函式分配記憶體給指標 h ，此指標可用來串街接之後新增的節點 使用巨集 INIT_LIST_HEAD 初始化指標 h

根據 C99 standard 的 malloc 描述如下：

Synopsis

#include <stdlib.h>
void *malloc(size_t size);

Description The malloc function allocates space for an object whose size is specified by size and whose value is indeterminate. Returns The malloc function returns either a null pointer or a pointer to the allocated space.

:monkey: commit bf419a8

Check null pointer

[What?] 新增檢查 h 是否有成功被分配到記憶體空間 [Why?] malloc 之回傳可能為 null pointer [How?] 在呼叫 INIT_LIST_HEAD 前先檢查 h 是否為 NULL

可知 malloc 之回傳可能為 null pointer 故在呼叫 INIT_LIST_HEAD 前須先檢查是否為 NULL

    struct list_head *h = (struct list_head *) malloc(sizeof(struct list_head));
-   INIT_LIST_HEAD(h);
+   if (h)
+       INIT_LIST_HEAD(h);
    return h;

q_free

:monkey: commit c3ed425

Implement q_free

[What?] 實作佇列刪除功能，並回收分配給該佇列的空間 [Why?] 使系統之後能用一個函式就刪除佇列 [How?] 遍歷佇列中所有節點釋放該空間，最後再釋放佇列標頭指標所佔空間

根據 C99 standard 的 free 描述如下：

Synopsis

#include <stdlib.h>
void free(void *ptr);

Description The free function causes the space pointed to by ptr to be deallocated, that is, made available for further allocation. If ptr is a null pointer, no action occurs. Otherwise, if the argument does not match a pointer earlier returned by the calloc, malloc, or realloc function, or if the space has been deallocated by a call to free or realloc, the behavior is undefined. Returns The free function returns no value.

使用 list_for_each_entry_safe 巨集以逐一釋放 entry 空間

/**
 * list_for_each_entry_safe - Iterate over list entries and allow deletes
 * @entry: pointer used as iterator
 * @safe: @type pointer used to store info for next entry in list
 * @head: pointer to the head of the list
 * @member: name of the list_head member variable in struct type of @entry
 *
 * The current node (iterator) is allowed to be removed from the list. Any
 * other modifications to the the list will cause undefined behavior.
 *
 * FIXME: remove dependency of __typeof__ extension
 */
#define list_for_each_entry_safe(entry, safe, head, member)                \
    for (entry = list_entry((head)->next, __typeof__(*entry), member),     \
        safe = list_entry(entry->member.next, __typeof__(*entry), member); \
         &entry->member != (head); entry = safe,                           \
        safe = list_entry(safe->member.next, __typeof__(*entry), member))

其中，list_entry 表 container_of

/**
 * list_entry() - Get the entry for this node
 * @node: pointer to list node
 * @type: type of the entry containing the list node
 * @member: name of the list_head member variable in struct @type
 *
 * Return: @type pointer of entry containing node
 */
#define list_entry(node, type, member) container_of(node, type, member)

參考自　Linux 核心原始程式碼巨集: container_of 巨集 container_of 在 offsetof 的基礎上，擴充為「給定成員的位址、struct 的型態，及成員的名稱，傳回此 struct 的位址」

    if (!l)
        return;
+   element_t *entry, *safe;
+   list_for_each_entry_safe (entry, safe, l, list) {
+       free(entry);
+   }
    free(l);

:monkey: commit c5ff2aa

Replace free() with q_release_element() on q_free

[What?] 釋放節點中 value 空間 [Why?] 原程式並無釋放節點中的字元指標 value 所佔用的空間，因此做以下修正 [How?] 以 q_release_element() 取代 free()

原程式並無釋放節點中的字元指標 value 所佔用的空間，因此做以下修正

-   free(entry);
+   q_release_element(entry);

q_insert_head

:monkey: commit a6d38b5

Implement q_insert_head, q_insert_tail

[What?] 實作新增節點到佇列的頭或尾之功能 [Why?] 使佇列能新增帶有指定字串的節點到頭尾 [How?] 先確認佇列是否存在，再嘗試分配空間給新的節點 tmp ，若分配成功則將指定字串 s 放入節點，最後利用list_add 和list_add_tail將節點加入佇列

根據 C99 standard 的 strcpy 描述如下：

Synopsis

#include <string.h>
char *strcpy(char * restrict s1,
const char * restrict s2);

Description The strcpy function copies the string pointed to by s2 (including the terminating null character) into the array pointed to by s1. If copying takes place between objects that overlap, the behavior is undefined. Returns The strcpy function returns the value of s1.

使用 strcpy 後在 commit 時遭遇以下問題 ：

Following files need to be cleaned up:
queue.c
Dangerous function detected in /home/elian/linux2024/lab0-c/queue.c
44:    strcpy(tmp->value, s);
57:    strcpy(tmp->value, s);

Read 'Common vulnerabilities guide for C programmers' carefully.
    https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml

根據訊息提供的 Common vulnerabilities guide for C programmers

The strcpy built-in function does not check buffer lengths and may very well overwrite memory zone contiguous to the intended destination. In fact, the whole family of functions is similarly vulnerable: strcpy, strcat and strcmp.

strcpy strcat strcmp 由於這些函式不會檢查緩衝區的長度，皆有可能發生相鄰記憶體區域覆寫的情形

於是改用 strncpy 來實現，更改完就能 commit 了

根據 C99 standard 的 strncpy 描述如下：

Synopsis

#include <string.h>
char *strncpy(char * restrict s1,
const char * restrict s2,
size_t n);

Description The strncpy function copies not more than n characters (characters that follow a null character are not copied) from the array pointed to by s2 to the array pointed to by s1. If copying takes place between objects that overlap, the behavior is undefined. If the array pointed to by s2 is a string that is shorter than n characters, null characters are appended to the copy in the array pointed to by s1, until n characters in all have been written. Returns The strncpy function returns the value of s1.

    if (!head)
        return false;
    element_t *tmp = malloc(sizeof(element_t));
    if (!tmp)
        return false;
-   strcpy(tmp->value, s);    
+   strncpy(tmp->value, s, (strlen(s) + 1));
    list_add(&tmp->list, head);

:monkey: commit 15790b1

Add allocation for new element's value

[What?] 為新增節點的value配置空間 [Why?] 由於節點中的字元指標 value 也需配置空間，才能存放字串 s ，故新增此功能 [How?] 配置 strlen(s) + 1 的空間給節點的 value，並檢查是否配置成功，若失敗則是放節點空間，並回傳 false

參考 millaker 為新增節點的value配置空間

+    tmp->value = (char *) malloc(sizeof(char) * (strlen(s) + 1));
+    if (!tmp->value) {
+        q_release_element(tmp);
+        return false;
+    }

q_insert_tail

:monkey: commit a6d38b5

Implement q_insert_head, q_insert_tail

[What?] 實作新增節點到佇列的頭或尾之功能 [Why?] 使佇列能新增帶有指定字串的節點到頭尾 [How?] 先確認佇列是否存在，再嘗試分配空間給新的節點 tmp ，若分配成功則將指定字串 s 放入節點，最後利用list_add 和list_add_tail將節點加入佇列

    if (!head)
        return false;
    element_t *tmp = malloc(sizeof(element_t));
    if (!tmp)
        return false;
-   strcpy(tmp->value, s); 
+   strncpy(tmp->value, s, (strlen(s) + 1));
    list_add_tail(&tmp->list, head);

q_remove_head

:monkey: commit ef95866

Implement q_remove_head, q_remove_tail

[What?] 實作從佇列頭或尾移除節點並回傳的函式 [Why?] 使節點可以從佇列頭尾移除 [How?] 先檢查佇列是否存在或是否為空，接著利用list_first_entry 或 list_last_entry取得佇列頭尾的節點，並將節點中的字串複製給 sp，最後利用list_del 將節點從佇列移除，回傳節點

使用list_empty 檢查佇列是否為空 使用list_first_entry 取得佇列第一個節點 strncpy不會複製最後一個字元\0 使用list_del 將該節點從佇列中移除

    if (!head || list_empty(head))
        return NULL;
    element_t *tmp = list_first_entry(head, element_t, list);
    strncpy(sp, tmp->value, bufsize);
+   sp[bufsize - 1] = '\0';
    list_del(&tmp->list);
    return tmp;

改成巨集後發現有以下問題

Testing remove_head...(0/10)

Segmentation fault occurred.  You dereferenced a NULL or invalid pointer

:monkey: commit 0656c4c

Modify the macro q_remove_base

[What?]新增 if (tmp && sp) 判別式到巨集 q_remove_base [Why?]原先方式會存取到 NULL [How?]在使用 tmp 和 sp 前先檢查是否為空

q_remove_tail

:monkey: commit ef95866

Implement q_remove_head, q_remove_tail

[What?] 實作從佇列頭或尾移除節點並回傳的函式 [Why?] 使節點可以從佇列頭尾移除 [How?] 先檢查佇列是否存在或是否為空，接著利用list_first_entry 或 list_last_entry取得佇列頭尾的節點，並將節點中的字串複製給 sp，最後利用list_del 將節點從佇列移除，回傳節點

使用list_last_entry 取得佇列最後一個節點

    if (!head || list_empty(head))
        return NULL;
+   element_t *tmp = list_last_entry(head, element_t, list);
    strncpy(sp, tmp->value, bufsize);
    sp[bufsize - 1] = '\0';
    list_del(&tmp->list);
    return tmp;

q_size

:monkey: commit 42858f3

Implement function : q_size

[What?] 實作取得佇列大小的函式 [Why?] 此函數可取得佇列大小 [How?] 使用了巨集 list_for_each 走訪所有節點，並利用 len 變數紀錄節點個數

使用了巨集 list_for_each 走訪所有節點

/**
 * list_for_each - Iterate over list nodes
 * @node: list_head pointer used as iterator
 * @head: pointer to the head of the list
 *
 * The nodes and the head of the list must be kept unmodified while
 * iterating through it. Any modifications to the the list will cause undefined
 * behavior.
 */
#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

    if (!head)
        return 0;
    int len = 0;
    struct list_head *li;
+   list_for_each (li, head)
+       len++;
    return len;

HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」

q_delete_mid

<approach 1>

:monkey: commit 093aebb

Implement q_delete_mid (first approach)

[What?] 實作刪除佇列中間節點之函式 [Why?] 使佇列能從中間移除節點 [How?] 第一個版本嘗試最簡單的方式，利用 q_size 取得佇列中間的位置，將指標移至中間刪除該節點

先嘗試最簡單的方式，利用q_size取得佇列中間的位置，將指標移至中間刪除該節點

+   int counter = q_size(head) / 2;
+   struct list_head *tmp = head->next;
+   while (counter--) {
+       tmp = tmp->next;
+   }
    list_del(tmp);
    q_release_element(list_entry(tmp, element_t, list));

<approach 2>

:monkey: commit 2808dbe

Implement approach 2 of the q_delete_mid

[What?] 提出另一個版本的方法 [Why?] 原方法需倚賴 q_size 函式來取得佇列大小，需要花一次遍歷佇列的時間，再走到佇列中間刪除節點。而新方法只需遍歷佇列一次即可。 [How?] 利用快慢指針的搭配找出中間節點 fast一次移動兩步，slow一次移動一步 當 fast 走訪完整個佇列後，slow會剛好落在佇列中間的位置

方法二利用快慢指針的搭配找出中間節點 fast一次移動兩步，slow一次移動一步 當 fast 走訪完整個佇列後，slow會剛好落在佇列中間的位置

+   struct list_head *fast = head->next->next;
+   struct list_head *slow = head->next;
+   while (fast != head && fast->next != head) {
+       fast = fast->next->next;
+       slow = slow->next;
+   }

q_delete_dup

C99 Standard

Synopsis

#include <string.h>
int strcmp(const char *s1, const char *s2);

Description The strcmp function compares the string pointed to by s1 to the string pointed to by s2. Returns The strcmp function returns an integer greater than, equal to, or less than zero, accordingly as the string pointed to by s1 is greater than, equal to, or less than the string pointed to by s2.

<approach 1.0>

:monkey: commit fc79a87

Implement q_delete_dup

[What?] 實作刪除佇列中連續相同節點之函式 [Why?] 使佇列可移除所有連續相同的節點 [How?] 利用 list_for_each_safe 走訪每個節點，發現有重複的節點便刪除之

:monkey: commit 036b0e1

Add flag on q_delete_dup

[What?] 新增旗標del_flag 以刪除所有重複相鄰節點 [Why?] 原先我誤會題目要求，以為刪除重複相鄰節點到剩下一個即可。而題目真正的要求是要刪除所有重複相鄰節點，故作此修改 [How?] 走訪佇列節點的過程中，若發現有重複相鄰節點，則刪除其中一個，並將旗標 del_flag 設為true，以利刪除最後一個多餘節點

利用 list_for_each_safe 走訪每個節點，發現有重複的節點便刪除之

:monkey: commit c9cc2dc

Revise the q_delete_dup function

[What?] 修改 q_delete_dup 函式，解決對 null pointer 取值之錯誤 [Why?] 執行 list_for_each_entry_safe 可以走訪整個 list 但是需要注意在走訪完時 n 會指向 head，且 head 是無法透過 container_of 找到節點的，因為它沒有嵌入到結構體中，這時如果對 n 取 contain_of 會拿到 NULL 如果再做取值 n->value 會報錯 成為無效的記憶體操作。 [How?] 新增 l->next != head 條件，避免對 null pointer 取值

參考 chiangkd 新增 l->next != head 條件，避免對 null pointer 取值

執行 list_for_each_entry_safe 可以走訪整個 list 但是需要注意在走訪完時 n 會指向 head，且 head 是無法透過 container_of 找到節點的，因為它沒有嵌入到結構體中，這時如果對 n 取 contain_of 會拿到 NULL 如果再做取值 n->value 會報錯 成為無效的記憶體操作。

    struct list_head *l, *r;
    bool del = false;
    list_for_each_safe (l, r, head) {
        element_t *nl = list_entry(l, element_t, list);
        element_t *nr = list_entry(r, element_t, list);
+       if (l->next != head && strcmp(nl->value, nr->value) == 0) {
            list_del(l);
            q_release_element(nl);
            del = true;
        } else if (del) {
            if (strcmp(nl->value, nr->value) == 0)
                del = true;
            else
                del = false;
            list_del(l);
            q_release_element(nl);

TODO: 撰寫為更精簡的程式碼

<approach 1.1>

:monkey: commit 5ce9dc5

Revise the q_delete_dup function

[What?] 移除 q_delete_dup 中多餘程式碼 [Why?] 後來發現先前寫法在跑某些測資時會存取到 NULL 原因在於下面這段程式碼完全是多餘的

-    if (strcmp(nl->value, nr->value) == 0)
-        del = true;
-    else
-        del = false;
+    del = false;

遭遇到重複節點只需多刪除最後一個節點即可，前面不管重複幾次都滿足條件 !strcmp(nl->value, nr->value) 。 進行多餘的判斷且沒使用 l->next != head 確保程式不會使用到空指標是危險的行為！ [How?] 刪除上述多餘程式碼，使功能正常運作

access 的翻譯是「存取」，而非「拜訪」(visit)

後來發現上述寫法在跑某些測資時會存取到 NULL。 原因在於下面這段程式碼完全是多餘的，遭遇到重複節點只需多刪除最後一個節點即可，前面不管重複幾次都滿足條件 !strcmp(nl->value, nr->value) 。 進行多餘的判斷且沒使用 l->next != head 確保程式不會使用到空指標是危險的行為！

-           if (strcmp(nl->value, nr->value) == 0)
-               del = true;
-           else
-               del = false;
+           del = false;

更改就能穩定通過測試項目 06 了

此處是「測試項目」(item)，而非「資料」，查閱辭典以理解二者的差異。

q_swap

<approach 0>

:monkey: commit 6ccf009

Implement q_swap

[What?] 實作交換佇列中兩兩相鄰節點之功能 [Why?] 使佇列能兩兩交換相鄰節點之位置 [How?] 利用list_for_each_safe走訪佇列，每兩步進行一次左右節點交換

:monkey: commit 8003196

Consider q_size is odd

[What?] 考量節點個數是奇數時，第一個節點會和最後一個節點交換的情形 [Why?] 若節點個數是奇數，則原程式碼會讓第一個節點和最後一個節點交換 [How?] 在迴圈中加入 if (r == head) 之判斷，即時中止迴圈

:monkey: commit f2bea72

Add counter on q_swap

[What?] 加入counter紀錄當前迴圈走了幾步，偶次步才進行節點交換 [Why?] 因為題目要求第1個節點和第2個節點交換，第3和第4交換…以此類推 [How?] 迴圈中加入判斷式 if (counter % 2 == 0) 若滿足才進行交換

利用list_for_each_safe走訪佇列，每兩步進行一次左右節點交換 並參考 vax-r，考量節點個數是奇數時，head 也會被交換的情形

    struct list_head *r, *l;
    int counter = 0;
    list_for_each_safe (l, r, head) {
+        if (r == head)
+            break;
        if (counter % 2 == 0) {
            l->next = r->next;
            r->prev = l->prev;
            l->prev->next = r;
            r->next->prev = l;
            l->prev = r;
            r->next = l;
        }
        ++counter;
    }

<approach １>

:monkey: commit 5c6caea

Revise the q_swap function

[What?] 寫個簡單的 for 迴圈取代 list_for_each_safe [Why?] 先前的寫法是錯的，原因是交換後 l 會指向右邊的節點，r 會指向左邊的節點 [How?] 以 for 迴圈將 l 指標推進，並將 l 和 r 交換位置。交換完後 l 會在右邊，因此 l 前進後可直接進行下一次的交換。 無須使用 if (counter % 2 == 0) 判斷式

上面的寫法是錯的，原因是交換後 l 會指向右邊的節點，r 會指向左邊的節點 於是我決定寫個簡單的 for 迴圈取代 list_for_each_safe

     int counter = 0;
-    list_for_each_safe (l, r, head) {
+    for (l = (head)->next; l != (head); l = l->next) {
        r = l->next;
        if (r == head)
            break;
-       if (counter % 2 == 0) {
            l->next = r->next;
            r->prev = l->prev;
            l->prev->next = r;
            r->next->prev = l;
            l->prev = r;
            r->next = l;
-       }
-       ++counter;

<approach ２>

:monkey: commit 5d87af3

Implement second version of q_swap

[What?] 提出第二個方法，並盡量使用 List API [Why?] 善用 List API，可精簡程式碼，提昇程式可讀性 [How?] 利用list_del和list_add_tail 將佇列前兩個節點移出佇列，並以相反的順序放回佇列尾端。

為了善用 List API，我寫了第二個版本的 q_swap 利用list_del和list_add_tail 將佇列前兩個節點移出佇列，並以相反的順序放回佇列尾端。

+       struct list_head *first = l, *second = r;
+       l = r->next;
+       list_del(first);
+       list_del(second);
+       list_add_tail(second, head);
+       list_add_tail(first, head);

q_reverse

:monkey: commit ce7affb

Implement q_reverse

[What?] 實作將佇列節點全部調換順序的函式 [Why?] 使佇列能更改方向 [How?] 依序將佇列所有 link 指向反方向。 並發現指標 l 一旦指到最後一個節點程式便會跳出迴圈，應當再補上一次迴圈內的動作

依序將佇列所有 link 指向反方向，並發現指標l一旦指到最後一個節點程式便會跳出迴圈，應當再補上一次迴圈內的動作

    if (!head || list_empty(head))
        return;
    struct list_head *r, *l;
    list_for_each_safe (l, r, head) {
        l->next = l->prev;
        l->prev = r;
    }
+   l->next = l->prev;
+   l->prev = r;

TODO: 善用 List API

q_reverseK

<approach 0>

:monkey: commit 5b9c697

Implement q_reverseK

[What?] 實作將佇列中每 k 個節點調換順序之函式 [Why?] 使佇列能以每 k 個節點來調換順序 [How?] 利用 counter 判別當前指標l r是否在 group 的交界處 若是，則將左方 group 反向串接到右方 group 否則執行單純的指標反轉

利用 counter 判別當前指標l r是否在 group 的交界處 若是，則將左方 group 反向串接到右方 group 否則執行單純的指標反轉

    struct list_head *l, *r, *leader;
    int counter = k;
    list_for_each_safe (l, r, head) {
        if (counter == k)
            leader = l;

        if (counter == 0) {
            r->prev = leader;
            l->prev = leader->next;
            leader->next->next = l;
            leader->next = r;
            counter = k;
        } else {
            l->next = l->prev;
            l->prev = r;
        }
        --counter;
    }

上述寫法是錯的

<approach 1>

:monkey: commit 13b8552

Revise the q_reverseK function

[What?] 修正 q_reverseK 函式，使功能正常。 使用 list_cut_position, list_splice_init 完成實作，修正程式的功能，同時也精簡化程式碼 [Why?] 原先寫法有誤 [How?] 首先利用 counter 判斷當前是否需要調換前面 k 個節點順序。 接著利用list_cut_position分出前面 k 個節點。 使用 q_reverse 函式調換 k 個節點的順序。 最後再用 list_splice_init 將 k 個節點放回佇列

於是參考 rkhuncle 使用 list_cut_position, list_splice_init 完成實作 下圖是我對 list_cut_position 的理解 leader為head_from的輸入，本身並不會放入head_to list 中

使用 list_cut_position 後

    struct list_head *l, *r, *leader;
+   struct list_head group;
    int counter = k - 1;
    for (l = (head)->next, r = l->next, leader = head; l != (head);
         l = r, r = l->next, --counter) {
         if (counter == 0) {
+           list_cut_position(&group, leader, l);
            q_reverse(&group);
+           list_splice_init(&group, leader);
+           leader = r->prev;
            counter = k;
         }
     }

q_sort

:monkey: commit b621694

Implement q_sort

[What?] 實作將佇列排序之函式，並盡量善用 List API 精簡化程式碼 [Why?] 此函式較為複雜，多使用 List API 可增加程式可讀性 [How?] 先宣告 list_head:l r 分別存放由list_cut_position 所分割的左右兩半佇列，接著再分別對左右兩半佇列進行 q_sort ，排序完畢後再將左右兩半進行 merge 。

以下是 merge 過程，先判別是否 descend，再依序比較左右兩個佇列的第一個 node.value ，將較 大/小 的 node 塞入head 的尾端，當有任何佇列為空則結束迴圈，再將非空佇列加入 head。

參考 Merge Sort – Data Structure and Algorithms Tutorials 和 linkedListSort 以了解 merge sort 的基本原理與實作方式。 subsidium 完善利用 List API，程式碼寫得精簡易讀，值得借鏡！

於是我花了30分鐘認真將 List API 的所有功能和實作細節看懂看熟，並開始撰寫 q_sort 程式碼。

先宣告 list_head:l r 分別存放由list_cut_position 所分割的左右兩半佇列，接著再分別對左右兩半佇列進行 q_sort ，排序完畢後再將左右兩半進行 merge 。

以下是 merge 過程，先判別是否 descend，再依序比較左右兩個佇列的第一個 node.value ，將較 大/小 的 node 塞入head 的尾端，當有任何佇列為空則結束迴圈，再將非空佇列加入 head。

   while (!list_empty(left) && !list_empty(right)) {
        element_t *l = list_entry(left->next, element_t, list);
        element_t *r = list_entry(right->next, element_t, list);
        if (descend) {
            if (strcmp(l->value, r->value) > 0) {
+               list_move_tail(left->next, head);
            } else {
+               list_move_tail(right->next, head);
            }
        } else {
            if (strcmp(l->value, r->value) < 0) {
+               list_move_tail(left->next, head);
            } else {
+               list_move_tail(right->next, head);
            }
        }
    }
    if (!list_empty(left))
+       list_splice_tail(left, head);
    else
+       list_splice_tail(right, head);

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

參考 2024/03/19,21 課堂簡記 164253

c 可以自己寫一個 next_permutation ，實作方式類似 leetcode 第 31 題， 過程中需要排序，考慮每次改變的區間可以發現，長度為

$k$ 的區間有

$f(k)$ 個

$f(n)=0,f(n-1)=n-1,f(k)=k(1+\sum _{i=k+1}^{n}f(i))$

$\{\begin{array}{r}\frac{f(k+1)}{k+1}-1=f(k+2)+\cdots +f(n)\\ \frac{f(k)}{k}-1=f(k+1)+\cdots +f(n)\end{array}$

$f(k)=f(k+1)\frac{k(k+2)}{k+1}=(n-1)\frac{(n-2)n}{n-1}\frac{(n-3)(n-1)}{n-2}\cdots \frac{k(k+2)}{k+1}=\frac{n!}{(k+1)!}k$

$f(n-1)=n-1$

$eg.$ 以數字1~8為例(n=8)，18765432 ⇨ 21345678 2移動了 n-1 格，可知每當首位數字變動時，才會有數字恰移動 n-1 格，因此長度為 n-1 的變動區間有 n-1 個。

$f(k)=k(1+\sum _{i=k+1}^{n}f(i))$

下圖是我的理解

可將變動區間的發生頻率定義成：

• 變動範圍 n-1 的區間有 n-1 個
• 每個變動範圍區間大於等於 k 的上下間隔必存在恰 k-1 個變動範圍為 k-1 的區間。

相當於

• 變動範圍為 1 的區間有 n!/2 個
• 每經歷 k-1 次區間範圍為 k-1 的變動，後續必會遭遇區間範圍大於等於 k 的變動，除了最後 k-1 次。

$<pf>$ [1] 由

$f(n-1)=n-1$ 首項成立

[2] 假設

$f(k)=k(1+\sum _{i=k+1}^{n}f(i))$ 成立，則

$f(k-1)=$

q_ascend

:monkey: commit 7145a8b

Implement q_ascend and q_descend

[What?] 實作移除不滿足 ascend 或 descend 排列順序的節點之函式 [Why?] 依作業需求實作此功能 [How?] 由佇列尾端沿著 prev 走訪整個佇列，並利用 curMin 紀錄先前遇過的最小字串，若當前存取的節點字串大於等於curMin 則刪除該節點。

由佇列尾端沿著 prev 走訪整個佇列，並利用 curMin 紀錄先前遇過的最小字串，若當前存取的節點字串大於等於curMin 則刪除該節點。

    while (tmp != head) {
        element_t *na = list_entry(tmp, element_t, list);

        if (strcmp(curMin, na->value) <= 0) {
            struct list_head *del = tmp;
            tmp = tmp->prev;
            list_del(del);
            q_release_element(na);
        } else {
            curMin = na->value;
            tmp = tmp->prev;
        }
    }

q_descend

:monkey: commit 7145a8b

Implement q_ascend and q_descend

[What?] 實作移除不滿足 ascend 或 descend 排列順序的節點之函式 [Why?] 依作業需求實作此功能 [How?] 由佇列尾端沿著 prev 走訪整個佇列，並利用 curMax 紀錄先前遇過的最大字串，若當前拜訪的節點字串小於等於curMax 則刪除該節點。

由佇列尾端沿著 prev 走訪整個佇列，並利用 curMax 紀錄先前遇過的最大字串，若當前拜訪的節點字串小於等於curMax 則刪除該節點。

    while (tmp != head) {
        element_t *t = list_entry(tmp, element_t, list);

        if (strcmp(curMax, t->value) >= 0) {
            struct list_head *del = tmp;
            tmp = tmp->prev;
            list_del(del);
            q_release_element(t);
        } else {
            curMax = t->value;
            tmp = tmp->prev;
        }
    }

q_merge

:monkey: commit dc78edf

Implement q_merge

[What?] 實作將多個佇列合併並排序之函式 [Why?] 依作業需求實作此功能 [How?] 此函式中傳入的 head 指向此 chain 的第一個節點（queue_contex_t）。 head->next為 first_q，用來整合其他 queue 中的節點。 只需造訪整條 chain 上的節點，利用list_splice_init 將所有佇列串接到 first_q ，最後再用 q_sort 將整個佇列排序即可。

參考 25077667 畫的圖，可知每個queue_contex_t 裝有一個 queue 的 list_head ，這些queue_contex_t 串起來就形成一個 chain 。

在此函式中傳入的 head 指向此 chain 的第一個節點（queue_contex_t） head->next為 first_q，用來整合其他 queue 中的節點 只需造訪整條 chain 上的節點，利用list_splice_init 將所有佇列串接到 first_q ，最後再用 q_sort 將整個佇列排序即可。

    int len = 0;
+   queue_contex_t *first_q = list_entry(head->next, queue_contex_t, chain);
    struct list_head *tmp;

    list_for_each (tmp, head) {
        if (tmp == head->next) {
            continue;
        }

+       queue_contex_t *another_q = list_entry(tmp, queue_contex_t, chain);
        if (list_empty(another_q->q))
            continue;
        len += another_q->size;
+       list_splice_init(another_q->q, first_q->q);
    }
+   q_sort(first_q->q, descend);

目前 95 分，但奇怪的是我在本地端用 make test 無法通過測試項目 06，上傳到 git hub 卻通過了 ？ 原來RAND會產生隨機字串，程式在跑某些測資時會發生 Segmentation fault occurred. You dereferenced a NULL or invalid pointermake 的狀況 目前發現問題出在 q_delete_dup ！ 已修正 :cactus: :cactus: :cactus: 詳見 q_delete_dup <approach 1.1> commit 8f13b09

---

Linux 核心原始程式碼的 lib/list_sort.c

研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差，也該嘗試改進針對鏈結串列排序實作的效能

• 詳閱改進 lib/list_sort.c含解說錄影

---

解釋 Linux 核心的 lib/list_sort.

likely, unlikely

在list_sort.c 中，經常使用

if (likely(bits)) 

之敘述，於是我參考 likely and unlikely macro

了解在 /include/linux/compiler.h 中存在巨集likely unlikely

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

:cactus:__built_expect()是 gcc 的內建 function，用來將 branch 的相關資訊提供給 compiler，告訴 compiler 設計者期望的比較結果，以便對程式碼改變分支順序來進行優化。 :cactus:!!(x)的用意是為了確保出來的值不是0就是1

• 因為x可以是任意數

  根據c99 standard :

  ​​​​if ( expression ) statement
  

  The controlling expression of an if statement shall have scalar type.

:cactus:使用likely 表示這段敘述(x)為 true 的機率比較大(比較常發生)，告訴 compiler 將 x==ture 的對應執行程式碼接在判斷後面

:cactus: 使用unlikely 表示這段敘述(x)為 true 的機率比較小(不常發生)，告訴 compiler 將 x==false 的對應執行程式碼接在判斷後面

cmp

另一個引起我注意的是 cmp 函式

if (cmp(priv, a, b) <= 0)

參考 The Linux Kernel API

void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)

• Parameters

void *priv private data, opaque to list_sort(), passed to cmp struct list_head *head the list to sort list_cmp_func_t cmp the elements comparison function

• Description

The comparison function cmp must

• return > 0 if a should sort after b ("a > b" if you want an ascending sort), and
• return <= 0 if a should sort before b or their original order should be preserved.
• It is always called with the element that came first in the input in a, and list_sort is a stable sort, so it is not necessary to distinguish the a < b and a == b cases.

This is compatible with two styles of cmp function:

• The traditional style which returns <0 / =0 / >0, or
• Returning a boolean 0/1.
• The latter offers a chance to save a few cycles in the comparison (which is used by e.g. plug_ctx_cmp() in block/blk-mq.c).

由上敘述可知，當 cmp 回傳大於0的值表 a>b，a 應排在 b 的後面，因此這段存在 merge 中的程式可這樣解讀 :

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

:cactus: 若 a<=b ，則 a 先加入 tail。若 a 為空，則將整個 b 佇列接到 tail 後方 :cactus: 若 a>b ，則 b 先加入 tail。若 b 為空，則將整個 a 佇列接到 tail 後方

將 Linux 核心的 lib/list_sort 引入 lab0-c

:monkey: commit ee5503b

Integrate the Linux kernel's lib/list_sort into lab0-c

[What?] 將 Linux 核心的 lib/list_sort 引入 lab0-c [Why?] 為了比較自己寫的 q_sort 和 Linux kernel 的 list_sort 之效能 [How?] 以下依修改檔案逐項說明

(1) 在 queue.c 中新增 list_sort 中三個函式 merge merge_final list_sort ，由於我先前已將某函式命名為 merge ，在此以 merge_list_sort 替代原 merge 函式。

static struct list_head *merge_list_sort(struct list_head *a, struct list_head *b)
static void merge_final(struct list_head *head,
			 struct list_head *a, struct list_head *b)
void list_sort(struct list_head *head)

函式內進行些微調整 ：

• 去除參數priv
• 以 strcmp 取代 cmp
• 參考 Kuanch 去除 islikely unlikely

(2) 參考 kart81604 修改 qtest.c

• 在函式 console_init 加入新命令 ADD_COMMAND(list_sort, "Sort queue in ascending order by list_sort", "");

ADD_COMMAND(list_sort, "Sort queue in ascending order by list_sort", "");

• 新增 do_list_sort 函式

bool do_list_sort(int argc, char *argv[])

• 宣告 list_sort 函式

void list_sort(struct list_head *head);

閱讀 George Spelvin 在 commit b5c56e0 提及的三篇論文

Bottom-up Mergesort: A Detailed Analysis

Wolfgang Panny, Helmut Prodinger Algorithmica 14(4):340–354, October 1995

---

The cost distribution of queue-mergesort, optimal mergesorts, andpower-of-two rules

Wei-Mei Chen, Hsien-Kuei Hwang, Gen-Huey Chen Journal of Algorithms 30(2); Pages 423–448, February 1999

---

Queue-Mergesort

Mordecai J. Golin, Robert Sedgewick Information Processing Letters, 48(5):253–259, 10 December 1993

---

這篇作者提出了 queue-mergesort 的方法，並將其方法類比為 Huffman encoding 來證明其方法的 merge tree 的 external path length 為最小，推得其權重為最小，因此該 merge tree 為最佳，queue-mergesort 為最佳 mergesort 之一。

• 若一個 mergesort 為最佳，表其在 worst case 的比較次數為最少 <–-> 其 merge tree 的 leaves 只分佈在樹的最底下兩層
• top-down 必最佳，bottom-up 經些微調整後也為最佳

虛擬碼

queue-mergesort(Q)
{
    while(Q.size!=1)do
        Q.put(Merge(Q.get, Q.get))
}

• 每次取最左方兩個佇列合併排序，並將排序完的佇列放置最右方，直到只剩一個佇列排序即完成。

示意圖

比較自己實作的 merge sort 和 Linux 核心程式碼之間效能落差

使用 perf 工具檢測效能 一開始perf_event_paranoid權限被設為 4

command 是「命令」，而非「指令」(instruction)

可使用以下命令修改權限(-1 為權限全開)

$ sudo sysctl kernel.perf_event_paranoid=-1

<方法零> 最粗糙的實驗方式 (實驗樣本不同)

分別對 sort / list_sort 執行相同命令，看跑完結果如何

$ sudo perf stat ./qtest
cmd> new
cmd> ih RAND 999999
cmd> sort / list_sort
cmd> quit

sort

 Performance counter stats for './qtest':

          1,173.50 msec task-clock                       #    0.028 CPUs utilized             
                37      context-switches                 #   31.530 /sec                      
                 6      cpu-migrations                   #    5.113 /sec                      
            35,235      page-faults                      #   30.026 K/sec                     
     6,588,902,076      cpu_core/cycles/                 #    5.615 GHz                         (99.66%)
     5,033,629,278      cpu_atom/cycles/                 #    4.289 GHz                         (0.33%)
     5,084,456,532      cpu_core/instructions/           #    0.77  insn per cycle              (99.66%)
       563,426,814      cpu_atom/instructions/           #    0.09  insn per cycle              (0.34%)
       725,644,366      cpu_core/branches/               #  618.359 M/sec                       (99.66%)
        91,778,539      cpu_atom/branches/               #   78.209 M/sec                       (0.34%)
        19,228,387      cpu_core/branch-misses/          #    2.65% of all branches             (99.66%)
            62,259      cpu_atom/branch-misses/          #    0.01% of all branches             (0.34%)
             TopdownL1 (cpu_core)                 #     66.4 %  tma_backend_bound      
                                                  #     11.0 %  tma_bad_speculation    
                                                  #      8.9 %  tma_frontend_bound     
                                                  #     13.7 %  tma_retiring             (99.66%)
             TopdownL1 (cpu_atom)                 #     97.5 %  tma_bad_speculation      (0.34%)
                                                  #      0.2 %  tma_frontend_bound       (0.34%)
                                                  #    106.7 %  tma_backend_bound      
                                                  #    106.7 %  tma_backend_bound_aux    (0.34%)
                                                  #      0.0 %  tma_retiring             (0.01%)

      42.189814609 seconds time elapsed

       1.005834000 seconds user
       0.168980000 seconds sys

list_sort

 Performance counter stats for './qtest':

          1,108.08 msec task-clock                       #    0.022 CPUs utilized             
                43      context-switches                 #   38.806 /sec                      
                 6      cpu-migrations                   #    5.415 /sec                      
            35,233      page-faults                      #   31.796 K/sec                     
     6,297,501,839      cpu_core/cycles/                 #    5.683 GHz                         (99.17%)
       808,320,907      cpu_atom/cycles/                 #    0.729 GHz                         (0.37%)
     4,719,015,350      cpu_core/instructions/           #    0.75  insn per cycle              (99.17%)
     2,629,617,057      cpu_atom/instructions/           #    0.42  insn per cycle              (0.73%)
       674,906,876      cpu_core/branches/               #  609.076 M/sec                       (99.17%)
       384,454,428      cpu_atom/branches/               #  346.954 M/sec                       (0.83%)
        19,209,980      cpu_core/branch-misses/          #    2.85% of all branches             (99.17%)
         2,627,089      cpu_atom/branch-misses/          #    0.39% of all branches             (0.83%)
             TopdownL1 (cpu_core)                 #     64.6 %  tma_backend_bound      
                                                  #      8.6 %  tma_bad_speculation    
                                                  #     13.1 %  tma_frontend_bound     
                                                  #     13.8 %  tma_retiring             (99.17%)
             TopdownL1 (cpu_atom)                 #     67.9 %  tma_bad_speculation      (0.83%)
                                                  #     10.8 %  tma_frontend_bound       (0.83%)
                                                  #     24.3 %  tma_backend_bound      
                                                  #     24.3 %  tma_backend_bound_aux    (0.83%)
                                                  #      0.0 %  tma_retiring             (0.47%)

      49.449310632 seconds time elapsed

       0.939995000 seconds user
       0.169441000 seconds sys

整理成表格，可發現我寫的 q_sort 表現與 list_sort 相差不大，但這是不合理的實驗。

	my sort	list sort
task clock	1,173.50 msec	1,108.08 msec
context switches	37	43
page faults	35,235	35,233
branches misses (core)	19,228,387	19,209,980
branches misses (atom)	62,259	2,627,089

<方法一> 使用同樣本 (仍不公平，因為不同演算法擅長的樣本不同)

參考 kart81604 將先隨機產生資料，並寫入 data.txt 中，如此兩次實驗即可共用相同輸入。 在 qtest 中新增 write read 兩個指令，分別代表寫入 data.txt 和從中讀取資料。

:monkey: commit 2a8d392

Add the "write" and "read" commands to qtest

[what?] 在 qtest.c 中加入 do_write do_read 兩個函式，分別代表將當前佇列節點資料寫入 data.txt 和從 data.txt 中讀取資料放入佇列 [why?] 由於實驗需以相同基準點衡量性能，故將隨機產生的資料寫入 data.txt，以利不同實驗對象讀取相同輸入 [how?] 在 qtest.c 中新增 do_write 函式，逐一將當前佇列節點資料寫進 data.txt。 新增 do_read 函式，從 data.txt 中讀取指定數量的字串，並插入當前佇列( buffer 大小設為 10)。

產生資料並寫檔

$./qtest
cmd> new
cmd> ih RAND 999999
cmd> write
cmd> quit

讀檔進行效能測試

$sudo perf stat ./qtest
cmd> new
cmd> read 999999
cmd> sort / list_sort
cmd> quit

q_sort

Performance counter stats for './qtest':

          1,010.43 msec task-clock                       #    0.027 CPUs utilized             
                37      context-switches                 #   36.618 /sec                      
                 8      cpu-migrations                   #    7.917 /sec                      
            35,236      page-faults                      #   34.872 K/sec                     
     5,322,818,753      cpu_core/cycles/                 #    5.268 GHz                         (99.65%)
       689,256,019      cpu_atom/cycles/                 #    0.682 GHz                         (0.32%)
     3,193,111,361      cpu_core/instructions/           #    0.60  insn per cycle              (99.65%)
     1,354,510,793      cpu_atom/instructions/           #    0.25  insn per cycle              (0.34%)
       651,937,624      cpu_core/branches/               #  645.209 M/sec                       (99.65%)
       269,959,937      cpu_atom/branches/               #  267.174 M/sec                       (0.35%)
        18,212,741      cpu_core/branch-misses/          #    2.79% of all branches             (99.65%)
         2,721,285      cpu_atom/branch-misses/          #    0.42% of all branches             (0.35%)
             TopdownL1 (cpu_core)                 #     70.7 %  tma_backend_bound      
                                                  #     13.4 %  tma_bad_speculation    
                                                  #      6.1 %  tma_frontend_bound     
                                                  #      9.8 %  tma_retiring             (99.65%)
             TopdownL1 (cpu_atom)                 #     90.3 %  tma_bad_speculation      (0.35%)
                                                  #      6.4 %  tma_frontend_bound       (0.35%)
                                                  #     10.6 %  tma_backend_bound      
                                                  #     10.6 %  tma_backend_bound_aux    (0.35%)
                                                  #      0.0 %  tma_retiring             (0.03%)

      37.838074239 seconds time elapsed

       0.995614000 seconds user
       0.016123000 seconds sys

list_sort

Performance counter stats for './qtest':

          1,040.56 msec task-clock                       #    0.035 CPUs utilized             
                38      context-switches                 #   36.519 /sec                      
                11      cpu-migrations                   #   10.571 /sec                      
            35,235      page-faults                      #   33.861 K/sec                     
     5,619,021,193      cpu_core/cycles/                 #    5.400 GHz                         (99.78%)
       709,118,105      cpu_atom/cycles/                 #    0.681 GHz                         (0.20%)
     2,848,500,928      cpu_core/instructions/           #    0.51  insn per cycle              (99.78%)
       130,223,207      cpu_atom/instructions/           #    0.02  insn per cycle              (0.22%)
       602,747,086      cpu_core/branches/               #  579.251 M/sec                       (99.78%)
        28,606,170      cpu_atom/branches/               #   27.491 M/sec                       (0.22%)
        18,072,038      cpu_core/branch-misses/          #    3.00% of all branches             (99.78%)
         1,106,266      cpu_atom/branch-misses/          #    0.18% of all branches             (0.22%)
             TopdownL1 (cpu_core)                 #     73.1 %  tma_backend_bound      
                                                  #      9.8 %  tma_bad_speculation    
                                                  #      8.5 %  tma_frontend_bound     
                                                  #      8.6 %  tma_retiring             (99.78%)
             TopdownL1 (cpu_atom)                 #     96.1 %  tma_bad_speculation      (0.22%)
                                                  #     10.0 %  tma_frontend_bound       (0.22%)
                                                  #     79.5 %  tma_backend_bound      
                                                  #     79.5 %  tma_backend_bound_aux    (0.22%)
                                                  #      0.0 %  tma_retiring             (0.02%)

      29.854585006 seconds time elapsed

       0.994007000 seconds user
       0.047903000 seconds sys

表格

	my sort	list sort
task clock	1,010.43 msec	1,040.56 msec
context switches	37	38
page faults	35,236	35,235
branches misses (core)	18,212,741	18,072,038
branches misses (atom)	2,721,285	1,106,266

<方法二> 參考 CPython 的 listsort 的說明文件 盡量涵蓋到不同樣本

random data

見方法一

descending data

$./qtest
cmd> new
cmd> ih RAND 999999
cmd> sort
cmd> reverse
cmd> write
cmd> quit

	my sort	list sort
task clock	394.22 msec	232.44 msec
context switches	30	32
page faults	35,235	35,236
branches misses (core)	2,759,462	1,794,584
branches misses (atom)	715,985	<not counted>

ascending data

$./qtest
cmd> new
cmd> ih RAND 999999
cmd> sort
cmd> write
cmd> quit

	my sort	list sort
task clock	370.47 msec	268.25 msec
context switches	35	37
page faults	35,236	35,239
branches misses (core)	2,931,585	1,621,214
branches misses (atom)	2,768,175	1,246,388

ascending, then 99999 random at the end

$./qtest
cmd> new
cmd> ih RAND 999999
cmd> sort
cmd> it RAND 99999
cmd> write
cmd> quit

	my sort	list sort
task clock	368.02 msec	421.53 msec
context switches	31	38
page faults	38,752	38,753
branches misses (core)	5,185,188	3,837,989
branches misses (atom)	47,711	62,375

ascending, then reverseK 7

$./qtest
cmd> new
cmd> ih RAND 100000
cmd> sort
cmd> reverseK 7
cmd> write
cmd> quit

	my sort	list sort
task clock	65.35 msec	64.16 msec
context switches	32	34
page faults	3596	3596
branches misses (core)	436,034	323,387
branches misses (atom)	185,322	227,083

many duplicates

$./qtest
cmd> new
cmd> ih RAND 10000
cmd> ih b 10000
cmd> ih RAND 10000
cmd> ih d 10000
cmd> ih RAND 10000
cmd> ih a 10000
cmd> ih RAND 10000
cmd> ih c 10000
cmd> ih RAND 10000
cmd> ih e 10000
cmd> write
cmd> quit

	my sort	list sort
task clock	83.52 msec	64.73 msec
context switches	30	33
page faults	3,595	38,753
branches misses (core)	880,806	937,747
branches misses (atom)	113,522	137,047

all equal

$./qtest
cmd> new
cmd> ih a 100000
cmd> write
cmd> quit

	my sort	list sort
task clock	49.54 msec	60.67 msec
context switches	28	36
page faults	3,595	3596
branches misses (core)	166,327	57,640
branches misses (atom)	<not counted>	62,937

翻閱統計學教科書，探討要什麼量體，才能代表樣本特徵？

研讀 Probability & Statistics for Engineers & Scientists, 9/e (GE-Paperback)

中央極限定理

<方法三> 重新撰寫腳本進行實驗

---

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

研讀論文〈Dude, is my code constant time?〉，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student's t-distribution 及程式實作的原理。

• 注意：現有實作存在若干致命缺陷，請討論並提出解決方案
• 在 oreparaz/dudect 的程式碼具備 percentile 的處理，但在 lab0-c 則無。

---

step1 測量執行時間

• 以兩種不同類型(fix vs random)資料作為輸入，統計其執行時間之分佈是否相同
• 使用 CPU cycle 數計算時間(cycle counter)
• 每次測量會隨機選一種類型的資料，以最小化環境變因

step2 後製處理

• 將極端值裁除
• 高階預處理 eg. centered product

step3 進行統計測試

• 嘗試推翻虛無假說 the two timing distributions are equql.
• t 測試 eg. Welch's test 比較兩者樣本分佈差異
  $$t=\frac{\overline{X_0}-\overline{X_1}}{\sqrt{\frac{s_1^2}{N_1}+\frac{s_2^2}{N_2}}}$$
• 無參數測試 eg. Kolmogorov-Smirnov

lab0-c/dudect 中的 fixture.c 和 constant.c

函式 test_const

測試常數時間的主要函式。會進行 10 次測試，每次測試會呼叫 ENOUGH_MEASURE / (N_MEASURES - DROP_SIZE * 2) + 1 次 doit 並將回傳值指派給變數 result。

• 其中 ENOUGH_MEASURE = 10000，N_MEASURES = 150，DROP_SIZE = 20。
• 10次測試中若 result 為真，則跳出迴圈並回傳 True。

函式 doit 與 dudect_main 之比較

doit (lab0-c)	dudect_main (dudect.h)
輸入僅有 mode，其他參數以N_MEASURES初始化	以結構體 dudect_ctx_t 做為輸入
執行 prepare_inputs ，初始化 input_data	執行 prepare_inputs，初始化 input_data
回傳值 ret 由 measure 取得	執行 measure，測量 exec_times
執行 differentiate 和 update_statistics	回傳值 ret 被指派為 DUDECT_NO_LEAKAGE_EVIDENCE_YET
ret 和 report 的回傳值取 & 後再回傳	若為第一次執行 dudect_main，則執行 prepare_percentiles。否則執行update_statistics 並更新 ret 為 report 之回傳值

結構體比較

lab0-c

typedef struct {
    double mean[2];//
    double m2[2];  //
    double n[2];   //
} t_context_t;    

dudect.h

typedef struct {
    double mean[2];//
    double m2[2];  //
    double n[2];   //
} 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;

函式 measure 之比較

lab0-c	dudect.h
利用 mode 判別當前是否為 insert_head insert_tail remove_head remove_tail	單一模式

函式 differentiate

利用measure 取得的紀錄，計算執行時間

函式 update_statistics 之比較

lab0-c	dudect.h
若執行時間非負，直接執行 t 測試	若執行時間非負，直接執行 t 測試
無	對利用 percentiles 刪減極端值後的執行時間進行 t 測試
無	當測量值超過10000次則進行二次測試

函式 report 之比較

lab0-c	dudect.h
無輸入	ctx 為輸入

函式 prepare_percentiles

產生 percentiles 用以篩除極端值

函式對應關係

lab0-c	dudect.h
doit	dudect_main
prepare_inputs	prepare_inputs
measure	measure
無	prepare_percentiles
update_statistics	update_statistics
report	report

修改 lab0-c 中的 dudect 程式碼

新增 prepare_percentiles 相關函式以篩除極端值

對函式輸入參數格式進行些微修改，由於原程式碼使用結構體 dudect_ctx_t 存放 exec_times 等資訊，而 lab0-c 中沒有，因此需將其作為參數輸入。

static int cmp(const int64_t *a, const int64_t *b) 
static int64_t percentile(int64_t *a_sorted, double which, size_t size)
static void prepare_percentiles(int64_t *exec_times,int64_t *percentiles)  

+#define DUDECT_NUMBER_PERCENTILES 100
static bool doit(int mode)
{
+    int64_t *percentiles = calloc(DUDECT_NUMBER_PERCENTILES, sizeof(int64_t));
+    prepare_percentiles(exec_times, percentiles);

:monkey: commit e9eab10

Add the prepare_percentiles function to filter out extreme values

[What?] 針對檢測程式執行時間的程式碼進行修改，使測試程式近似原 dudect 程式
[Why?] 原測試程式無實作 prepare_percentiles 功能，可能導致極端值影響判斷 [How?] 將相關程式碼加入 fixture.c ，並對函式輸入參數格式進行些微修改。由於原程式碼使用結構體 dudect_ctx_t 存放 exec_times 等資訊，而 lab0-c 中沒有，因此需將其作為參數輸入。

修改完後發現可以通過測試項目 17

---

在 qtest 提供新的命令 shuffle

在 qtest 提供新的命令 shuffle，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作，需要以統計的原理來分析你的實作，探究洗牌的「亂度」

在 queue.c 新增 q_shuffle 函式

根據 Fisher–Yates shuffle 演算法來實作洗牌 [1] 先用 q_size 取得 queue 的大小 len。 [2] 隨機從 0 ~ (len - 1) 中抽出一個數字 random，然後 old 將指向從前面數來第random 個節點，new 會指向最後一個未被抽到的節點，將 old 和 new 指向的節點的值交換，再將 len - 1。 [3] 隨著 len 大小變小，已經被抽到過，並交換值到 queue 後面的會愈來愈多，直到所有的節點都已經被抽到過，shuffle 就結束。

在 qtest.c 新增函式 q_shuffle，並新增 shuffle 命令以便呼叫 q_shuffle。

+ void q_shuffle(struct list_head *head)
+ static bool do_shuffle(int argc, char *argv[])
+ ADD_COMMAND(shuffle, "Using the Fisher-Yates shuffle algorithm to shuffle", "");

:monkey: commit 5816f1b

Add "shuffle" command

[What?] 在 qtest.c 新增函式 q_shuffle，並新增 shuffle 命令以便呼叫 q_shuffle。 [Why?] 依作業要求在 qtest 提供新的命令 shuffle ，以探究洗牌亂度。 [How?] 參考 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌操作。

利用測試程式統計 shuffle 結果

發現我一開始的做法有誤，結果並不平均

原因出在我把 srand(time(NULL)) 寫在 q_shuffle 函式中，導致srand(time(NULL))會被重複呼叫。由於電腦指令跑很快，幾乎同時間的亂數會很多，使得重複相同亂數會很多。

當我把 srand(time(NULL)) 移至主函式後，雖然分佈遍均勻了，卻又發現我寫的程式有死角，只有一半的情況會發生。

後來發現原因出在指派 new 指標時少走一次 next，修改後問題已改善。

:monkey: commit 66d9a67

Revise "shuffle" command

[What?] 修正 q_shuffle 函式使其能正確運作，達到均勻亂數洗牌 [Why?] 原因出在我把 srand(time(NULL)) 寫在 q_shuffle 函式中，導致srand(time(NULL))會被重複呼叫。由於電腦指令跑很快，幾乎同時間的亂數會很多，使得重複相同亂數會很多。 當我把 srand(time(NULL)) 移至主函式後，雖然分佈遍均勻了，卻又發現我寫的程式有死角，只有一半的情況會發生。 後來發現原因出在指派 new 指標時少走一次 next，修改後問題已改善。 [How?] 修正 srand(time(NULL)) 位置，修正 new 指派位置。

---

比較亂數產生器的品質

在 qtest 中執行 option entropy 1 並搭配 ih RAND 10 一類的命令，觀察亂數字串的分布，並運用「資訊與熵互補，資訊就是負熵」的觀念，設計一組新的命令或選項，得以在 qtest 切換不同的 PRNG 的實作 (可選定 Xorshift)，搭配統計分析工具，比較亂數產生器 (如 Xorshift vs. 內建) 的品質

• 參見: 由大數法則理解訊息熵 (entropy) 的數學意義
• 參見: The Linux Pseudorandom Number Generator Revisited

web

確保 qtest 提供的 web 命令得以搭配上述佇列實作使用，目前一旦網頁伺服器啟動後，原本處理命令列操作的 linenoise 套件就無法使用，請提出改善機制

• 提示: 使用 select 系統呼叫

2024q1 Homework3 (Tic-Tac-Toe)

• 將 Linux 核心的 linux/list.h 標頭檔與 hlist 相關的程式碼抽出，成為 hlist.h，並確保後者可與 lab0-c 既有的 list.h 並存，jserv/ttt 專案的 zobrist.[ch] 會用到 hlist.h
• 修改 qtest 程式，使其新增 ttt 命令，其作用是執行與人類對弈的井字遊戲，並使用 Monte Carlo tree search (MCTS) 演算法，確保使用定點數來取代原本 jserv/ttt 的浮點數運算。
• 擴充上述 ttt 命令，在 qtest 引入新的 option (參照 cmd> 命令提示的 help 說明文字)，允許使用者切換「人 vs.電腦」或「電腦 vs. 電腦」的對弈，注意後者應該採取 MCTS 以外的演算法 (也可納入你發展的演算法)。對弈的過程中，要在螢幕顯示當下的時間 (含秒數)，並持續更新。
• 針對 ttt 命令的「電腦 vs. 電腦」的對弈模式，參照〈並行程式設計：排程器原理〉，引入若干 coroutine (注意：不得使用 POSIX Thread，採取教材提到的實作方式)，分別對應到 AI₁, AI₂ (具備玩井字遊戲的人工智慧程式，採取不同的演算法) 和鍵盤事件處理，意味著使用者可連續觀看多場「電腦 vs. 電腦」的對弈，當按下 Ctrl-P 時暫停或回復棋盤畫面更新 (但運算仍持續)、當按下 Ctrl-Q 時離開「電腦 vs. 電腦」的對弈，注意不該使用 (n)curses 函式庫。當離開「電腦 vs. 電腦」的對弈時，ttt 應顯示多場對弈的過程，亦即類似 Moves: B2 -> C2 -> C3 -> D3 -> D4 的輸出，儘量重用現有的結構體和程式碼。 關於鍵盤事件和終端機畫面的處理機制，可參見 mazu-editor 原始程式碼和〈Build Your Own Text Editor〉。
• 亂數產生器對於 MCTS 相當重要，可參照 Improving performance and efficiency of PRNG，嘗試引入其他快速的 PRNG 實作並比較 MCTS 實作獲得的效益。
• 在「電腦 vs. 電腦」的對弈模式，比照前述 load average 的計算方式，規範針對下棋 AI 的 load 機制，並運用定點數來統計不同 AI 實作機制對系統負載的使用率，整合到 qtest 輸出，開發過程中應有對應的數學分析和羅列實作考量因素。
• 考慮到畫面更新不該混雜其他 printf 的訊息，可運用 GDB 進行遠端除錯。

將 jserv/ttt 專案的程式碼部分整合進 lab0-c

引入 hash list 標頭檔

:monkey: commit 979d357

Add header file of hash list

[What?] 新增 hlist.h 標頭檔 [Why?] 依作業要求整合 ttt 專案部份程式碼到 lab0-c [How?] 將 Linux 核心的 linux/list.h 標頭檔與 hlist 相關的程式碼抽出，成為 hlist.h，並確保後者可與 lab0-c 既有的 list.h 並存，jserv/ttt 專案的 zobrist.[ch] 會用到 hlist.h

新增 ttt 命令執行與人類對弈的井字遊戲 (使用 Monte Carlo tree search)

:monkey: commit 2c249ec

Add Noughts and Crosses game command

[What?] 修改 qtest 程式，使其新增 ttt 命令 [Why?] 為了實現 AI 與人類對弈的井字遊戲 [How?] 將 jserv/ttt 專案的程式碼部分整合進 lab0-c，，使用 Monte Carlo tree search (MCTS) 演算法作為 AI 玩家，演算法仍使用浮點數運算。

Monte Carlo tree search 原理

UCT value

$$UCT=\frac{w_i}{n_i}+c\sqrt{\frac{\ln t}{n_i}}$$

• $w_i$ : the number of simulated wins from that node after the i-th move.
• $n_i$ : the number of simulations that have occured for that node after the i-th move.
• $c$ : the exploration parameter
• $t$ : the total number of simulations that have occured after i moves.

其中

$\frac{w_i}{n_i}$ 代表利用，

$c\sqrt{\frac{\ln t}{n_i}}$代表探索，其作用在於探詢可能的路徑，避免有更好的路徑沒被開發(可由式子中發現使用次數越少的節點

$\sqrt{\frac{\ln t}{n_i}}$ 會越大，且當模擬次數越多時探索力度會稍微加大，但其加大幅度會遞減)。調整

$c$ 值可改變探索與利用的比例。

four basic phases to MCTS:

• selection : 選擇 USB 最高的節點形成一條路徑
• expansion : 生成 selection 所選路徑的下一步所有狀態，並隨機挑選一種狀態
• simulation : 從上步所選狀態開始模擬試玩，直到分出勝負或平手
• back-propagation : 依模擬結果打分數，並反向傳播給整條路徑上的節點，以更新 UCB 值

設計以定點數運算取代浮點數運算的蒙地卡羅搜尋樹演算法

Robert Love 在 Linux Kernel Development 一書論及浮點運算:

No (Easy) Use of Floating Point When using floating-point instructions kernel normally catches a trap and then initiates the transition from integer to floating point mode. Unlike user-space, the kernel does not have the luxury of seamless support for floating point because it cannot easily trap itself. Using a floating point inside the kernel requires manually saving and restoring the floating point registers. Except in the rare cases, no floating-point operations are in the kernel.

以下實驗使用 Ubuntu 24.04 LTS 進行開發

$  uname -r
6.8.0-31-generic

$ gcc --version
gcc (Ubuntu 13.2.0-23ubuntu4) 13.2.0

$ lscpu
架構：                    x86_64
  CPU 作業模式：          32-bit, 64-bit
  Address sizes:          46 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   22
  On-line CPU(s) list:    0-21
供應商識別號：            GenuineIntel
  Model name:             Intel(R) Core(TM) Ultra 7 155H
    CPU 家族：            6
    型號：                170
    每核心執行緒數：      2
    每通訊端核心數：      16
    Socket(s):            1
    製程：                4
    CPU(s) scaling MHz:   25%
    CPU max MHz:          4800.0000
    CPU min MHz:          400.0000
    BogoMIPS:             5990.40

原 MCTS 程式碼在計算分數時會使用到浮點數運算，改以定點數表示之

+typedef long fixed_point;
+#define shift 10 //frac = 2^10
+#define EXPLORATION_FACTOR fixed_sqrt(2)
struct node {
-   double score;
+   fixed_point score;
};    

• 定點數縮放因子

  • $frac=2^{10}$
    • 1
      $\leftrightarrow$
      $2^{10}$
    • 0.5
      $\leftrightarrow$
      $2^9$
    • 0
      $\leftrightarrow$ 0
    • -1
      $\leftrightarrow$
      $-2^{10}$
    • DBL_MAX
      $\leftrightarrow$ LONG_MAX

• 加法減法 : 可直接進行

• 乘法 : 結果要多除

  $frac$

• 除法 : 結果要多乘

  $frac$

• 自然對數

  $ln$

  根據泰勒展開式可得
  

  $$lnx=(\frac{x-1}{x})+\frac{1}{2}(\frac{x-1}{x}{)}^2+\frac{1}{3}(\frac{x-1}{x}{)}^3+...$$
  $$=\sum _{n=1}^{\mathrm{\infty }}\frac{1}{n}(\frac{x-1}{x}{)}^n$$

  使用 frac = 1024 實作 (利於使用 bitwise)

  • 其在 1<x<100 之表現 :

    

  • 如圖可知 UCT value 的分佈多位於 0~3.5 之間，但 ln的輸入為 t (the total number of simulations that have occured after i moves)必為整數，因此不須特別考量 0<t<1 之情況。

    

• 平方根

  • 使用十分逼近法求平方根
    
  • 可發現當 x<4 會求出 0
    
  • 發現問題出在逼近值的上限設成
    $\frac{x}{2}$，調整後可正常擬合
    
  • 0<x<1 的表現也正常
    
    

當我把定點數 ln 和平方根運算寫入 ttt 遊戲中才發現，如果要追求極高的精度只會導致演算法下棋速率緩慢，該如何權衡精度與運算速率是一大問題。

UCT value 分佈比較

依序輸入命令 c3 c2 c1

• 可發現使用定點數的 UCT value 主要集中在特定數值上，相較浮點數很不均勻
  
  
  

參考資料

• C99 standard
• Linux 核心專題: 改進 lib/list_sort.c
• Tic Tac Toe at the Monte Carlo