# 期末問答
###### tags: `linux2020`

### a) 知道 x - y < 0 敘述為何不能寫為 x < y 嗎？ (CS:APP 第 2 章)
**因為 overflow 的可能性**。

考慮以下程式碼：

char greater_sub(int a, int b)
{
    if(a - b < 0){
        return 'b';
    }
    return 'a';
}

char greater_cmp(int a, int b)
{
    if(a < b){
        return 'b';
    }
    return 'a';
}

int main(){
    int a = INT_MAX, b = -100;
    printf("%c\d", greater_sub(a, b));
    printf("%c\d", greater_cmp(a, b));
    a = INT_MIN, b = 100;
    printf("%c\d", greater_sub(a, b));
    printf("%c\d", greater_cmp(a, b));
    return 0;
}

以西檢的方式做比較時，若出現正數減負數導致超過 $2^{31} - 1$ 或負數減正數導致少於 $-2^{31}$都會出現 overflow 的情況，因此上述程式碼會輸出：

b
a
a
b

可知以比較的方式才有正確性。

### b) 知道 C 語言規格書如何解釋 ptr++ 和 *ptr++ 行為的差異嗎？
以 C99 規格書 (ISO/IEC 9899:1999) 做說明：

#### `ptr++`
接著，6.5.2.4.2 的敘述：
> **The result of the postfix ++ operator is the value of the operand.** After the result is obtained, the value of the operand is incremented. (That is, the value 1 of the appropriate type is added to it.) See the discussions of additive operators and compound assignment for information on constraints, types, and conversions and the effects of operations on pointers. **The side effect of updating the stored value of the operand shall occur between the previous and the next sequence point.**

( Annex C 中列出所有 sequence point )

因此，假設以下程式碼：

/* ptr == 0x1000FFFF */
printf("%p\n", ptr++);
printf("%p\n", ptr);

第二行的 `ptr++` 回傳 `0x1000FFFF`，且由於 `printf()` 為一個 function call, 在得到所有參數的內容之後，到實際呼叫之前，必會進行 increment，在第三行時 `ptr` 已為 `0x10010000`。

#### `*ptr++`

§6.5 Expression - 註解 74 中：
> The syntax specifies the precedence of operators in the evaluation of an expression, which is the same
as the order of the major subclauses of this subclause, highest precedence first.

而規格書中，
+ `*` (unary * operator) 在 §6.5.3 內,
+ `++` (postfix increment) 在 §6.5.2 內

可以得知後者的 precedence 高於前者，可以視為
`(*(ptr++))`。

接著，執行 `ptr++`，由於 `ptr++` 會提供原始值，會對 0x1000FFFF 進行 dereference，並在下個 sequence point 前的任一時間進行 ptr 的 increment。

### c) 知道 `void (*signal(int sig, void (*handler)(int))) (int);` 這樣的宣告該如何解讀嗎？

**此為函式 signal() 的宣告式。**

參數：
+ `int sig`
+ 一個傳入 `int` 回傳 `void` 的 function pointer `handler`

回傳值：
+ 一個傳入 `int` 回傳 `void` 的 function pointer

### d) 知道 Linux 核心 <include/linux/list.h> 裡頭：<br>`#define list_for_each_prev(pos, head)` <br> `for (pos = (head)->prev; pos != (head); pos = pos->prev)` <br>這樣的巨集到底在做什麼？以及 `head` 使用時需要加小括號，為何？

+ 這個 macro 可以用在 linux 中使用的 linked-list 的 node 之中。linux 系通中設計的 linked_list 為雙向環狀，因此若從 `head` 開始一路倒退，可以以倒序對 list 成員進行處理。

+ `head` 需要加括號的原因是為了避免巨集發生錯誤，舉例來說，這個巨集除去 `head` 的小括號並搭配三元運算子： list_for_each_prev(node_ptr, flag ? head1 : head2)`，展開後會變成 for(node_ptr = flag ? head1 : head2->prev; node_ptr != flag ? head1 : head2; node_ptr = node_ptr->prev)`，顯然跟想使用的方式不同。

### e) 知道從 color space RGBA8888 轉換為 8-bit 灰階的程式如何撰寫，又如何透過 SIMD 進行最佳化嗎？

### f) 知道如何對 linked list 進行 merge sort 嗎？真實世界中的應用場景為何？

#include <stdlib.h>
#include <stdio.h>

#define connect(a, b) (struct Node[]){{a, b}}

typedef struct Node{
    int data;
    struct Node *next;
}node_t;

void print_list(node_t *head){
    while(head){
        printf("%d ->", head->data);
        head = head->next;
    }
    putchar('\n');
    return;
}

node_t *merge_list(node_t *l, node_t *r)
{
    node_t *head = NULL;
    node_t **temp = &head;

    // Pick smaller of both list's head, until one is empty
    while (l && r) {
        if (l->data < r->data) {
            *temp = l;
            l = l->next;
        } else {
            *temp = r;
            r = r->next;
        }
        temp = &((*temp)->next);
    }

    // Connect the remains
    if (l)
        *temp = l;
    if (r)
        *temp = r;

    return head;
}

