2019q1 Homework1 (list)

contributed by < grant7163 >

tags: sysprog2019_q1

作業要求

依據 F02:list 要求。

• 回答「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 顯示結果

​​#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 有何作用？在程式碼中扮演什麼角色？
  typeof 會回傳一個傳入參數的資料型態，參數表達可以分為二種形式：

• expression

typeof(x)

• type

typeof(int *)

實驗觀察 p, w, y ,z 的資料型態

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

(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個資料型態不同的變數，就無法知道回傳變數的資料型態
• 回傳的變數會被執行兩次

#define max(a,b) ((a) > (b) ? (a) : (b))

將 max 改寫成 maxint 的方式可以解決第二個的問題

• 將傳入變數的資料型態變為一致，雖然可以確定回傳變數的資料型態，但資料有可能會不一致(被隱式轉型)，所以傳入變數的資料型態需要一致性
  • e.g : float 轉 int
  • 回傳的變數就只會被執行一次
  ​​#define maxint(a,b) \
  ​​({int _a = (a), _b = (b); _a > _b ? _a : _b; })
  

實驗將 int a, float b 代入 maxint 中，觀察其結果

#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 印出來的結果發現已經跟傳入時的數值不一致了

maxint 7.000000  

再進一步將 int 換成 typeof(a)，就可以增加 max 的擴充性，不過傳入變數的資料型態仍需一致性

#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

#define max(x,y) ({ \
    typeof(x) _x = (x);	\
	typeof(y) _y = (y);	\
	(void) (&_x == &_y);	\
	_x > _y ? _x : _y; })  

• 解釋以下巨集的原理

#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 的說明
compound statement ({ …; …; …; })

• 回傳 compound statement 中的最後一個表達式的值
• 增加使用巨集時的安全

依據 5.39 Alternate Keywords 的說明
__extension__

• 在關鍵字的前後加上 __ 可以解決關鍵字因為編譯參數 -ansi、-std=c99 等等而失效
• 防止因使用編譯參數 -Wpedantic、-pedantic 等等而讓 GNU C extensions 產生的警告

offsetof 將0強制轉成指向 TYPE 這個資料型態中的 MEMBER ，0 會被當作該 TYPE 的起始地址，然後在以 & 取得 MEMBER 的位址，即可得到 MEMBER 在 TYPE 中的 offest。

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

在 container_of 的第3行主要行為

• 紀錄所要觀察的成員位址
• 跟 max 的資料型態問題一樣，因為無法確認傳入的資料型態是否一致，用這樣的方式讓編譯器做資料型態的檢查。

const __typeof__(((type *) 0)->member) *__pmember = (ptr);

再把選定的成員位址減去 offset 就可以取得 structure 的起始位址了。

(type *) ((char *) __pmember - offsetof(type, member));  

實驗觀察 container_of 的輸出

#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 的位址是一樣的

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

struct list_head {
    uint16_t size;
    struct list_head *prev;
    struct list_head *next;
};

由圖中發現 seq 耗費的時間有很明顯的降低並略低於 random

時間單位 scale 放大

merge sort