Try   HackMD

2024q1 Homework1 (lab0)

contributed by < yeh-sudo >

開發環境

$ uname -a
Linux andyyeh-ubuntu 6.5.0-21-generic #21~22.04.1-Ubuntu SMP PREEMPT_DYNAMIC Fri Feb  9 13:32:52 UTC 2 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         44 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  16
  On-line CPU(s) list:   0-15
Vendor ID:               AuthenticAMD
  Model name:            AMD Ryzen 7 4800HS with Radeon Graphics
    CPU family:          23
    Model:               96
    Thread(s) per core:  2
    Core(s) per socket:  8
    Socket(s):           1
    Stepping:            1
    Frequency boost:     enabled
    CPU max MHz:         2900.0000
    CPU min MHz:         1400.0000
    BogoMIPS:            5788.79
Virtualization features: 
  Virtualization:        AMD-V
Caches (sum of all):     
  L1d:                   256 KiB (8 instances)
  L1i:                   256 KiB (8 instances)
  L2:                    4 MiB (8 instances)
  L3:                    8 MiB (2 instances)

指定的佇列操作

開發順序依照作業要求依次進行。

q_new

commit 544eb0

配置記憶體空間，並使用 list.h 中提供的 INIT_LIST_HEAD 進行初始化。

q_free

commit 544eb0

首先檢查佇列是否為 NULL ，若不為 NULL ，則使用 list_for_entry_safe 這個巨集，避免在走訪的時候出現未定義行為。

q_insert_head, q_insert_tail

這兩者在邏輯上類似，都是新增一個 element_t ，如果是 q_insert_head ，在函式最後呼叫的API就是 list_add ，如果是 q_insert_tail ，則呼叫 list_add_tail 。

commit 544eb0

​​​​在此 commit 中兩者重複的部份太多，會在之後的 commit 中修改。

commit 68caaa

在這個 commit 中補足巨集 strlcpy ，因為我原本的是使用 strcpy 將移除節點裡面的字串複製到 sp 這個變數之中，但在 commit 時顯示出以下警告訊息。閱讀訊息中的內容，將 strcpy 改成建議的方法，確保複製字串是安全的。

Dangerous function detected in /home/andyyeh/linux2024/lab0-c/queue.c
85:    strcpy(sp, remove_element->value);
97:    strcpy(sp, remove_element->value);

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

strlcpy 巨集

#ifndef strlcpy
#define strlcpy(dst,src,sz) snprintf((dst), (sz), "%s", (src))
#endif

q_remove_head, q_remove_tail

這兩者在邏輯上也是相同的，差別在於一開始取得的節點位置， q_remove_insert 是取 head->next ，而 q_remove_tail 是取 head->prev 。

commit 544eb0

此 commit 的實作也是重複的部份太多。

commit 68caaa

在執行 make test 時，在 TESTING trace trace-08-robust 這項測試資料一直觸發 segmentation fault ，經過檢查，發現是在函式一開始沒有檢查佇列是否為空，所以導致 segmentation fault ，補上 list_empty() 這個條件就不會在發生錯誤。
在其他測試，發現只要有觸發 segmentation fault ，最後的得分顯示位置與其他測資不太一樣，造成版面不一致且閱讀困難。

+++ TESTING trace trace-07-string:
# Test of truncated strings
ERROR: Removed value aardvark_bear_dolphin_gerbil_jaguar != expected value     meerkat_panda_squirrel_vulture_wolf
ERROR: Removed value aardvark_bear_dolphin_gerbil_j != expected value meerkat_panda_squirrel_vulture
ERROR: Removed value meerkat_ != expected value aardvark
ERROR: Removed value meerkat_panda_squirrel_vulture_wolf != expected value aardvark_bear_dolphin_gerbil_jaguar
---	trace-07-string 0/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---	trace-08-robust 0/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---	trace-09-robust 6/6

q_size

commit 544eb0

使用 list_for_each 去走訪整個鏈結串列，以此算出這個佇列的大小。

q_delete_mid

commit 544eb0

使用快慢指標的方式，找出佇列中間的節點並將它刪除。

q_delete_dup

commit f379f3

使用 list_for_each_entry_safe ，比較 entry 和 safe 的字串是否相等，如果相等，就將 delete_entry 這個變數設為 true ，在 entry 和 safe 都不相等時，如果 delete_entry 為 true ，代表 entry 是連續相等字串的最後一個。

q_swap

commit bf3125

原本的做法是使用迴圈走訪整個鏈結串列，並將每一個節點的 prev 和 next 都交換，但是運行的結果不如預期，有些節點會沒有連結到。

commit b64103

捨棄原本的做法，使用 list.h 的 list_move 將現在的節點移到下一個節點前面，比較簡潔易懂。

