2023q1 Homework1 (lab0)

contributed by < KHLee529 >

作業描述

開發環境

$gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0

$lscpu
Architecture:            x86_64
CPU op-mode(s):          32-bit, 64-bit
Byte Order:              Little Endian
Address sizes:           39 bits physical, 48 bits virtual
CPU(s):                  8
On-line CPU(s) list:     0-7
Thread(s) per core:      2
Core(s) per socket:      4
Socket(s):               1
NUMA node(s):            1
Vendor ID:               GenuineIntel
CPU family:              6
Model:                   94
Model name:              Intel(R) Core(TM) i7-6770HQ CPU @ 2.60GHz
Stepping:                3
CPU max MHz:             3500.0000
CPU min MHz:             800.0000
BogoMIPS:                5199.98
Virtualization:          VT-x
L1d cache:               128 KiB 
L1i cache:               128 KiB 
L2 cache:                1 MiB 
L3 cache:                6 MiB 
NUMA node0 CPU(s):       0-7

開發過程

開發順序主要依照 make test 當中的任務順序進行

q_new 與 q_free

這兩個函式較單純，主要是先熟悉 linux 風格的 linked list API。

在建立新的佇列時，動態配置成員 head 所需的記憶體後對其進行初始化。

在清除一個佇列時，遍歷其中每個節點並將其所佔空間釋放。其中由於標頭檔已提供許多便利的函式與巨集，妥善應用即可滿足需求。
由於遍歷過程中會將節點移除，因此需要使用會紀錄下一節點的 list_for_each_safe 而非 list_for_each。

插入與移除

在新增節點的操作中，由於 List API 有提供將現有節點插入頭尾的界面，因此將它們分為「建立節點」與「插入節點」的兩個部份。

與插入操作相同，移除操作亦分為「解除鏈結」以及「複製節點內容」兩個部份。

待解決

目前在 make test 當中的第 17 項測試–-

$O(1)$ 插入與移除測試–-還尚未通過。而插入現有節點的操作對於任意節點而言皆只有 4 項數值指派，故應為

$O(1)$。目前推論複雜度不是

$O(1)$ 的地方應在以下部份中

1. 字串長度計算
2. 字串複製

更新

在基本上沒有更改運算邏輯，僅修改先前字串儲存空間不足 (未包含到 '\0' 的問題後) 便通過了一次第 17 項測試。但緊接再重新編譯執行一次測試時便又失敗，目前仍未找到問題點。
計畫先閱讀 dudect 相關論文後尋找原因。

2023/02/17 10:30

q_size

由於鏈結串列當中的每個節點記憶體不連續，無法利用記憶體位址進行長度計算，故決定透過遍歷整個串列中每個節點的方式計算節點數。

q_delete_mid

由於雙向鏈結串列可以從頭尾分別進行正向與逆向遍歷分別由成員 head 的 next 與 prev 兩個相鄰節點出發，分別以正向順序與反向順序依序走訪其接下來各節點。
故透過這個特性，當走訪兩個方向走訪到相同或相鄰兩節點時，便是正中間節點。
在找到正中間節點後透過 List API 移除並釋放該節點即可完成此目標。

詳閱「資訊科技詞彙翻譯」，以得知用語調整。「逆向」不是好的詞彙，因為這是 doubly-linked list。

jserv

q_delete_dup

由於此函式僅會在序列已排序的狀況下被呼叫，故所有重複的節點皆會是在串列中連續的節點。故使用以下演算法進行實做 實作。
在遍歷 整個串列的過程中尋找「與下個節點等值的節點」，當找到時提出該值後將往後相同值的節點全數刪除，重複以上過程直到最後。

詳閱「資訊科技詞彙翻譯」，以得知用語調整。

jserv

q_swap

在遍歷整個佇列的過程當中連續操作「提出一個節點、放置到下一個位置」以達到兩兩交換的效果。

反向重排

要將整個鏈結串列進行反向重排時，可以透過「在走訪各個節點的過程中，將每個節點都移動到最前面」的方式進行實作。如以下順序所示。

透過連續提出 K 個節點的子串列後倒序排列的方式將每 K 個節點倒序。
而當要將串列以 K 個節點為一組進行反向重排時，可以將要被反向重排的 K 個節點作為一個子串列分離出來，透過 q_reverse 反向重排後在重新插入原本位置即可。