node_t *sort(node_t *head)
{
    // Base cases
    if (!head || !head->next) {
        return head;
    }

    // Split list into 2 paritions
    node_t *fast = head->next;
    node_t *slow = head;

    while (fast) {
        fast = fast->next;
        if (fast) {
            slow = slow->next;
            fast = fast->next;
        }
    }
    fast = slow->next;
    slow->next = NULL;

    // Sort each parition
    node_t *l = sort(head);
    node_t *r = sort(fast);

    return merge_list(l, r);
}

int main(){
    node_t *head = connect(4, connect(1, connect(9, connect(3, connect(5, NULL)))));

    print_list(head);
    head = sort(head);
    print_list(head);
    return 0;
}

Output:

4 ->1 ->9 ->3 ->5 ->
1 ->3 ->4 ->5 ->9 ->

#### 應用場景
假設有下方的樣子的拼圖：
因為形狀相同，可以被隨機拼湊，例如這樣：

我們就可以用上方的演算法，將其對半分開 (`slow` 和 `fast` 的部分)，
對兩半繼續以遞迴的方式進行排序，最終完成

libc++ 中， 在符合某些限制的情況 (<span style="color:gray">e.g., 足夠的額外記憶體空間</span>)，`std::stable_sort()` 也會使用 merge-sort 來進行排序。

### g) 知道 memory misalignment 對程式正確性和效能的影響嗎？
當我們試著從一個 word 的中央進行記憶體 access 時，稱為 memory mislignment。

#### 正確性影響：

#### 效能影響：
若某系統只能對各個 word 開頭進行 load, 遇見如上面的 misalignment access 必須如下進行：

1. 對使用到的兩個 word 分別進行 load
2. 利用 shift 將雙方的所需資料移置所需位置
3. 利用 OR 等方式進行合併

### h) 知道如何用 bit-wise operator 實作 clz / ctz (count leading/tailing zero) 嗎？

### i) 知道 C 語言規格書中如何定義 object 的生命週期嗎？能否舉出至少兩相對應的 CVE 呢？

### j) 知道如何寫出時間複雜度和空間複雜度皆為 O(1) 的 abs64 嗎？(沒有分支) 這樣的 abs64 又可用於真實世界哪邊？

### k) 知道 C 語言編譯器如何做 Tail Call Optimization (TCO) 嗎？以 gcc 來說，什麼樣的遞迴程式可做 TCO，又有什麼樣的遞迴程式無法呢？

### l) 知道 page fault 嗎？Segmentation fault 的訊息是如何顯示出來，請以 GNU/Linux 為例解說

### m) 知道 fixed point 嗎？相較於 floating point，這樣的機制有何優缺點呢？知道真實世界如何運用嗎？

#### Fixed Point
將小數點　(decimal / radix) 的位置固定於一個 word 的某處，使左方 (整數部分)和右方(小數部分)皆以某固定位元數表示。舉例來說，
不考慮負數，這個範例便可以以 32-bit 表示從 $0$ 開始，每個 step 大小為 $2^{-24}$，到 $2^9 - 2^{-24}$ 範圍內的所有數字。

**優點**:
+ 範圍內每個有效數字的精度相同
+ 與整數計算方式相同，速度較快

**缺點**:
+ 可表示數字範圍小

#### Floating Point
$(-1)^{\text{sign}}\times2^{\text{exponent}-127}\times1.\text{fraction}_2$ 用來計算代表的值

**優點**:
+ 可以表示大範圍的數字

**缺點**:
+ 與整數的計算方式相異且速度較慢
+ 在極大和極小的數字之精度差

#### 運用方式
假設今日我們可以確定小數點後的位數，我們可以選用 fixed point 來表示數字：
假設小數點最多三位，我們可以用 `00...001` 來表示 0.001，`00...010` 表示 0.002，以此類推，便可以以整數計算相同的速度來處理這些數字。

而 floating point 則比較 general-purpose, 用來應對不確定可能值的狀況。

### n) 知道 Poisson distribution 在本學期的課程主題中，出現在哪？以及為何工程議題需要考慮機率統計，能舉例嗎？

引用自 Wiki:
> The Poisson distribution is popular for modeling the number of times an event occurs in an interval of time or space.

### o) 知道 LRU replacement policy 對程式碼效能的影響嗎？如何撰寫程式去驗證某個處理器的 cache 行為呢？

### p) 看懂 CS:APP 第 9 章講虛擬記憶體的描述嗎？知道 Linux 如何處理嗎？

### q) 知道傅立葉分析在通訊領域的應用嗎？舉例說明

### r) 知道如何用 gcc 內建的 __builtin_ctz 改寫 GCD (最大公因數) 求值程式嗎？做了這樣的最佳化，預期在 x86_64 上可省下多少 cycle 呢？

### s) 知道如何實作無失真資料壓縮嗎？你知道有哪些相關演算法？
首先，無失真資料壓縮的定義為：
+ **在資料還原時能夠還原出原始資訊。**

