2022q1 Quiz2

tags: linux2022

contributed by <ganoliz>

測驗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);
}

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

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

請問,
EXP1 = ?
EXP2 = ?
EXP3 = ?

解題思路

根據左移算子我們可以知道a>>1與b>>1相當於是除以二,那這裡會遇到一個問題是當a為奇數且b為奇數的情況會造成出來的平均會少1。當發生這個情況的時候我們直覺是使用if-else的branch來實作,但這樣就等於沒有用到 bit-wise 操作的快速與不用進行分支預測的好處了。

根據數位邏輯

a b result
0 0 0
0 1 0
1 0 0
1 1 1

於是我們只需要把 a,b 最後 1 bits & 起來即可,因此 EXP1 = a & b & 1

EXP2與EXP3 我首先使用 bit wise 的寫法,使用 a & b 來當作進位, a | b 當作加法。
得到此式 :

((a & b)+1) >> 1)+((a | b) >> 1) 

顯然相當不漂亮,EXP2 這樣寫是為了配合 EXP3 進行 or 運算所損失的數值才寫成這樣。但是的確很不符合 bit-wise 的作法,因為 and 也要位移再做加法才得到最後的進位。後來想起數位邏輯的加法器

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

加法使用 xor 運算來實現,進位則由 and 運算來負責,因此重寫 EXP2 及 EXP3

 (a & b)+( (a ^ b) >> 1)

延伸問題:

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

  • 移動平均(Moving average),又稱滾動平均值、滑動平均,在統計學中是種藉由建立整個資料集合中不同子集的一系列平均數,來 分析資料點的計算方法。

測驗二

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

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

請問,
EXP4 = ?
EXP5 = ?

解題思路

根據式子,

  • 若 a > b ,則反推 a ^ 0 = a 為 max 的值
  • 若 a < b ,則需要 一個 b - a 來跟 a 做 xor 運算

根據EXP5 ,我們假設為 a < b ,當 a > b 時,右式得到的值是0,因此輸出為 a 。若 a < b 則根據 uint32_t 輸出為 0xFFFF (有號位整數的 -1),因此右式的值會變為 EXP4 的值,也就代表 a ^ EXP4 ,簡單思考一下可以知道 b - a 、 a + b 的值都可以用 xor 表示(不考慮借位與進位),因此 EXP4 應為 a ^ b ,根據數位邏輯的布林代數驗證一下也可以知道 a ^ a ^ b 為 b 。
因此答案為:

return a ^ ((a ^ b) & -(a < b));

延伸問題:

  • 1.解釋上述程式碼運作的原理
  • 2.針對 32 位元無號/有號整數,撰寫同樣 branchless 的實作
  • 3.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 檢索。

測驗三

考慮以下 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;
}

改寫為以下等價實作:

#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; }

請問,
COND = ?
RET = ?

解題思路

首先我們先看這個 condition :

!((u | v) & 1)
  • u & 1 的意思:在二進制下,若出現 LSB 為 1 則為 1
  • (u | v) & 1 的意思: 在二進制下,只要 u 或 v 的 LSB 任一為 1 則輸出為 1
  • !((u | v) & 1) 的意思: 在二進制下,只要 u 或 v 的 LSB 不為 1 則輸出為 1

因此,shift 這個 for 迴圈在做的事就是將 u 跟 v 共同的二倍數找出來。
當我們找完之後就是把還有二倍數的任一數除乾淨(因為我們已經不再會有二倍數的公因數了),
接著進入餘數定理:

a=b1q1+r1
q1=b2q2+r2

因此,當我們的 v 小於 1時就應該結束,所以跟一開始的程式結束條件是一樣的 while (v)。
然後我們要 return 的值是 u 乘以左移shift的次數(二的次方): u * (1 << shift)。

} while (v); return u * (1 << shift);

延伸問題:

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

測驗四

在影像處理中,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→0→0→0→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 為 000101b ,那 t 就會變成 000001b,接著就可以透過 XOR 把該位的 1 清掉,其他保留 (此為 XOR 的特性)。
若 bitmap 越鬆散 (即 1 越少),於是 improved 的效益就更高。

請問,
EXP6 = ?

解題思路

首先,我參考了 Introduction to Low Level Bit Hacks 提供的這篇文章,我們可以知道怎麼 get right-most bit value 。
即是使用:

y = x & (-x)  // -x is 2's complement

因此,EXP6 :

uint64_t t = bitset & (-bitset);

