2020q3 Homework (quiz6)

contributed by < hankluo6 >

測驗 1





















float fp32tobf16(float x) {
    float y = x;
    int *py = (int *) &y;
    unsigned int exp, man;
    exp = *py & 0x7F800000u;
    man = *py & 0x007FFFFFu;
    if (!exp && !man) /* zero */           
        return x;
    if (exp == 0x7F800000u) /* infinity or NaN */
        return x;

    /* Normalized number. round to nearest */
    float r = x;
    int *pr = (int *) &r;
    *pr &= BB1;
    r /= 256;
    y = x + r;

    *py &= BB2;
    return y;
}


    exp = *py & 0x7F800000u;
    man = *py & 0x007FFFFFu;

兩行分別取出 exponent 以及 mantissa 的部分，




    if (!exp && !man) /* zero */           
        return x;
    if (exp == 0x7F800000u) /* infinity or NaN */
        return x;

檢查是否為 0,

\infty

或 NAN，因 fp32 與 bfloat16 表達這些數字的格式相同，故可以直接回傳。






    /* Normalized number. round to nearest */
    float r = x;
    int *pr = (int *) &r;
    *pr &= BB1;
    r /= 256;
    y = x + r;

接著處理 round 的部分，因為 bfloat16 會將 fp32 後 23 bits 的 mantissa 縮減為 7 bits，所以要判斷 fp32 的 mantissa 中第 8 個 bit 是否為 1，來決定是否要進位。TODO


    *py &= 0xffff0000;
    return y;

最後就是把 fp32 後多出來的 bits 縮減，因多出來 16 bits 不需要，所以答案為 0xffff0000。

延伸題目:

解釋上述程式碼的運作機制，需要搭配 BFloat16: The secret to high performance on Cloud TPUs 和 Making floating point math highly efficient for AI hardware 解說;
改進上述程式碼，實作 DP/SP 轉換程式，並針對 BFloat16 撰寫測試程式，應儘量涵蓋有效的數值輸入和輸出範圍;
考慮批次轉換 FP32/FP64 為 BFloat16 的需求，請改進上述程式碼，得以提高轉換的效率;

測驗 2

#define RINGBUF_DECL(T, NAME) \
    typedef struct {          \
        int size;             \
        int start, end;       \
        T *elements;          \
    } NAME

#define RINGBUF_INIT(BUF, S, T)             \
    {                                       \
        static T static_ringbuf_mem[S + 1]; \
        BUF.elements = static_ringbuf_mem;  \
    }                                       \
    BUF.size = S;                           \
    BUF.start = 0;                          \
    BUF.end = 0;

#define NEXT_START_INDEX(BUF) \
    (((BUF)->start != (BUF)->size) ? ((BUF)->start + 1) : 0)
#define NEXT_END_INDEX(BUF) (((BUF)->end != (BUF)->size) ? ((BUF)->end + 1) : 0)

#define is_ringbuf_empty(BUF) ((BUF)->end == (BUF)->start)
#define is_ringbuf_full(BUF) (NEXT_END_INDEX(BUF) == (BUF)->start)

#define ringbuf_write_peek(BUF) (BUF)->elements[(BUF)->end]
#define ringbuf_write_skip(BUF)                   \
    do {                                          \
        (BUF)->end = NEXT_END_INDEX(BUF);         \
        if (is_ringbuf_empty(BUF))                \
            (BUF)->start = NEXT_START_INDEX(BUF); \
    } while (0)

#define ringbuf_read_peek(BUF) (BUF)->elements[(BUF)->start]
#define ringbuf_read_skip(BUF) (BUF)->start = NEXT_START_INDEX(BUF);

#define ringbuf_write(BUF, ELEMENT)        \
    do {                                   \
        ringbuf_write_peek(BUF) = ELEMENT; \
        ringbuf_write_skip(BUF);           \
    } while (0)

#define ringbuf_read(BUF, ELEMENT)        \
    do {                                  \
        ELEMENT = ringbuf_read_peek(BUF); \
        ringbuf_read_skip(BUF);           \
    } while (0)

