2024q1 Homework1 (lab0)

# 2024q1 Homework1 (lab0) contributed by < [wu81177](https://github.com/wu81177/lab0-c) > ## 開發環境 ```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: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz CPU family: 6 Model: 140 Thread(s) per core: 2 Core(s) per socket: 4 Socket(s): 1 Stepping: 1 CPU max MHz: 4700.0000 CPU min MHz: 400.0000 BogoMIPS: 5606.40 ``` ## 指定的佇列操作 ### `q_new` 實作 `q_new` 過程中，我學習到 `list.h` 中 `list_head` 和 `INIT_LIST_HEAD` 的部份 #### `LIST_HEAD` 從結構成員可以發現 `list_head` 組成的佇列是雙向佇列，同時我也理解到 `list_head` 除了獨立當作佇列的頭，也會嵌入佇列成員結構體中，佇列成員在這份作業中為 `element_t` #### `INIT_LIST_HEAD` 此<s>函數</s> 函式是用來初始化已存在的 `list_head` ，如果要同時宣告並初始化可用 `LIST_HEAD（）` :::danger 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利) ::: ### q_free `list_for_each_safe` 和 `list_for_each_entry_safe` 都能確保釋放當前節點不會遺失下一個節點，然而後者有使用 `list_entry` ，選用它就能輕鬆獲得元素的指標並釋放成員迴圈中使用 `q_release_element` 來釋放空間，最後再釋放 head :::danger 改進你的漢語表達。 ::: 而在運行 `q_test` 的時候發現有問題因此使用 Valgrind 檢查，以下為檢察結果 : ``` ERROR: Attempted to free unallocated block. Address = 0x4b8e850 ==31792== Invalid read of size 8 ==31792== at 0x10F43C: find_header (harness.c:98) ==31792== by 0x10F43C: test_free (harness.c:181) ==31792== by 0x10F72E: q_release_element (queue.h:120) ==31792== by 0x10F72E: q_free (queue.c:30) ... ``` 發現少檢查 head 為空的情況 ```diff void q_free(struct list_head *head) { + if (!head) + return; element_t *entry, *safe; list_for_each_entry_safe (entry, safe, head, list) q_release_element(entry); free(head); } ``` ### q_insert_head & q_insert_tail 原先 `value` 是直接使用 `s` 的空間，後來參考別人的發現應該使用 `strdup` ，因為 `s` 可能會被改動 ```diff bool q_insert_head(struct list_head *head, char *s) { if (!head) return false; element_t *e = malloc(sizeof(element_t)); if (!e) return false; - e->value = s; + e->value = strdup(s); list_add(&e->list, head); return true; } ``` 使用 `list_add` 可以將新元素放置在 head 後面， `list_add_tail` 則可以放到 head 前面發現應該要檢查 `strdup` 是否成功，如果失敗應該要釋放當前元素，如下 ```diff bool q_insert_head(struct list_head *head, char *s) { if (!head || !s) return false; element_t *e = malloc(sizeof(element_t)); if (!e) return false; e->value = strdup(s); + if(!e->value){ + free(e); + return false; + } list_add(&e->list, head); return true; } ``` ### q_remove_head & q_remove_tail 從 `list.h` 中可以發現 `container_of` 和 `list_entry` 的功能完全相同，我選擇了前者來獲取 `element_t` 的指標移除元素有 `list_del` 和 `list_del_init` 可用，我選用後者，否則再次使用已移除的元素時可能會出錯 * 發現沒有排除佇列為空的情況，原先的程式在下列第四行會出錯 ```diff - if (!head) + if (!head || list_empty(head)) return NULL; element_t *e = container_of(head->next, element_t, list); ``` ### q_size 使用 `list_for_each` 走訪佇列並且計數 ### q_delete_mid 我使用的方法是從鏈結串列頭 head 出發，同時使用兩個指標進行走訪，一個指標順行，另一個指標則逆行，直到它們相遇（奇數個元素情況）或者在交會前一步（偶數個元素情況）再刪除順行指標所指向的元素 * 發現使用 `q_release_element` 後再用 `free` 釋放元素內容是多餘的 ```diff bool q_delete_mid(struct list_head *head) { if (!head || list_empty(head)) return false; struct list_head *forward = head->next; struct list_head *backward = head->prev; while (forward != backward && forward->next != backward) { forward = forward->next; backward = backward->prev; } element_t *e = container_of(forward, element_t, list); list_del(forward); q_release_element(e); - free(forward) return true; } ``` :::danger :warning: 留意詞彙的使用： * [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary) * [詞彙對照表](https://hackmd.io/@l10n-tw/glossaries) ::: ### q_delete_dup 使用兩層迴圈比對，原本都想用 `list_for_each` ，後來發現會重複比對，改成以下這樣 ```diff list_for_each (outer, head) { - list_for_each(inner, head){ + for (inner = (outer)->next; inner != (head); inner = inner->next) { ... } } ``` 發現當沒有元素或單元素應該 return true ```diff - if (!head || head->prev == head->next) { + if (!head) return false; + if (head->prev == head->next) + return true; ``` 原先的寫法一直無法順利運作 <s> bool q_delete_dup(struct list_head *head) { // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ if (!head || head->prev == head->next) { return false; } struct list_head *outer, *inner, *tmp; element_t *outer_ele, *inner_ele; for (outer = (head)->next; outer != (head)->prev; outer = outer->next) { for (inner = (outer)->next; inner != (head);) { outer_ele = container_of(outer, element_t, list); inner_ele = container_of(inner, element_t, list); if (strcmp(outer_ele->value, inner_ele->value) == 0) { tmp = inner->next; list_del(inner); q_release_element(inner_ele); inner = tmp; } else { inner = inner->next; } } } return true; } </s> :::danger 明確標注同學的 GitHub 帳號名稱 ::: 於是換了寫法，經過<s>同學</s> [kkkkk1109](https://github.com/kkkkk1109/lab0-c) 提醒發現輸入的佇列是已排序的，因此改用他的寫法 :::danger 你的洞見和檢討呢？ ::: 原先針對為排序的串列要使用兩層迴圈檢查有沒有重複，但由於輸入串列已排序，相同的鍵值一定會相鄰，因此只需要檢查相鄰的節點，如果和前者相同即刪除，如此一來可以將時間複雜度降低 N 倍 ### q_reverse 使用 `list_for_each_safe` 走訪佇列，沿途使用 `list_move` 將元素移至首位，如此一來就能倒轉順序原先想將 `q_reverse` 視為 `q_reverseK` 的特例，後來覺得在 `q_reverseK` 中呼叫 `q_reverse` 比較好實作 * 多檢查空元素和單元素的情況以提早退出 ```diff - if (!head) + if (!head || head->prev == head->next) return; ``` ### q_reverseK 使用 `list_cut_position` 剪下子佇列，用 `q_reverse` 倒序後再用 `list_splice` 接回去 `list_cut_position(head_to, head_from, node)` 剪下的部份並不包含 `head_from` 和 `node` 兩個節點 ### q_swap 視為 `q_reverseK` k 為2的特例 ### q_ascent 從 head 逆向走訪佇列，如果下一個元素大於當前元素則使用 `list_del` 刪除下個元素，如此一來就能留下遞增元素學會 `strcmp ()` 怎麼用，此函數會開始比較每一個字串的第一個字元。如果它們彼此相等，會繼續往下進行配對，直到字元不同或到達較短字串的結尾 ### q_descent 從 head 逆向走訪佇列，如果下一個元素小於當前元素則使用 `list_del` 刪除下個元素，如此一來就能留下遞減元素 ### q_sort 由於我在 `q_merge` 中會使用這個函式，在使用的前一步它已經是分段排序的佇列，這時候如果用 merge sort 會有不錯的效果，所以我選擇用 merge sort實作之用來合併兩以排序佇列的函式我定義為 `merge_two` ，在裡面原先判斷是否遞減和兩元素比較大小的部份使用兩層 `if` ，後來改為以下較緊湊的寫法 ```diff while (!list_empty(l1) && !list_empty(l2)) { element_t *ele_l1 = list_first_entry(l1, element_t, list); element_t *ele_l2 = list_first_entry(l2, element_t, list); - if(descend){ - if(strcmp(ele_l1->value, ele_l2->value) < 0) - list_move_tail(l2->next, &tmp_head); - else - list_move_tail(l1->next, &tmp_head); - } else { - if(strcmp(ele_l1->value, ele_l2->value) < 0) - list_move_tail(l1->next, &tmp_head); - else - list_move_tail(l2->next, &tmp_head); - } + if (descend == (strcmp(ele_l1->value, ele_l2->value) < 0)) { + list_move_tail(l2->next, &tmp_head); + } else { + list_move_tail(l1->next, &tmp_head); + } } ``` 而在 `q_sort` 中，使用先前 `q_delete_mid` 函式中的方法找到中點，再使用 `list_cut_position` 剪下後半段，用遞迴的方式分別排序前後兩段再用 `merge_two` 合併 ### q_merge 我首先去理解 `queue_contex_t` 的運作原理每個 `queue_contex_t` 代表了一個佇列，其中 `q` 會指向佇列的頭，而 `chain` 則是用來連接不同的 `queue_contex_t` 在這個函式中，我將所有的佇列使用 `list_splice` 拼接到第一個佇列，並且使用 `list_del_init` 移除已合併的佇列，最後再使用 `q_sort` 排序 * 取第一個佇列時誤用 `list_entry`，後來使用 `list_first_entry` ```diff -queue_contex_t *first_q = list_entry(&head->next, queue_contex_t, chain); +queue_contex_t *first_q = list_first_entry(head, queue_contex_t, chain); ``` 有時會出現 merge 完佇列消失的情況 ``` l = [c r z] cmd> merge l = [] ``` 後來發現在清空佇列後不移除當前 `queue_contex_t` 就好了 ```diff list_for_each_entry_safe (curr, safe, head, chain) { if (curr == first_q) continue; first_q->size += curr->size; list_splice_init(curr->q, first_q->q); - list_del_init(&curr->chain); } ``` ### 結果使用 `make test` 測試，只剩 trace-17 無法通過 ``` +++ 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 ERROR: Probably not constant time or wrong implementation ERROR: Probably not constant time or wrong implementation Probably constant time Probably constant time --- trace-17-complexity 0/5 --- TOTAL 95/100 make: *** [Makefile:60: test] Error 1 ``` 可以看到唯 `it` 和 `ih` 無法通過，有時候 `it` 會通過，分數為95 最後經由底下[修改 lab0/dudect](https://hackmd.io/D8_dNDEwTHi7RHGinG0bPQ?view#%E4%BF%AE%E6%94%B9-lab0dudect) 後可以得到100分 ## 使用 Valgrind 檢查錯誤先前使用 Valgrind 發現了實作 `q_free` 的暇疵，而最後我也嘗試使用它來找出 `trace-17` 中 `it` 和 `ih` 無法通過的原因，使用過程如下 ``` $ valgrind -q --leak-check=full ./qtest cmd> option simulation 1 cmd> it Probably constant time cmd> ih Probably constant time cmd> rh Probably constant time cmd> rt Probably constant time cmd> option simulation 0 cmd> quit Freeing queue ``` Valgrind 沒有找到記憶體使用問題，同時也發現可能在通過邊緣，上面單獨測試`it` 和 `ih` 沒問題 ## 實作 Shuffle 在 `queue.c` 中加上 `q_shuffle` 函式， `q_test` 中加上 `do_shuffle` 函式檢查是否為空或單節點，還有 `console_init` 中加上 `ADD_COMMAND(shuffle, "Do Fisher-Yates shuffle", "");` ```diff * void q_shuffle(struct list_head *head) { if (!head || head->next == head->prev) return; for (int len = q_size(head)-1; len > 0; len--) { int random = 1 + rand() % len; struct list_head *old = NULL, *new = NULL; int j = 1; struct list_head *pos; list_for_each(pos, head) { if (j == random) { old = pos; } if (j == len + 1) { new = pos; break; } j++; } struct list_head *pre_new = new->prev; struct list_head *pre_old = old->prev; if(old->next == new){ list_del(old); list_add(old,new); + } else { + list_del(new); + list_del(old); + list_add(new, pre_old); + list_add(old, pre_new); } } } ``` :::danger 使用 `git diff` 或 `diff -u` 來產生程式碼之間的變異清單，不要憑感覺填入，注意位移量。 ::: 首先在外層迴圈把 len 減少，裡面抽出要交換的 index 後用 `list_for_each` 找到要交換的 `old` 和 `new` ，最後交換節點，交換的部份原先的寫法沒考慮到兩節點相鄰的狀況 ### 實驗結果 ![Figure_1](https://hackmd.io/_uploads/SycnYG766.png) 測試 [1, 2, 3, 4] 做 shuffle 1,000,000 次的直方圖，可以看到結果很平均 --- ## 改進 lab0-c 的 constant time test ### 閱讀 [〈Dude, is my code constant time?〉](https://eprint.iacr.org/2016/1123.pdf) :::danger 避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。 ::: 檢查程式是否為常數運行時間很重要是因為如果不是，有機會受到時序攻擊，資安上存在疑慮而作者提出了 dudect 工具來測試程式是否為 constant time ，且相較於其他常見工具， dudect 不需要對硬體行為進行建模，也使用了 cropping 預處理，捨棄掉大於 p percentile 的資料，避免離群值過分影響統計結果，而 t value 的計算是使用 Welch’s t 檢定法。 ### 修改 lab0/dudect 檢查 `fixture.c` 發現沒有進行 cropping ，因此從作者的原始碼以 percentile 為關鍵字找到 `percentile` 和 `prepare_percentiles` 函式，接著將前述兩個函式和他們會使用到的函式複製到 `fixture.c` 裡面，再修改 data type 就可以通過 trace-17-complexity，得到滿分 ``` +++ 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 ``` --- ## Linux 核心鏈結串列排序研讀 Linux 核心原始程式碼的 [lib/list_sort.c (commit b5c56e)](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) ，首先覺得陌生的就是` __attribute__((nonnull())) `，後來了解到` __attribute__ ` 是 gcc 中用來附加屬性給函式或結構的用法，提供編譯器額外的訊息，而 `nonnull(2,3,4,5)` 是用來表示函式內的第 2,3,4,5 個參數不能為空，如此一來就不用在函式內檢查，接下來逐一記錄研讀 `list_sort.c` 中函式的心得。 :::danger 不要「舉燭」，你該質疑 Linux 核心開發者「如果不這樣做，會怎樣？」 ::: ### `merge` 此函式是用來合併已排序鏈結串列，過程中走訪兩個傳入的串列並且使用 `cmp(priv, a, b)` 來比較 a, b 節點中 `priv` 的大小，決定誰要排在前面，最後回傳合併的串列值得注意的是，根據註解的說法，此函式回傳的是單向並且非環狀的串列，這樣比較適合多次合併使用。 ### `merge_final` ```clike= for (;;) { /* if equal, take 'a' -- important for sort stability */ if (cmp(priv, a, b) <= 0) { tail->next = a; a->prev = tail; tail = a; a = a->next; if (!a) break; } else { tail->next = b; b->prev = tail; tail = b; b = b->next; if (!b) { b = a; break; } } } ``` 前面的 for 迴圈中，除了將兩個串列合併之外，也建立了雙向的連接，然而就算是 b 先結束， a 剩下部份的開頭也統一改名為 b ```clike= tail->next = b; do { /* * If the merge is highly unbalanced (e.g. the input is * already sorted), this loop may run many iterations. * Continue callbacks to the client even though no * element comparison is needed, so the client's cmp() * routine can invoke cond_resched() periodically. */ if (unlikely(!++count)) cmp(priv, b, b); b->prev = tail; tail = b; b = b->next; } while (b); /* And the final links to make a circular doubly-linked list */ tail->next = head; head->prev = tail; } ``` 這段主要是將 b 剩下的部份改成雙向串列，並且在最後將頭尾相接使其形成環狀，但 `if (unlikely(!++count))` 這段看不懂，經過查找資料後了解 `unlikely` 是一個巨集被定義為 `# define unlikely(x) __builtin_expect(!!(x), 0)` ，其中 `!!(x)` 會確保輸入值轉變為布林值，而 `__builtin_expect` 是 gcc 的內建函式，查看[手冊](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)中 Built-in Function: long __builtin_expect (long exp, long c) 舉例： ``` if (__builtin_expect (x, 0)) foo (); ``` 當 `foo ()` 被執行的情況很罕見的時候可以這樣寫，幫助編譯器最佳化而在 `merge_final` 中 `count` 增加，就會變非 0 ，執行 `cmp(priv, b, b)` ，但我還是不知道為什麼要執行 `cmp(priv, b, b)` 比較 b 自己，而且由於 ++ 是在前面，所以在執行第一次的時候 `count` 就會是非 0 ### `list_sort` ```clike= /* 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; ``` for 迴圈會逐位尋找二進位 `count` ，直到遇到第一個 0 結束迴圈，接下來判斷如果剩餘的位數存在 1 就進行合併，這樣做相當於當 count+1 不為 $2^k$ 時合併，參考[何時合併](https://hackmd.io/@sysprog/linux2024-lab0-e#%E4%BD%95%E6%99%82%E5%90%88%E4%BD%B5)的表格： | count 變化 | count 二進位 | merge | pending 上的節點 | | ----------- | ------------------- | ----------- | ----------------------------------------- | | 0 $\to$ 1 | 0000 $\to$ 0001 | no（$2^0$） | 1 | | 1 $\to$ 2 | 0001 $\to$ 0010 | no（$2^1$） | 1 $\gets$ 1 | | 2 $\to$ 3 | 0010 $\to$ 001==1== | yes | (2) $\gets$ 1 | | 3 $\to$ 4 | 0011 $\to$ 0100 | no（$2^2$） | 2 $\gets$ 1 $\gets$ 1 | | 4 $\to$ 5 | 0100 $\to$ 010==1== | yes | 2 $\gets$ (2) $\gets$ 1 | | 5 $\to$ 6 | 0101 $\to$ 01==1==0 | yes | (4) $\gets$ 1 $\gets$ 1 | | 6 $\to$ 7 | 0110 $\to$ 011==1== | yes | 4 $\gets$ (2) $\gets$ 1 | | 7 $\to$ 8 | 0111 $\to$ 1000 | no（$2^3$） | 4 $\gets$ 2 $\gets$ 1 $\gets$ 1 | | 8 $\to$ 9 | 1000 $\to$ 100==1== | yes | 4 $\gets$ 2 $\gets$ (2) $\gets$ 1 | | 9 $\to$ 10 | 1001 $\to$ 10==1==0 | yes | 4 $\gets$ (4) $\gets$ 1 $\gets$ 1 | | 10 $\to$ 11 | 1010 $\to$ 101==1== | yes | 4 $\gets$ 4 $\gets$ (2) $\gets$ 1 | | 11 $\to$ 12 | 1011 $\to$ 1==1==00 | yes | (8) $\gets$ 2 $\gets$ 1 $\gets$ 1 | | 12 $\to$ 13 | 1100 $\to$ 110==1== | yes | 8 $\gets$ 2 $\gets$ (2) $\gets$ 1 | | 13 $\to$ 14 | 1101 $\to$ 11==1==0 | yes | 8 $\gets$ (4) $\gets$ 1 $\gets$ 1 | | 14 $\to$ 15 | 1110 $\to$ 111==1== | yes | 8 $\gets$ 4 $\gets$ (2) $\gets$ 1 | | 15 $\to$ 16 | 1111 $\to$ 10000 | no（$2^4$） | 8 $\gets$ 4 $\gets$ 2 $\gets$ 1 $\gets$ 1 | 而整個函式會逐一把原始串列 `list` 的節點移到待處理串列 `pending` ，而 `pending` 中已排序的子串列會以前段提到的規則合併，直到原始 `list` 輸入完，接著在最後的 for 迴圈中會繼續合併 `pending` 中子串列，在這個階段是取最後一個和倒數第二個子串列合併成一個，直到只剩兩個子串列就結束迴圈，執行 `final_merge` 完成全部的合併 ### 閱讀 [< BOTTOM-UP MERGESORT A Detailed Analysis > ](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.5260) Merge sort 可分成 bottom-up 和 top-down ， top-down 為課本典型的演算法，將待排序序列分成左右兩個子序列，左右又繼續分裂直到子序列長度是一再合併，適合遞迴處理; bottum-up 則是將待排序序列元素逐一處理，在適當的時機合併，適合非遞迴實作，[commit b5c56e](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09) 屬於 bottom-up 的一種變形，也是逐一將元素讀入，差別在於合併的時機不同。下表為 bottom-up 和 top-down　的性能較比較： | Case | Best Case | Average Case | Worst Case | |------------|-----------|----------------------|--------------------| | Top-Down | 1 | 2N lg N - 0.146N | N lg N - 1.248N | N lg N - 0.943N | | Bottom-Up | 1 | 2N lg N - 0.146N | N lg N - 0.965N | N lg N - 0.701N | 雖然 bottom-up 的最差情況效能略輸 top-down ，但是 bottom-up 不需要預先知道序列長度，適合 link-list 實作的序列，這點使得它的實用性大於 top-down。 ### 閱讀 [Queue-Mergesort](https://doi.org/10.1016/0020-0190(93)90088-q) 這篇文章主要介紹一種合併排序的變體稱為 Queue Mergesort ，使用佇列存放待合併序列，先將每個元素單獨作為一個待排序序列存放於佇列，之後不斷從頭部取出兩個進行合併後放到尾部，直到佇列中剩下一個序列即完成排序。作者也證明這種方法是 optiml mergesort ，也就是對任何待排序元素個數 N ，最差情況下比較次數不比其他 mergesort <s>算法</s> 演算法多 :::danger algorithm 是「演算法」，而「算法」是 the way you calculate，也就是你在國中小學數學測驗卷上的「計算過程」，二者不同。 ::: ### 閱讀 [The cost distribution of queue-mergesort, optimal mergesorts, and power-of-two rules](https://doi.org/10.1006/jagm.1998.0986) 當兩個要合併的序列長度比值是2的冪時，也就是使用 power-of-2 rules ，有機會使得整體的時間複雜度隨著 N 變大時線性成長，既使合併兩序列的複雜度是超線性，因此相較於 half-half rules ，使用 power-of-2 rules 可以在 N 很大的時候顯著降低運算時間，而在 [commit b5c56e](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09) 中選用合併序列長度比值上限為 2 是因為不論 N 多少每一步合併都能限制在這個比值以下。 ### 引入 lib/list_sort.c 到 lab0-c 經過了上面的理解，我意識到自己之前實作 `q_sort` 的方法是多麼天真且愚蠢，因此我引入 lib/list_sort.c 的<s>算法</s> 演算法到 lab0-c [(commit 9837691)](https://github.com/sysprog21/lab0-c/commit/98376912f884a6766f0adb9e28eb3de656549ba6)。過程中做了一些改寫，為了簡化實作，刪去了編譯器優化的部份`__attribute__((nonnull())`, `likely` 和 `unlikely` ，還有以 `strcmp` 取代 `cmp` 函式，因此也刪減了有關函式的傳入參數 `prev`, `cmp` 。

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.