改進漢語表達。

jserv

q_descend

透過雙向鏈結串列可以倒序遍歷由反向順序走訪各個節點的優勢，將此一目標視為「在反向順序走訪各節點的過程中，刪除所有『小於先前所有節點』的節點」，便可以達成此目標。

注意用語：「倒序」需要先行定義，或者改用其他詞彙。

jserv

merge 與 sort

首先考慮將多個已排序的佇列進行合併。
透過先分別將兩連續佇列進行合併後往前移動少總佇列數，並反覆進行此一操作直到最後僅剩一個佇列。如下圖所示。

而在進行佇列內排序時，由於多個佇列的鏈結方式與佇列內的鏈結方式相同，故應可以將每個節點視為上圖的一個 queue 後直接進行合併即可。然而，由於佇列內的資料結構與每個佇列的資料結構不同，較難將程式碼再利用，因此先以遞迴的合併排序 (mergesort) 演算法進行 q_sort 實作。

透過自行實作的合併排序演算法進行 200000 個節點的排序，藉由 qtest 的 time 指令 命令計算時間約須 0.175 秒。
透過 list_sort.c 的排序演算法進行 200000 個節點的排序，藉由 qtest 的 time 命令計算時間約須 0.155 秒。

注意用語，參見 資訊科技詞彙翻譯
張貼程式碼之前，你應該闡述策略和思考因素。後續仍要改進。

jserv

問題

目前執行 make test 中進行的測試第 15 項結果如下

+++ TESTING trace trace-15-perf:
# Test performance of sort 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
---     trace-15-perf   6/6

其中提到

$O(n^2)$ 時間複雜度測驗失敗但

$O(n\log n)$ 時間複雜度測驗通過，仍未確定其意含以及原因。

詳讀論文

Linux 核心實作 lib/list_sort.c

在研讀 lib/list_sort.c 與 Linux 核心的鏈結串列排序 首先注意到的事情是其如何減少排序當中的記憶體使用。

原先在自行實作合併排序法 (mergesort) 的過程中，由於可以將串列當中的每一個節點都視為一個單獨的串列後直接合併 (buttom-up mergesort)，進而透過類似實作佇列合併示意圖的方式進行實作。
然而當初想到的方式是先透過與待排序的串列等長的 struct list_head 結構所構成的陣列作為將個節點拆開成的子串列的 head 成員。但由於在作業中 q_sort 實作不得使用 malloc 而作罷，改為實作透過遞迴呼叫進行的 top-down mergesort。
即便如此，由於在 top-down mergesort 的分割 (partition) 階段仍然建立了左右分別的 head 成員，僅是將原先計畫使用 malloc 生成的部份改在 stack 當中儲存。甚至由於每一次分割皆須要生成 2 個 head 成員，其所佔的記憶體空間從原本的

$n\times \mathtt{\text{sizeof(struct list\_head)}}$ 進而變成其 2 倍。

而在 lib/list_sort.c 當中節省空間利用的方式為「將原先維護的雙向鏈結串列改為單向」，由此便可以透過原先已存在於每個節點的 prev 成員建立另一個單向鏈結串列，而透過這個以 prev 連接的鍊結串列來紀 buttom-up mergesort 過程當中待合併的子串列。

以下是 8 個節點的鏈結串鏈排序過程示意圖，其中黑色箭頭代表原本的串列本身，紅色箭頭部份代表「透過 prev 成員連接的各個子串列間的連結 (單向)」，藍色箭頭代表「以合併後的子串列內的連結 (單向)」。

比較 lib/list_sort.c 與自行實作的合併排序演算法差異

• 時間複雜度：整體來看，兩者都使用合併演算法，即便是最差的狀況時間複雜度皆為
  $O(n\log n)$
  • 自行實作的合併排序演算法包含分割與合併兩個步驟，而 buttom-up 的合併演算法僅有合併，這部份可以省下一些時間。
  • 僅比較自行實作的合併部份，由於維護的資料結構仍為原本的雙向鏈結串列，在每一次合併的過程中移除與接合所需的指令數亦較高。