-    for (node = head->next; node != head; node = node->next) {
-        if (node->next == head) {
-            break;
-        }
-        struct list_head *next = node->next;
-        node->next = next->next;
-        if (node->prev == head) {
-            head->next = next;
-        }
-        next->prev = node->prev;
-        node->prev = next;
-        next->next = node;
+    for (node = head->next; node != head && node->next != head;
+         node = node->next) {
+        list_move(node, node->next);
     }

q_reverse

commit 949343

原本的做法是將每個節點的 prev 與 next 互換。

commit b64103

經過測試，原本的做法是錯的，想到反轉整個鏈結串列就是將節點刪除再加到開頭的節點上，所以採用 list_del_init 與 list_add 配合，成功將整個鏈結串列反轉。

-    struct list_head *node;
-    for (node = head; node != head; node = node->prev) {
-        struct list_head *next = node->next;
-        node->next = node->prev;
-        node->prev = next;
+    struct list_head *node, *safe;
+    list_for_each_safe (node, safe, head) {
+        list_del_init(node);
+        list_add(node, head);
     }

q_reverseK

commit 82f7ba

將鏈結串列拆分成很多個長度為 K 的小鏈結串列，並分別將這些較小的鏈結串列反轉，再透過 list_splice_tail_init 將反轉過的鏈結串列加入到另外一個鏈結串列中，當全部的鏈結串列反轉過後，就將這些鏈結串列重新加入到 head 中。

commit 5c6a07

原本是使用 q_new 去初始化反轉鏈結串列和臨時存放反轉過鏈結串列的 head ，但是在進行這項測試的時候，是禁止配置記憶體的，於是改用一般變數的方法宣告以及初始化。

-    struct list_head *tmp_head = q_new();
-    struct list_head *reverse_head = q_new();
-    struct list_head *node;
-    int cnt;
-    for (cnt = 0, node = head->next; node != head;) {
+    LIST_HEAD(tmp_head);
+    LIST_HEAD(reverse_head);
+    struct list_head *node, *safe;
+    int cnt = 1;
+    list_for_each_safe (node, safe, head) {
         if (cnt == k) {
-            node = node->next;
-            cnt = 0;
-            list_cut_position(reverse_head, head, node->prev);
-            q_reverse(reverse_head);
-            list_splice_tail(tmp_head, reverse_head);
-            continue;
+            list_cut_position(&reverse_head, head, node);
+            q_reverse(&reverse_head);
+            list_splice_tail_init(&reverse_head, &tmp_head);
+            cnt = 1;
+        } else {
+            cnt++;
         }
-        node = node->next;
-        cnt++;
     }
-    list_splice(tmp_head, head);
+    list_splice(&tmp_head, head);
+}

q_sort

commit b64103

首先，實作 mergeTwoLists 這個函式，參考你所不知道的 C 語言: linked list 和非連續記憶體中的 mergeTwoLists ，並額外加上 descend 這個參數，決定要升序排序或是降序排序。
接著實作比較字串大小的 cmp 函式。因為才剛學完 bitwise 的章節與操作，我想試試不需要判斷 cmp 的大小與 descend 參數就可以決定要用 L1 的節點還是 L2 的節點，參考解讀計算機編碼中的常數時間實作，將 strcmp 的結果右移 31 位，如果比較出來的結果是 s1 > s2 ，右移 31 位之後會得到 0x00000000 ，再加上一之後就會變成 0x00000001 ，但如果 s1 < s2 ，右移 31 位會得到 0xffffffff ，加上一之後會變成 0x00000000 ，再加上以下的真值表，就可以得出 cmp(s1, s2) + 1 與 descend 的關係是進行 xor 之後再進行 not 操作，即可決定要使用 L1 或是 L2 。

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

cmp(s1, s2) + 1 descend need
0 0 1 (L1)
0 1 0 (L2)
1 0 0 (L2)
1 1 1 (L1)

從此表格可以得出與判斷使用 L1 或是 L2 的關係式如以下 Version 1 中的第 11 行。

  • Version 1
int cmp(const chat *s1, const chat *s2)
{
    return strcmp(s1, s2) >> 31;
}

void mergeTwoLists(struct list_head *L1, struct list_head *L2, bool descend)
{
    if (!L1 || !L2)
        return;
    struct list_head head;
    INIT_LIST_HEAD(&head);
    while (!list_empty(L1) && !list_empty(L2)) {
        element_t *e1 = list_first_entry(L1, element_t, list);
        element_t *e2 = list_first_entry(L2, element_t, list);
        struct list_head *node =
            !((cmp(e1->value, e2->value) + 1) ^ descend) ? L1->next : L2->next;
        list_move_tail(node, &head);
    }
    list_splice_tail_init(list_empty(L1) ? L2 : L1, &head);
    list_splice(&head, L1);
}

但是在進行 git commit -a 時，顯示出以下的錯誤。

queue.c:223:27: portability: Shifting signed 32-bit value by 31 bits is implementation-defined behaviour [shiftTooManyBitsSigned]
    return strcmp(s1, s2) >> 31;

依照 C 語言規格書 6.5.7.5 敘述：

The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

為了修正這個錯誤，只能改成以下的 Version 2 。

  • Version 2
bool cmp(const char *s1, const char *s2)
{
    return strcmp(s1, s2) > 0 ? true : false;
}

void mergeTwoLists(struct list_head *L1, struct list_head *L2, bool descend)
{
    if (!L1 || !L2)
        return;
    struct list_head head;
    INIT_LIST_HEAD(&head);
    while (!list_empty(L1) && !list_empty(L2)) {
        element_t *e1 = list_first_entry(L1, element_t, list);
        element_t *e2 = list_first_entry(L2, element_t, list);
        struct list_head *node =
            !(cmp(e1->value, e2->value) ^ descend) ? L1->next : L2->next;
        list_move_tail(node, &head);
    }
    list_splice_tail_init(list_empty(L1) ? L2 : L1, &head);
    list_splice(&head, L1);
}

實作完 mergeTwoLists 與 cmp 兩個函式之後，接著實作 q_sort ，參考你所不知道的 C 語言: linked list 和非連續記憶體中的遞迴版本，以快慢指標的方式找到中間節點並分割成兩個鏈結串列，在遞迴分割後，兩兩分個的鏈節串列使用 mergeTwoLists 合併。

struct list_head *slow = head;
struct list_head *fast = head->next;
for (; fast != head && fast->next != head; fast = fast->next->next)
    slow = slow->next;
struct list_head left;
list_cut_position(&left, head, slow);

TODO: 考慮到後續 Timsort 的整合，除了原本亂數產生的節點內容外，要針對不同情境提供排序用的測試資料。

q_ascend, q_descend

commit 5c6a07

兩個函式的作用是差不多的，差別只在於是升序還是降序，所以我用一個函式 remove_nodes() 將這兩個操作合併。
做法是使用一個堆疊存放節點，當堆疊是空的，就將現行的節點 entry 放入堆疊，若不是空的，就將堆疊最上面的元素與現行節點比較，只要判斷式為 true ，就會持續將堆疊最上方的元素取出並釋放，當判斷式為 false 時，就將現行節點放入堆疊，而判斷式的邏輯與 q_sort 類似，就不多贅述，當迴圈結束時，就將堆疊中的元素全部都放回 head 中，並回傳鏈結串列的大小。

int remove_nodes(struct list_head *head, bool descend)
{
    if (!head || list_empty(head))
        return 0;
    if (list_is_singular(head))
        return 1;
    element_t *entry, *safe;
    LIST_HEAD(tmp_head);
    list_for_each_entry_safe (entry, safe, head, list) {
        if (list_empty(&tmp_head)) {
            list_move_tail(&entry->list, &tmp_head);
        } else {
            element_t *e = list_last_entry(&tmp_head, element_t, list);
            while (!list_empty(&tmp_head) &&
                   (cmp(e->value, entry->value) ^ descend)) {
                list_del(&e->list);
                free(e->value);
                free(e);
                e = list_last_entry(&tmp_head, element_t, list);
            }
            list_move_tail(&entry->list, &tmp_head);
        }
    }
    list_splice_tail(&tmp_head, head);
    return q_size(head);
}

q_merge

commit b64103

核心邏輯與 mergeTwoLists 函式相同，做法是以 list_for_each_entry_safe 走訪整個鏈結串列，並且將現行的鏈結串列 entry 與第一個鏈結串列合併，最後回傳第一個鏈結串列的大小。

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

提出 dudect ，分為以下三個步驟：

  1. Measure Execution Time
    • 使用 fix class 和 random class 作為輸入，不斷測量函式的執行時間。
    • 為了將環境對結果的影響降到最低，美一次測量都對應到一個隨機的類別，並且，決定類別與準備輸入資料的工作都在測量前結束。
  2. Apply Post-processing
    • Cropping 。
    • Higher-order preprocessing 。
  3. Apply Statistical Test
    使用統計方法嘗試拒絕虛無假設，「 the two timing distributions are equal 」，若拒絕，則說明程式不是以常數時間運行。
    • 使用 t-test 檢測平均值，也是本次作業使用的方法。
    • 使用 non-parametric test ，但可能收斂較慢且需要更多樣本。

Simulation 原理

oreparaz/dudect 中的 dudect_main 對應到 dudect/fixture.c 中的 doit ，而 lab0-c 的執行順序是如下，而 lab0-c 缺少 percentile 的步驟，也就是去除極端值。

  1. measure
    測量方法都是先插入一個字串，再測量插入令一個字串或是刪除的時間，若兩者之間的佇列大小差值不是 1 ，則算失敗。
  2. differentiate
    取 before_ticks 與 after_ticks 的差值。
  3. update_statistics
    透過 t-push 執行 t-test。
  4. report
    得出函式是否為常數時間。

percentile

percentile 在 dudect 中對應的程式碼如下，目的是為了去除極端值。





















static int64_t percentile(int64_t *a_sorted, double which, size_t size) {
  size_t array_position = (size_t)((double)size * (double)which);
  assert(array_position < size);
  return a_sorted[array_position];
}

/*
 set different thresholds for cropping measurements.
 the exponential tendency is meant to approximately match
 the measurements distribution, but there's not more science
 than that.
*/
static void prepare_percentiles(dudect_ctx_t *ctx) {
  qsort(ctx->exec_times, ctx->config->number_measurements, sizeof(int64_t), (int (*)(const void *, const void *))cmp);
  for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) {
    ctx->percentiles[i] = percentile(
        ctx->exec_times, 1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES)),
        ctx->config->number_measurements);
  }
}

