2022q1 第 2 週測驗題

tags: `linux2022`

目的: 檢驗學員對 數值系統, linked list, bitwise 的認知

作答表單: 測驗 1-4 (Linux 核心設計)
作答表單: 測驗 5-7 (Linux 核心實作)

測驗 `1`

考慮以下對二個無號整數取平均值的程式碼:

#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
    return (a + b) / 2;
}

這個直覺的解法會有 overflow 的問題，若我們已知 a, b 數值的大小，可用下方程式避免 overflow:

#include <stdint.h>
uint32_t average(uint32_t low, uint32_t high)
{
    return low + (high - low) / 2;
}

接著我們可改寫為以下等價的實作:

#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
    return (a >> 1) + (b >> 1) + (EXP1);
}

其中 EXP1 為 a, b, 1 (數字) 進行某種特別 bitwise 操作，限定用 OR, AND, XOR 這三個運算子。書寫規範:

運算子和運算元之間用一個半形空白區隔，如: a | b ^ 1
EXP1 必定包含 a, b, 及 1 (數字) 等字元
總是先寫 a 再寫 b
不要包含任何小括號，即 ( 和 )
以最精簡的形式撰寫程式碼

我們再次改寫為以下等價的實作:

uint32_t average(uint32_t a, uint32_t b)
{
    return (EXP2) + ((EXP3) >> 1);
}

其中 EXP2 和 EXP3 為 a 和 b 進行某種特別 bitwise 操作，限定用 OR, AND, XOR 這三個運算子。書寫規範:

運算子和運算元之間用一個半形空白區隔，如: a | b
EXP2 和 EXP3 必定包含 a 和 b 字元
總是先寫 a 再寫 b
不要包含任何小括號，即 ( 和 )
以最精簡的形式撰寫程式碼

延伸閱讀: Introduction to Low Level Bit Hacks

作答區
EXP1 = ?
EXP2 = ?
EXP3 = ?

延伸問題:

解釋上述程式碼運作的原理
比較上述實作在編譯器最佳化開啟的狀況，對應的組合語言輸出，並嘗試解讀 (可研讀 CS:APP 第 3 章)
研讀 Linux 核心原始程式碼 include/linux/average.h，探討其 Exponentially weighted moving average (EWMA) 實作，以及在 Linux 核心的應用

移動平均（Moving average)，又稱滾動平均值、滑動平均，在統計學中是種藉由建立整個資料集合中不同子集的一系列平均數，來分析資料點的計算方法。
移動平均通常與時間序列資料一起使用，以消除短期波動，突出長期趨勢或周期。短期和長期之間的閾值取決於應用，移動平均的參數將相應地設置。例如，它通常用於對財務數據進行技術分析，如股票價格、收益率或交易量。它也用於經濟學中研究國內生產總值、就業或其他宏觀經濟時間序列。

測驗 `2`

改寫〈解讀計算機編碼〉一文的「不需要分支的設計」一節提供的程式碼 min，我們得到以下實作 (max):

#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
    return a ^ ((EXP4) & -(EXP5));
}

其中 EXP4 為 a 和 b 進行某種特別 bitwise 操作，限定用 OR, AND, XOR 這三個運算子。書寫規範:

運算子和運算元之間用一個半形空白區隔，如: a | b ^ 1
EXP4 必定包含 a 和 b 字元
總是先寫 a 再寫 b
不要包含任何小括號，即 ( 和 )
以最精簡的形式撰寫程式碼

EXP5 為 a 和 b 的比較操作，亦即 logical operator，限定用 >, <, ==, >=, <=, != 這 6 個運算子。書寫規範:

運算子和運算元之間用一個半形空白區隔，如: a > b
EXP5 必定包含 a 和 b 字元
總是先寫 a 再寫 b
不要包含任何小括號，即 ( 和 )
以最精簡的形式撰寫程式碼

延伸閱讀:

That XOR Trick

video: Branchless Programming: Why "If" is Sloowww… and what we can do about it!

Making Your Code Faster by Taming Branches

作答區
EXP4 = ?
EXP5 = ?

延伸問題:

解釋上述程式碼運作的原理
針對 32 位元無號/有號整數，撰寫同樣 branchless 的實作

Linux 核心也有若干 branchless / branch-free 的實作，例如 lib/sort.c:

/*
 * Logically, we're doing "if (i & lsbit) i -= size;", but since the
 * branch is unpredictable, it's done with a bit of clever branch-free
 * code instead.
 */
__attribute_const__ __always_inline
static size_t parent(size_t i, unsigned int lsbit, size_t size)
{
    i -= size;
    i -= size & -(i & lsbit);
    return i / 2;
}