• 空間複雜度：討論除了被排序的鏈結串列本身之外額外所需的空間使用，在 lib/list_sort.c 當中使用到的額外空間為
  $O(1)$。然而自行實作的版本在串列本身之外仍需要至少
  $2n\times \mathtt{\text{sizeof(struct list\_head)}}$，使用量差異甚大。

dudect

由於在進行 queue.c 實做時，進行 make test 的最後一個

$O(1)$ 測試時插入節點命令大多無法通過，但在多次重複測試後仍會出現數次通過的結果。因此開始研究其測試方式。

文獻閱讀

論文 <Dude, is my code constant time?> 當中提到的測試方式主要分成三個步驟

1. 測量函式執行時間
2. 資料後處理
3. 進行統計假說檢定

假說檢定

在包含不確定性與誤差的實驗當中，並不能保證每一次實驗的結果皆完全相同，因此透過機率分佈的方式來將不確定性建模。而實務上，通常將「每次結果皆應相同」的實驗結果視為常態機率分佈 (Normal Distribution)。而假說檢定便是透過對抽樣的不確定性進行建模後判定「抽樣結果是否符合特定機率分佈」的方式。

而在本論文當中，由於預期的函式執行為常數時間，每次執行時間應相同，故亦假設其執行時間的符合常態分佈。故便透過常用於檢驗常態分佈的 t-test 進行假說檢定。

t-test

對於一個「滿足期望值為

$\mu$ 的常態分佈的隨機變數

$X$」進行抽樣後的抽樣結果，透過其抽樣平均值

$\overline{X}$ 與抽樣標準差

$S$ 進行計算得到的隨機變數

$\frac{T=\overline{X}-\mu }{S/\sqrt{n}}$ 應滿足 T 分佈 (T-distribution)。
故可以透過抽樣結果計算出來的

$T$ 值在 T 分佈當中出現的機率來判定該隨機變數

$X$ 是否確實來自「期望值為

$\mu$ 的常態分佈」。

然而，由於此一定義的 t-test 需要有一個預期的期望值

$\mu$，對於預期期望值未知的隨機變數便可以透過 Welch's t-test 的變形方式進行判定「兩隨機變數是否來自相同的常態分佈」。而此時隨機變數

$T$ 的定義方式便修正為 $T = \bar X_1 - \bar X_2| \over \sqrt{S_1^2 \over n_1 + \sqrt{S_2^2 \over n_2}}

在論文當中使用 Welch's t-test 進行兩機率分佈的比對，而兩抽樣結果分別為「固定輸入函式執行時間」以及「隨機輸入函式執行時間」，其中虛無假說便是「若函式執行為

$O(1)$ 時，『透過固定輸入得到的執行時間機率分佈』與『隨機輸入得到的執行時間機率』分佈有相同的期望值」。

函式執行時間

由於單一函式執行時間可能是 ns 數量級，以此為單位進行量測較難精確量測，因此可以使用硬體提供的 CPU 指令計數器進行紀錄與量測函式執行。這部份在 lab0-c 的實作當中也能看到對於不同硬體架構的相關使用。

/* dudect/cpycycles.h */
static inline int64_t cpucycles(void)
{
#if defined(__i386__) || defined(__x86_64__)
    unsigned int hi, lo;
    __asm__ volatile("rdtsc\n\t" : "=a"(lo), "=d"(hi));
    return ((int64_t) lo) | (((int64_t) hi) << 32);

#elif defined(__aarch64__)
    uint64_t val;
    asm volatile("mrs %0, cntvct_el0" : "=r"(val));
    return val;
#else
#error Unsupported Architecture
#endif
}

資料後處理

論文當中有提到，實驗得到的資料中有可能會因為作業系統的中斷或是其他因素導致出現極端離群值。
然而，如此的極端離群值對於平均數的影響極大，若極端值與普遍峰值相差數個數量級的便會平均值得計算造成極大的影響，進而影響 t-test 結果。因此應在資料後處理階段將離群值去除。

對於此一描述，嘗試透過自行實做的簡易時間量測程式進行實驗。