去除極端值可參考 25077667 的實作。

commit f379f3

     bool ret = measure(before_ticks, after_ticks, input_data, mode);
     differentiate(exec_times, before_ticks, after_ticks);
+    prepare_percentiles(exec_times);
     update_statistics(exec_times, classes);
     ret &= report();


 static void update_statistics(const int64_t *exec_times, uint8_t *classes)
 {
-    for (size_t i = 0; i < N_MEASURES; i++) {
+    for (size_t i = 10; i < N_MEASURES; i++) {
         int64_t difference = exec_times[i];
         /* CPU cycle counter overflowed or dropped measurement */
-        if (difference <= 0)
+        if (difference < 0)
             continue;
 
         /* do a t-test on the execution time */
-        t_push(t, difference, classes[i]);
+        t_push(t[0], difference, classes[i]);
+
+        for (size_t crop_index = 0; crop_index < DUDECT_NUMBER_PERCENTILES;
+             crop_index++) {
+            if (difference < percentiles[crop_index]) {
+                t_push(t[crop_index + 1], difference, classes[i]);
+            }
+        }
     }
 }

當你確認上方程式碼修改符合論文精神 (部分內容不精準，需要重新詮釋)，對 sysprog21/lab0-c 提交 pull request。

以 Valgrind 排除記憶體錯誤

以 make valgrind 運行，在 trace-17-complexity 出現以下錯誤。訊息顯示在 fixture.c 中的 test_const 有記憶體洩漏。

# 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
==6944== 48 bytes in 1 blocks are possibly lost in loss record 1 of 5
==6944==    at 0x484DA83: calloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==6944==    by 0x1108C0: test_const (fixture.c:213)
==6944==    by 0x110E70: is_insert_head_const (fixture.c:245)
==6944==    by 0x10C988: queue_insert (qtest.c:190)
==6944==    by 0x10CD40: do_ih (qtest.c:280)
==6944==    by 0x10E011: interpret_cmda (console.c:181)
==6944==    by 0x10E5C6: interpret_cmd (console.c:201)
==6944==    by 0x10E9C7: cmd_select (console.c:610)
==6944==    by 0x10F2B3: run_console (console.c:705)
==6944==    by 0x10D403: main (qtest.c:1258)
==6944== 
==6944== 4,848 bytes in 101 blocks are definitely lost in loss record 2 of 5
==6944==    at 0x484DA83: calloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==6944==    by 0x1108C0: test_const (fixture.c:213)
==6944==    by 0x110E70: is_insert_head_const (fixture.c:245)
==6944==    by 0x10C988: queue_insert (qtest.c:190)
==6944==    by 0x10CD40: do_ih (qtest.c:280)
==6944==    by 0x10E011: interpret_cmda (console.c:181)
==6944==    by 0x10E5C6: interpret_cmd (console.c:201)
==6944==    by 0x10E9C7: cmd_select (console.c:610)
==6944==    by 0x10F2B3: run_console (console.c:705)
==6944==    by 0x10D403: main (qtest.c:1258)
==6944== 
==6944== 4,896 bytes in 102 blocks are definitely lost in loss record 3 of 5
==6944==    at 0x484DA83: calloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==6944==    by 0x1108C0: test_const (fixture.c:213)
==6944==    by 0x110E8E: is_insert_tail_const (fixture.c:245)
==6944==    by 0x10C93F: queue_insert (qtest.c:190)
==6944==    by 0x10CD24: do_it (qtest.c:286)
==6944==    by 0x10E011: interpret_cmda (console.c:181)
==6944==    by 0x10E5C6: interpret_cmd (console.c:201)
==6944==    by 0x10E9C7: cmd_select (console.c:610)
==6944==    by 0x10F2B3: run_console (console.c:705)
==6944==    by 0x10D403: main (qtest.c:1258)
==6944== 
==6944== 4,896 bytes in 102 blocks are definitely lost in loss record 4 of 5
==6944==    at 0x484DA83: calloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==6944==    by 0x1108C0: test_const (fixture.c:213)
==6944==    by 0x110EAC: is_remove_head_const (fixture.c:245)
==6944==    by 0x10C4B2: queue_remove (qtest.c:302)
==6944==    by 0x10C8FC: do_rh (qtest.c:410)
==6944==    by 0x10E011: interpret_cmda (console.c:181)
==6944==    by 0x10E5C6: interpret_cmd (console.c:201)
==6944==    by 0x10E9C7: cmd_select (console.c:610)
==6944==    by 0x10F2B3: run_console (console.c:705)
==6944==    by 0x10D403: main (qtest.c:1258)
==6944== 
==6944== 4,896 bytes in 102 blocks are definitely lost in loss record 5 of 5
==6944==    at 0x484DA83: calloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==6944==    by 0x1108C0: test_const (fixture.c:213)
==6944==    by 0x110ECA: is_remove_tail_const (fixture.c:245)
==6944==    by 0x10C469: queue_remove (qtest.c:302)
==6944==    by 0x10C8E0: do_rt (qtest.c:415)
==6944==    by 0x10E011: interpret_cmda (console.c:181)
==6944==    by 0x10E5C6: interpret_cmd (console.c:201)
==6944==    by 0x10E9C7: cmd_select (console.c:610)
==6944==    by 0x10F2B3: run_console (console.c:705)
==6944==    by 0x10D403: main (qtest.c:1258)
==6944==

從錯誤訊息中，摘錄後續討論用到的部分即可。

了解。

經過檢查，發現在 init_once 函式中重複配置記憶體，導致記憶體洩漏，修改完程式碼後， valgrind 就沒有再顯示有任何的記憶體洩漏或是其他錯誤。

commit 2234ec

@@ -201,7 +201,6 @@ static void init_once(void)
 {
     init_dut();
     for (int i = 0; i < DUDECT_TESTS; i++) {
-        t[i] = calloc(1, sizeof(t_context_t));
         t_init(t[i]);
     }
 }

Valgrind 測試結果

scripts/driver.py -p /tmp/qtest.nfmAYL --valgrind 
---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---	trace-01-ops	5/5
...
# Test performance of insert_tail
---	trace-16-perf	6/6
+++ 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		100/100

Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.nfmAYL --valgrind -t <tid>

整合 Timsort

實作並測試 Timsort 正確性

commit bfad4d

在整合之前，為了之後能將 Timsort 與 q_sort 一起測試，將參數都統一，我修改了 cmp 這個函式，加入 priv 計算比較次數。

-bool cmp(const char *s1, const char *s2)
+bool cmp(void *priv, const char *s1, const char *s2)
 {
+    if (priv)
+        *((int *) priv) += 1;
     return strcmp(s1, s2) > 0 ? true : false;
 }

另外，與測驗不同的是，在這裡的 Timsort 必須要是比較字串，還要有決定升序或是降序的功能，所以也必須要修改 Timsort 中相對應的程式碼。 Timsort 中的所以函式都必須再多增加一個參數 descend 用來決定要升序還是降序，另外，有使用到 cmp 的函式，判斷條件都要改成與 qsort 一樣。

  • 以 merge 函式為例
 static struct list_head *merge(void *priv,
                                list_cmp_func_t cmp,
                                struct list_head *a,
-                               struct list_head *b)
+                               struct list_head *b,
+                               bool descend)
 {
     struct list_head *head;
     struct list_head **tail = &head;
@@ -30,11 +32,15 @@
 
     for (node = NULL; a && b; *node = (*node)->next) {
         /* if equal, take 'a' -- important for sort stability */
-        node = (cmp(priv, a, b) <= 0) ? &a : &b;
+        node = !(cmp(priv, list_entry(a, element_t, list)->value,
+                     list_entry(b, element_t, list)->value) ^
+                 descend)
+                   ? &a
+                   : &b;
         *tail = *node;
         tail = &(*tail)->next;
     }
-    *tail = (struct list_head *)((uintptr_t) a | (uintptr_t) b);
+    *tail = (struct list_head *) ((uintptr_t) a | (uintptr_t) b);
     return head;
 }

