Try   HackMD

2019q1 Homework1 (list)

contributted by < chengWei1123 >

開發環境

$ uname -a
Linux wei-X550JX 4.18.0-15-generic #16~18.04.1-Ubuntu SMP Thu Feb 7 14:06:04 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0

作業要求

節錄自： F02: list

  • 回答「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼

    • 自我檢查事項:

      • 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
      • Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
      • GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？
      • 解釋以下巨集的原理 
        ​​​​​​​​​​​​#define container_of(ptr, type, member)                            \
​​​​​​​​​​​​    __extension__({                                                \
​​​​​​​​​​​​        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
​​​​​​​​​​​​        (type *) ((char *) __pmember - offsetof(type, member));    \
​​​​​​​​​​​​    })
      • 除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作，為什麼呢？這些有什麼益處？
      • LIST_POISONING 這樣的設計有何意義？
      • linked list 採用環狀是基於哪些考量？
      • 什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現
      • 什麼情境會需要需要找到 第 k 大/小元素 呢？又，你打算如何實作？
      • list_for_each_safe 和 list_for_each 的差異在哪？"safe" 在執行時期的影響為何？
      • for_each 風格的開發方式對程式開發者的影響為何？
        • 提示：對照其他程式語言，如 Perl 和 Python
      • 程式註解裡頭大量存在 @ 符號，這有何意義？你能否應用在後續的程式開發呢？
        • 提示: 對照看 Doxygen
      • tests/ 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
      • tests/ 目錄的 unit test 可如何持續精進和改善呢？

  • 從 linux-list 學習裡頭的技巧，包含裡頭 unit test 的設計，透過給定的 linked list 操作，實作出 merge sort

  • 附上你的修改過程，也需要讓 qtest 得以支援

  • 可將 dict 裡頭的測試資料拿來作效能分析的輸入

  • 思考提升排序效率的方法，需要做平均和最壞狀況的分析

自我檢查清單

為何 Linux 採用 macro 來實作 linked list？

macro 只是單純的文字替換，雖然會增加 code section 的大小，但能省去 call function 時對stack 的操作，進而加快執行速度。

另外，我覺得 macro 在某些情況會比 function 更具彈性，例如 list.h 中的 list_for_each

#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

programmer 只要在呼叫 macro 後加上對 list node 的操作就好，而這一點使用 function 可能就比較難做到（可能要把對 list node 的操作寫成 function ，再把 function pointer 當成參數傳入 list_for_each function ）。

下面是我在 Macro vs Function in C 看到有人對 macro 和 function 的優缺點所做的統整

  • Macro features:

    • Macro is Preprocessed
    • No Type Checking
    • Code Length Increases
    • Use of macro can lead to side effect
    • Speed of Execution is Faster
    • Before Compilation macro name is replaced by macro value
    • Useful where small code appears many time
    • Macro does not Check Compile Errors

  • Function features:

    • Function is Compiled
    • Type Checking is Done
    • Code Length remains Same
    • No side Effect
    • Speed of Execution is Slower
    • During function call, Transfer of Control takes place
    • Useful where large code appears many time
    • Function Checks Compile Errors

不要只摘錄網路上的討論文字，設計實驗來檢驗，附上組合語言和 cycle count 分析，及早脫離「文組TM」
:notes: jserv

考慮以下程式碼 test.c























#include <stdlib.h>
#define add_m(a,b,c) a+b+c
int add_f(int a,int b,int c){
    return a+b+c;
}
int main(int argc, char *argv[]) {
    int i,j,k,result;
    int opt = atoi(argv[1]);
    int times = atoi(argv[2]);
    if(opt == 0){
        for(i=0;i<times;i++)
            for(j=0;j<times;j++)
                for(k=0;k<times;k++)
                    result = add_m(i,j,k);
    }
    else{
        for(i=0;i<times;i++)
            for(j=0;j<times;j++)
                for(k=0;k<times;k++)
                    result = add_f(i,j,k);
    }
}