其實我一開始是想到使用:

uint64_t t = bitset & ~(bitset-1)

不過轉換後其實兩者布林代數是相等的,而且前者的可讀性更好。

延伸問題:

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

測驗五

以下是 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 = ? (巨集)
EEE = ? (表示式)

解題思路







test



Map

Hash table

0

1

2

3

4

5

...

size - 1



Key

int Key=remainder

int index

list_head link



Map:3->Key





Key2

int Key=remainder

int index

list_head link



Key:2->Key2





首先我們可以看看 Hash Table 的結構,我們可以知道我們使用 remainder 當作 Key 來查表,當我們有符合的 Key 在該項 Hash Table 裡時則回傳該 node 的 index。因此我們可以先解 MMM 與 EEE 是:

list_add_tail(&node->link, &head[reminder % size]);

透過 HashTable 映射到對應的 Hlist_head 來搜尋 key 值,因此我們儲存節點就要依此邏輯來存取。
現在我們考慮 PPP ,







test



Map

decimal point .

1

2

3

4

5

6

...

size - 1



Map:6->Map:3


Recurring Decimal



當我們無法從 Hash Table 找到位置時,代表我們尚未有該值,建立一個 hash table 的 element 下次方便找 index 值,然後便將值寫入在 *decimal ( 也就是 q 目前的位置 ),並往下一位數前進。

因此當我們 find 到 pos 的時候,代表我們在這個位數的值等於前面某一個位數的值(已經確定有循環小數了),此時我們應該先將循環小數前的位數寫入 result ,因此 PPP 應為(原本我想的條件是 pos - i > 0 但一行解決的確是 pos ):

        if (pos >= 0) {
            while (pos-- > 0)        //while (PPP > 0)
                *p++ = *decimal++;
            *p++ = '(';
            while (*decimal != '\0')
                *p++ = *decimal++;
            *p++ = ')';
            *p = '\0';
            return result;
        }

最後再將循環位數利用下一個 while 迴圈填入左括號與右括號之間,直到 decimal 為 "\0" 。

延伸問題:

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

  2. 在 Linux 核心原始程式碼的 mm/ 目錄 (即記憶體管理) 中,找到特定整數比值 (即 fraction) 和 bitwise 操作的程式碼案例,予以探討和解說其應用場景

測驗六

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)

請問,
M = ?
X = ?

首先,這段程式雖然短卻不好了解,先拆開來

&((struct {char c; t _h;} *)0) ->M 

我們宣告一個 struct 指標, 0 是虛擬地址(正如同offsetof"它假定結構的位址為0,然後獲得成員的偏移值")
重新複習運算子優先順序因此可以知道我們先取 成員 M 再取得它的位置,接著:

((char *)(&((struct { char c; t _h; } *)0)->M) - (char *)X)

就是將我們取得的位置轉型成 char 指標再跟 X 這個char 指標相減。我們要使用 struct 裡面 佔最大的成員當成 alignment 的大小,那由於 char 指標只佔 1 bit ,我們只要看 _h 的大小來決定是幾位元。
因此,M 應為 _h。 而 X 應為 0 (為 struct 的開頭成員 char c 的位置) ,透過相減取得 _h 成員的偏移。

延伸問題:

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

測驗七

考慮貌似簡單卻蘊含實作深度的 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 的(格式)字串,可分類為以下三種:

  1. 整數格式字串 "%d" : 長度為 2 B
  2. “Fizz” 或 “Buzz” : 長度為 4 B
  3. “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)。

請補完,使得程式碼符合預期,儘量以最簡短且符合一致排版的形式來撰寫。
請問,
KK1 = ? (變數名稱)
KK2 = ? (變數名稱)
KK3 = ? (表示式,不包含小括號)

解題思路

我們可以知道 FizzBuzz 的長度變化是跟是否能被 3 與 5 整除來增長的,因此我們可以從 div3 與 div5 得到是否整除的關係,因此 KK1 = div3 , KK2 = div5 兩者其實可以更換。

至於 KK3 則是針對 FizzBuzz 字串要從哪裡複製來做位移。因為字串從起始位置 9 開始,往前四格開始就是 divide 2 因此假如 div5 為 1 就從起始位置 4 開始。至於 KK3 的地方的話,因為只要 div3 為 1 的情況,就應該從起始位置 0 的地方開始,因此 KK3 應為 div3 * 4 直接讓起始位置歸零。

延伸問題:

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