請在 Linux 核心原始程式碼中，找出更多類似的實作手法。請善用 git log 檢索。

測驗 `3`

考慮以下 64 位元 GCD (greatest common divisor, 最大公因數) 求值函式:

#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
    if (!u || !v) return u | v;
    while (v) {                               
        uint64_t t = v;
        v = u % v;
        u = t;
    }
    return u;
}

註: GCD 演算法

If both x and y are 0, gcd is zero
$g c d (0, 0) = 0$ .
$g c d (x, 0) = x$ and
$g c d (0, y) = y$ because everything divides
$0$ .
If x and y are both even,
$g c d (x, y) = 2 * g c d (\frac{x}{2}, \frac{y}{2})$ because
$2$ is a common divisor. Multiplication with
$2$ can be done with bitwise shift operator.
If x is even and y is odd,
$g c d (x, y) = g c d (\frac{x}{2}, y)$ .
On similar lines, if x is odd and y is even, then
$g c d (x, y) = g c d (x, \frac{y}{2})$ . It is because
$2$ is not a common divisor.

改寫為以下等價實作:

#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
    if (!u || !v) return u | v;
    int shift;
    for (shift = 0; !((u | v) & 1); shift++) {
        u /= 2, v /= 2;
    }
    while (!(u & 1))
        u /= 2;
    do {
        while (!(v & 1))
            v /= 2;
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (COND);
    return RET;
}

請補完程式碼。書寫規範:

運算子和運算元之間用一個半形空白區隔，如: u | v
不要包含任何小括號，即 ( 和 )
以最精簡的形式撰寫程式碼

作答區
COND = ?
RET = ?

延伸問題:

解釋上述程式運作原理;
在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升;
Linux 核心中也內建 GCD (而且還不只一種實作)，例如 lib/math/gcd.c，請解釋其實作手法和探討在核心內的應用場景。

測驗 `4`

在影像處理中，bit array (也稱 bitset) 廣泛使用，考慮以下程式碼:

#include <stddef.h>
size_t naive(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
    size_t pos = 0;
    for (size_t k = 0; k < bitmapsize; ++k) {
        uint64_t bitset = bitmap[k];
        size_t p = k * 64;
        for (int i = 0; i < 64; i++) {
            if ((bitset >> i) & 0x1)
                out[pos++] = p + i;
        }
    }
    return pos;
}

考慮 GNU extension 的 __builtin_ctzll 的行為是回傳由低位往高位遇上連續多少個 0 才碰到 1。

範例: 當 a = 16
16 這個十進位數值的二進位表示法為 00000000 00000000 00000000 00010000
從低位元 (即右側) 往高位元，我們可發現
$0 \to 0 \to 0 \to 0 \to 1$ ，於是 ctz 就為 4，表示最低位元往高位元有 4 個 0

用以改寫的程式碼如下:
















#include <stddef.h>
size_t improved(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
    size_t pos = 0;
    uint64_t bitset;
    for (size_t k = 0; k < bitmapsize; ++k) {
        bitset = bitmap[k];
        while (bitset != 0) {
            uint64_t t = EXP6;
            int r = __builtin_ctzll(bitset);
            out[pos++] = k * 64 + r;
            bitset ^= t;                           
        }
    }
    return pos;
}

其中第 9 行的作用是找出目前最低位元的 1，並紀錄到 t 變數。舉例來說，若目前 bitset 為

000101_{b}

，那 t 就會變成

000001_{b}

，接著就可以透過 XOR 把該位的 1 清掉，其他保留 (此為 XOR 的特性)。

若 bitmap 越鬆散 (即 1 越少)，於是 improved 的效益就更高。

請補完程式碼。書寫規範:

bitwise 運算子和運算元之間用一個半形空白區隔，如: bitset | 0x1
考慮到 -bitwise 的特性
不要包含任何小括號，即 ( 和 )
以最精簡的形式撰寫程式碼

作答區
EXP6 = ?

延伸問題:

解釋上述程式運作原理，並舉出這樣的程式碼用在哪些真實案例中;
設計實驗，檢驗 ctz/clz 改寫的程式碼相較原本的實作有多少改進？應考慮到不同的 bitmap density;
思考進一步的改進空間;
閱讀 Data Structures in the Linux Kernel 並舉出 Linux 核心使用 bitmap 的案例;

測驗 `5`

以下是 LeetCode 166. Fraction to Recurring Decimal 的可能實作:

#include <stdbool.h>                       
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"
    