此題為一般 circular queue 的操作方式，有兩個指標 start 與 end 用來記錄 queue 目前的開頭與結尾。從 ringbuf_write_peek(BUF) 中可以看到寫入的位置為 (BUF)->end，而 ringbuf_read_peek(BUF) 中讀取的位置則為 (BUF)->start，且 start 與 end 皆從 0 開始。可以推測出位移指標的 ringbuf_XXXX_skip(BUF) 中就是將目前指標加 1，所以答案 RB1 以及 RB2 皆為 1。

延伸題目:

解釋上述程式碼的運作機制，包含 do { … } while (0) 使用的考量

確認詳閱 C 語言前置處理器應用篇和 C 語言程式設計技巧

這邊使用 do { … } while (0) 主要是維持 code-style 一致，考慮以下程式碼
```
#define ringbuf_write(BUF, ELEMENT)    \
    ringbuf_write_peek(BUF) = ELEMENT; \
    ringbuf_write_skip(BUF);           

if (...)
    ringbuf_write(...);
else
    ...
```
此時程式會出錯， if 後只能匹配到下一行，而因 else 上方多出一行程式碼無法通過編譯，假如改成：
```
#define ringbuf_write(BUF, ELEMENT)    \
{                                      \
    ringbuf_write_peek(BUF) = ELEMENT; \
    ringbuf_write_skip(BUF);           \
}
```
則會因 ; 的存在而編譯不過，解決方法只能將 if 裡 marco 改成 ringbuf_write(...)，但這樣又有 code-style 與其他程式碼不同的情況。故使用 do { … } while (0) 能夠維持程式碼整潔，又能達到想要的效果。
此外使用 do { … } while (0) 還能防止 dangling else 的情況發生，從程式碼來看，假如為了程式能編譯而寫成以下形式：
```
if (...)
    ringbuf_write_skip(...)
else
    ...
```
則展開後會變成：
```
if (...)
    (BUF)->end = NEXT_END_INDEX(BUF);
    if (is_ringbuf_empty(BUF))
        (BUF)->start = NEXT_START_INDEX(BUF);
else
    ...
```
會發現程式可以通過編譯，但根據規格書 ISO/IEC 9899:TC3 提到：

An else is associated with the lexically nearest preceding if that is allowed by the syntax.

else 是跟著最近的 if，所以此程式運作可能會不如預期，下方的 else 會跟在最近的 if，且難以 Debug。使用 do { … } while (0) 也能夠防止此問題。

研讀 Super Fast Circular Ring Buffer Using Virtual Memory trick，指出效能改善的機制並用 C99/C11 (可搭配 GNU extension) 重新實作;

假如我們需要 enqueue 一個陣列，目前程式碼必須使用一個 for 迴圈並呼叫 ringbuf_write，而內部則會呼叫 ringbuf_write_skip 並有一次 branch 操作。
文章內先提出用 memcpy 將資料複製進 buffer 中，對應的 c 程式碼如下：

#define ringbuf_write_array(BUF, ELEMENTS, SIZE, T)                \
    do {                                                           \
        size_t part1, part1_sz, part2_sz;                          \
        part1 = min(SIZE, (BUF)->size + 1 - (BUF)->end);           \
        part1_sz = part1 * sizeof(T);		                     \
        part2_sz = SIZE * sizeof(T) - part1_sz;                    \
        memcpy((BUF)->elements + (BUF)->end, ELEMENTS, part1_sz);  \
        memcpy((BUF)->elements, ELEMENTS + part1, part2_sz);       \
        (BUF)->end = ((BUF)->end + SIZE) % ((BUF)->size + 1);      \
    } while(0)

這邊 (BUF)->size 需要加 1 是因為題目中的 buffer 為 size + 1 的陣列，用來區分 empty 與 full 兩種狀態，故為了符合原結構必須加 1。

但這種方法會呼叫到兩次 memcpy，因為複製的資料大小有可能會超過 buffer 的尾端，所以分成一次複製目前 index buffer.end ~ buffer.size - 1，另一次則從 0 ~ 資料長度。

可以透過 virtual memory 來讓硬體幫我們做上述的事情，概念是使用到 mmap function

mmap() creates a new mapping in the virtual address space of the calling process.

個人理解是將 process 內的記憶體映射到虛擬記憶體上，就能透過一般記憶體操作來存取外部資料。

