# 2024q1 Homework1 (lab0)
contributed by < `mesohandsome` >
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.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): 12
On-line CPU(s) list: 0-11
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 151
Model name: 12th Gen Intel(R) Core(TM) i5-12400
Stepping: 2
CPU MHz: 2500.000
CPU max MHz: 4400.0000
CPU min MHz: 800.0000
BogoMIPS: 4992.00
Virtualization: VT-x
L1d cache: 288 KiB
L1i cache: 192 KiB
L2 cache: 7.5 MiB
L3 cache: 18 MiB
NUMA node0 CPU(s): 0-11
```
## 針對指定佇列操作的實作
### `q_new`
可能會有 allocation failed。
剛開始還沒發現 `list.h` 中已經有定義好許多巨集可以使用，其中有定義 `INIT_LIST_HEAD` 可以直接使用。
```c
struct list_head *head =
(struct list_head *) malloc(sizeof(struct list_head));
if (!head)
return NULL;
INIT_LIST_HEAD(head);
```
### `q_free()`
原本使用 while 迴圈去走訪並 free 每一個節點，後續發現也有定義好的巨集可以使用。
開始要清除節點時，我並不知道 struct 內有哪些資料需要清除，看了 queue.h 發現 `element_t` 與 `list_head` 有關聯，所以也要把它清除。
```diff
list_for_each_safe (iterator, safe, l) {
element_t *entry = list_entry(iterator, element_t, list);
list_del(iterator);
- free(entry->value);
- free(entry);
+ q_release_element(entry);
}
```
### `q_insert_head()`
考量到會有 allocation failed 的狀況，需要再判斷並清除已經配置過的空間。
```diff
element_t *new_element = (element_t *) malloc(sizeof(element_t));
+ if (!new_element)
+ return false;
new_element->value = strdup(s);
+ if (!new_element->value) {
+ free(new_element->value);
+ free(new_element);
+ return false;
+ }
list_add(&new_element->list, head);
```
### `q_insert_tail()`
和 q_insert_head() 相差不多，在寫這個 function 時有發現定義好的 q_release_element 可以使用。
```diff
new_element->value = strdup(s);
if (!new_element->value) {
- free(new_element->value);
- free(new_element);
+ q_release_element(new_element);
return false;
}
```
### `q_remove_head()`
原本使用 `memcpy()` 複製字串，後來改用 `strncpy()`。
`strncpy()` 會保證字串都是以 `\0` 結尾，如果字串長度小於 `bufsize - 1`，也會自動添加 `\0`
```diff
if (sp && bufsize > 0) {
- memcpy(sp, entry->value, bufsize - 1);
+ strncpy(sp, entry->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
```
### `q_remove_tail()`
和 `q_remove_head()` 除了 `list_last_entry()` 外，其他都相同。
```diff
- element_t *entry = list_first_entry(head, element_t, list);
+ element_t *entry = list_last_entry(head, element_t, list);
```
### `q_size()`
使用 `list.h` 中的 `list_for_each` 走訪過每一個節點計算長度
```c
list_for_each (iterator, head) {
size++;
}
```
### `q_delete_mid()`
原本對 `q_delete_mid()` 的實作，需要先透過 `q_size()` 走訪一次取得長度，再找到中間點。
```c
int size = q_size(head) / 2;
struct list_head *iterator, *safe;
list_for_each_safe (iterator, safe, head) {
if (size-- == 0) {
element_t *entry = list_entry(iterator, element_t, list);
list_del(&entry->list);
q_release_element(entry);
break;
}
}
```
後來使用快慢指標<s>實做</s> 實作，不用事先取得 list 的長度就直接找到中間點並刪除。
```c
while (fast != head && fast->next != head) {
fast = fast->next->next;
slow = slow->next;
}
element_t *entry = list_entry(slow, element_t, list);
list_del(&entry->list);
q_release_element(entry);
```
### `q_delelte_dup()`
每次都判斷下一個節點的字串是否與當前相同，若相同就將當前節點刪除。
刪除到最後，如果之前自己有和其他節點重複，也必須將自己刪除，因此使用了一個 boolean 值來紀錄。
```c
if (safe != head &&
strcmp(current_entry->value, next_entry->value) == 0) {
delete_flag = true;
list_del(¤t_entry->list);
q_release_element(current_entry);
} else {
if (delete_flag) {
delete_flag = false;
list_del(¤t_entry->list);
q_release_element(current_entry);
}
}
```
### `q_swap()`
找出需要被交換的兩個節點，將他們指向的 next 和 prev 交換。
發現與這兩個節點前後的 next 和 prev 也需要更新。
```diff
while (first != head && second != head) {
first->next = second->next;
+ second->next->prev = first;
second->next = first;
second->prev = first->prev;
+ first->prev->next = second;
first->prev = second;
first = first->next;
second = first->next;
}
```
### `q_reverse()`
從頭開始將 next 和 prev 交換，再往後一個個更新。
```c
do {
temp = current->next;
current->next = current->prev;
current->prev = temp;
current = temp;
} while (current != head);
```
:::warning
TODO: 善用 List API，撰寫更精簡的程式碼。
:::
使用 `list_for_each_safe()` 將目前遇到的節點都向 head 移動，從而翻轉整個 list。
```diff
- do {
- temp = current->next;
- current->next = current->prev;
- current->prev = temp;
- current = temp;
- } while (current != head);
+ list_for_each_safe (current, safe, head)
+ list_move(current, head);
```
### `q_reverseK()`
中間與 `q_reverse()` 大致相同，多了一個變數計算目前換了幾次。
每次換完就再將當前位置的指標更新。
```diff
do {
do {
...
} while (current != head && remain > 0);
+ current->prev->prev = prev;
+ prev->next = current->prev;
+ start->next = current;
+ prev = start;
+ start = current;
} while (size > k);
```
### `q_ascend()`
從尾端開始往前檢查，將起始節點的 value 設定為目前的最小值。
向前存取每一個節點，如果值較大就刪除。
~~因為 function 敘述上面寫的是 remove，所以只把節點 unlink，並未把 element_t 清除~~
發現如果沒有 release 的話，在 make test 有一部分沒辦法通過，所以 queue.h 中的 function 敘述不是 remove 而是要改成 delete，或是要修改 test 本身？
```diff
while (ptr != head && ptr->prev != head) {
element_t *entry = list_entry(ptr->prev, element_t, list);
if (strcmp(entry->value, current_min) < 0) {
current_min = entry->value;
ptr = ptr->prev;
} else {
list_del(&entry->list);
+ q_release_element(entry);
}
}
```
:::warning
確認後，提交 GitHub issue / pull request。
:::
### `q_descend()`
與 `q_ascend()` 除了比較函式外都相同。
```diff
- if (strcmp(entry->value, current_min) <= 0)
+ if (strcmp(entry->value, current_max) >= 0)
```
:::danger
避免非必要的項目列舉 (即 `* `)，以清晰明確的漢語書寫。
:::
:::warning
TODO: 提高程式碼的可重用程度。
:::
`q_ascend()` 和 `q_descend()` 只有比較函式不同，所以額外寫了一個函式並使用一個 bool 參數去控制目前要使用哪一個比較。
```c
if (descend ? strcmp(entry->value, current_value) >= 0
: strcmp(entry->value, current_value) <= 0)
```
### `q_sort()`
使用快慢指標找到中間節點，將鏈結串列拆成左右二側。
再修改 [Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/description/) 中有使用過 merge 兩個 list 的方式合併拆出的 list。
```c
list_cut_position(&left, head, slow);
list_splice_init(head, &right);
q_sort(&left, descend);
q_sort(&right, descend);
```
### `q_merge()`
將 chain 中的所有 list 都先合併到第一個 list，再使用前面完成的 `q_sort()` 做排序。
```c
list_for_each_safe (node, safe, head) {
if (node == head->next)
continue;
queue_contex_t *current_entry = list_entry(node, queue_contex_t, chain);
size += current_entry->size;
list_splice_init(current_entry->q, entry->q);
}
q_sort(entry->q);
```
---
## 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉並改進 lab0-c 的 dudect
### student's t-distribution
t-distribution 和常態分佈的分佈狀況相似，圖上表示都是對稱而中間隆起的形狀。
> 紅線表示 t-distribution 藍線表示常態分佈。
但 t-distribution 的兩側會比常態分佈來的更厚，代表會有更多數據分佈在兩端，所以 t-distribution 適合用在小量數據的分析，因為數據不多的情況下，很有可能會出現極端值影響整體的分佈狀況。
### Welch's t-test
論文中使用這個方式檢驗，計算中會需要一個 p-value，為下圖大於 t 的機率密度值
不同於常態分佈需要大量資料才會有正常的機率分佈，透過 t-distribution 可以處理資料量小的情況，讓計算過程中可以取得合適的 p-value 將極端值切除，因此論文中採用 t-distribution 是合適的。
:::warning
探討用於本處是否合適。
:::
### 改進 lab0-c/dudect
dudect 會將超出一定範圍的資料切除/忽略，在 [dudect Source code](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 中的 Percentiles 在做這件事。
但目前 test 中缺少了這部份的檢查，將缺少的部份補上後即可通過 trace-17-complexity 的檢測。
```diff
bool ret = measure(before_ticks, after_ticks, input_data, mode);
+ bool first_time = percentiles[DUDECT_NUMBER_PERCENTILES - 1] == 0;
+ update_statistics(exec_times, classes);
+ if (first_time) {
+ prepare_percentiles(exec_times, percentiles);
+ } else {
+ differentiate(exec_times, before_ticks, after_ticks);
+ update_statistics(exec_times, classes);
+ ret &= report();
+ }
```
## 新增 shuffle 命令
### `qtest` 新增命令
在 `qtest.c` 的 `console_init()` 中加入新的命令。
```diff
+ ADD_COMMAND(shuffle, "Shuffle the queue", "");
```
參考原先就有的測試函式，添加一個 `do_shuffle()` 函式並將呼叫的函式修改為新增的 `q_shuffle()`。
```diff
if (exception_setup(true))
- q_reverseK(current->q, k);
+ q_shuffle(current->q);
```
### `q_shuffle()`
參考 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm) 演算法，實作 `q_shuffle()`。
```c
while (size && current != head) {
int index = rand() % (size--);
struct list_head *target = head->next;
while (index--)
target = target->next;
if (current == target)
continue;
if (current != target) {
struct list_head *temp = target->prev;
list_move(target, current);
list_move(current, temp);
current = target->prev;
} else {
current = current->prev;
}
}
```
```text
Expectation: 41666
Observation: {'1234': 41841, '1243': 41335, '1324': 41735, '1342': 41830, '1423': 41653, '1432': 41390, '2134': 41641, '2143': 41523, '2314': 41365, '2341': 41591, '2413': 41730, '2431': 41493, '3124': 42083, '3142': 41394, '3214': 41922, '3241': 41859, '3412': 41771, '3421': 41642, '4123': 41635, '4132': 41643, '4213': 41989, '4231': 41660, '4312': 41699, '4321': 41576}
chi square sum: 21.043920702731242
```
## 引入 lib/list_sort.c 並比較 q_sort
### 新增 list_sort 命令
將 list_sort.c 中的 `cmp` 都先更換成之前 `q_descend` 中有使用到的 `strcmp`。
在程式中加入 `likely()` 及 `unlikely()` 兩個 macro。
```c
# define likely(x) __builtin_expect(!!(x), 1)
# define unlikely(x) __builtin_expect(!!(x), 0)
```
並用和新增 `shuffle` 命令時一樣的方式新增一個 `list_sort` 命令。
```text
help | Show summary
ih str [n] | Insert string str at head of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
it str [n] | Insert string str at tail of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
list_sort | Sort queue with lib/list_sort
log file | Copy output to file
```
### 比較 q_sort
建立 shell script 在不同的資料量時各測量 5 次，將數據取平均做觀察。
```shell
for i in {1..5}; do
echo -e "new\n it RAND ${NUMBER}\n time sort" | ./qtest | grep "Delta"
done
```
從結果上可以看出，`list_sort` 比起自己實做的 `q_sort` 更快，尤其是在資料量增加時，差距更加顯著。
## 研讀 lib/list_sort.c
如果是通常的 merge sort，在出現 2 個同為 $2^k$ 大小的 list 時，就會將 2 個合併，但 list_sort 中會等到同時出現大小為 `2 : 1` 的 list 才會合併，讓長度較長的 list 不會很快就產生，以此降低 [cache thrashing](https://en.wikipedia.org/wiki/Thrashing_(computer_science))
```
* 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.
```
Sign in with Wallet
Connect another wallet