接著在 qtest 中新增 timsort 的命令，用來測試 Timsort 的正確性，修改 traces/trace-15-perf.cmd ，將 sort 命令改成 timsort ，另外加入 descend 命令，同時檢測升序與降序的正確性，並且確認時間複雜度在

O(nlogn)，測試後沒有出現錯誤，以 valgrind 檢測，也沒有出現記憶體洩漏。

# Test performance of Timsort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
option fail 0
option malloc 0
new
ih RAND 10000
timsort
reverse
timsort
free
new
ih RAND 50000
timsort
reverse
timsort
free
new
ih RAND 100000
timsort
reverse
timsort
free
option descend 1
new
ih RAND 10000
timsort
reverse
timsort
free
new
ih RAND 50000
timsort
reverse
timsort
free
new
ih RAND 100000
timsort
reverse
timsort
free
  • Valgrind 測試結果

Screenshot from 2024-03-15 15-19-05

問題 1 ：無法修改 queue.h

我在 queue.h 中新增操作 q_timsort ，結果在 commit 時出現以下警告， pre-commit 設定 queue.h 與 list.h 是無法修改的，意謂現階段我沒辦法新增 q_timsort 的操作，要另外想辦法。

Following files need to be cleaned up:
qtest.c
queue.c
queue.h
sort_impl.h
timsort.c
/usr/bin/sha1sum: WARNING: 1 computed checksum did NOT match
[!] You are not allowed to change the header file queue.h or list.h
  • 修改 queue.h
 /**
  * q_sort() - Sort elements of queue in ascending/descending order
+ * @priv: count the number of compare calls
  * @head: header of queue
  * @descend: whether or not to sort in descending order
  *
  * No effect if queue is NULL or empty. If there has only one element, do
  * nothing.
  */