struct rem_node {
    int key;
    int index;
    struct list_head link;
};  
    
static int find(struct list_head *heads, int size, int key)
{
    struct rem_node *node;
    int hash = key % size;
    list_for_each_entry (node, &heads[hash], link) {
        if (key == node->key)
            return node->index;
    }
    return -1;
}

char *fractionToDecimal(int numerator, int denominator)
{
    int size = 1024;
    char *result = malloc(size);
    char *p = result;

    if (denominator == 0) {
        result[0] = '\0';
        return result;
    }

    if (numerator == 0) {
        result[0] = '0';
        result[1] = '\0';
        return result;
    }

    /* using long long type make sure there has no integer overflow */
    long long n = numerator;
    long long d = denominator;

    /* deal with negtive cases */
    if (n < 0)
        n = -n;
    if (d < 0)
        d = -d;

    bool sign = (float) numerator / denominator >= 0;
    if (!sign)
        *p++ = '-';

    long long remainder = n % d;
    long long division = n / d;

    sprintf(p, "%ld", division > 0 ? (long) division : (long) -division);
    if (remainder == 0)
        return result;

    p = result + strlen(result);
    *p++ = '.';

    /* Using a map to record all of reminders and their position.
     * if the reminder appeared before, which means the repeated loop begin,
     */
    char *decimal = malloc(size);
    memset(decimal, 0, size);
    char *q = decimal;

    size = 1333;
    struct list_head *heads = malloc(size * sizeof(*heads));
    for (int i = 0; i < size; i++)
        INIT_LIST_HEAD(&heads[i]);

    for (int i = 0; remainder; i++) {
        int pos = find(heads, size, remainder);
        if (pos >= 0) {
            while (PPP > 0)
                *p++ = *decimal++;
            *p++ = '(';
            while (*decimal != '\0')
                *p++ = *decimal++;
            *p++ = ')';
            *p = '\0';
            return result;
        }
        struct rem_node *node = malloc(sizeof(*node));
        node->key = remainder;
        node->index = i;

        MMM(&node->link, EEE);

        *q++ = (remainder * 10) / d + '0';
        remainder = (remainder * 10) % d;
    }

    strcpy(p, decimal);
    return result;
}

請補完，使得程式碼符合預期，儘量以最簡短且符合一致排版的形式來撰寫。

作答區
PPP = ? (表示式)
MMM = ? (List API 函式)
EEE = ? (表示式)

延伸問題:

解釋上述程式碼運作原理，指出其中不足，並予以改進

例如，判斷負號只要寫作 bool isNegative = numerator < 0 ^ denominator < 0;
搭配研讀 The simple math behind decimal-binary conversion algorithms
在 Linux 核心原始程式碼的 mm/ 目錄 (即記憶體管理) 中，找到特定整數比值 (即 fraction) 和 bitwise 操作的程式碼案例，予以探討和解說其應用場景

測驗 `6`

__alignof__ 是 GNU extension，以下是其可能的實作方式:

/*
 * ALIGNOF - get the alignment of a type
 * @t: the type to test
 *
 * This returns a safe alignment for the given type.
 */
#define ALIGNOF(t) \
    ((char *)(&((struct { char c; t _h; } *)0)->M) - (char *)X)

請補完上述程式碼，使得功能與 __alignof__ 等價。

請補完，使得程式碼符合預期，儘量以最簡短且符合一致排版的形式來撰寫。

作答區
M = ?
X = ?

延伸問題:

解釋上述程式碼運作原理
在 Linux 核心原始程式碼中找出 __alignof__ 的使用案例 2 則，並針對其場景進行解說
在 Linux 核心源使程式碼找出 ALIGN, ALIGN_DOWN, ALIGN_UP 等巨集，探討其實作機制和用途，並舉例探討 (可和上述第二點的案例重複)。思索能否對 Linux 核心提交貢獻，儘量共用相同的巨集

測驗 `7`

考慮貌似簡單卻蘊含實作深度的 FizzBuzz 題目:

從 1 數到 n，如果是 3的倍數，印出 "Fizz"
如果是 5 的倍數，印出 "Buzz"
如果是 15 的倍數，印出 "FizzBuzz"
如果都不是，就印出數字本身

直覺的實作程式碼如下: (naive.c)

#include <stdio.h>
int main() {
    for (unsigned int i = 1; i < 100; i++) {
        if (i % 3 == 0) printf("Fizz");
        if (i % 5 == 0) printf("Buzz");
        if (i % 15 == 0) printf("FizzBuzz");
        if ((i % 3) && (i % 5)) printf("%u", i);
        printf("\n");
    }
    return 0;
}

