# 2023q1 Homework1 (lab0)
contributed by<`aaron881011`>
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0
Copyright (C) 2019 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
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 16
On-line CPU(s) list: 0-15
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 141
Model name: 11th Gen Intel(R) Core(TM) i7-11800H @ 2.30GHz
```
## 開發紀錄
### Function實作
#### q_new
此函式回傳配置記憶體後指向該記憶體指標，在配置失敗的時候則回傳空指標。 由於 `malloc` 失敗時也會回傳空指標，透過判斷該回傳指標是否為空便可以知道是否該對其進行初始化，之後將指標回傳即可。
```cpp
struct list_head *q_new()
{
struct list_head *head;
head = malloc(sizeof(struct list_head));
if (head) {
INIT_LIST_HEAD(head);
}
return head;
}
```
#### q_free
使用 linux list api 中的 `list_for_each_entry_safe` 便可以在迭代時對此代的節點進行操作而不必擔心未定義情況發生。
```cpp
void q_free(struct list_head *l)
{
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, l, list) {
free(entry->value);
free(entry);
};
free(l);
}
```
#### q_insert_head (q_insert_tail)
此處只須將節點插入`head->next` 處即可(在 `q_insert_tail` 的情況下則插入 `head->prev` )。需要注意的是由於此函式需要進行許多記憶體操作，可能會在 `malloc` 或是 `strdup` 時失敗，此時需要釋放在失敗前所配置的記憶體避免佔用。
```cpp
bool q_insert_head(struct list_head *head, char *s)
{
if (!head || !s) {
return false;
}
element_t *element = malloc(sizeof(element_t));
if (!element) {
return false;
}
char *tmp_str = strdup(s);
if (!tmp_str) {
free(element);
return false;
}
element->value = tmp_str;
INIT_LIST_HEAD(&element->list);
list_add(&element->list, head);
return true;
}
```
#### q_remove_head (q_remove_tail)
將位於 `head->next` 的節點移除( `q_remove_tail` 則是移除位於 `head->prev` 的節點)， 並複製所代表的元素所包含的 string 至指定的指標下，再將該元素回傳。對 string 進行複製時需要注意其目的指標下所配置的記憶體並加入中止字元 `\0` 。
```cpp
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head)) {
return NULL;
}
element_t *element = list_first_entry(head, element_t, list);
list_del(head->next);
if (sp && bufsize > 0) {
strncpy(sp, element->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return element;
}
```
#### q_size
透過迭代過整個 list 並在每一代將長度 `len` ＋1 便可以得到 list 的長度。
```cpp
int q_size(struct list_head *head)
{
if (!head) {
return 0;
}
int len = 0;
struct list_head *li;
list_for_each (li, head)
len++;
return len;
}
```
#### q_delete_mid
使用快慢指標的技巧可以快速的得到 list 的中間項,將該項從 list 中移除後再將其元素何其包含的 string 所配置之記憶體釋放即可。
```cpp
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head)) {
return false;
}
struct list_head *slow = head, *fast = head;
do {
fast = fast->next->next;
slow = slow->next;
} while (fast != head && fast->next != head);
list_del(slow);
element_t *ele = list_entry(slow, element_t, list);
free(ele->value);
free(ele);
return true;
}
```
#### q_delete_dup
此函式須將 list 中其元素擁有重複 string 的節點刪除，在呼叫此函式前將 list 進行排序，此函式擁有 $O(n)$ 的時間複雜度。在每一次迭代時將此代的元素與後續的元素進行比較，若相同便將其刪除；反之則代表 list 中沒有與此代元素擁有相同 string 的其他元素，直接進行下一次迭代。在下一次迭代前會先判斷是否有刪除過元素，若有刪除過責將此代元素一併刪除。另外未避免未定義情況發生，所有的節點刪除和記憶體釋放都會在下一代執行。
```cpp
bool q_delete_dup(struct list_head *head)
{
if (!head)
return false;
if (list_empty(head) || list_is_singular(head))
return true;
struct list_head *cur = head->next;
int flag = 0;
while (cur != head) {
element_t *ele_cur = list_entry(cur, element_t, list);
struct list_head *tmp_node = cur->next;
while (tmp_node != head) {
element_t *ele_tmp = list_entry(tmp_node, element_t, list);
tmp_node = tmp_node->next;
if (strcmp(ele_cur->value, ele_tmp->value) == 0) {
flag = 1;
list_del(tmp_node->prev);
free(ele_tmp->value);
free(ele_tmp);
} else
break;
}
cur = cur->next;
if (flag) {
flag = 0;
list_del(cur->prev);
free(ele_cur->value);
free(ele_cur);
}
}
return true;
}
```
#### q_swap
此函式將 list 中每兩個節點進行反轉。透過 list api 進行迭代，將此代節點移至其後一個節點之後，下一次迭代便會是元節點的下下個節點，請參考以下示意圖。若 list 長度為 $n$ ， 此法僅迭代過 $n/2$ 個節點。
* 此代節點為 A
* 將 A 移至其後一節點( B )之後
* 下一次迭代節點為 A 的下一節點， 即 C
```cpp
void q_swap(struct list_head *head)
{
if (!head) {
return;
}
struct list_head *node;
list_for_each (node, head) {
if (node->next == head) {
break;
}
list_move(node, node->next);
}
}
```
#### q_reverse
此函式會將整個 list 反轉。透過 list api 裡的 `list_for_each_safe` 可以操作該次迭代的節點而保證不影響迭代順序，因此調用該巨集並將該次迭代之節點前後反指即可。
```cpp
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head)) {
return;
}
struct list_head *node, *safe;
list_for_each_safe (node, safe, head) {
struct list_head *tmp = node->next;
node->next = node->prev;
node->prev = tmp;
}
struct list_head *tmp = head->next;
head->next = head->prev;
head->prev = tmp;
}
```
#### q_reverseK
此函式會將 list 中每 $k$ 個節點進行反轉。首先紀錄 list 原先的結尾位置，將在那之前的每 $k$ 個節點使用 `q_reverse` 進行反轉後移至 list 尾端，最後再將湊不齊 $k$ 個的節點們直接移至 list 尾端即可。
```cpp
void q_reverseK(struct list_head *head, int k)
{
if (!head || list_empty(head) || list_is_singular(head)) {
return;
}
struct list_head left, *tail = head->prev;
int len = q_size(head);
while (len >= k) {
struct list_head *node = head;
for (int i = 0; i < k; i++) {
node = node->next;
}
list_cut_position(&left, head, node);
q_reverse(&left);
list_splice_tail_init(&left, head);
len -= k;
}
list_cut_position(&left, head, tail);
list_splice_tail_init(&left, head);
}
```
#### q_descend
此函式會將 list 中在節點右端仍有大於節點值的節點的節點刪除，形成一遞減的 list。
從 list 尾端進行迭代，將此次迭代的節點與其前一個節點進行比較，若前一節點的值大於該代節點則刪除前一節點，如此便能保證list為遞減形式。
```cpp
int q_descend(struct list_head *head)
{
if (!head || list_empty(head)) {
return 0;
}
if (list_is_singular(head)) {
return 1;
}
struct list_head *node = head->prev;
while (node != head && node != head->next) {
struct list_head *prev = node->prev;
element_t *cur_ele = list_entry(node, element_t, list);
element_t *prev_ele = list_entry(prev, element_t, list);
if (strcmp(cur_ele->value, prev_ele->value) > 0) {
list_del(prev);
free(prev_ele->value);
free(prev_ele);
} else {
node = prev;
}
}
return q_size(head);
}
```
#### q_sort
此函式以 merge sort 實作排序問題，其時間複雜度為 $O(nlog(n))$ 。首先用快慢指標將 list 分成兩部分，再使用 list api 將 list 分成兩個 list，以遞迴方式將其切到長度為 1 後再兩個兩個將其合併。
```cpp
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head)) {
return;
}
struct list_head *slow = head, *fast = head;
do {
fast = fast->next->next;
slow = slow->next;
} while (fast != head && fast->next != head);
assert(slow != head);
LIST_HEAD(left);
list_cut_position(&left, head, slow);
q_sort(head);
q_sort(&left);
q_merge_two(head, &left);
}
```
#### q_merge_two
此函式將兩個 list 合併，將 `L2` 合併至 `L1` 中。這裡使用間接指標用來指向指向 list 的第一個節點的指標，藉此可以透過操作間接指標來進行迭代。另外，在這裡加入了 gcc builtin exepctation 來進行判斷以加速表現效果。
```cpp
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
void q_merge_two(struct list_head *L1, struct list_head *L2)
{
if (likely(L1 && L2)) {
if (unlikely(L1 == L2)) {
return;
} else if (unlikely(list_empty(L2))) {
return;
} else if (unlikely(list_empty(L1))) {
list_splice_tail_init(L2, L1);
return;
} else {
struct list_head *tail = L1->prev, *node = NULL;
while (node != tail && !list_empty(L2)) {
element_t *ele_1 = list_first_entry(L1, element_t, list);
element_t *ele_2 = list_first_entry(L2, element_t, list);
node = strcmp(ele_1->value, ele_2->value) < 0 ? &ele_1->list
: &ele_2->list;
list_move_tail(node, L1);
assert(list_entry(node, element_t, list)->value != NULL);
}
if (list_empty(L2)) {
LIST_HEAD(left);
list_cut_position(&left, L1, tail);
list_splice_tail_init(&left, L1);
} else {
list_splice_tail_init(L2, L1);
}
}
}
return;
}
```
#### q_merge
此函式將複數個 list 進行合併，採用兩兩合併的策略來維持合併後 list 的長度不至於差距太大。此實作法分別從 list 的頭 `head->next` 尾 `head->prev` 以進行合併，並在每次合併後更新 list 的長度。
```cpp
int q_merge(struct list_head *head)
{
// https://leetcode.com/problems/merge-k-sorted-lists/
if (!head || list_empty(head)) {
return 0;
}
if (list_is_singular(head)) {
queue_contex_t *qct = list_first_entry(head, queue_contex_t, chain);
return qct->size;
}
struct list_head *end = head->prev;
while (end != head->next) {
for (struct list_head *start = head->next;
start->prev != end && start != end;
start = start->next, end = end->prev) {
queue_contex_t *qct_s = list_entry(start, queue_contex_t, chain);
queue_contex_t *qct_e = list_entry(end, queue_contex_t, chain);
q_merge_two(qct_s->q, qct_e->q);
qct_s->size += qct_e->size;
qct_e->size = 0;
}
}
queue_contex_t *qct_res = list_first_entry(head, queue_contex_t, chain);
return qct_res->size;
}
```
### linux list_sort 閱讀/引入
程式碼解讀參考了 <`eric88525`> 學長的[共筆](https://hackmd.io/@eric88525/list_sort)，而比較函數 `cmp` 定義如下：
```cpp
#include "list.h"
int cmp(void *priv, const struct list_head *a, const struct list_head *b)
{
element_t *a_entry = list_entry(a, element_t, list);
element_t *b_entry = list_entry(b, element_t, list);
return strcmp(a_entry->value, b_entry->value);
}
```
#### perf
由於 `q_sort` 的實作採用了 top down 的模式，與 `list_sort` 的 bottom up 相比 cache 被參照的次數更少，不斷的遷入遷出容易造成 cache thrashing，測試用指令如下。
* `perf.cmd` 使用 `q_sort`
```shell
option fail 0
option malloc 0
new
it dolphin 1000000
ih gerbil 1000000
sort
```
* `perf_linux.cmd` 使用 `list_sort`
```shell
option fail 0
option malloc 0
new
it dolphin 1000000
ih gerbil 1000000
sort_linux
```
上述所提到的 cache thrashing 可以觀察 cache-misses 的次數，首先使用 `perf stat` 比較執行結果
```shell
$ perf stat -e cache-misses -r 100 ./qtest -v 0 -f perf.cmd
Performance counter stats for './qtest -f perf.cmd' (100 runs):
56,959,286 cache-misses ( +- 0.17% )
0.96087 +- 0.00360 seconds time elapsed ( +- 0.37% )
$ perf stat -e cache-misses -r 100 ./qtest -v 0 -f perf_linux.cmd
Performance counter stats for './qtest -f perf_linux.cmd' (100 runs):
46,542,039 cache-misses ( +- 0.12% )
0.67788 +- 0.00308 seconds time elapsed ( +- 0.45% )
```
可以看到兩邊的執行結果，使用 `q_sort` 的 cache-misses 發生次數高上許多，再來使用 `perf record` 細看
```shell
$ perf record -e cache-misses ./qtest -v 0 -f perf.cmd; perf report
[ perf record: Woken up 1 times to write data ]
[ perf record: Captured and wrote 0.131 MB perf.data (2816 samples) ]
Samples: 2K of event 'cache-misses', Event count (approx.): 56888841
Overhead Command Shared Object Symbol
38.82% qtest qtest [.] q_sort ◆
35.86% qtest qtest [.] q_show ▒
8.73% qtest libc-2.31.so [.] __strcmp_avx2 ▒
4.83% qtest qtest [.] q_size ▒
2.16% qtest qtest [.] q_merge_two ▒
1.70% qtest [kernel.kallsyms] [k] try_charge_memcg ▒
1.03% qtest [kernel.kallsyms] [k] kthread_blkcg ▒
1.00% qtest [kernel.kallsyms] [k] mem_cgroup_charge_statistics.isra.0 ▒
0.99% qtest [kernel.kallsyms] [k] charge_memcg ▒
0.96% qtest [kernel.kallsyms] [k] __count_memcg_events ▒
0.74% qtest qtest [.] do_sort ▒
0.74% qtest [kernel.kallsyms] [k] cgroup_rstat_updated ▒
0.48% qtest [kernel.kallsyms] [k] __cgroup_throttle_swaprate
```
```shell
$ perf record -e cache-misses ./qtest -v 0 -f perf_linux.cmd; perf report
[ perf record: Woken up 1 times to write data ]
[ perf record: Captured and wrote 0.120 MB perf.data (2526 samples) ]
Samples: 2K of event 'cache-misses', Event count (approx.): 46093836
Overhead Command Shared Object Symbol
44.55% qtest qtest [.] q_show
24.18% qtest libc-2.31.so [.] __strcmp_avx2
6.01% qtest qtest [.] q_size
4.71% qtest qtest [.] list_sort
4.65% qtest qtest [.] cmp
3.07% qtest qtest [.] merge
2.50% qtest [kernel.kallsyms] [k] try_charge_memcg
1.33% qtest [kernel.kallsyms] [k] __count_memcg_events
1.32% qtest [kernel.kallsyms] [k] kthread_blkcg
1.15% qtest qtest [.] do_sort_linux
1.14% qtest qtest [.] 0x0000000000002710
1.00% qtest [kernel.kallsyms] [k] cgroup_rstat_updated
0.92% qtest [kernel.kallsyms] [k] mem_cgroup_charge_statistics.isra.0
```
可以看到兩種函式佔據整個程式的 cache-misses 的百分比相差巨大，`list_sort` 函式所發生的 cache-misses 次數預估(此處僅包含呼叫到的函式，並不嚴謹)為 ${ \frac{4.71+4.65+3.07}{100} * 46093836 = 5729463}$ 次， 而 `q_sort`則為 ${\frac{38.82+2.16}{100}*56888841=23313047}$，差距可達到四倍之多。
### shuffle
在 `q_test` 中實作了 Fisher-Yates shuffle 的演算法如下，為了維持 coding-style 的一致性，這裡分成 `q_shuffle` 的洗牌方法跟 do_shuffle 的執行洗牌方法。
#### q_shuffle
這裡紀錄了兩個實作方法。由於初次的實作過於 naïve ，在實驗後發現其可被證明不符合 uniform distribution，因此再度實作了新的方法。
* **failed ver.**
此實作將隨機選擇到的節點放至 queue 的結尾，是 [Fisher-Yates 原來的方法](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Fisher_and_Yates'_original_method)。
:::danger
此實作方法在經過實驗測試後證實不為 uniform distribution。
:::
```cpp
void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head)) {
return;
}
int len = q_size(head);
for (int i = len - 1; i > 0; i--) {
int j = rand() % (i + 1);
struct list_head *node = head->next;
for (int k = 0; k < j; k++) {
node = node->next;
}
list_move_tail(node, head);
}
}
```
* **new ver.** ([參考連結](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm))
此實作將隨機選到的節點與尚未被選擇過的最後方的節點互換，增加了隨機性。
```cpp!
/* Shuffle queue using Fisher-Yates shuffle*/
void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head)) {
return;
}
int len = q_size(head);
int j = random() % len;
struct list_head *node = head->next;
if (j != len - 1) {
for (int k = 0; k < j; k++) {
node = node->next;
}
struct list_head *tmp = head->prev;
list_move(tmp, node);
}
list_del_init(node);
q_shuffle(head);
list_add_tail(node, head);
}
```
#### do_shuffle
```cpp!
static bool do_shuffle(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
if (!current || !current->q)
report(3, "Warning: Calling shuffle on null queue");
error_check();
set_noallocate_mode(true);
if (exception_setup(true))
q_shuffle(current->q);
exception_cancel();
set_noallocate_mode(false);
q_show(3);
return !error_check();
}
```
#### 洗牌的亂度驗證 卡方分佈
使用了皮爾森卡方檢定來驗證 `q_shuffle` 的結果是否遵守 Uniform distribution。
設虛無假說：
* $H_0$（虛無假說）: shuffle 結果機率相同，符合 uniform distribution
* $H_1$（對立假說）: shuffle 結果至少有一個機率不同
首先計算 chi-square test statics $X^2 = \sum_{i=1}^{n}\frac{(O_i-E_i)^2}{E_i}$，其中 $O_i$ 為第 i 項的發生次數， $E_i$ 為第 i 項的期望值（由於是 uniform distribution，這裡的期望值為所有情況數量 $n$ 的倒數 $\frac1n$）。
因為所有情況的機率總和為 1 ，其中一種情況的機率將會是 $1-\sum{P(其他情況)}$，所以自由度為 $1-n$，對應的 P-value 則可以透過卡方分佈表來查詢。若 p-value 低於所選擇之信心水準, 則可以證明虛無假說 $H_0$ 為偽，反之則沒有證據證明其為偽。
#### 實驗
執行以下程式：
```python!
import subprocess
import re
from itertools import permutations
import random
# 測試 shuffle 次數
test_count = 1000000
input = "new\nit 1\nit 2\nit 3\nit 4\n"
for i in range(test_count):
input += "shuffle\n"
input += "free\nquit\n"
# 取得 stdout 的 shuffle 結果
command='./qtest -v 3'
clist = command.split()
completedProcess = subprocess.run(clist, capture_output=True, text=True, input=input)
s = completedProcess.stdout
startIdx = s.find("l = [1 2 3 4]")
endIdx = s.find("l = NULL")
s = s[startIdx + 14 : endIdx]
Regex = re.compile(r'\d \d \d \d')
result = Regex.findall(s)
def permute(nums):
nums=list(permutations(nums,len(nums)))
return nums
def chiSquared(observation, expectation):
return ((observation - expectation) ** 2) / expectation
# shuffle 的所有結果
nums = []
for i in result:
nums.append(i.split())
# 找出全部的排序可能
counterSet = {}
shuffle_array = ['1', '2', '3', '4']
s = permute(shuffle_array)
# 初始化 counterSet
for i in range(len(s)):
w = ''.join(s[i])
counterSet[w] = 0
# 計算每一種 shuffle 結果的數量
for num in nums:
permutation = ''.join(num)
counterSet[permutation] += 1
# 計算 chiSquare sum
expectation = test_count // len(s)
c = counterSet.values()
chiSquaredSum = 0
for i in c:
chiSquaredSum += chiSquared(i, expectation)
print("Expectation: ", expectation)
print("Observation: ", counterSet)
print("chi square sum: ", chiSquaredSum)
print("Degree of freedom: ", len(s) - 1)
```
#### 執行結果：
* failde ver.
```shell!
lab0-c$ python scripts/shuffle_test.py
Expectation: 41666
Observation: {'1234': 41799, '1243': 41782, '1324': 41353, '1342': 41975, '1423': 41501, '1432': 41697, '2134': 41675, '2143': 41581, '2314': 41638, '2341': 41389, '2413': 41212, '2431': 41271, '3124': 41987, '3142': 41747, '3214': 41767, '3241': 41840, '3412': 41865, '3421': 41600, '4123': 42000, '4132': 41286, '4213': 42087, '4231': 41992, '4312': 41595, '4321': 41361}
chi square sum: 36.75217203475256
Degree of freedom: 23
```
透過計算出了 chi square sum 和自由度[計算 $X^2$](http://courses.atlas.illinois.edu/spring2016/STAT/STAT200/pchisq.html)，P-value 在 $0.03$ 左右，低於信心水準 $\alpha = 0.05$。
* new ver.
```shell!
Expectation: 41666
Observation: {'1234': 41761, '1243': 41652, '1324': 41504, '1342': 41676, '1423': 42133, '1432': 41460, '2134': 41890, '2143': 41412, '2314': 41528, '2341': 41545, '2413': 41631, '2431': 41642, '3124': 41917, '3142': 41717, '3214': 41604, '3241': 41933, '3412': 41564, '3421': 41580, '4123': 41619, '4132': 41647, '4213': 41560, '4231': 41678, '4312': 41792, '4321': 41555}
chi square sum: 15.527048432774931
Degree of freedom: 23
```
同樣計算 p value 約等於 $0.8748$， 大於所選的信心水準 $\alpha = 0.05$， 沒有證據顯示虛無假說 $H_0$ 為偽。
#### 繪圖
```python!
import matplotlib.pyplot as plt
import numpy as np
permutations = counterSet.keys()
counts = counterSet.values()
x = np.arange(len(counts))
plt.bar(x, counts)
plt.xticks(x, permutations)
plt.xlabel('permutations')
plt.ylabel('counts')
plt.title('Shuffle result')
plt.savefig("shuffle.png")
plt.show()
```
使用新版本實作來繪圖，各情況分佈如下圖，大致呈 uniform distribution：
### dudect
#### 概念介紹
本篇論文的概念非常簡單，透過比較程式對於固定和隨機資料所執行的時間來進行統計測試，證明此程式對於兩種類資料所耗費的執行時間分佈是否相同，本篇作者使用的是 t-test 中的 [Welch's t-test
](https://en.wikipedia.org/wiki/Welch%27s_t-test)。
#### t test
Sign in with Wallet
Connect another wallet