-void q_sort(struct list_head *head, bool descend);
+void q_sort(void *priv, struct list_head *head, bool descend);
 
 /**
  * q_ascend() - Remove every node which has a node with a strictly less
@@ -250,4 +251,16 @@ int q_descend(struct list_head *head);
  */
 int q_merge(struct list_head *head, bool descend);
 
+
+/**
+ * q_timsort() - Sort elements of queue in ascending/descending order by Timsort
+ * @priv: count the number of compare calls
+ * @head: header of queue
+ * @descend: whether or not to sort in descending order
+ *
+ * No effect if queue is NULL or empty. If there has only one element, do
+ * nothing.
+ */
+void q_timsort(void *priv, struct list_head *head, bool descend);
+
 #endif /* LAB0_QUEUE_H */

問題 2 ： Null pointer dereference

修改完之後，再做一次 commit ，這次是沒辦法通過靜態檢查，顯示的錯誤訊息如下，但是在 merge 與 merge_final 中迴圈的判斷條件是 a && b ，而在 find_run 中的判斷條件是 while(next && ...) ，因此在使用 list_entry 時，傳入的參數不可能出現 NULL ，經過確認我的 Cppcheck 版本為 2.7 ，並且參考 jasperlin1996 的 pull request ，其中有說明這個錯誤是因為 container_of 中的 (type *) 0 造成，修改 pre-commit.hook 後順利 commit 。