常見的壓縮演算法有例如以下數種：
- 泛用
+ Huffman Coding
+ Lempel-Ziv Compression 家族
- 音訊
+ FLAC
- 2D 圖像
+ PNG
+ JPEG-LS

簡單試著說明 Huffman Code 的演算法，便是：
1. 根據各字元權重創建 Huffman Tree (二元數)，其中各字元都在葉節點，可以根據位置得到每個字元的編碼
2. 接著以查表方式輸出壓縮結果

### t) 知道 Bloom filter 嗎？以你寫過或用過的程式，舉例說明這機制帶來的好處

### u) 知道 ARMv7-A 指令的 conditional execution 嗎？請舉例說明其用法。

簡單來說，**Conditional Execution** 是一個利用 CPSR Register 狀態來決定是否執行一個 Instruction 的方法。在程式執行中，CPSR Register 的各個位元會根據某些指令的執行結果以下方的 Table 寫出的方式作改變。


舉例來說，以下程式碼

mv a0, #3
cmp a0, #3`

由於比較時會出現 `a0 - 3` 的行為，由於 3 - 3 = 0，此時 CPSR 中 的 Z bit 會被設定為 `1`，滿足 **EQ** 的 condition.

此時，假設接下來的指令為 `ADDEQ xx, xx`，由於滿足 condition **EQ**，這個指令就會被執行。反之，若接下來的指令 `ADDLE xx, xx`，由於 CPSR 的狀態不符合執行條件，這個指令就不會被執行。

#### 範例

void func(int a, int b)
{
    if(a == b){
        a = 1;
    }
    
    /* ... */
}

上述的 if 條件判斷可以用 condition execution 來撰寫:

CMP    r0, r1
MOVEQ  r0, #1 @ assign 1 to r0 if a == b

### v) 本學期課程內容中，讓你印象最深刻、顛覆過往認知的部分是什麼？請舉例說明

### w) 知道 locality of reference 嗎？請以本學期教材或作業的程式碼，說明 locality 對於 cache 的影響

**計算機在存取記憶體時，接觸位置相近的記憶體的程度**
提高 locality 可以因 Cache Hit Rate 上升等等效應進而增進計算的效能。

用計算機結構課程 [HW4 Exercise 3](https://hackmd.io/j9fIjj0QQmme6xMWDm-WTw?view#Exercise-2---Loop-Ordering-and-Matrix-Multiplication) 做說明：

以下對矩陣進行轉置的程式碼：

void transpose_blocking(int n, int blocksize, int *dst, int *src) {
    int block_count = n / blocksize;

    for(int i = 0; i < block_count; ++i){
        for(int j = 0; j < block_count; ++j){
            for(int a = 0; a < blocksize; ++a){
                for(int b = 0; b < blocksize; ++b){
                    int r = i * blocksize + a;
                    int c = j * blocksize + b;
                    if(r < n && c < n){
                        dst[c + r * n] = src[c * n + r];
                    }
                }
            }
        }
    }
}

利用將矩陣分成數個小矩陣後轉置，與直接轉置的結果相同的特性計算。

與以下直觀寫法做速度的比較：

void transpose_naive(int n, int *dst, int *src){
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
             src[i * n + j] = src[i * n + j];           
        }
    }
}

若將 n = {100, 1000, 2000, 5000, 10000} 進行比較，可以發現當矩陣愈大(越難整個塞進 cache 之中)，速度的進步愈明顯。

# test.sh
BLOCKSIZE=20
FILENAME="transpose"
SIZE_ARR=(100, 1000, 2000, 5000, 10000)

gcc -o $FILENAME $FILENAME.c -O3

for SIZE in "${SIZE_ARR[@]}"
do
   ./$FILENAME $SIZE $BLOCKSIZE
done
Testing naive transpose: 0.004 milliseconds
Testing transpose with blocking: 0.006 milliseconds
Testing naive transpose: 1.201 milliseconds
Testing transpose with blocking: 2.173 milliseconds
Testing naive transpose: 15.191 milliseconds
Testing transpose with blocking: 5.453 milliseconds
Testing naive transpose: 132.247 milliseconds
Testing transpose with blocking: 33.325 milliseconds
Testing naive transpose: 670.757 milliseconds
Testing transpose with blocking: 192.385 milliseconds

rm $FILENAME

### new g) 知道 memory misalignment 對程式正確性和效能的影響嗎？

### new q) 知道 cache thrashing 和 false-sharing 嗎？請以 Linux 核心原始程式碼作為解說。

### new r) 請舉例說明 lock-free data structure，搭配 Linux 核心原始程式碼解說。

### new s) 讀完授課教師撰寫的 Linux scheduler 電子書了嗎？你學到什麼呢？

### newt) 能否自行撰寫 SPSC, MPSC, SPMC, MPMC 程式碼呢？請用 lock-free 程式設計。

### new v) 本學期課程內容中，讓你印象最深刻、顛覆過往認知的部分是什麼？請舉例說明。