argv[1] 為 0 則使用 macro, 否則用 function ; argv[2] 則為各層迴圈數。

result :

  • ​​​ $ sudo perf record ./test 0 1000
​​​ $ sudo perf report


  • ​​​ $ sudo perf record ./test 1 1000
​​​ $ sudo perf report

  • 不同迴圈次數下使用 macro 和 function 的 cycle count

Linux 應用 linked list 在哪些場合？

GNU extension 的 typeof 有何作用？

typeof(x) 會回傳 x 的 type
其中 x 可以是變數也可以是 type

例如：

  1. ​​​ int x;
​​​ typeof (x) y = 0;

    相當於

    ​​​​int y = 0;

  2. ​​​ typeof (typeof (char *)[4]) y;

    相當於

    ​​​​char *y[4];

解釋以下巨集的原理






#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })
  • __extension__
    • 使用 GNU C extensions 編譯時可能會產生 warning ，可以在 expression 前加上 __extension__ 來避免
    • Alternate Keywords
  • { }
    • braced-group within expression， compiler 會把大括號中所有 statement 當成一個 expression，並用最後一則 statement 的值作為此 expression 的結果
    • Statements and Expressions
  • __typeof__(((type *) 0)->member) *__pmember = (ptr);
    • (type *) 0:
      把0位置強制轉型成為一個指向 type 型別的指標
    • __typeof__(((type *) 0)->member)：
      取得 type 所有的 member 之型別
    • __typeof__(((type *) 0)->member) *__pmember：
      將 __pmember 宣告為指向 member 的 pointer
    • __typeof__(((type *) 0)->member) *__pmember = (ptr)
      將 ptr 的位址 assign 給 __pmembe

雖然看得懂這行在做什麼，但不太明白其中的必要性

  • offsetof(type, member):
    struct 和 member 記憶體位置的差值
  • (char *) __pmember - offsetof(type, member):
    得到 struct 的起始位置

為何除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作？

LIST_POISONING 這樣的設計有何意義？

linked list 採用環狀是基於哪些考量？

什麼情境會需要對 linked list 做排序呢？

什麼情境會需要需要找到 第 k 大/小元素 呢？

list_for_each_safe 和 list_for_each 的差異在哪？

for_each 風格的開發方式對程式開發者的影響為何？

程式註解裡頭大量存在 @ 符號，這有何意義？

tests/ 目錄底下的 unit test 的作用為何？

tests/ 目錄的 unit test 可如何持續精進和改善呢？

Merge Sort

應列出你的思路和規劃，不是急著列出程式碼。
需要提及驗證正確性和時間/空間複雜度分析
:notes: jserv

  • 程式碼
  • 思路分析

    • merge sort 主要有三個工作

      1. 把 input list 分成 2 等分
      2. 再分別對這兩個 list 做排序
      3. 把排序過的兩個 list 合併成一個排序好的 list

    • 把 input list 分成 2 等分

      • 首先要找到 list 的中點，我原本用的方法是先走訪 list 所有點的到總點數，再走訪一半的點找到中點，但後來改用直接把 list 長度當參數傳入，便可以少一次走訪全部點的時間
      • 接著用 list_cut_position() 把 list 前半移到一個 list，另一半移到另一個 list

    • 分別對這兩個 list 做排序

      • 遞迴呼叫 merge sort 就好

    • 合併兩個 sorted list

      • 當其中一個 list 為空時，只要把另一個 list 用 list_splice_tail() 接在 result list 後面
      • 當兩者都不為空時, 比較持有兩個 list 第一個 node 的 listitem 中 member i 的大小，將具有較小的 member i 者，移至 result list 的尾巴(使用 list_del()、list_add_tail() )

效能分析

random_shuffle_array 所產生的數據 (average case for all)

Last changed by 
 
cheng wei chang
0
442
Published on HackMD