Try   HackMD

2022q1 Homework2 (quiz2)

contributed by < ShiaoLin >

作業要求

測驗 1

解釋程式碼運作的原理

對二個無號整數取平均值的程式碼，我們可改寫為以下等價的實作:

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

a 與 b 皆為無號數，向右邏輯位移 1 位乍看之下等同於兩數的一半相加，在算術上的邏輯是成立的，但是考量到 bits 的表達方式，a 與 b 各自向右移位會導致 bit 0 被忽略掉，在此之上要補回對於 bit 0 的運算。
以下以無號數 4 位元簡單表示：

Raw shift right
a 1 0 0 1 0 1 0 0
b 1 0 0 0 0 1 0 0
result x 1 0 0 0

上述表格透過直接右移一位於結果來說沒有問題，但是下面表格就會出現錯誤了

Raw shift right
a 1 0 0 1 0 1 0 0
b 1 0 0 1 0 1 0 0
result x 1 0 0 0

可以看到我們預期 a 與 b 的平均結果應該是 1001，所以我們必須對於 bit 0 進行修正，也就是加上 a & b & 1 去檢查兩數 bit 0 的狀況

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

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

我們可以透過 a + b = (a & b) << 1 + a ^ b 進行操作，也就將 (a + b) 進行邏輯右移取得平均值，也就是 a & b + (a ^ b) >> 1

比較上述實作在編譯器最佳化開啟的狀況，對應的組合語言輸出

使用指令進行編譯器最佳化的觀察

gcc -S -Og filename.c

會得到 filename.s 這個編譯到一半的檔案，其中可以觀察各程式轉變為組合語言的指令對應
首先觀察最一開始的取平均做法

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

會得到如下的結果

average:
.LFB0:
        .cfi_startproc
        endbr64
        leal    (%rdi,%rsi), %eax
        shrl    %eax
        ret
        .cfi_endproc

endbr64 的解釋What does the endbr64 instruction actually do?
leal (%rdi,%rsi), %eax，表示將 (%rdi,%rsi) 處理完後的地址加載到 %eax 這個地址去，lea 指令不儘可以處理加法也可以處理乘法，相較於 add 或 mul 來說節省了一道後續 mov 指令，可以在大量的組合語言中看到 lea 的使用
shrl %eax 則是將 %eax 做右移一位的處理，等同於將值除以 2 的操作

接下來觀察改寫後的操作

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

會得到下列結果

average:
.LFB0:
        .cfi_startproc
        endbr64
        movl    %edi, %eax
        shrl    %eax
        movl    %esi, %edx
        shrl    %edx
        addl    %edx, %eax
        andl    %esi, %edi
        andl    $1, %edi
        addl    %edi, %eax
        ret
        .cfi_endproc

得到了相對多於上述操作的組合語言指令，雖然指令上使用的較多，但是是相對獲得防止 overflow 的作法

同樣觀察下列操作的組合語言

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

average:
.LFB0:
        .cfi_startproc
        endbr64
        movl    %edi, %eax
        andl    %esi, %eax
        xorl    %esi, %edi
        shrl    %edi
        addl    %edi, %eax
        ret

同樣防止溢位，此次操作又比上述的操作少了一些指令

研讀 Linux 核心原始程式碼 include/linux/average.h，探討其 Exponentially weighted moving average (EWMA) 實作，以及在 Linux 核心的應用

根據移動平均的定義，相較於一般的平均數的操作，移動平均會對於新加入的值提升權重，使新值影響移動平均較大，以下是核心定義設時間

t 的實際數值為
Yt，而時間
t 的 EMA 則為
St；時間
t−1 的 EMA 則為
St−1，計算時間
t≥2 是方程式為

St=α∗Yt+(1−α)Yt−1

接下來觀察 linux 中相關的 EMA 程式碼，透過 macro 宣告包含初始化結構體、讀取結構體的值以及增加新值至原先結構體的方法

#define DECLARE_EWMA(name, _precision, _weight_rcp)

這邊有 3 個參數， name 表示結構體的命名， _precision 表示用多少 bits 儲存值的小數部分，_weight_rcp 表示為加權數，這邊為

α 的倒數

這邊觀察到程式碼內大量使用的以下的錯誤檢查式

BUILD_BUG_ON(!__builtin_constant_p(_precision));
BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp));
BUILD_BUG_ON((_precision) > 30);
BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp);

其中 BUILD_BUG_ON 表示括號內的表達數如果出現 false 則強制讓編譯器出現錯誤，BUILD_BUG_ON 的原定義來自於 BUILD_BUG_ON_ZERO，相關操作可參bit-field的說明

static inline void ewma_##name##_add(struct ewma_##name *e,	\
					     unsigned long val)		\
	{								\
		unsigned long internal = READ_ONCE(e->internal);	\
		unsigned long weight_rcp = ilog2(_weight_rcp);		\
		unsigned long precision = _precision;			\
									\
		BUILD_BUG_ON(!__builtin_constant_p(_precision));	\
		BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp));	\
		BUILD_BUG_ON((_precision) > 30);			\
		BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp);		\
									\
		WRITE_ONCE(e->internal, internal ?			\
			(((internal << weight_rcp) - internal) +	\
				(val << precision)) >> weight_rcp :	\
			(val << precision));				\
	}

