# 2024q1 Homework1 (lab0)
contributed by < `Jimmy01240397` >
### Reviewed by `jujuegg`
- 不用張貼完整程式碼
- dudect 的部分可以把詳細實作列出，或者貼出 commit 的連結來參考
- 我認為可以適當的在程式碼中間加入一點空行，增加可讀性。
> 工程人員說話要明確，避免說「感覺」
> 與其談「心法」，不如設想「如果我是你」，我會怎麼做，示範一次給同學看，而且檢討自己哪裡沒做好，從而呼應原本學員的不足處。
> [軟體工程師要學會說故事](https://ruddyblog.wordpress.com/2016/06/18/)，本作業要求學員從良性詳盡的批評開始。繼續檢討！
## 開發環境
```shell
$ gcc --version
gcc (Debian 12.2.0-14) 12.2.0
Copyright (C) 2022 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
Address sizes: 40 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 1
On-line CPU(s) list: 0
Vendor ID: GenuineIntel
Model name: Common KVM processor
CPU family: 15
Model: 6
Thread(s) per core: 1
Core(s) per socket: 1
Socket(s): 1
Stepping: 1
BogoMIPS: 5999.99
```
## 實驗圖表生成程式
`python labtest.py config.yml labtest.png`
```python
import sys
import matplotlib.pyplot as plt
import subprocess
import yaml
import importlib
with open(sys.argv[1], 'r') as f:
config = yaml.load(f, Loader=yaml.FullLoader)
data = [[] for a in config['lab']]
size = list(range(int(config['size']['min']), int(config['size']['max']), int(config['size']['step'])))
for a in size:
for idx, b in enumerate(config['lab']):
testcase = importlib.import_module(f'testcase.{b["testcasegen"]}').init(a)
time = subprocess.run(b['command'], input=testcase, stdout=subprocess.PIPE).stdout.decode()
time = float(time.split('\n')[0])
data[idx].append(time)
plt.xlabel('size', fontsize=20)
plt.ylabel('time', fontsize=20)
for idx, a in enumerate(data):
plt.scatter(size, a, c=config['lab'][idx]['color'], alpha=0.5)
plt.savefig(sys.argv[2])
```
## 針對佇列操作的程式碼實作
### q_new
實作建立一個空的佇列，建立一個 `list_head` 用來連結佇列的第一個節點以及最後一個節點。
:::danger
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
> 已修
:::
```c
struct list_head *q_new()
{
struct list_head *node = malloc(sizeof(struct list_head));
if (!node)
return NULL;
INIT_LIST_HEAD(node);
return node;
}
```
### q_free
實作佇列的釋放，當佇列被釋放，裡面的所有節點理應被釋放，如果佇列為空的 for 便不會執行，直接釋放佇列本身。
```c
void q_free(struct list_head *l)
{
if (!l)
return;
struct list_head *node, *safe;
list_for_each_safe (node, safe, l) {
list_del(node);
element_t *element = container_of(node, element_t, list);
e_free(element);
}
free(l);
}
```
### q_insert_head 與 q_insert_tail
建立一個新節點並且加入到鏈結串列的頭部或尾部。
考慮到堆疊釋放的情況，因此要對字串做複製。
```diff
if (!head || !s)
return false;
element_t *element = e_new(s);
if (!element)
return false;
- list_add(&(element->list), head);
+ list_add_tail(&(element->list), head);
return true;
```
考慮到兩者有高度相似，可運用巨集來代替減少重複程式。
```c
/* Base function for insert an element into queue */
#define q_insert_base(head, s, list_add_method) \
if (!head || !s) \
return false; \
element_t *element = e_new(s); \
if (!element) \
return false; \
list_add_method(&(element->list), head); \
return true;
/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
q_insert_base(head, s, list_add);
}
/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
q_insert_base(head, s, list_add_tail);
}
```
### q_remove_head 與 q_remove_tail
從鏈結串列的頭部或尾部移除一個節點。
```diff
- if (!head || head->next == head) return NULL;
- element_t *element = container_of(head->next, element_t, list);
+ if (!head || head->prev == head) return NULL;
+ element_t *element = container_of(head->prev, element_t, list);
list_del(&(element->list));
strncpy(sp, element->value, bufsize - 1);
sp[bufsize - 1] = '\0';
return element;
```
同理，可以運用巨集來代替減少重複程式。
```c
#define q_remove_base(head, sp, bufsize, nextprev) \
if (!head || head->nextprev == head) \
return NULL; /* When head->next or head->prev == head queue is empty \
*/ \
element_t *element = container_of(head->nextprev, element_t, list); \
list_del(&(element->list)); \
strncpy(sp, element->value, bufsize - 1); \
sp[bufsize - 1] = '\0'; \
return element;
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
q_remove_base(head, sp, bufsize, next);
}
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
q_remove_base(head, sp, bufsize, prev);
}
```
實作時也產生一個疑問是為甚麼 `list_del` 的無效記憶體位址一定要是 0x00100100 與 0x00200200 而不是其他數字如：0x00100101、0x00200202、0x0 之類的。
:::warning
這問題很好，你可參見 Linux 核心原始程式的 git log 來解讀。
:::
### q_size
實作計算佇列的長度。
由於計算需要迭代計算，如果一次走兩步或許可以加快運行的速度。
> <s>所以真的有比較快嗎? 真心發問</s>
> 雖然迴圈次數減少一半，但是實際上指標還是前進了整個佇列，條件也相對變多，請問真的會比較快嗎?
> [name=jujuegg]
:::danger
不要書寫「真心發問」，詳盡提出你的疑慮和佐證，這樣才能有效溝通。
真誠地分享你的專業知識，讓溝通能夠達到共鳴，才是真正展現禮貌的方式。
:::
```c
int q_size(struct list_head *head)
{
if (!head)
return -1;
int size = 0;
struct list_head *node;
for (node = head->next; node != head && node->next != head;
node = node->next->next, size+=2) {
}
size += (node != head) & 1;
return size;
}
```
#### 實驗
<s>測資產生器</s>
:::danger
「產生器」不是精準的詞彙，因為你應當有明確的測試計畫，並從數學分析 (或已有的論述) 證實該計畫可行，接著才用程式碼去產生對應的資料輸入。否則，你只是「憑感覺」做事，根本不能算是「工程」。
:::
```python
def init(size):
return f"""new
ih RAND {size}
size
quit
""".encode()
```
設定檔
```yaml
size:
min: 1000
max: 100000
step: 100
lab:
# 一步一步算
- command:
- "./qtest-normal"
- "-v"
- "0"
color: 'blue'
testcasegen: 'size'
# 二步二步算
- command:
- "./qtest"
- "-v"
- "0"
color: 'red'
testcasegen: 'size'
```
結果：
- min: 100 max: 1000 step: 1
- min: 1000 max: 10000 step: 10
- min: 1000 max: 100000 step: 100
結論：在 size 高的情況兩步兩步算真的比較快一點點
:::danger
需要更多的解讀，從電腦科學的基礎學科的角度去陳述，避免說「真的比較快一點點」。
:::
### q_delete_mid
參考「[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)」，使用快慢指標並且由於使用環狀鏈結串列因此終止判斷會以 `= head` 為標準。
```c
for (fast = head->next, slow = head->next;
fast != head && fast->next != head;
fast = fast->next->next, slow = slow->next) {
}
list_del(slow);
element_t *element = container_of(slow, element_t, list);
e_free(element);
```
### `q_delete_dup`
由於 github action 上的 ubuntu 以及我自己的 debian 版本所使用的 glibc 版本皆低於 2.38，而 2.38 後的 strcmp 有做<s>優化</s>，在這之前的 strcmp 都是一個字元做比較，效能不佳。
:::danger
某些濫用「優化」的語境，根本與「改良」和「改善」無異，那為何不直接講「改良」和「改善」呢？
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
- Debian 12.4
```
$ ldd --version
ldd (Debian GLIBC 2.36-9+deb12u4) 2.36
Copyright (C) 2022 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.
Written by Roland McGrath and Ulrich Drepper.
```
- Ubuntu 22.04.3 LTS
```
$ ldd --version
ldd (Ubuntu GLIBC 2.35-0ubuntu3.6) 2.35
Copyright (C) 2022 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.
Written by Roland McGrath and Ulrich Drepper.
```
- glibc 2.38 前的 strcmp 實作
```c
int
STRCMP (const char *p1, const char *p2)
{
const unsigned char *s1 = (const unsigned char *) p1;
const unsigned char *s2 = (const unsigned char *) p2;
unsigned char c1, c2;
do
{
c1 = (unsigned char) *s1++;
c2 = (unsigned char) *s2++;
if (c1 == '\0')
return c1 - c2;
}
while (c1 == c2);
return c1 - c2;
}
```
因此這邊將優化後的 strcmp 做移植，作為 newstrcmp。
```c
list_for_each_safe (node, safe, head) {
element_t *element = container_of(node, element_t, list);
if (!check || newstrcmp(check, element->value)) {
check = element->value;
continue;
}
list_del(node);
e_free(element);
}
```
### q_swap
for 迴圈同時使用兩個節點，一次移動兩步，當其中有一個為 head 時停止。
```c
void q_swap(struct list_head *head)
{
struct list_head *nodea, *nodeb, *safea, *safeb, *tmp = NULL;
for (nodea = head->next, nodeb = nodea->next,
safea = nodea->next->next, safeb = nodeb->next->next;
nodea != head && nodeb != head;
nodea = safea, nodeb = safeb,
safea = nodea->next->next, safeb = nodeb->next->next) {
list_move(nodea, nodeb);
}
}
```
### q_reverse
一個一個的把 head->prev 移到 head->next 後面。
```c
void q_reverse(struct list_head *head)
{
if (!head)
return;
for (struct list_head *node = head, *move = head->prev; node != move;
node = move, move = head->prev) {
list_move(move, node);
}
}
```
### q_reverseK
從頭迭代 k 次並把這個範圍的節點取出來另外存成一個鏈結串列以後做一次 `q_reverse` 再放回來原來的位置。
```c
for (first = head->next, last = first; first != head;
first = lastnext, last = first) {
for (int i = 0; i < k - 1 && last != head; i++, last = last->next) {
}
if (last == head)
return;
firstprev = first->prev;
lastnext = last->next;
lastnext->prev = firstprev;
firstprev->next = lastnext;
tmphead.next = first;
first->prev = &tmphead;
tmphead.prev = last;
last->next = &tmphead;
q_reverse(&tmphead);
list_splice(&tmphead, firstprev);
}
```
### q_ascend 與 q_descend
從後面往前迭代，當出現大於/小於前一個節點時，便刪除該節點。
```c
for (node = head->prev, safe = node->prev; node != head;
node = safe, safe = node->prev) {
element = container_of(node, element_t, list);
if (check && newstrcmp(check, element->value) op 0) {
list_del(node);
e_free(element);
continue;
}
check = element->value;
len++;
}
```
### q_sort
參考 [Linux 核心的鏈結串列排序](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-e) 並且閱讀 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)，這邊採用 Queue-Mergesort。
先寫一個巨集來處理合併兩個列表
```c
#define mergelist(nodea, nodeb, mergeadd, mergesplice, mergehead) \
{ \
struct list_head *lastnode = nodeb, *safe, **pnode; \
while (nodea && nodeb) { \
element_t *elementa = container_of(nodea, element_t, list), \
*elementb = container_of(nodeb, element_t, list); \
bool cmpresult = ((!descend) * 2 - 1) * \
newstrcmp(elementa->value, elementb->value) < \
0; \
pnode = cmpresult ? &nodea : &nodeb; \
safe = (*pnode)->next; \
lastnode = cmpresult ? nodeb : nodea; \
mergeadd(*pnode, mergehead); \
*pnode = safe; \
} \
mergesplice(lastnode, mergehead); \
}
```
sort 總共有兩個階段，第一個階段是將 `list` 移到 `pending` 並且對部分節點做合併，第二階段是將所有 pending 做合併。
第一階段的每個迴圈先做 `count++` 接著判斷是否做合併最後將原本的 `pending` 放到 `list` 上並且 `list` 成為新 `pending` 然後切到下一個 `list`。當需要合併時，對 `count` 做 `ffs` 得到需要對哪兩個列表做合併，使用 `mergelist` 處理合併，最後更新 `*ppending`。
第二階段時先對 `head` 做初始化，並且使用 `mergelist` 對 `head` 與目前的 `pending` 做合併。
### q_merge
每兩個鏈結串列一組做合併，遇到長度為 0 就跳過，持續到只有一條鏈結串列有東西為止。
```c
do {
count = 0;
mergehead = NULL;
list_for_each_safe (node, safe, head) {
queue_contex_t *queue = container_of(node, queue_contex_t, chain);
if (!queue->q || (!queue->size && queue->q != head->next)) {
continue;
}
count++;
if (mergehead) {
mergehead->q->prev->next = NULL;
queue->q->prev->next = NULL;
struct list_head *nodea = mergehead->q->next,
*nodeb = queue->q->next;
INIT_LIST_HEAD(mergehead->q);
INIT_LIST_HEAD(queue->q);
mergehead->size = 0;
queue->size = 0;
mergelist(nodea, nodeb, descend, queuemergeadd,
queuemergesplice, mergehead);
queue = NULL;
count--;
}
mergehead = queue;
}
} while (count > 1);
```
:::danger
當你選定合併排序，現有的測試案例要如何涵蓋合併排序的最差狀況呢？
:::
## 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉並改進 lab0-c 的 dudect
與 [dudect](https://github.com/oreparaz/dudect) 原始程式搭配對照。
- dudect_main <-> doit
- prepare_inputs <-> prepare_inputs
- measure <-> measure
- update_statistics <-> update_statistics
- report <-> report
其中缺少 `percentile` 相關用來去除極端值的程式碼。將該功能寫入即可。
:::danger
指出論文和實作的出入之處，尚有其他！
:::
```diff
prepare_inputs(input_data, classes);
bool ret = measure(before_ticks, after_ticks, input_data, mode);
differentiate(exec_times, before_ticks, after_ticks);
+prepare_percentiles(exec_times);
update_statistics(exec_times, classes);
ret &= report();
```
Sign in with Wallet
Connect another wallet