or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Syncing
xxxxxxxxxx
2023q1 Homework1 (lab0)
contributed by < KHLee529 >
開發環境
開發過程
開發順序主要依照
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)\) 的地方應在以下部份中更新
在基本上沒有更改運算邏輯,僅修改先前字串儲存空間不足 (未包含到 '\0' 的問題後) 便通過了一次第 17 項測試。但緊接再重新編譯執行一次測試時便又失敗,目前仍未找到問題點。
計畫先閱讀
dudect
相關論文後尋找原因。- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →q_size
由於鏈結串列當中的每個節點記憶體不連續,無法利用記憶體位址進行長度計算,故決定透過遍歷整個串列中每個節點的方式計算節點數。
q_delete_mid
由於雙向鏈結串列可以
從頭尾分別進行正向與逆向遍歷分別由成員head
的next
與prev
兩個相鄰節點出發,分別以正向順序與反向順序依序走訪其接下來各節點。故透過這個特性,當走訪兩個方向走訪到相同或相鄰兩節點時,便是正中間節點。
在找到正中間節點後透過 List API 移除並釋放該節點即可完成此目標。
詳閱「資訊科技詞彙翻譯」,以得知用語調整。「逆向」不是好的詞彙,因為這是 doubly-linked list。
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →q_delete_dup
由於此函式僅會在序列已排序的狀況下被呼叫,故所有重複的節點皆會是在串列中連續的節點。故使用以下演算法進行
實做實作。在
遍歷整個串列的過程中尋找「與下個節點等值的節點」,當找到時提出該值後將往後相同值的節點全數刪除,重複以上過程直到最後。詳閱「資訊科技詞彙翻譯」,以得知用語調整。
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →q_swap
在遍歷整個佇列的過程當中連續操作「提出一個節點、放置到下一個位置」以達到兩兩交換的效果。
反向重排
要將整個鏈結串列進行反向重排時,可以透過「在走訪各個節點的過程中,將每個節點都移動到最前面」的方式進行實作。如以下順序所示。
透過連續提出 K 個節點的子串列後倒序排列的方式將每 K 個節點倒序。而當要將串列以 K 個節點為一組進行反向重排時,可以將要被反向重排的 K 個節點作為一個子串列分離出來,透過
q_reverse
反向重排後在重新插入原本位置即可。改進漢語表達。
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →q_descend
透過雙向鏈結串列可以
倒序遍歷由反向順序走訪各個節點的優勢,將此一目標視為「在反向順序走訪各節點的過程中,刪除所有『小於先前所有節點』的節點」,便可以達成此目標。注意用語:「倒序」需要先行定義,或者改用其他詞彙。
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →merge 與 sort
首先考慮將多個已排序的佇列進行合併。
透過先分別將兩連續佇列進行合併後往前移動少總佇列數,並反覆進行此一操作直到最後僅剩一個佇列。如下圖所示。
而在進行佇列內排序時,由於多個佇列的鏈結方式與佇列內的鏈結方式相同,故應可以將每個節點視為上圖的一個 queue 後直接進行合併即可。然而,由於佇列內的資料結構與每個佇列的資料結構不同,較難將程式碼再利用,因此先以遞迴的合併排序 (mergesort) 演算法進行
q_sort
實作。注意用語,參見 資訊科技詞彙翻譯
張貼程式碼之前,你應該闡述策略和思考因素。後續仍要改進。
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →問題
目前執行
make test
中進行的測試第 15 項結果如下其中提到 \(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
與自行實作的合併排序演算法差異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?> 當中提到的測試方式主要分成三個步驟
假說檢定
在包含不確定性與誤差的實驗當中,並不能保證每一次實驗的結果皆完全相同,因此透過機率分佈的方式來將不確定性建模。而實務上,通常將「每次結果皆應相同」的實驗結果視為常態機率分佈 (Normal Distribution)。而假說檢定便是透過對抽樣的不確定性進行建模後判定「抽樣結果是否符合特定機率分佈」的方式。
而在本論文當中,由於預期的函式執行為常數時間,每次執行時間應相同,故亦假設其執行時間的符合常態分佈。故便透過常用於檢驗常態分佈的 t-test 進行假說檢定。
t-test
對於一個「滿足期望值為 \(\mu\) 的常態分佈的隨機變數 \(X\)」進行抽樣後的抽樣結果,透過其抽樣平均值 \(\bar X\) 與抽樣標準差 \(S\) 進行計算得到的隨機變數 \(T = \bar X - \mu \over S / \sqrt n\) 應滿足 T 分佈 (T-distribution)。
故可以透過抽樣結果計算出來的 \(T\) 值在 T 分佈當中出現的機率來判定該隨機變數 \(X\) 是否確實來自「期望值為 \(\mu\) 的常態分佈」。
然而,由於此一定義的 t-test 需要有一個預期的期望值 \(\mu\),對於預期期望值未知的隨機變數便可以透過 Welch's t-test 的變形方式進行判定「兩隨機變數是否來自相同的常態分佈」。而此時隨機變數 \(T\) 的定義方式便修正為 $T = + \sqrt{S_2^2 \over n_2}}
在論文當中使用 Welch's t-test 進行兩機率分佈的比對,而兩抽樣結果分別為「固定輸入函式執行時間」以及「隨機輸入函式執行時間」,其中虛無假說便是「若函式執行為 \(O(1)\) 時,『透過固定輸入得到的執行時間機率分佈』與『隨機輸入得到的執行時間機率』分佈有相同的期望值」。
函式執行時間
由於單一函式執行時間可能是 ns 數量級,以此為單位進行量測較難精確量測,因此可以使用硬體提供的 CPU 指令計數器進行紀錄與量測函式執行。這部份在 lab0-c 的實作當中也能看到對於不同硬體架構的相關使用。
資料後處理
論文當中有提到,實驗得到的資料中有可能會因為作業系統的中斷或是其他因素導致出現極端離群值。
然而,如此的極端離群值對於平均數的影響極大,若極端值與普遍峰值相差數個數量級的便會平均值得計算造成極大的影響,進而影響 t-test 結果。因此應在資料後處理階段將離群值去除。
對於此一描述,嘗試透過自行實做的簡易時間量測程式進行實驗。
需要將
queue.h
中紀錄malloc
與free
的 harness 先去除。透過以下命令執行
下圖為測試結果 (經排序)。
下圖為去除最後 20 個資料點的測試結果。
下圖為去除最後 40 個資料點的測試結果。在這個階段,整體資料看起來便很接近常態分佈了。
由上面的測試結果可以看出,大概在排序後的全體資料的最後 4% 會出現明顯的離群值。
lab0 中的 dudect 實作
前置處理器技巧
在一開始尋找
option simulation 1
命令會對於測試造成的影響時發現,在qtest.c
當中各個註冊成為命令的do_xxx
函式當中,可以進行 \(O(1)\) 時間複雜度測試的項目皆有is_xxxx_const
函數作為測試函式。但直接在整個 repo 當中尋找相關的函數宣告時,並無法找到相應的宣告,僅能在編譯後的目的檔 (object file) 當中尋找到相應的函式宣告。
其中,在
dudect/fixture.o
為唯一包含在 dudect 函式庫當中的地方,最後在dudect/fixture.h
當中發現到以下的宣告。並且在
dudect/constant.h
與dudect/fixture.c
中也找到了類似的宣告。在此可以發現到相同的
DUT_FUNCS
透過不同的_(x)
定義在不同的需求定義了不同的巨集。測試流程與改善方案
從
is_xxxx_const
函式出發,可以找到實際測試會使用到的關鍵函式流程為「test_const
\(\rightarrow\)doit
\(\rightarrow\)measure
\(\rightarrow\)report
」。其中,measure
主要將運行時間測試完成後,交給report
進行 t-test 的比對。然而在
measure
函式的實作當中,可以看到應該是「紀錄後進行資料處理」的測試流程卻是以「直接少做要刪除的次數」的方式進行,如以下程式碼中的註解。這部份應當改成「做完
N_MEASURES
次紀錄後進行排序再刪除前後各DROP_SIZE
個資料點」。經修正後的程式碼如下以下部份實作有嚴重錯誤,下方有相關探討
後來發現,若將
DROP_SIZE
調整為 0 後,並未去除任何資料時,僅執行執行時間排序後亦可通過測試,但在將該時間排序函數去除後便無法通過,這個現象與預期的並不相同。就假說檢定的基礎來說,t 檢定的目的是檢測兩個預期是呈現常態分佈的隨機變數,因此對於相同的資料集合應得到相同的結果。然而因為資料輸入的順序產生資料驗證的差異並非期望中出現的現象,故先將所有結果列出。
而在列出結果後,發現錯誤是出在在對
exec_times
進行排序時,並未將classes
的相依性列入考量,導致之後變成另類的打亂結果,因此整個錯誤的運行反而產生了「以為正確」的結果。以上調整完全錯誤。須嘗試以新的方法進行。
首先嘗試的方法是基於與原先相同的邏輯,唯排序的陣列改為
Valgrind
首先透過
make valgrind
命令進行檢查,發現每一個測試當中都會出現以下的記憶體洩漏問題而從其回溯函式呼叫的流程可以看出此一記憶體洩漏問題並非
queue.c
的實作問題而是在qtest.c
當中。最後發現在原先透過
add_quit_helper
註冊作為結束階段函式的q_quit
函式的第一行便是return true
使得接下來所有的記憶體釋放操作都無法進行,進而產生這些問題。當將該錯誤操作移除後呼叫make valgrind
命令便沒有出現相關問題。