觀察 printf 的(格式)字串，可分類為以下三種:

整數格式字串 "%d" : 長度為 2 B
"Fizz" 或 "Buzz" : 長度為 4 B
"FizzBuzz" : 長度為 8 B

考慮下方程式碼:

char fmt[M9];
strncpy(fmt, &"FizzBuzz%u"[start], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");

我們若能精準從給定輸入 i 的規律去控制 start 及 length，即可符合 FizzBuzz 題意:

 string literal: "fizzbuzz%u"
         offset:  0   4   8

以下是利用 bitwise 和上述技巧實作的 FizzBuzz 程式碼: (bitwise.c)

static inline bool is_divisible(uint32_t n, uint64_t M)
{
    return n * M <= M - 1;
}

static uint64_t M3 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 3 + 1;
static uint64_t M5 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 5 + 1;

int main(int argc, char **argv)
{
    for (size_t i = 1; i <= 100; i++) {
        uint8_t div3 = is_divisible(i, M3);
        uint8_t div5 = is_divisible(i, M5);
        unsigned int length = (2 << KK1) << KK2;

        char fmt[9];
        strncpy(fmt, &"FizzBuzz%u"[(8 >> div5) >> (KK3)], length);
        fmt[length] = '\0';

        printf(fmt, i);
        printf("\n");
    }
    return 0;
}

其中 is_divisible 函式技巧來自 Faster remainders when the divisor is a constant: beating compilers and libdivide，甚至 gcc-9 還內建了 FizzBuzz optimization (Bug 82853 - Optimize x % 3 == 0 without modulo)。

請補完，使得程式碼符合預期，儘量以最簡短且符合一致排版的形式來撰寫。

對於處理器來說，每個運算所花的成本是不同的，比如 add, sub 就低於 mul，而這些運算的 cost 又低於 div 。依據〈Infographics: Operation Costs in CPU Clock Cycles〉，可發現整數除法的成本幾乎是整數加法的 50 倍。

所以如何處理 div 運算是每個編譯器最佳化都關注的議題。考慮

\frac{n}{d}

，

d

是一個 constant，除式可以表示成

n \times (\frac{2^{n}}{d}) \times \frac{1}{2^{n}}

，若

d

是 2 的冪，可以將除法轉換成乘法跟位移，cost 會比 div 少很多，如果除數

d

不是 2 的冪，則

\frac{2^{n}}{d}

需要做一些特別的處理，在若干微處理器架構中，若

n

足夠大，其實

\frac{2^{n}}{d}

可事先預估。

文章中還有介紹一些其他的除法如下:

Division by invariant integers using multiplication, by Granlund and Montgomery (1994)
Hacker's Delight, by Warren
N-Bit Unsigned Division via N-Bit Multiply-Add, by Robison

作答區
KK1 = ? (變數名稱)
KK2 = ? (變數名稱)
KK3 = ? (表示式，不包含小括號)

延伸問題:

解釋上述程式運作原理並評估 naive.c 和 bitwise.c 效能落差
- 避免 stream I/O 帶來的影響，可將 printf 更換為 sprintf
分析 Faster remainders when the divisor is a constant: beating compilers and libdivide 一文的想法 (可參照同一篇網誌下方的評論)，並設計另一種 bitmask，如「可被 3 整除則末位設為 1」「可被 5 整除則倒數第二位設定為 1」，然後再改寫 bitwise.c 程式碼，試圖運用更少的指令來實作出 branchless;
- 參照 fastmod: A header file for fast 32-bit division remainders on 64-bit hardware
研讀 The Fastest FizzBuzz Implementation 及其 Hacker News 討論，提出 throughput (吞吐量) 更高的 Fizzbuzz 實作
解析 Linux 核心原始程式碼 kernel/time/timekeeping.c 裡頭涉及到除法運算的機制，探討其快速除法的實作 (注意: 你可能要對照研讀 kernel/time/ 目錄的標頭檔和程式碼)

過程中，你可能會發現可貢獻到 Linux 核心的空間，請充分討論

2022q1 第 2 週測驗題

tags: linux2022

測驗 1

測驗 2

測驗 3

測驗 4

測驗 5

測驗 6

測驗 7

Read more

單一指令處理器 (OISC)

從 CPU cache coherence 談 Linux spinlock 可擴展能力議題

淺談 Microkernel 設計和真實世界中的應用

並行程式設計: 概念

tags: `linux2022`

測驗 `1`

測驗 `2`

測驗 `3`

測驗 `4`

測驗 `5`

測驗 `6`

測驗 `7`