READ_ONCE 以及 WRITE_ONCE 是為了避免不同 thread 同時進行操作導致數值存取錯誤的問題發生，ilog2 則是返回某數以 2 為底的整數部分，以利後續使用位移進行快速操作方便，這段程式碼的關鍵就在於 WRITE_ONCE 中的參數其中的分支，若 internal 為 0，則 e->internal = val << precision，等同於

St=α∗Yt，而 internal 不為 0 時，等同於完整的表達式
St=α∗Yt+(1−α)Yt−1

測驗 2

解釋程式碼運作原理

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

利用 XOR 的特性思考：

  • a ^ 0 = a
  • a ^ a = 0
  • a ^ (a ^ b) 因具備結合律等同於 (a ^ a) ^ b = b

假設 EXP4 為 a ^ b，則 -(EXP5) 則必須具備表達 a 與 b 的大小關係式
進一步假設如果 EXP5 為 a > b 或 a >= b 時：

  • 當 a >= b 為真， return a ^ ((a ^ b) & -1) 其結果為 return b，假設與結果不符
  • 當 a < b 為真， return a ^ ((a ^ b) & 0) 其結果為 return a，同樣假設與結果不符

故得知 EXP5 的正確表達式為 a < b

針對 32 位元無號/有號整數，撰寫同樣 branchless 的實作

參考不需要分支的設計將有 32 位有號數較小值的函式作修改

int32_t max(int32_t a, int32_t b) {
    int32_t diff = (a - b);
    return a - (diff & (diff >> 31));
}

請在 Linux 核心原始程式碼中，找出更多類似的實作手法

測驗 3

解釋程式運作原理

    int shift;
    for (shift = 0; !((u | v) & 1); shift++) {
        u /= 2, v /= 2;
    }

根據備註 3. If x and y are both even, gcd(x,y)=2∗gcd(x2,y2) because 2 is a common divisor. Multiplication with 2 can be done with bitwise shift operator.
若 u v 兩數皆為偶數則先共同約去 2，用 shift 紀錄約去的次數

    while (!(u & 1))
        u /= 2;

根據備註 4. If x is even and y is odd, gcd(x,y)=gcd(x2,y).
如果 u 為偶數，則可先約去 2 的冪部份，因為與奇數的最大公因數不會有 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;

根據備註 5. On similar lines, if x is odd and y is even, then gcd(x,y)=gcd(x,y2). It is because 2 is not a common divisor.
同樣的，對 v 進行備註 4 的處理方式後，就可以就剩下的數字進行最大公因數的尋找，這邊參考輾轉相除法，而輾轉相除法的停止條件是餘數為零，也就是 u - v 的結果，故 COND = v，而最後回傳值除了剩餘的 u 之外，還要包含上方若有對 2 進行約分的部份，也就是 RET = u << shift

在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升

Linux 核心中也內建 GCD (而且還不只一種實作)，例如 lib/math/gcd.c，請解釋其實作手法和探討在核心內的應用場景

測驗 4

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

思考 -bitwise 的特性，-bitwise = ~bitwise + 1，所以當 bitwise & -bitwise 時會留下 bitwise 最靠近右端的 1，最後再透過 bitwise ^= t 去掉最右端的 1
EXP6 為 bitset & -bitset

測驗 5

    /* 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;
    }

在 hash table 中的元素建立資料，第一次進入 for 迴圈時由於 pos 從 find 的回傳值為 -1，所以會進行新增節點的動作，故 MMM 為 list_add，而節點的插入點 EEE 為 &heads[remainder % size]
而 PPP 與 pos 相關，當循環小數不從小數點後一位開始時， *p++ = *decimal++; 會先記錄循環小數開始前的數字，故 PPP 為 pos--

測驗 6

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

參考 container_of 的巨集，以 char* 指針形式回傳的 struct { char c; t _h; } * 結構體指針，透過 0 指針指向 t 型態的地址，再減去作為開頭 char* 0 的偏移量，故 M = _h，X = 0

測驗 7

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

根據 string literal 的長度思考：

字串長度 Offset
3非5的數 4 0
5非3的數 4 4
3且5的數 8 0
非3非5的數 2 8

觀察結果發現不論是字串長度與 Offset 皆為 2 的冪，所以剛好符合 KK1 = div3 及 KK2 = div5

再來關於 (9 >> div5) >> (KK3) 的部份，套入上表格可得到

字串長度 (9 >> div5) >> (KK3) KK3
3非5的數 4 0 3
5非3的數 4 4 0
3且5的數 8 0 2
非3非5的數 2 8 0

題目有誤，應修正為 (8 >> div5) >> (KK3) 且 KK3 = div3 <<2

Last changed by 
 
shiao
0
198
Published on HackMD