/* time_meas_exp.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "dudect/cpucycles.h"
#include "random.h"
#include "queue.h"

int main() {
    FILE *f = fopen("record.txt", "w");
    struct list_head *head = NULL;
    head = q_new();
    for (int i = 0; i < 1000; i++) {
        int64_t a, b;
        char s[8];
        randombytes((uint8_t *)s, 8);
        s[7] = 0;
        a = cpucycles();
        q_insert_head(head, s);
        b = cpucycles();
        fprintf(f, "%ld\n", b - a);
    }
    q_free(head);
    fclose(f);
}

需要將 queue.h 中紀錄 malloc 與 free 的 harness 先去除。

diff --git a/queue.h b/queue.h
index ce833d2..c3eb506 100644
--- a/queue.h
+++ b/queue.h
@@ -10,7 +10,7 @@
 #include <stdbool.h>
 #include <stddef.h>
 
-#include "harness.h"
 #include "list.h"
 
 /**
@@ -116,8 +116,10 @@ element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize);
  */
 static inline void q_release_element(element_t *e)
 {
-    test_free(e->value);
-    test_free(e);
+    free(e->value);
+    free(e);
 }
 
 /**

透過以下命令執行

$ gcc -O1 -Wall -Werror time_meas_exp.c random.c queue.c -o time_meas_exp
$ ./time_meas_exp
$ sort -n record.txt > tmp.txt
$ gnuplot -e "plot 'tmp.txt' using 1 with linespoints"

下圖為測試結果 (經排序)。

下圖為去除最後 20 個資料點的測試結果。

下圖為去除最後 40 個資料點的測試結果。在這個階段，整體資料看起來便很接近常態分佈了。

由上面的測試結果可以看出，大概在排序後的全體資料的最後 4% 會出現明顯的離群值。

lab0 中的 dudect 實作

前置處理器技巧

在一開始尋找 option simulation 1 命令會對於測試造成的影響時發現，在 qtest.c 當中各個註冊成為命令的 do_xxx 函式當中，可以進行

$O(1)$ 時間複雜度測試的項目皆有 is_xxxx_const 函數作為測試函式。
但直接在整個 repo 當中尋找相關的函數宣告時，並無法找到相應的宣告，僅能在編譯後的目的檔 (object file) 當中尋找到相應的函式宣告。

$ grep -r is_insert_head_const .
grep: ./qtest: binary file matches
grep: ./dudect/fixture.o: binary file matches
./qtest.c:        bool ok = is_insert_head_const();
grep: ./qtest.o: binary file matches

其中，在 dudect/fixture.o 為唯一包含在 dudect 函式庫當中的地方，最後在 dudect/fixture.h 當中發現到以下的宣告。

...
#include "constant.h"

/* Interface to test if function is constant */
#define _(x) bool is_##x##_const(void);
DUT_FUNCS
#undef _
...

並且在 dudect/constant.h 與 dudect/fixture.c 中也找到了類似的宣告。

/* dudect/constant.h */
...
#define DUT_FUNCS  \
    _(insert_head) \
    _(insert_tail) \
    _(remove_head) \
    _(remove_tail)

#define DUT(x) DUT_##x

enum {
#define _(x) DUT(x),
    DUT_FUNCS
#undef _
};
...

/* dudect/fixture.c */
...
#define DUT_FUNC_IMPL(op) \
    bool is_##op##_const(void) { return test_const(#op, DUT(op)); }

#define _(x) DUT_FUNC_IMPL(x)
DUT_FUNCS
#undef _

在此可以發現到相同的 DUT_FUNCS 透過不同的 _(x) 定義在不同的需求定義了不同的巨集。

測試流程與改善方案

從 is_xxxx_const 函式出發，可以找到實際測試會使用到的關鍵函式流程為「test_const

$\to$ doit

$\to$ measure

$\to$ report」。其中，measure 主要將運行時間測試完成後，交給 report 進行 t-test 的比對。

然而在 measure 函式的實作當中，可以看到應該是「紀錄後進行資料處理」的測試流程卻是以「直接少做要刪除的次數」的方式進行，如以下程式碼中的註解。

    switch (mode) {
    case DUT(insert_head):
        /* only conduct (N_MEASURES - 2 * DROP_SIZE) times of measurement */
        for (size_t i = DROP_SIZE; i < N_MEASURES - DROP_SIZE; i++) {
            char *s = get_random_string();
            dut_new();
            dut_insert_head(
                get_random_string(),
                *(uint16_t *) (input_data + i * CHUNK_SIZE) % 10000);
            int before_size = q_size(l);
            before_ticks[i] = cpucycles();
            dut_insert_head(s, 1);
            after_ticks[i] = cpucycles();
            int after_size = q_size(l);
            dut_free();
            if (before_size != after_size - 1)
                return false;
        }
        break;
    ...
    }