先從虛擬記憶體取得一個兩倍 buffer.size 的空間來放置 buffer，接著將 buffer 映射到一個暫存檔的開頭，注意這邊將 buffer 分成兩區塊，兩區塊都映射到同個檔案的開頭位置，這樣當 memcpy 超過 buffer 大小時(也就是複製到第二區塊)，因為第二區塊指向的位置就是檔案的開頭(第一區塊的開頭)，所以複製到第二區塊的資料會寫入到檔案的開頭，就能夠形成環狀的效果，最後再將 buffer.end 設定到正確的位置即可。

底下舉出例子來說明：

先 enqueue 一個三個元素的陣列 [a, b, c]：

接著 enqueue 另一個兩個元素的陣列 [d, e]，此時超過 queue 的大小，所以會覆蓋掉開頭的元素：

此時也會更新 buffer.end 回到 1st mmap's buffer 上。

對應的程式碼如下：

#define RINGBUF_INIT(BUF, S, T)                                             \
    do {						                      \
        const size_t pagesize = getpagesize();                              \
        size_t size = ((float)(S * sizeof(T)) / pagesize) * (pagesize + 1); \
        const int fd = fileno(tmpfile());                                   \
        if (fd == -1) {						       \
            fprintf(stderr, "error on open temporary file");                \
            exit(1);							       \
        }						                      \
        ftruncate(fd, size);						       \
        my_buf.elements = mmap(NULL, 2 * size, PROT_NONE,                   \
                       MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);                 \
        if (my_buf.elements == MAP_FAILED) {			    	       \
            fprintf(stderr, "error on mapping");               	       \
            exit(1);                                                        \
        }                                                                   \
        mmap(my_buf.elements, size, PROT_READ | PROT_WRITE,	               \
                       MAP_SHARED | MAP_FIXED, fd, 0); 		       \
        mmap(my_buf.elements + size / sizeof(T), size,			\
                       PROT_READ | PROT_WRITE, MAP_SHARED | MAP_FIXED, fd, 0);\
        BUF.size = size / sizeof(T);                                        \
        BUF.start = 0;                                                      \
        BUF.end = 0; 						               \
        } while(0) 							       \
        
#define ringbuf_write_array(BUF, ELEMENTS, SIZE, T)                        \
    do {                                                                   \
        memcpy((BUF)->elements + (BUF)->end, ELEMENTS, SIZE * sizeof(T));  \
        (BUF)->end = ((BUF)->end + SIZE) % ((BUF)->size + 1);              \
    } while(0)

與原本使用迴圈的版本進行效能分析，下方圖為寫入 1500 個 integer 進 1024 bytes 大小的 ring buffer 10000 次的時間：

可看出使用 for 的版本時間遠大於 memcpy 的版本，與預期結果相符。

將 memcpy 版本放大來看使用 virtual memory 的效能是否較好：

只有些微的差距，其時間應該為第二個 memcpy 運作的時間所影響。

測驗 3

#include <stdio.h>

/* clang-format off */
#define cons(x, y) (struct llist[]){{y, x}}
/* clang-format on */

struct llist {
    int val;
    struct llist *next;
};

void sorted_insert(struct llist **head, struct llist *node)
{
    if (!*head || (*head)->val >= node->val) {
        node->next = *head;
        *head = node;	
        return;
    }
    struct llist *current = *head;
    while (current->next && current->next->val < node->val)
        current = current->next;
    node->next = current->next;
    current->next = node;
}

void sort(struct llist **head)
{
    struct llist *sorted = NULL;
    for (struct llist *current = *head; current;) {
        struct llist *next = current->next;
        sorted_insert(&sorted, current);
        current = next;
    }
    *head = sorted;
}

int main()
{
    struct llist *list = cons(cons(cons(cons(NULL, A), B), C), D);
    struct llist *p;
    for (p = list; p; p = p->next)
        printf("%d", p->val);
    printf("\n");

    sort(&list);
    for (p = list; p; p = p->next)
        printf("%d", p->val);
    printf("\n");
    return 0;
}

摘錄自 C 語言程式設計技巧：

C99 [6.5.2.5] Compound literals

The type name shall specify an object type or an array of unknown size, but not a variable length array type.

A postfix expression that consists of a parenthesized type name followed by a braceenclosed list of initializers is a compound literal. It provides an unnamed object whose value is given by the initializer list.

If the type name specifies an array of unknown size, the size is determined by the initializer list as specified in 6.7.8, and the type of the compound literal is that of the completed array type. Otherwise (when the type name specifies an object type), the type of the compound literal is that specified by the type name. In either case, the result is an lvalue.