C99 (6.3.2.3):
An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant.

Following files need to be cleaned up:
qtest.c
queue.c
sort_impl.h
timsort.c
timsort.c:35:28: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
        node = !(cmp(priv, list_entry(a, element_t, list)->value,
                           ^
timsort.c:36:22: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
                     list_entry(b, element_t, list)->value) ^
                     ^
timsort.c:76:28: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
        node = !(cmp(priv, list_entry(a, element_t, list)->value,
                           ^
timsort.c:77:22: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
                     list_entry(b, element_t, list)->value) ^
                     ^
timsort.c:104:19: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
    if (cmp(priv, list_entry(list, element_t, list)->value,
                  ^
timsort.c:105:13: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
            list_entry(next, element_t, list)->value) ^
            ^
timsort.c:116:36: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
        } while (next && cmp(priv, list_entry(list, element_t, list)->value,
                                   ^
timsort.c:117:30: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
                             list_entry(next, element_t, list)->value) ^
                             ^
timsort.c:125:38: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
        } while (next && !(cmp(priv, list_entry(list, element_t, list)->value,
                                     ^
timsort.c:126:32: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
                               list_entry(next, element_t, list)->value) ^
                               ^

Fail to pass static analysis.
  • 修改 pre-commit.hook
 --suppress=nullPointerRedundantCheck:harness.c \
 --suppress=nullPointer:queue.c \
 --suppress=nullPointer:qtest.c \
+--suppress=nullPointer:timsort.c \
 --suppress=returnDanglingLifetime:report.c \
 --suppress=constParameterCallback:console.c \
 --suppress=constParameterPointer:console.c \

問題 3 ： Misspelled word

在撰寫完 commit message 之後進行存檔，又顯示出拼字錯誤，結果是檢查到 Timsort ，因為暫時想不到解決方法，所以只能先將 Timsort 改成 another sort 。

Implement Timsort and test it's correctness                                [line 1]
 - Possible misspelled word(s): Timsort

How to Write a Git Commit Message: https://chris.beams.io/posts/git-commit/
Proceed with commit? [e/n/?]

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

Bottom-up Mergesort: A Detailed Analysis

這篇論文分析了 bottom-up 的合併排序法，得出最佳、平均與最差情況下的比較次數，並與 top-down 的合併排序法進行比較。

best case average case worst case
top-down
nlogn−0.146n
nlogn−1.248n
nlogn−0.943n
bottom-up
nlogn−0.146n
nlogn−0.965n
nlogn−0.701n

在 commit b5c56e 中，多次使用這篇論文的數值，像是 bottom-up 的係數 0.965 ，並且也提出了使用 queue-mergesort 的特性，解決了 bottom-up 合併排序在 n 比大小為 2 的冪次多一點點，效能變差的情況，例如 commit 文中提到的 n=1028 。

The simple eager merge pattern causes bad performance when n is just
over a power of 2. If n=1028, the final merge is between 1024- and
4-element lists, which is wasteful of comparisons. (This is actually
worse on average than n=1025, because a 1204:1 merge will, on average,
end after 512 compares, while 1024:4 will walk 4/5 of the list.)

在 commit 中， n=1025 的舉例，後面應該是 1024:1 而不是 1204:1 。

Queue-mergesort

這篇論文介紹了合併排序法的另一種變形，適合用來對鏈結串列進行排序的 queue-mergesort ，藉由不斷將佇列中的鏈結串列取出，合併後再放回佇列裡面來達成排序的目的，也證明了 queue-mergesort 是 optimal mergesort ，也就是在最差的情況下，比較次數小於或等於其他種合併排序。與 bottom-up 的合併排序法進行比較，在最差情況，

n=2k+1 時， bottom-up 合併排序會比 optimal 的合併排序多出
n−log2n 次比較次數，但在這篇論文中，並沒有提及合併時要維持 2 : 1 的比例，也沒有任何與 cache 優化相關的敘述。

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

將 list_sort.c 引入 lab0-c

commit 6f1a59

有了引入 Timsort 的經驗，我以同樣的方式引入 list_sort ，在 qtest.c 中新增新的命令 listsort ，接著修改 list_sort 中的 cmp 函式，讓比較的規則與 Timsort 和 q_sort 相同，最後修改 pre-commit.hook ，使 Null pointer dereference 的錯誤不要出現。

  • 在 qtest.c 中新增命令
     ADD_COMMAND(reverseK, "Reverse the nodes of the queue 'K' at a time",
                 "[K]");
     ADD_COMMAND(timsort, "Sort the queue with Timsort", "");
+    ADD_COMMAND(listsort, "Sort the queue with list_sort", "");
     add_param("length", &string_length, "Maximum length of displayed string",
               NULL);
     add_param("malloc", &fail_probability, "Malloc failure probability percent",
  • 修改 pre-commit.hook
 --suppress=nullPointer:queue.c \
 --suppress=nullPointer:qtest.c \
 --suppress=nullPointer:timsort.c \
+--suppress=nullPointer:list_sort.c \
 --suppress=returnDanglingLifetime:report.c \
 --suppress=constParameterCallback:console.c \
 --suppress=constParameterPointer:console.c \

與 Timsort 一樣，修改 trace-15-perf.cmd 進行測試，沒有發生錯誤，並以 valgrind 檢測結果，沒有記憶體洩漏。

  • Valgrind 測試結果

image

提供新的命令 shuffle

commit b4c4e9

在 qtest.c 加入新的命令 shuffle ，並新增 shuffle.c ，在這個檔案中實作 Fisher–Yates shuffle ，依照維基百科中的虛擬碼進行實作，不斷將 len 減一，將最後一個沒有被抽到的節點與隨機抽取的節點作交換，交換的方式是使用 list_move 移動節點，直到整個鏈結串列的節點都被抽到後，就結束 shuffle 。

     ADD_COMMAND(timsort, "Sort the queue with Timsort", "");
     ADD_COMMAND(listsort, "Sort the queue with list_sort", "");
+    ADD_COMMAND(shuffle, "Shuffle all the nodes in queue with Fisher-Yates shuffle", "");
     add_param("length", &string_length, "Maximum length of displayed string",
               NULL);
  • shuffle.c
while (len >= 1) {
    int random = rand() % len;
    old = q_nth_node(head, random);
    prev = old->prev;
    if (old != new) {
        list_move(old, new);
        list_move(new, prev);
    }
    new = old->prev;
    len--;
}

測試結果

利用作業說明中的測試程式，得出的圖表是大致符合 uniform distribution 的。
Figure_1

以不同的資料測試排序演算法

新增 mergesort 命令

新增 mergesort 命令用來執行合併排序，因為 queue.c 沒辦法修改，使得想要在 q_sort 的參數中代入計算比較次數的 count 會變得麻煩，所以直接將合併排序法獨立出來，其中的實作方式與 q_sort 一模一樣。

    ADD_COMMAND(listsort, "Sort the queue with list_sort", "");
     ADD_COMMAND(shuffle,
                 "Shuffle all the nodes in queue with Fisher-Yates shuffle", "");
+    ADD_COMMAND(mergesort, "Sort the queue with list_sort", "");
     add_param("length", &string_length, "Maximum length of displayed string",
               NULL);
     add_param("malloc", &fail_probability, "Malloc failure probability percent",

新增 quicksort 命令

新增 quicksort 命令，將測驗 1 的 quick 移植過來，選擇 pivot 的方式選用效能測試中最穩定的隨機選取，詳細實作請見 2024q1 Homework2 (quiz1+2) 。

     ADD_COMMAND(timsort, "Sort the queue with Timsort", "");
     ADD_COMMAND(listsort, "Sort the queue with list_sort", "");
+    ADD_COMMAND(mergesort, "Sort the queue with merge sort", "");
+    ADD_COMMAND(quicksort, "Sort the queue with quick sort", "");
     ADD_COMMAND(shuffle,
                 "Shuffle all the nodes in queue with Fisher-Yates shuffle", "");
-    ADD_COMMAND(mergesort, "Sort the queue with list_sort", "");
     add_param("length", &string_length, "Maximum length of displayed string",
               NULL);
     add_param("malloc", &fail_probability, "Malloc failure probability percent",

修改 shuffle 函式

在現實世界的資料中，很多往往都不是完全隨機的，因此，我在 shuffle 函式中多加入了一個參數 n ，代表要進行幾次 shuffle ，如果 n 為 0 ，則進行 Fisher-Yates shuffle ，若 n 不為 0 ，則進行 n 次 shuffle 的操作，以下面的例子為例，原本排序好的鏈結串列，在經過 4 次 shuffle 後，會變成一個部份排序好的鏈結串列。

cmd> show
Current queue ID: 0
l = [0 1 2 3 4 5 6 7 8 9]
cmd> shuffle 4
l = [6 7 2 3 4 5 9 8 1 0]
  • 修改 shuffle
-void shuffle(struct list_head *head)
+void shuffle(struct list_head *head, int n)
 {
     if (!head || list_empty(head) || list_is_singular(head))
         return;
 
-    int len = q_size(head);
+    int len = (n == 0) ? q_size(head) : n;
     struct list_head *prev = NULL;
     struct list_head *old = NULL;

進行測試

測試 1: 隨機資料

比較次數

以隨機資料測試四種排序演算法的比較次數，其中，快速排序法的表現是最差的，其比較次數高出其他排序演算法很多，根據維基百科的敘述，快速排序法需要經過大約

1.39nlogn 的比較次數，遠比合併排序要大的多。 Timsort 在針對隨機的鏈結串列排序的表現稍差，由於隨機的資料有可能被分成很多很小的 run ，為了分割這些很小的 run ，在比較次數上就略多於合併排序。在 commit b5c56e 中的第三篇論文有提到， top-down 與 queue-mergesort 都是 optimal merge sort ，但是兩者的比較次數仍是 top-down 的方法較小，在 commit 中也有點出 list_sort 的方法比較次數與 top-down 的方法相差
0.04n 倍。

在〈Linux 核心的鏈結串列排序〉中有證明 list_sort 是 optimal sort ，為何 top-down merge sort 與 list_sort 都是 optimal merge sort ，但還是會有微小的差距？

counts

執行時間

執行時間使用 dudect 裡面的 cpucycle 進行測量，由於快速排序法是使用隨機挑選 pivot ，會需要額外的時間成本來存取 pivot ，由於 Timsort 與 list_sort 都是採用深度優先的合併順序，將較於對 cache 較不友善的 top-down 方法， Timsort 與 list_sort 的執行時間會快一點，由於是隨機的鏈結串列， Timsort 的效能又會比 list_sort 再差一些。

cycles

測試 2: 已排序資料

比較次數

比較次數的與隨機資料的結果，兩種合併排序法與快速排序法的順序是一樣的，但是 Timsort 的比較次數領先了一大截，因為已排序的鏈結串列就是部份排序的資料的特例，所以相比於隨機資料有顯著的提升。

counts

執行時間

在這個例子中， Timsort 只分割出一個 run ，不需要進行其他合併的操作，所以效能相比於合併排序更好。

cycles

測試 3: 部份排序

比較次數

測試 3 的結果與測試 2 相同，都是 Timsort 比較次數最好，而 top-down 合併排序法與 list_sort 幾乎一模一樣，在這個部份比較符合 optimal merge sort 的定義。

counts

執行時間

由於 Timsort 分割 run 的特性，使得它的效能比 list_sort 好一點，而 top-down 由於對 cache 不友善，所以效能與前兩者有落差。

cycles

分析 cache

閱讀〈Teach Yourself Programming in Ten Years〉

踏實

在聽老師上課與我們的互動時，可以很清楚的感受到，老師希望我的深入的了解一件事背後的原理，而不是只有完成作業的要求，在與同學的互動中，總會有同學沒辦法對目前自己做的作業有清楚的理解，例如在課堂討論中，老師問同學快速排序法與合併排序法的差異，以及兩者的 locality 哪個較好，但同學僅止於做好作業的要求，完成程式碼的實作，沒有深入探討兩者的差異。一件事新不新其實一點都不重要，關鍵是「做得好不好」。

As Alexander Pope said, a little learning is a dangerous thing.

One possible point is that you have to learn a tiny bit of C++ (or more likely, something like JavaScript or Processing) because you need to interface with an existing tool to accomplish a specific task. But then you're not learning how to program; you're learning to accomplish that task.

寫作業才是主體

在本學期的第一堂課，也就是課程說明，在投影片中清楚地說，本課程寫作業才是主體，在課堂中最主要是做互動，老師花三小時講解作業規範，學員花 30 小時學習並在過程中檢討，也說不適合的選修學生族群是「覺得每週看著游泳教練或鋼琴教師表演，但自己不下水或不動手，卻又期盼可學到什麼技能的人」。

The best kind of learning is learning by doing.

師生互動

授課時間最主要是師生互動，包含 code review 、問答還有認識自己，老師在業界待了很多年，也算是 programmers ，與其他的 programming 討論，才能意識的自己的不足，有經驗的 programmers ，包含以後面試的主管或是資深工程師，判斷一個人懂不懂，只需要一些很基礎的問題，這些問題看似不難，但對於沒辦法深入了解一件事背後原理的人來說，是非常困難的問題，老師在上課的時候就像模擬面試，我在課堂分享我的快速排序的實作評估時，清楚的感受到面試的氛圍，我自己也有面試過一些公司，但都是實習生的職位，問的問題都非常淺，但假如今天是面試正職，我已經被刷掉了。另外，老師在上課時常講一句話，「每天都與大牛合作討論，怎麼能不牛」，經由與更有經驗的 programmer 討論，或是親自參與開源專案，與開發者互動，學到那些大師們的經驗，勝過單純只閱讀網路上的教材或書籍。

Talk with other programmers; read other programs. This is more important than any book or training course.

When you're the worst, you learn what the masters do, and you learn what they don't like to do (because they make you do it for them).

閱讀各種第一手資料與規格書

老師在同學們的作業中，或是講座中，時常會強調一定要閱讀 C 語言規格書，還要了解編譯器的原理，也有許多作業要求是要我們援引規格書中的解釋，目的是要讓我們更加了解 C 語言的特性，寫出更優雅簡潔的程式碼，也要讓我們重視程式安全性的議題，避免因為忽略了規格書或是編譯器的規範，而造成程式的錯誤，或是遭到各種攻擊，歷史上有太多事件都是因為程式碼的疏忽而造成不必要的人員傷亡或是巨大的金錢損失，在軟體缺失導致的危害這份教材中就有許多血淋淋的案例。

Get involved in a language standardization effort.

Last changed by 
 
yeh-sudo
0
1
888

Read more

memtier_benchmark

於 2013 年以 GPLv2 的授權形式發布，並於隔年 2014 年更新，除了基本的測試空能，新增隨機資料，且可以使用高斯分布去存取資料，以及限制資料大小範圍等功能。

Aug 23, 2024
2024q1 Homework5 (assessment)

contributed by &lt; yeh-sudo &gt;

May 3, 2024
2024q1 Homework6 (integration)

contributed by &lt; yeh-sudo &gt;

Apr 29, 2024
2024q1 Homework2 (quiz1+2)

contributed by &lt; yeh-sudo &gt;

Apr 11, 2024
Read more from yeh-sudo
Published on HackMD