# 2019q1 Homework1 (list)
contributed by < `grant7163` >
###### tags: `sysprog2019_q1`
## 作業要求
依據 [F02:list](https://hackmd.io/s/S12jCWKHN) 要求。
* 回答「Linux 風格的 linked list」裡頭「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼
* 從 linux-list 學習裡頭的技巧，包含裡頭 unit test 的設計，透過給定的 linked list 操作，實作出 merge sort
* 附上你的修改過程，也需要讓 qtest 得以支援
* 可將 dict 裡頭的測試資料拿來作效能分析的輸入
* 思考提升排序效率的方法，需要做平均和最壞狀況的分析
## 自我檢查
- [ ] 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
macro 會在編譯階段被編譯器展開的程式碼
* 可以加速程式的速度
* 無法充分檢查資料型態
* 增加 code size
function call 執行時需 jump 到 functiion 的進入點
* push / pop 資料到 stack
* 相同算式可以共用同一個 function
實驗觀察使用 function call 與 macro 的執行時間差異，並用 gnuplot 顯示結果
```clike=
#define OUT_FILE "func.txt"
#define OUT_FILE2 "mac.txt"
#define multi_m(a,b,c) a * b * c
int multi_f(int a,int b,int c){
return a * b * c;
}
static double diff_in_second(struct timespec t1, struct timespec t2);
int main(void)
{
struct timespec start, end;
double func_time1 = 0;
double macr_time1 = 0;
int cnt = 1000000;
int cnt2 = 1000000;
FILE *output = fopen(OUT_FILE, "a");
while(cnt--)
{
clock_gettime(CLOCK_REALTIME, &start);
multi_f(2, 4, 6);
clock_gettime(CLOCK_REALTIME, &end);
func_time1 += diff_in_second(start, end);
fprintf(output, "func_time1() %.8lf\n", func_time1);
}
fclose(output);
FILE *output2 = fopen(OUT_FILE2, "a");
while(cnt2--)
{
clock_gettime(CLOCK_REALTIME, &start);
multi_m(2, 4, 6);
clock_gettime(CLOCK_REALTIME, &end);
macr_time1 += diff_in_second(start, end);
fprintf(output2, "macr_time1() %.8lf\n", macr_time1);
}
fclose(output2);
return 0;
}
```
由圖發現當 function / macro 呼叫次數超過 10萬次時， function call 的耗時開始會比 macro 耗時還要高
- [ ] Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
- [ ] GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
typeof 會回傳一個傳入參數的資料型態，參數表達可以分為二種形式：
* expression
```shell
typeof(x)
```
* type
```shell
typeof(int *)
```
實驗觀察 p, w, y ,z 的資料型態
```clike=
int func(int a, int b)
{
return a + b;
}
int main(int argc, char *argv[])
{
int *x;
int *p[4];
typeof(x) y[3];
typeof(func(1, 3)) z;
typeof (typeof (x)[4]) w;
return 0;
}
```
使用 GDB 觀察 p, w, y ,z 的資料型態
* w 等效於 p
```shell
(gdb) whatis y
type = int *[3]
(gdb) whatis z
type = int
(gdb) whatis p
type = int *[4]
(gdb) whatis w
type = int *[4]
```
若在 runtime 時執行到 max 會產生2個問題
* 傳入的2個資料型態不同的變數，就無法知道回傳變數的資料型態
* 回傳的變數會被執行兩次
```clike=
#define max(a,b) ((a) > (b) ? (a) : (b))
```
將 max 改寫成 maxint 的方式可以解決第二個的問題
* 將傳入變數的資料型態變為一致，雖然可以確定回傳變數的資料型態，但資料有可能會不一致(被隱式轉型)，所以傳入變數的資料型態需要一致性
* e.g : float 轉 int
* 回傳的變數就只會被執行一次
```clike=
#define maxint(a,b) \
({int _a = (a), _b = (b); _a > _b ? _a : _b; })
```
實驗將 int a, float b 代入 maxint 中，觀察其結果
```clike=
#define maxint(a,b) ({int _a = (a), _b = (b); _a > _b ? _a : _b; })
int main(int argc, char *argv[])
{
int a = 3;
float b = 7.8;
float c= 0;
c = maxint(a, b);
printf("maxint %f \n", c);
return 0;
}
```
由 c 印出來的結果發現已經跟傳入時的數值不一致了
```shell
maxint 7.000000
```
再進一步將 int 換成 typeof(a)，就可以增加 max 的擴充性，不過傳入變數的資料型態仍需一致性
```clike=
#define max(a,b) \
({ typeof (a) _a = (a); \
typeof (b) _b = (b); \
_a > _b ? _a : _b; })
```
在更進階的版本，在比大小之前先確認資料型態有沒有一致，若二者資料型態不一致的話， 編譯階段就會丟出 comparison of distinct pointer types lacks a cast 的警告訊息
以下程式碼擷取自 [linux/arch/powerpc/boot/types.h](https://github.com/torvalds/linux/blob/6f0d349d922ba44e4348a17a78ea51b7135965b1/arch/powerpc/boot/types.h)
```clike=
#define max(x,y) ({ \
typeof(x) _x = (x); \
typeof(y) _y = (y); \
(void) (&_x == &_y); \
_x > _y ? _x : _y; })
```
- [ ] 解釋以下巨集的原理
```clike=
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
依據 [6.1 Statements and Declarations in Expressions](https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html) 的說明
compound statement ({ ...; ...; ...; })
* 回傳 compound statement 中的最後一個表達式的值
* 增加使用巨集時的安全
依據 [5.39 Alternate Keywords](http://pdplab.it.uom.gr/teaching/gcc_manuals/gcc/Alternate-Keywords.html) 的說明
`__extension__`
* 在關鍵字的前後加上 `__` 可以解決關鍵字因為編譯參數 -ansi、-std=c99 等等而失效
* 防止因使用編譯參數 -Wpedantic、-pedantic 等等而讓 GNU C extensions 產生的警告
`offsetof` 將0強制轉成指向 TYPE 這個資料型態中的 MEMBER ，0 會被當作該 TYPE 的起始地址，然後在以 & 取得 MEMBER 的位址，即可得到 MEMBER 在 TYPE 中的 offest。
```clike=
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
```
在 container_of 的第3行主要行為
* 紀錄所要觀察的成員位址
* 跟 max 的資料型態問題一樣，因為無法確認傳入的資料型態是否一致，用這樣的方式讓編譯器做資料型態的檢查。
```clike=
const __typeof__(((type *) 0)->member) *__pmember = (ptr);
```
再把選定的成員位址減去 offset 就可以取得 structure 的起始位址了。
```clike=
(type *) ((char *) __pmember - offsetof(type, member));
```
實驗觀察 container_of 的輸出
```clike=
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
typedef struct node
{
int a, b, c;
struct node *next;
}node_t;
int main(int argc, char *argv[])
{
node_t newnode =
{
.a = 1,
.b = 2,
.c = 3,
.next = &newnode
};
printf("newnode addr %p \n", container_of(&(newnode.b), node_t, b));
printf("newnode addr %p \n", &newnode);
return 0;
}
```
輸出結果符合預期，用二種方式得到 node_t newnode 的位址是一樣的
```shell
newnode addr 0x7ffcc391a880
newnode addr 0x7ffcc391a880
```
- [ ] 除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作，為什麼呢？這些有什麼益處？
- [ ] LIST_POISONING 這樣的設計有何意義？
- [ ] linked list 採用環狀是基於哪些考量？
- [ ] list_for_each_safe 和 list_for_each 的差異在哪？“safe” 在執行時期的影響為何？
在 lsit.h 中看到
## Sorting
三種排序的時間複雜度：
| 名稱 | 最佳 | 平均 | 最差 |
| ---------- | -------- | -------- | -------- |
| insert sort| $O(n)$ | $O(n^2)$ | $O(n^2)$ |
| quick sort | $O(nlgn)$ | $O(nlgn)$ | $O(n^2)$ |
| merge sort | $O(nlgn)$ | $O(nlgn)$ | $O(nlgn)$ |
### insertion sort
由圖中發現 random 耗費的時間明顯高於 seq
### quick sort
在範例程式中 quick sort 總是選 head list 的第一個 item 當 pivot
由圖中發現 random 耗費的時間明顯低於 seq
改善 seq 耗費的成本
總是選 head list 的第中間 item 當 pivot
為了降低搜尋在中間位置的 item，在 struct list_head 新增 size 紀錄 array 大小，不過這樣在分類 list_less, list_greater 時都要分別紀錄 size
```clike=
struct list_head {
uint16_t size;
struct list_head *prev;
struct list_head *next;
};
```
由圖中發現 seq 耗費的時間有很明顯的降低並略低於 random
時間單位 scale 放大
### merge sort
Google Drive
Gist
Clipboard
Sign in with Wallet