分析 #define cons(x, y) (struct llist[]){{y, x}} 的行為，對照上述規格書的內容，可知 {{y, x}} 為 compound literals，會回傳一個 unnamed object 且其 type 為給定的 struct llist[]。又因 array 為 unknown size，所以回傳的 object 之 size 應為 initializer list 中的數量。

這邊 {{y, x}} 有兩層 braces(中括號)是因為最外面那層用來將 expression 轉為 compound literals，裡面那層則是宣告一個 type 為 struct llist 的 array 且其擁有 1 個 元素。

其實這邊不需要兩層 braces，GCC 會自動判斷陣列合適的長度

回到程式中：

struct llist *list = cons(cons(cons(cons(NULL, A), B), C), D);

會先從內部 cons(NULL, A) 開始展開，會回傳一個匿名的 struct 陣列，其含有一元素且內部的值為 val = A, next = NULL，先稱之為 unnamed，接著執行 cons(unnamed, B) 會將剛剛的陣列傳入，因為陣列的開頭位置 = 陣列第一個元素的位置 = 陣列名稱指向之位置，所以將陣列 unnamed 傳入到 struct llist *next 時等同於將 next 指向 unnamed 的第一個元素之位置，就能達成 linked list 串接的動作，剩下以此類推。

sort 函式使用 insertion sort 來完成 linked list 的排序。其中 for 迴圈遍歷整個 list，對每個 node 皆做 sorted_insert 的插入動作，最後再將 head 改成 sorted list 的 head。

sorted_list 當中，可以發現 if (!*head || (*head)->val >= node->val) 檢查 head 是否為空以及當前 node 的 value 是否比 head 的 value 還小，這兩種情形都須將 node 插入到 head 的前方，所以答案應為 node->next = *head; 及 *head = node;，接著 while 迴圈用來尋找已排序的 list 中第一個 value 比 node 還大的位置，並插入進去。

延伸題目:

解釋上述程式碼的運作機制，參照 C 語言程式設計技巧，需要列出相關的 C 語言規格描述並解讀;

研讀 Doubly Linked Lists in C 並比對 Linux 核心的 linked list 實作予以解說;

Linux kernel 提供的 List 可以被嵌入至自定義的結構中來使用，其定義如下：

struct list_head {
    struct list_head *next, *prev;
};

有兩個指標，分別指向 prev 以及 next 的 list_head，此結構將會內嵌至使用者定義的結構中，例如以下：

struct foo {
    int data;
    struct list_head my_list;
    int other_data;
};

要開始使用之前，需要建立一個 head 當作 linked list 的起點(head 不包含在自定義結構內)，可以透過 INIT_LIST_HEAD 來初始化 list_head，其內部會展開成：

#define LIST_HEAD(name) \
    struct list_head name = { &(name), &(name) }

要將新增的 list_head 插入至目前 linked list 中可使用

static inline void list_add(struct list_head *new, struct list_head *head)
static inline void list_add_tail(struct list_head *new, struct list_head *head)

兩函式，其內部 __list_add 可以選擇插入的位置。

同理，移除節點只需呼叫

static inline void list_del(struct list_head *entry)

就會將該節點的 prev 與 next 相接，並將 entry 接到 LIST_POISON1 與 LIST_POISON2。

LIST_POISON 定義在 poison.h 當中，根據註釋：

These are non-NULL pointers that will result in page faults under normal circumstances, used to verify that nobody uses non-initialized list entries.

可以保證此記憶體不會被使用到。

list_entry 函式提供了一個方法用來從結構中的成員取得到其所在結構的位置，以上面的例子就是可以從一個 list_head 的位置來得到所在的 foo 結構的物件位置，其分別使用到的 marco 有以下：

#define offsetof(TYPE, MEMBER)	((size_t)&((TYPE *)0)->MEMBER)
    
#define container_of(ptr, type, member) ({				\
    void *__mptr = (void *)(ptr);					\
    BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) &&	\
             !__same_type(*(ptr), void),			\
             "pointer type mismatch in container_of()");	\
    ((type *)(__mptr - offsetof(type, member))); })

#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

先看 offsetof，將 0 強制轉型為 (TYPE *)，此時 0 可當作 TYPE 的起始位置，接著透過這個位置取其成員 MEMBER 之位置，就是該成員與 0 位置(TYPE 的位置) 的offset。

