# 2024q1 Homework1 (lab0)
contributed by < `yinghuaxia` >
### Reviewed by `yu-hsiennn`
> 原本判斷如果 left 的大小不為 0，則將 left 加到 new_list 中，否則將 right 加到 new_list 中，但是這樣在執行多筆測資時會造成超時的錯誤，因為這種做法還會需要考慮到執行 q_size 這個函式的時間。因此我們直接將判斷式移除，對兩個串列可能剩下的節點都執行加到 new_list 的動作以避免超時的問題發生。
這邊不需要知道整條串列的長度也可以進行串接，只需要判斷 `left` 是否為空就足夠了，即
`left ? list_splice_tail(left, &new_list) : list_splice_tail(right, &new_list)`
## 開發環境
```shell
$ 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: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-9700 CPU @ 3.00GHz
CPU family: 6
Model: 158
Thread(s) per core: 1
Core(s) per socket: 8
Socket(s): 1
Stepping: 13
CPU max MHz: 4700.0000
CPU min MHz: 800.0000
BogoMIPS: 6000.00
```
## 針對指定串列操作的實作
### q_new
使用 [malloc](https://man7.org/linux/man-pages/man3/malloc.3.html) 指派一個空間給我們要建立的 `list_head`，並用 `INIT_LIST_HEAD` 對其作初始化。
:::danger
參照 C 語言規格書和 Linux man page，使用 https://man7.org/linux/man-pages/ 的超連結。
> ok
:::
### q_free
直觀的想法是走訪每一個節點並一次將其空間釋放，因此我們需要得到每個 element 的位址。`list_for_each_entry_safe` 這個巨集的程式如下所示：
```c
#define list_for_each_entry_safe(pos, n, head, member) \
for (pos = list_first_entry(head, typeof(*pos), member), \
n = list_next_entry(pos, member); \
!list_entry_is_head(pos, head, member); \
pos = n, n = list_next_entry(n, member))
```
:::danger
- [ ] traverse (動詞) 和 traversal (名詞)
根據 Dictionary.com 的[解釋](https://www.dictionary.com/browse/traverse
): (作為及物動詞和不及物動詞都有類似的意思，以下列出作為及物動詞的寓意)
* to pass or move over, along, or through.
* to go to and fro over or along.
其實這意思很好懂，就像我們「走過」/「穿越」校園一般，於是 traverse a linked list 就會是「(用某種手段) 存取多個鏈結串列的節點」，但這裡卻沒有必要「所有」的範圍：英語的 "move over/through" 用於某個區域時，根本沒有這樣的隱含意義。如果將 traverse 翻譯為「遍歷」，就會導致「超譯」，也就是跳脫「直譯」和「意譯」。
當我們回頭看 "traverse" 所在的技術描述內容，例如 "traverse every node"，若翻譯為「遍歷每個節點」，那麼既然都「遍」(意即「全面」、「到處」)，又何來「每個」節點呢？於是，合理的翻譯應改為「逐一走訪每個節點」 —— 差異在哪？在 "traverse every node" 的應用場景中，可能是我們嘗試在鏈結串列尋找特定的節點內含的資料，一旦找到就停止，或者我們要偵測給定的鏈結串列是否包含環狀 (circular) 結構 ，並沒有真的要「遍」(到處/全面)「歷」(意即「經過」) 每個節點。在我們的用語中，要區分「意圖」(intention) 和「實際作用」(reaction)，濫用「遍歷」會使得語意不清，從而難以推測英語原文的訴求。
還有個更重要的原因是，「遍歷」這詞已在理工領域存在，且廣泛使用，即「遍歷理論」(Ergodic theory)，後者是研究具有不變測度 (invariant measure) 的動力系統及其相關問題的一個數學分支。 遍歷理論研究遍歷變換，由試圖證明統計物理中的遍歷假設 (Ergodic hypothesis) 演進而來。
在統計學中，若單一個物理系統在不同時間內重複相同的實驗 (如丟擲一枚硬幣)，其取樣數據所得的統計結果 (如硬幣出現正面的機率) 和極多個完全相同的物理系統的系集 (如丟極多個相同的硬幣) 在同時作相同的實驗取樣數據的統計結果假設為相同時，此種假設即稱為「遍歷性假設」或「遍歷假設」。基於這個假設，對時間平均的統計方式及結果，便可由對系集的平均及統計方式得到。在一般物理系統中，尤其在統計力學範圖中，均採用此遍歷性假設為基本的假設。在流體力學中對亂流的實驗分析，亦是採用此假設。
遍歷 (Ergodic) 源於以下二個希臘詞：
* ergon (對應英語的 work)
* odos (對應英語的 path 或 way)
最初這是由奧地利物理學家波茲曼 ([Ludwig Boltzmann](https://en.wikipedia.org/wiki/Ludwig_Boltzmann)) 於統計力學領域 (statistical mechanics) 提出的概念，其一廣為人知的結果是：在經過長時間後，時間平均將會趨近空間平均。此事實在動力系統扮演極重要的角色，在隨機分析領域亦然。
因此，若貿然將 traverse 翻譯為「遍歷」，一來語意不清，二來增加和理工多項領域專業人員的溝通成本，實在得不償失。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
我們輸入 `pos` 和 `n` 作為暫定的指標讓此巨集<s>遍歷</s> 串列，因為 `n` 是指向 `pos` 的下一個 element，因此在釋出 `pos` 時，我們仍然可以繼續往後找到下一個 element。
我選擇使用 `q_release_element` 釋出一個 element 的位址，這個巨集的功能包含釋放傳入的 `element_t` 的 `value` 以及指標本身。如果不使用此巨集也可以用 `free` 來完成釋放記憶體的動作。
### q_insert_head / q_insert_tail
指派一個空間給我們要插入的節點，大小設定為一個 `element_t` 的大小。接著定義這個節點的 `value` 空間，大小是變數 `s+1` 的長度乘上一個 `char` 的長度，使用 [memcpy](https://cplusplus.com/reference/cstring/memcpy/) 把 `s` 的資訊傳入新節點的 `value`。最後確認 `string` 的最後一個`char` 是空後，把這個節點用`list_add`加到`head`指到的位置即可。若是 `q_insert_tail` 則是使用 `list_add_tail` 。
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
> 已更改
:::
### q_remove_head / q_remove_tail
首先需要對傳入的 `head` 作判斷，若 `head` 是 empty 或 NULL 都需要回傳 `NULL` ，不繼續進行移除的動作。這兩個函式主要想要做的除了移除串列的第一個 / 最後一個節點之外，也需要將節點中的 `value` 存進大小為 `bufsize` 的 `sp` 中，可以使用 [strncpy](https://cplusplus.com/reference/cstring/strncpy/) 將 `value` 複製到 `sp`。
### q_size
使用 `list_for_each` 逐個走訪串列中的每個 element，並使用變數 `count` 累計個數。
### q_delete_mid
最常見的作法就是使用快慢指標來找到一個串列的中點，也就是讓快指標的前進速度是慢指標的兩倍，當快指標到達整個串列的最後一個節點（快指標的 `next` 指向 `head`）時，慢指標會指向整個串列的中點，因此我們就可以繼續進行刪除節點的動作。但針對環狀串列也可以使用另一種反向迭代的方式實作，我們可以設置一個指標持續往後，一個指標持續往前，在兩個指標相遇的地方（或是往前指標的 `next` 是往後指標指向的節點，因串列節點個數是奇是偶而異）就是中點。
:::danger
對照 Dictionary.com 對 [implement](https://www.dictionary.com/browse/implement) 一詞的解釋:
* to fulfill; perform; carry out:
* to put into effect according to or by means of a definite plan or procedure.
* Computers. to realize or instantiate (an element in a program), often under certain conditions as specified by the software involved.
* to fill out or supplement
「實作」會是符合上述 "implement" 語意的譯詞，取「起」以「創作」的意思，而「製造」本質上是固定輸入並通常產生固定輸出的行為。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
> 使用快慢指標的缺點在於快指標每次移動會需要執行 `next` 兩次，加上慢指標每次移動執行 `next` 一次，因此每次移動需要三次讀取記憶體的時間：而使用反向迭代的優勢在於兩個指標每次移動都只需要執行 `next` 一次，所以每次移動只需要兩次讀取記憶體的時間，在兩種方式的時間複雜度都為 $O(\frac{n}{2})$的情況下，反向迭代的方式又更有效率。
:::warning
考慮到環狀雙向佇列的特性，改進現有的程式碼。
:::
### q_delete_dup
想法是在<s>遍歷</s> 串列前，設置一個 `bool flag=false`，如果串列前後的節點有相同的 `value` ，則會讓 `flag=true` 並執行刪除節點的動作。
一開始<s>遍歷</s> 節點和針對要不要刪除該節點的判斷式寫法如下：
```c
list_for_each_safe (pos, n, head) {
element_t *pos_element = list_entry(pos, element_t, list);
char *n_val = list_entry(n, element_t, list)->value;
if (strcmp(pos_element->value, n_val) == 0 || flag) {
/*刪除節點*/
}
```
其中， [strcmp](https://www.programiz.com/c-programming/library-function/string.h/strcmp) 是用來比較兩個位址所存的字串是否相同的函式。
這樣會產生下面的錯誤：
```text
Segmentation fault occurred. You dereferenced a NULL or invalid pointerAborted (core dumped)
```
原因是當 `pos->next==head` ，我們在用 `list_for_each_safe` <s>遍歷</s> 串列時宣告的 `char *n_val = list_entry(n, element_t, list)->value;` 不會有 `value` 值，因此在執行 `strcmp` 時就會產生 Segmentation fault，因此做了以下修正。
```c
if (pos->next != head &&
(strcmp(pos_element->value, n_val) == 0 || flag)) {
if (flag == true)
flag = false
else
flag = true
list_del(&pos_element->list);
q_release_element(pos_element);
}
```
在大部分的測資中，這個程式都可以成功的將重複的節點移除，但是遇到最後一個節點同時也是需要被移除的情況時，會出現下面的錯誤訊息：
```text
ERROR: Duplicate strings are in queue or distinct strings are not in queue
```
這是因為在<s>遍歷</s> 到最後一個節點且該節點也需要被移除的情況下，會因為 `pos->next==head` 的原因沒辦法進入刪除節點的判斷式對最後一個節點作刪除的動作，因此將與 `flag` 有關的判斷獨立出來以避免最後一個節點沒有辦法被刪除的情況發生。
```c
if (pos->next != head && strcmp(pos_element->value, n_val) == 0) {
flag = true;
list_del(&pos_element->list);
q_release_element(pos_element);
} else if (flag) {
flag = false;
list_del(&pos_element->list);
q_release_element(pos_element);
}
```
### q_swap
初始化一個 `bool odd=false` 用來判斷是否要做 swap 的動作。使用 `list_for_each_safe` <s>遍歷</s> 串列時，如果串列的順序是偶數，則用 `list_move(pos, pos->prev->prev)` 移動該節點至前一個節點前面。
### q_reverse
一開始的想法是另外用一個指標作為轉換的暫存，像是要交換兩個物件的位置一樣的概念，但是查資料時看到更好的作法：[zeddyuu](https://github.com/zeddyuu) 的作法更精簡也更不容易在指派指標時產生混亂，程式碼如下：
```c
struct list_head *pos, *n;
list_for_each_safe (pos, n, head) {
list_del(pos);
list_add(pos, head);
}
```
這個作法的概念是使用 `list_for_each_safe` 巨集來<s>遍歷</s> 串列中的節點，若查看 [linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h#L682) 中此巨集的程式：
```c
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; \
!list_is_head(pos, (head)); \
pos = n, n = pos->next)
```
`pos` 在巨集中被定義為 `head->next`，而 `n` 則是被定義為 `pos->next`。因此在原本的程式中，使用 `list_del` 將 `pos` 指向的節點從串列中移除，再將該節點用 `list_add` 加在 `head` 指向的節點之前，隨著 `pos` 指標在串列的逐個走訪過程，節點會被一個個移除並加到新串列的最前面，因此就可以達到反轉串列的效果。
:::danger
1. 改進你的漢語表達。
2. 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
> <s>已更改</s>
> 不要急著宣稱「已更改」，你的漢語表達真的明確嗎？例如「再將該節點用 `list_add` 加在當前 `head` 指向的節點之前」，是否會讓人誤解為「`head` 不只有『當前』，也有『以前』或『未來』呢？」清晰流暢又明確的漢語很難，值得我們反覆推敲，這也是工程素養的一環：做好溝通的準備。
$\to$ [沒有中國用語的一年 (2024 年第 4 週)](https://www.thenewslens.com/feature/366days/199104)
:::
### q_reverseK
因為前面已經有實作過 `reverse` ，因此想法是將 k 個節點切除來，呼叫 `q_reverse` 將其反轉之後再連接回原本的串列。將節點切出來成一個新的串列的動作透過 [list_cut_position](https://www.unix.com/man-page/centos/9/list_cut_position/) 完成，我們也需要宣告一個指針來紀錄當前位置，來得知下一次要切的節點位置。
### q_sort
這個函式隱藏的要求是時間複雜度必須為 $N\log{N}$ 。若使用時間複雜度為 $N^2$ 的排序演算法會造成超時，也就表示不能使用 bubble sort, selection sort 這些排序演算法。這邊選擇實作 [merge sort](https://alrightchiu.github.io/SecondRound/comparison-sort-merge-sorthe-bing-pai-xu-fa.html) 演算法來對串列進行排序。
:::danger
對照 Dictionary.com 對 [implement](https://www.dictionary.com/browse/implement) 一詞的解釋:
* to fulfill; perform; carry out:
* to put into effect according to or by means of a definite plan or procedure.
* Computers. to realize or instantiate (an element in a program), often under certain conditions as specified by the software involved.
* to fill out or supplement
「實作」會是符合上述 "implement" 語意的譯詞，取「起」以「創作」的意思，而「製造」本質上是固定輸入並通常產生固定輸出的行為。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
整個實作的流程可以分為以下兩個大方向：
* 將串列分成兩等分(`q_sort`)
這個部份使用快慢指標的方式找到串列的中點，並呼叫 `list_cut_position` 巨集把串列一分為二( left 和 right )。不斷的重複這個流程直到串列無法再分割為止（遞迴的寫法）。
* 將串列依照順序合併( `q_merge_two` )
這個函式是自行定義的，用來合併兩個已排序過的串列。我們先初始化一個新的串列( `new_list` )，用來儲存排序後的節點。在兩個要比較的串列中都還有節點的情況下，宣告兩個指標分別指向兩個串列中最左邊(值最小)的節點，開始對兩者做比較：
* 比較小的節點會使用 `list_move_tail` 被移動到 `new_list` 的尾端，然後該串列的指標會向右移動一個節點，進行下一次的比較。
* 最後比較完後，可能會因為其中一個串列比另一個串列多一個節點，而需要進行另外的處理，因此我們使用 [list_splice_tail_init](https://archive.kernel.org/oldlinux/htmldocs/kernel-api/API-list-splice-tail-init.html) 將最後還未被添加到排序後的串列的節點加到 `new_list` 中。
* 再將排序之後的新串列加回原本的 left 串列中即完成 sort 的動作
:bulb: 原本判斷如果 left 的大小不為 0，則將 left 加到 `new_list` 中，否則將 right 加到 `new_list` 中，但是這樣在執行多筆測資時會造成超時的錯誤，因為這種做法還會需要考慮到執行 `q_size` 這個函式的時間。因此我們直接將判斷式移除，對兩個串列可能剩下的節點都執行加到 `new_list` 的動作以避免超時的問題發生。
```diff
- q_size(left) ? list_splice_tail(left, &new_list)
- : list_splice_tail(right, &new_list)
+ list_splice_tail_init(left, &new_list);
+ list_splice_tail_init(right, &new_list);
```
> [commit e312a1d](https://github.com/sysprog21/lab0-c/commit/e312a1da57bd7cece261059e79cdc35c19dc00f6)
:::danger
使用 `git diff` 或 `diff -u` 命令來產生程式碼之間變異列表，不要憑感覺填入，注意位移量。
:::
### q_ascend / q_descend
這個函式的要求是「只要這個節點的右邊有比他更小的值存在，就刪除該節點」。因此我的想法是，我們可以從串列的最後一個節點開始往前<s>遍歷</s> 節點，並且記錄最小的節點值，如果在往前<s>遍歷</s> 的過程中，遇到比該數值大的節點，就對其進行刪除。同理， `q_descend` 則是記錄最大的節點值，如果在往前<s>遍歷</s> 的過程中，遇到比該數值小的節點，就對其進行刪除。
### q_merge
在實作 q_merge 這個函式之前，我們需要先了解 `queue_contex_t` 的架構。從 [queue.h](https://github.com/sysprog21/lab0-c/blob/master/queue.h) 這個檔案中我們可以找到這個架構的描述與內部細節：
```c
/**
* queue_contex_t - The context managing a chain of queues
* @q: pointer to the head of the queue
* @chain: used by chaining the heads of queues
* @size: the length of this queue
* @id: the unique identification number
*/
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;
```
* `q` ：指向 queue 的指標，queue 裡面存的是我們要合併的 circular doubly linked list
* `chain` ：連接每個 `queue_contex_t` 的 `list_head`
* `size` ：指 queue 的大小
* `id` ：代表每個 `queue_contex_t` 獨特數值
作法是定義一個 `struct list_head first` 並用 `INIT_LIST_HEAD` 做初始化，用這個 `list_head` 作為合併之後的儲存新串列的位置。合併兩個串列使用的是前面有實作過的 `q_merge_two` 函式。最後需要留意的是，我們要將合併好的串列移動到 `head` 指到的節點中的 `q` 中，如以下的程式所示: 首先找到 `head->next` 這個節點的 `q` 指標，再用 `list_splice_tail` 將 `first` 指向的串列移動到 `q` 指標指向的位置。
```c
list_splice_tail(&first, list_entry(head->next, queue_contex_t, chain)->q);
```
回傳的串列大小（ type: `int`）使用 `q_size` 作計算。
## 在 qtest 提供新的命令 `shuffle`
根據 [說明](https://hackmd.io/@sysprog/linux2024-lab0-d#%E5%9C%A8-qtest-%E6%8F%90%E4%BE%9B%E6%96%B0%E7%9A%84%E5%91%BD%E4%BB%A4-shuffle) 中，我們要利用 [Fisher-Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm) 來實作洗牌。為了證明這種方式是隨機且沒有偏好的，我們希望最後測試的結果中，每一種排列出現的次數要大致上相等。舉例來說，如果我們的串列中有四個節點，那我們總共就會有 $4! = 24$ 種排列方式，給定每種排列方式一個編號，統計進行 $10^6$ 次 shuffle 後每次排列出現的次數，
執行 [lab0-d](https://hackmd.io/@sysprog/linux2024-lab0-d#%E6%B8%AC%E8%A9%A6%E7%A8%8B%E5%BC%8F) 提供的測試腳本後，結果如下所示：
```
$ ./scripts/test_shuffle.py
Expectation: 41666
Observation: {
'1234': 41844, '1243': 41892, '1324': 41579,
'1342': 41721, '1423': 41520, '1432': 41971,
'2134': 41454, '2143': 41743, '2314': 41488,
'2341': 41847, '2413': 41903, '2431': 41652,
'3124': 41556, '3142': 41770, '3214': 41848,
'3241': 41606, '3412': 41490, '3421': 41944,
'4123': 41768, '4132': 41466, '4213': 41268,
'4231': 41303, '4312': 41710, '4321': 41657
}
chi square sum: 21.357269716315457
```
Chi-square test statistic $X^2 = \Sigma_{i=1}^n \frac{(O_i - E_i)^2}{E_i}$
從結果中我們可以得知 expectation $E = 41666 (= 10^6 / 24)$, chi square sum $X^2 = 23.203235$。因為我們的測資 shuffle 4 個數字，因此共有 24 種組合方式，自由度為 $24 - 1 = 23$，對照 [Chi-Square Distribution Table](https://www.accessengineeringlibrary.com/content/book/9780071795579/back-matter/appendix5) 可以得知，因為 $X^2$ 介於 18.1 和 22.3 之間，所以其 P value 介於 0.25 和 0.5 之間。拒絕虛無假說( $H_0$ )的前提在於觀察到的結果須有統計顯著性，也就是 P value 要小於 $\alpha = P(拒絕 H_0｜H_0 為真) = 0.05$，然而我們測試得到的結果並不滿足此條件，因此無法「推翻樣本資料不拒絕 shuffle 的結果遵循 Uniform distribution」的論點。
### q_shuffle
實作這個函式的想法是：我們從最後一個 list 的節點(`tail`)開始往前走，讓每一次被交換的節點不會重複。針對隨機產生的數值，使用 `new` 搭配 for loop 去指到對應的節點位置，如果 `tail == new`，則代表不需要進行互換的動作。兩個節點交換位置的動作則是由四個步驟完成：先用 `temp` 指向 `new` 前面的節點，再將 `new` 指向的節點移到 `tail` 的位置，最後把 `tail` 移動到 `temp` 的位置，之後更新 `tail` 指標即可完成整個交換的動作。
```c
for (tail = head->prev; tail != head; tail = tail->prev, size--) {
struct list_head *new = head->next;
for (int j = rand() % (size + 1); j > 0; j--)
new = new->next;
if (tail == new)
continue;
struct list_head *temp = new->prev;
list_move(new, tail);
list_move(tail, temp);
tail = new;
}
```
---
## 論文閱讀 <[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)>
這篇論文提出了 [deduct](https://github.com/oreparaz/dudect)，來檢測一段程式的執行是否為 constant time。跟當前已有的 ctgrind 和 stverif 等相比，這個工具較不受硬體的限制，此外，deduct 使用時間統計分析( statistical analysis )而不是 [靜態程式分析](https://en.wikipedia.org/wiki/Static_program_analysis)，因此降低對於硬體的要求。
作者使用的方式是基於 leakage detection time，檢測程式的執行是否為 constant time，分成下列三個步驟執行：
1. Measure execution time
* Class definition: 輸入兩個類型的資料(一種為固定的測資，另一種為隨機的測資)，對兩者作測量和比較，此論文使用的是fix-vs-random test。
* Cycle counter：用 CPU 中提供的 cycle counter 可以精準的計算執行時間。
* Environment conditions：想要降低環境變因對實驗產生的差異，所以每次執行測量都會隨機的對應一個類別。
2. Apply post-processing
* Cropping：主要的測量會因為作業系統或是外部函式而產生 positive skewed ，因此想透過 cropping 把超過 threshold 的值給濾除。
* High-order preprocessing：透過 high-order preprocessing 可能可以有更好的效果。
3. Apply statistical test
* t-test: 使用 [Welch's t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test) 試圖推翻 null hypothesis 所說的兩個時間的分佈相同的論點。
* [Non-parametric tests](https://zh.wikipedia.org/zh-tw/%E7%84%A1%E6%AF%8D%E6%95%B8%E7%B5%B1%E8%A8%88): Kolmogorov-Smirnov，在樣本數不多時，計算相對簡單的統計方式。
## deduct
:::danger
這裡是「測試項目」(item)，而非「測試資料」(data)，查閱辭典以理解二者的差異。
command 是「命令」，而非「指令」(instruction)
> 項目：事物分類的條目
> 資料：可供參考或研究的材料或記錄 ; 計算機中一切數值、記號和事實的概稱
>
> 因此針對測試的每一個條目，使用項目一詞會比資料準確
:::
在執行 `make test` 時，第 17 筆測試項目會無法通過測試，細看裡面給的命令 ：
```
option simulation 1
it
ih
rh
rt
option simulation 0
```
在 `qtest.c` 中，`simulation` 會呼叫 `is_insert_tail_const`() 或 `is_insert_head_const()` 來對 `insert_head()` 與 `insert_tail` 做執行時間使否為 constant time 的檢查。這兩個函式放置的位置可以從 `/deduct/fixture.h` 中得到一些線索。`fixture.h` 中定義了 `DUT_FUNCS`，註解中提到他正是測試函式執行是否為 constant time 的界面。
```c
#include "constant.h"
/* Interface to test if function is constant */
#define _(x) bool is_##x##_const(void);
DUT_FUNCS
#undef _
```
繼續追蹤到 `fixture.h` 中引用的標頭檔 `constant.h`，我們可以看到被定義的 `DUT_FUNCS`，裡面包含了四個函式，也就是第 17 筆測資中要測試的四個函式：
```c
#define DUT_FUNCS \
_(insert_head) \
_(insert_tail) \
_(remove_head) \
_(remove_tail)
```
我們回到 `fixture.c` 去查看檢查 constant time 的函式如何實作。實際執行的主要程式是 `static bool doit(int mode)` 函式，觀察其與 [deduct 原始程式碼](https://github.com/oreparaz/dudect/blob/master/src/dudect.h#L298)的 `main` 函式的差異，我們可以發現 `doit` 中缺少的是對 `percentile` 閾值控制的實作，因此我們須將其補上。
```diff
+#define NUM_PERCENTILES 100
static bool doit(int mode)
{
int64_t *before_ticks = calloc(N_MEASURES + 1, sizeof(int64_t));
int64_t *after_ticks = calloc(N_MEASURES + 1, sizeof(int64_t));
int64_t *exec_times = calloc(N_MEASURES, sizeof(int64_t));
uint8_t *classes = calloc(N_MEASURES, sizeof(uint8_t));
uint8_t *input_data = calloc(N_MEASURES * CHUNK_SIZE, sizeof(uint8_t));
+ int64_t *percentiles = calloc(NUM_PERCENTILES, sizeof(int64_t));
...
}
```
並對其作宣告：
```c
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];
}
```
deduct 在 `update_statistics` 函式中，基於 `percentiles` 執行了多次的 cropping，是我們在 `fixture.c` 中沒有實作到的，因此我們將該部份的程式移植到 `fixture.c` 中，並將 `percentiles` 參數傳入 `update_statistics` 並修改其格式：
```c
for (size_t crop_index = 0; crop_index < NUM_PERCENTILES; crop_index++) {
if (difference < percentiles[crop_index]) {
t_push(t, difference, classes[i]);
}
}
```
回去細看 `main` 中的程式碼，發現在呼叫 `update_statistics` 前，也呼叫了 `prepare_percentiles`。因此我們也在 `fixture.c` 中加入此函式及相關的函式。
```c
static int cmp(const int64_t *a, const int64_t *b)
{
return (int)(*a - *b);
}
static void prepare_percentiles(int64_t *percentiles, int64_t *exec_times)
{
qsort(exec_times, N_MEASURES, sizeof(int64_t), (int (*)(const void *, const void *))cmp);
for (size_t i = 0; i < NUM_PERCENTILES; i++) {
percentiles[i] = percentile(
exec_times, 1 - (pow(0.5, 10 * (double)(i + 1) / NUM_PERCENTILES)),
N_MEASURES);
}
}
```
:::danger
本處指「測試項目」(item)，而非「測試資料」，參閱辭典以理解詞彙間的差異。
:::
修改後結果：第 17 筆測試項目可以成功通過
```shell
+++ 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
```
> [commit 4a6f652](https://github.com/sysprog21/lab0-c/commit/4a6f6521463bc96a2cb4cff585c54fed08e50219)
## 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
以下的程式的目的是在 `list_sort.c` 中，使用 `cmp` 這個比較函式對串列進行排序：
```c
__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
struct list_head *list = head->next, *pending = NULL;
size_t count = 0; /* Count of pending */
if (list == head->prev) /* Zero or one elements */
return;
/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;
```
根據 [gcc 文件](https://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Variable-Attributes.html) 中對 `__attribute` 的定義：
> The keyword __attribute__ allows you to specify ==special attributes== of variables or structure fields. This keyword is followed by an attribute specification inside double parentheses. Some attributes are currently defined generically for variables. Other attributes are defined for variables on particular target systems. Other attributes are available for functions (see Function Attributes) and for types (see Type Attributes). Other front ends might define more attributes (see Extensions to the C++ Language).
亦即 `__attribute__((nonnull(2,3)))` 在 `__attribute__` 中輸入了屬性 `nonnull'`，告訴編譯器函式 `list_sort` 期望第二和第三個參數( `head` 和 `cmp` )不為空指針，這個設定會讓編譯器在 `head` 或 `cmp` 是空指針時產生警告。
在 `list_sort` 的函式內部，將 `list` 初始化為串列的第一個節點，而 `pending` 設置為 `NULL`; `count` 是用來計算串列中待處理節點的數量，先將其設置為 0。如果串列中只有零個或一個節點，則不需要進行排列，直接返回。最後將串列的最後一個節點的 `next` 指標設為 `NULL`，變成一個單向的 linked list。
根據在 [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 中對於 merge sort 的註解：
```c
/* This mergesort is as eager as possible while always performing at least
* 2:1 balanced merges. Given two pending sublists of size 2^k, they are
* merged to a size-2^(k+1) list as soon as we have 2^k following elements.
*
* Thus, it will avoid cache thrashing as long as 3*2^k elements can
* fit into the cache. Not quite as good as a fully-eager bottom-up
* mergesort, but it does use 0.2*n fewer comparisons, so is faster in
* the common case that everything fits into L1.
*/
```
Merge sort 的重點在於：
* 當有兩個 sublist 在待處理列表時，只要後續有 $2^k$ 個元素，這兩個 sublist 就會被合併為一個 $2^{k+1}$ 的 list。
* 要合併的兩個 sublist 必須要至少是 $2:1$ 的狀態，這是為了確保排序的效能與穩定性，需要確保兩個要合併的 sublist 長度不會相差過大
* 此設計的目的在於避免 cache 中有 $3 * 2^k$ 的元素時，不會有 cache thrashing 的情況發生; 如果能確保 cache 中可以容納 $3 * 2^k$ 個元素，則 cache thrashing 不會發生
* 雖然此方式不會比 fully-eager bottom-up mergesort(進可能力即將所有 sublist 合併的排序法)的效能還要好，但是在 cache 中可以容納 $3 * 2^k$ 個元素的情況下，這個方式會比較快(因為會執行較少的比較操作)
在 merge sort 的方式中，使用的是 `count` 來判斷是否進行合併的動作。[chloe0919](https://hackmd.io/9CKl_3L3Temd5ugu7iNOxA?both) 用了清楚的表示來呈現什麼時候應該要執行合併的動作，對其做 `count` 的補充：
*$\Longrightarrow$ : 進行合併*
* count = 1($0001_2$) | $2^0$
* count = 2($0010_2$) | $2^0$ + $2^0$ ( $2$ 的冪，不合併 )
* count = 3($0011_2$) | $2^0$ + $2^0$ + $2^0$ $\Longrightarrow$ $2^1$ + $2^0$
* count = 4($0100_2$) | $2^1$ + $2^0$ + $2^0$ ( $2$ 的冪，不合併 )
* count = 5($0101_2$) | $2^1$ + $2^0$ + $2^0$ + $2^0$ $\Longrightarrow$ $2^1$ + $2^1$ + $2^0$
* count = 6($0110_2$) | $2^1$ + $2^1$ + $2^0$ + $2^0$ $\Longrightarrow$ $2^2$ + $2^0$ + $2^0$
* count = 7($0111_2$) | $2^2$ + $2^0$ + $2^0$ + $2^0$ $\Longrightarrow$ $2^2$ + $2^1$ + $2^0$
一開始會先將串列的最後一個節點的 `next` 接到 `NULL`，讓串列變成單向而非雙向，接著透過下面的程式來觀察 `count` 如何將節點移動到待處理列表：
```c=
do {
size_t bits;
struct list_head **tail = &pending;
/* Find the least-significant clear bit in count */
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
/* Do the indicated merge */
if (likely(bits)) {
struct list_head *a = *tail, *b = a->prev;
a = merge(priv, cmp, b, a);
/* Install the merged result in place of the inputs */
a->prev = b->prev;
*tail = a;
}
/* Move one element from input list to pending */
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
} while (list);
```
在程式中的第 9 行是 `if(likely(bits))`，`likely` 這個巨集的目的是要幫助編譯器最佳化，與 `likely` 相對應的是 `unlikely`，這兩個巨集被定義在 [/include/linux/compiler.h](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h) 中，如下所示：
```c=
# ifndef likely
# define likely(x) (__branch_check__(x, 1, __builtin_constant_p(x)))
# endif
# ifndef unlikely
# define unlikely(x) (__branch_check__(x, 0, __builtin_constant_p(x)))
# endif
#define __branch_check__(x, expect, is_constant) ({ \
long ______r; \
static struct ftrace_likely_data \
__aligned(4) \
__section("_ftrace_annotated_branch") \
______f = { \
.data.func = __func__, \
.data.file = __FILE__, \
.data.line = __LINE__, \
}; \
______r = __builtin_expect(!!(x), expect); \
ftrace_likely_update(&______f, ______r, \
expect, is_constant); \
______r; \
})
```
其中，第 18 行的 `__builtin_expect` 會將工程師所希望的 branch 的資訊提供給 compiler，以便對程式碼的分之進行順序的調整，進而達到優化的效果，其中的 `!!(x)` 是為了確保輸出的值為 0 或 1。當在程式中寫到 `if(likely(x))` 時，代表 `x` 為 `true` 的機率比較大，告訴編譯器把 `x == true` 對應到的程式接在該判段式之後，這種作法可以增進程式效率的原因在於 cache 的 spatial locality 機制，當程式碼被在相近的位置時，他們可能會被一起移動到 cache 中，進而提升程式的效能。`likely / unlikely` 就是在將比較可能被執行的程式向前移，較不可能被執行到的程式向後移。
:::danger
上方的 `__branch_check__` 作用是什麼？參閱 Linux 核心的 git log 和 git blame 結果來探討。
:::
:::info
在 gcc 的文件中，對 [`__branch_check__`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fexpect) 有這樣的一段敘述：
> You may use __builtin_expect to provide the compiler with branch prediction information. In general, you should prefer to use actual profile feedback for this (-fprofile-arcs), as programmers are notoriously bad at predicting how their programs actually perform. However, there are applications in which this data is hard to collect.
舉以下例子做說明：
```C
if (__builtin_expect (x, 0))
foo ();
```
上述的程式指的是我們並不預期去呼叫 `foo` 函式，因為我們預期 `x` 的值為 0，而我們也可以使用以下程式對指標或浮點數做 `_builtin_expect_` 的判斷。
```C
if (__builtin_expect (ptr != NULL, 1))
foo (*ptr);
```
此外，[`__builtin_constant_p(x)`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fconstant_005fp) 巨集的功能在於判斷 `x` 在編譯時是否為常數，是則回傳 1 ，否則回傳 0。
在 `likely` 巨集的定義中，我們看到 `__brach_check(x, 1, __builtin_constant_p(x))`，`x` 是我們要進行分支預測的條件式; 第二個參數 `1` 則是對應 `likely` (預測為真); 第三個參數則是判斷如果 `x` 為常數，那在編譯器編譯時就可以知道 `x` 的數值，進而進行優化。
總而言之， `__branch_check` 是程式開發者向編譯器提供他們對分支的期望，以減少分支預測錯誤所帶來的影響。
:::
參考資料：[[Linux Kernel 慢慢學] likely and unlikely macro](https://meetonfriday.com/posts/cecba4ef/#%E5%89%8D%E8%A8%80)
回到 `list_sort` 的程式，在 while 迴圈中，我們首先會先使用一個 for 迴圈來找到 `count` 中的 least significant clear bit，當 `bits` 不為 0 時，代表有 sublist 可以進行合併，而 tail 會被移動到待 merge 的節點。然後在 if 判斷是否需要 merge，當 `count` 是 2 的冪，就不會進行 merge 的動作; 若否則會進行 merge，然後移動 pending 和 list 的位置，直到 list 沒有節點。pending 指向的是已經經過 merge 的節點序列，而 list 指向的是還沒經過 merge 的節點序列。
在 `merge` 函式中使用的是 `cmp` 巨集進行兩個節點大小的比較，`cmp(priv, a, b)` 大於零表示節點 a 的數值大於節點 b，因此要將 pending 先接 b 再接 a; 反之則先接 a 再接 b。`merge_final` 函式的目的則是將最後的節點與前面所有的節點做合併，即完成所有的合併動作。
我們在我們的專案中新建立 `list_sort.c` 和 `list_sort.h` 檔案來存 list sort 的程式，首先我們從 [linux / lib / list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 中找到 sort 相關的程式，並移植到我們的 `list_sort.c` 中，其中主要的程式是 `list_sort`，它會呼叫該檔案中的其他函式幫助它完成排序的動作，像是 `merge`、`merge final`、`cmp` 函式; 在 `list_sort.h` 中則是參照 [/include / linux / linux / list_sort.h](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h) 對 `list_sort.c` 中的函式進行宣告。
> [commit 961d263](https://github.com/sysprog21/lab0-c/commit/961d26371bbe58ec81e40b27e825bf2ac2f85121)
:::danger
這裡不是「指令」(instruction)。
:::
為了確保可以呼叫該函式，我們需要在 `qtest.c` 中增加對於 `list_sort` 函式的命令，對比於實作 `q_shuffle` 時直接在檔案中新增一個外部函式宣告 [extern](https://chenhh.gitbooks.io/parallel_processing/content/cython/c_syntax.html) 的指令，我們直接在開頭處引入 `list_sort.h` 的標頭檔。在 `qtest.c` 中新增 `q_shuffle` 外部函式宣告的原因在於，因為 `queue.h` 不接受更動，而 extern 的用途在於多文件專案中，C 語言允許程式碼分散在多個檔案中，分別編譯並連結到一起。因此我們透過外部宣告的方式來增加對 `q_shuffle` 函式的宣告。
> [commit c32e9b3](https://github.com/sysprog21/lab0-c/commit/c32e9b3b425bc863fd96c49b1c1ffd364bca212a)
:::danger
強調相互結合的意境時，譯作「[連結](https://dict.revised.moe.edu.tw/dictView.jsp?ID=64001)」，例如「動態連結函式庫」(dynamic-link library)，而強調資料因結合而呈現[鏈狀](https://dict.revised.moe.edu.tw/dictView.jsp?ID=3626)樣貌，用「鏈結」，如鏈結串列 (linked list)。
file 的翻譯是「檔案」，而非「文件」(document)。
:::
針對 timsort，我們參考[第一週測驗二](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-2)的演算法，將其加到我們新增的 `timsort.c` 和 `timsort.h` 中，整體流程與實作 `list_sort` 相似。
> [commit 01242b9](https://github.com/sysprog21/lab0-c/commit/01242b96437c047a2f722616e9acef57ca6cc5af)
#### 比較兩種 sort 方式的效能差異
首先我們針對兩者在對 1000000 個節點進行排序時所耗費的時間進行比較。因為我們可以使用 `make check` 針對 `trace / trace-eg.cmd` 單筆測試項目做測試，因此我修改了這個檔案以利我們做效能的評估。作法是分別建立兩個長度為 1000000 的串列，再用 `time` 這個命令去紀錄兩者在排序時所耗費的時間。以下是執行 `make check` 所得到的結果：
**List sort**
```shell
./qtest -v 3 -f traces/trace-eg.cmd
l = []
l = [xdokbai uvnqnwun kkjswothb ievvtgu ubgvh prvbsq aktzm yqrlsp uhnwf azoeomt ykxlnp gfvhsb yfuiucyhn abmapdsuk ilehuqagz uxicvm fsnqf yhpwxa nyuqqznv fxnajfzd iqbqzndq uukkcfyh krvfv zxtxke sogyqw pbavdamr rcwiill rwknjh yjlhukj ygdufhwt ... ]
l = [aaaab aaaaf aaaapnqv aaaaql aaabaomnu aaabh aaacjxk aaadawm aaadqxmj aaadzrysi aaadztjg aaaeniw aaaeryz aaaeti aaaeztt aaafl aaaflpcdn aaafu aaafur aaagaj aaagsbkp aaahl aaahteml aaaigqhe aaaij aaaiy aaaizcpb aaajaivf aaajc aaajl ... ]
Delta time = 0.836
l = NULL
Freeing queue
```
**Timsort**
```shell
./qtest -v 3 -f traces/trace-eg.cmd
l = []
l = [orklxqanp jmtabmkd tjkwjd bmxqwao vbibqsioc yrjvqb wchxjr tjzeuhy bhgrzatb qycdsgy iogaxquc xeqbs sgvdxn bijljrpc wzbjb aozqo dhtdcpnd ltizvnag yysjpcr vchxo gchpr unovk qydpa fbsev pjmnja blkkjbfvc dexvyxtls coxpok dztdw ciftlb ... ]
l = [aaaacdv aaaaiiof aaaau aaabk aaaccmkxh aaacjb aaacuba aaadsap aaaec aaaehrtf aaaenepov aaaeulzb aaaewvc aaafbyq aaafmfj aaafndmu aaagb aaagoeox aaahcgoaa aaahnkrz aaahts aaajfnp aaajkkw aaajubwra aaalen aaalqrhg aaamaobdv aaamg aaamrfb aaandq ... ]
Delta time = 1.203
l = NULL
Freeing queue
```
由於 merge sort 在排序 1000000 個節點時會有 `Time Limit Exceeded` 的問題發生，因此我們將串列節點個數調整為 100000 個再進行執行時間的測試：
| | list sort | tim sort | merge sort |
| -------- | -------- | -------- | -------- |
| Execution time | 0.040 | 0.050 | 0.119 |
從執行時間我們可以看到 list sort 所耗費的時間較 timsort 短，推測是因為我們的串列序列是亂數生成的，而 timsort 主要適用的情境是在子串列已有排序時，排序會較快速。此外，我們從 `list_sort.c` 和 `timsort.c` 的程式碼中可以觀察到：兩種排序方式所採用的比較節點大小的方式都是用 `cmp` 這個函式，因此如果能夠知道在該排序方式中，進入到 `cmp` 函式中的次數，也能夠得知該排序方式的效率。
在測試項目有部份排序的情況下，我們再對三個排序演算法的執行時間進行觀察，串列的節點數一樣為 100000 個：
| | list sort | tim sort | merge sort |
| -------- | -------- | -------- | -------- |
| Execution time | 0.043 | 0.041 | 0.086 |
可以看到在這個測試項目下， timsort 的執行時間的確比 list sort 還要短，驗證了我們的猜想。
### Valgrind 分析記憶體問題
[Valgrind](https://valgrind.org/) 是一個可以檢測 C / C++ 程式碼中記憶體相關問題的工具，舉例像是 memory leak、invalid memory access、buffer overflow 等; 它同時也可以對程式進行效能的分析。確實的管理記憶體重要的地方在於可以避免資源的浪費、性能下降以及一些不可預測的行為，降低可能會影響我們程式執行結果的變因。
在對測試項目進行 Valgrind 測試之前，我們需要了解 `make` 這個指令運作的方式。從 `Makefile` 中我們可以看到 `make` 後面可以加的指令，像是我們如果執行 `make check`，則會因為 `Makefile` 中下面的程式碼，讓我們可以執行 `traces/trace-eg.cmd` 中的命令，再連結到 `qtest.c` 中各個命令對應到的函式呼叫與檢查，我們就可以針對不同命令的組合測試我們的函式是否有正確的執行。
```cmake
check: qtest
./$< -v 3 -f traces/trace-eg.cmd
```
為了針對函式做記憶體相關的測試，我們可以在 `Makefile` 中新增一個 `make` 的指令來完成這件事：
```cmake
check-massif: qtest
valgrind --tool=massif ./$< -v 3 -f traces/trace-massif.cmd
```
這個命令會使用 Valgrind 中的 massif 工具，針對 `traces/trace-massif.cmd` 做測試。Valgrind 中提供[不同的工具](https://valgrind.org/info/tools.html)讓我們測試，而 Massif 是一個 cache 的分析器，這個工具會繪製圖表，呈現 heap 隨著時間的使用量，包含程式碼中的哪一個部份造成最多記憶體的配置。為了做此分析， massif 會讓程式執行的速度慢 20 倍。
執行 `make check-massif` 這個命令後， massif 會開始對指定檔案的內容進行分析，並輸出一張 `massif.out.xxxxxx` 形式的圖表，我們可以使用 `ms_print` 這個命令將圖表呈現於 terminal 中。下面的圖表呈現了針對 `q_insert_head` 的測試結果。
```shell
Command: ./qtest -v 3 -f traces/trace-massif.cmd
Massif arguments: (none)
ms_print arguments: massif.out.162326
--------------------------------------------------------------------------------
MB
1.299^ #
| @ @ #
| @ @ #
| @ @ #
| @ @ : #
| : @ @ : #
| : : @ @ @ : #:
| : ::@ @ : @ : #:
| : : : ::@ @ : : @ : #:
| : : : : ::@ @: : : :@ :@ #:::
| ::: : : : ::@ : @: : : :@ :@ : #:::
| ::: : : : @ :: @ : ::@ :: @: : : :@ : ::@ : #:::
| : ::: : : : @ : @ : ::@ :: @: : : :@ : ::@: : #:::
| : ::: : : :: @ : @ : ::::@ ::::@: : : :@ : ::@: : #::::
| : ::::: : : :: @ : @ : : ::@ ::::@: : : :@ : ::@:::: #::::
| : ::::: : : :: @ @ : :@ : : ::@::::::@::::: :@ ::::@:::: #::::
| : ::::: :: : :: @ @ :: :@:: : ::@: ::::@::::: :@ ::::@:::: #::::
|:: ::::: :: :::: :::@: @ :: :@:: : ::@: ::::@:::::@:@ ::::@:::: #::::
|:: :::::: :: :: : :::@: @ :: :@:::: ::@: ::::@:::::@:@ ::::@:::::#::::
|::::::::: :: :: :::::@: :@:@:: :@:::: ::@: ::::@:::::@:@:::::@:::::#::::
0 +----------------------------------------------------------------------->Gi
0 13.81
Number of snapshots: 95
Detailed snapshots: [24, 28, 30, 34, 42, 49, 59, 65, 75, 85, 86 (peak)]
```
在[文件](https://valgrind.org/docs/manual/ms-manual.html)中有說明如何觀察產生的圖表，每行代表該瞬間的 snapshot，在此例子中共有 95 個 snapshot，每一個 snapshot 代表的是每次 heap 的存取紀錄。Massif 的特性在於，一開始它會對每次 heap 的存取做 snapshot，但隨著程式執行時間的推進，它會減少 snapshot 的次數或是丟棄較舊的 snapshot，旨在保留合理數量的 snapshot。
一般的 snapshot 會用 `:` 表示; 而包含比較多細節的 snapshot 是用 `@` 表示，同時也會在圖表下面的 'Detailed snapshots' 中標示; 包含最高峰( peak )的 snapshot 用 `#` 表示。而最高峰的出現只會發生在釋放存取後，避免每次大量存取 heap 後都會產生一個最高峰。但這也表示如果程式沒有釋放存取的情況下，就不會紀錄到任何最高峰。
```shell
--------------------------------------------------------------------------------
n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B)
--------------------------------------------------------------------------------
87 14,028,501,660 713,472 632,723 80,749 0
88 14,143,262,552 1,017,256 898,706 118,550 0
89 14,258,023,487 767,656 680,480 87,176 0
90 14,372,784,448 320,792 289,913 30,879 0
91 14,487,545,318 787,704 698,127 89,577 0
92 14,602,306,150 525,944 469,308 56,636 0
93 14,717,066,978 441,248 395,151 46,097 0
94 14,831,827,934 482,832 431,743 51,089 0
```
Massif 也針對每個 snapshot 給出更精細的數據(如上表所示)，也可以使用 `massif-visualizer` 畫出可視化效果更好的圖：
Sign in with Wallet
Connect another wallet