這部份應當改成「做完 N_MEASURES 次紀錄後進行排序再刪除前後各 DROP_SIZE 個資料點」。經修正後的程式碼如下

/* dudect/constant.c */
...
bool measure(int64_t *before_ticks,
             int64_t *after_ticks,
             uint8_t *input_data,
             int mode)
{
    ...
    switch (mode) {
    case DUT(insert_head):
        for (size_t i = 0; i < N_MEASURES; i++) {
            ...
        }
        break;
    case DUT(insert_tail):
        for (size_t i = 0; i < N_MEASURES; i++) {
            ...
        }
        break;
    case DUT(remove_head):
        for (size_t i = 0; i < N_MEASURES; i++) {
            ...
        }
        break;
    case DUT(remove_tail):
        for (size_t i = 0; i < N_MEASURES; i++) {
            ...
        }
        break;
    default:
        for (size_t i = 0; i < N_MEASURES; i++) {
            ...
        }
    }
    ...
}

以下部份實作有嚴重錯誤，下方有相關探討

20230306

/* dudect/fixture.h */
...
static int cmp(const void *a, const void *b) {
    return *(uint64_t *)a - *(uint64_t *)b;
}

static bool doit(int mode)
{
    ...
    /* ... */
    prepare_inputs(input_d

    bool ret = measure(before_ticks, after_ticks, input_data, mode);
    differentiate(exec_times, before_ticks, after_ticks);
    
    /* sort the results of measurements and drop from front and end */
    qsort(exec_times, N_MEASURES, sizeof(int64_t), cmp);
    memset(exec_times, 0, DROP_SIZE * sizeof(int64_t));
    memset(&exec_times[N_MEASURES - DROP_SIZE], 0, DROP_SIZE * sizeof(int64_t));
    
    update_statistics(exec_times, classes);
    ret &= report();
    ...
    /* ... */
 
}
...

然後就終於看到皮卡丘了，不過總覺得更改評分程式讓自己變成正確的好像不太有道理。

確實真沒有道理！
20230306

---

後來發現，若將 DROP_SIZE 調整為 0 後，並未去除任何資料時，僅執行執行時間排序後亦可通過測試，但在將該時間排序函數去除後便無法通過，這個現象與預期的並不相同。

就假說檢定的基礎來說，t 檢定的目的是檢測兩個預期是呈現常態分佈的隨機變數，因此對於相同的資料集合應得到相同的結果。然而因為資料輸入的順序產生資料驗證的差異並非期望中出現的現象，故先將所有結果列出。
而在列出結果後，發現錯誤是出在在對 exec_times 進行排序時，並未將 classes 的相依性列入考量，導致之後變成另類的打亂結果，因此整個錯誤的運行反而產生了「以為正確」的結果。

以上調整完全錯誤。須嘗試以新的方法進行。

首先嘗試的方法是基於與原先相同的邏輯，唯排序的陣列改為

Valgrind

首先透過 make valgrind 命令進行檢查，發現每一個測試當中都會出現以下的記憶體洩漏問題

==356040== 32 bytes in 1 blocks are still reachable in loss record 1 of 6
==356040==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==356040==    by 0x10CBEE: do_new (qtest.c:145)
==356040==    by 0x10DE1A: interpret_cmda (console.c:181)
==356040==    by 0x10E3CF: interpret_cmd (console.c:201)
==356040==    by 0x10E7D0: cmd_select (console.c:610)
==356040==    by 0x10F0BC: run_console (console.c:705)
==356040==    by 0x10D20C: main (qtest.c:1223)

而從其回溯函式呼叫的流程可以看出此一記憶體洩漏問題並非 queue.c 的實作問題而是在 qtest.c 當中。
最後發現在原先透過 add_quit_helper 註冊作為結束階段函式的 q_quit 函式的第一行便是 return true 使得接下來所有的記憶體釋放操作都無法進行，進而產生這些問題。當將該錯誤操作移除後呼叫 make valgrind 命令便沒有出現相關問題。