因此行為在 C11 為未定義行為，故 GCC 有提供內建的 __builtin_offsetof 來達成上述行為。

參考 Offsetof

有了 member 與起始點的 offset 後，只要知道 member 真正的位置，減掉 offset 後就是該結構物件的位置，最後在轉行為該結構的指標回傳。

現在在看 list_entry 就很清楚了，給定 member 位置，就能夠得到該成員所屬結構的記憶體位置，有了這些知識後，就能理解 list_for_each_entry 的實作：

/**
 * list_for_each_entry	-	iterate over list of given type
 * @pos:	the type * to use as a loop cursor.
 * @head:	the head for your list.
 * @member:	the name of the list_head within the struct.
 */
#define list_for_each_entry(pos, head, member)		        \
    for (pos = list_first_entry(head, typeof(*pos), member);	        \
         !list_entry_is_head(pos, head, member);			 \
         pos = list_next_entry(pos, member))

#define list_first_entry(ptr, type, member) \
    list_entry((ptr)->next, type, member)
    
#define list_next_entry(pos, member) \
    list_entry((pos)->member.next, typeof(*(pos)), member)

pos 會取得 member 所在之結構的位置，就能透過此位置來存取其他想要的資料，接著再透過相同的 member 來取得下一個 node，就能遍歷 linked list 所有元素。

練習 LeetCode 148. Sort List，嘗試將 Optimizing merge sort 的手法引入到 C 程式中實作

測驗 4

int findDuplicate(int *nums, int numsSize)
{
    int res = 0;
    const size_t log_2 = 8 * sizeof(int) - __builtin_clz(numsSize);
    for (size_t i = 0; i < log_2; i++) {
        int bit = 1 << i;
        int c1 = 0, c2 = 0;
        for (size_t k = 0; k < numsSize; k++) {
            if (k & bit)
                ++c1;
            if (nums[k] & bit)
                ++c2;
        }
        if (c1 < c2)
            res += bit;
    }
    return res;
}

開頭的 log_2 用來紀錄 MSB 的位置，因為 nums 值範圍只會在 1 ~ numsSize - 1 之中，所以 bit 操作只須到 MSB 的位置即可。

接著對每個 bit 操作，要判斷多出來的那個數字在此 bit 位置上為 0 或 1，用兩個變數 c1 與 c2，c1 會計算 0 ~ numsSize - 1 在該 bit 上為 1 的數量，而 c2 則是 nums 內在該 bit 上為 1 的元素數量。可以知道當 nums 內剛好 0 ~ numsSize - 1 每個數字皆出現時，c1 == c2，但現在 nums 中有一個數字出現兩次以上，就會佔掉範圍 0 ~ numsSize - 1 中 0 的部份，造成此數字多出對應的 bit 數量，故答案為 c1 < c2。

延伸題目:

解釋上述 LeetCode 題目和程式碼的運作機制，指出改進空間並實作;
實作不同的程式碼 (合法的 C 程式，可運用 GNU extension)，使其表現優於上述程式碼;

參考 leetcode solution，可以將每個 entry 的值當成 index 連接到陣列中的其他 entry，因為陣列中必有重複元素，所以此連接圖最後一定會出現一個 cycle，且此 cycle 的進入點為重複元素。

這樣此題就能夠用 Floyd's algorithm 求解 cycle 的進入點。
```
int findDuplicate(int* nums, int numsSize){
    int h,t;
    h = t = nums[0];
    do {
        t = nums[t];
        h = nums[nums[h]];
    } while (t != h);

    t = nums[0];
    while (t != h) {
        t = nums[t];
        h = nums[h];
    }

    return h;
}
```
Runtime: 4 ms, faster than 99.44% of C online submissions for Find the Duplicate Number.
Memory Usage: 7.3 MB, less than 100.00% of C online submissions for Find the Duplicate Number.

2020q3 Homework (quiz6)

測驗 1

延伸題目:

測驗 2

延伸題目:

測驗 3

延伸題目:

測驗 4

延伸題目:

tags: linux2020

Read more

Linked List Sort

2021q1 Homework5 (sort)

2022q1 Homework5 (quiz5)

2022q1 Homework5 (quiz6)

tags: `linux2020`