第 1,2 週課堂問答簡記

`Uduru0522`

Linux 核心的 hash table 實作中，用以處理 hash 數值碰撞的 hlist_node:

struct hlist_node {
    struct hlist_node *next, **pprev;
};

其中 pprev 為何要宣告為指標的指標？
探討典型 doubly-linked list delete 會產生的問題。

考慮我們使用典型的 doubly-linked list:

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

dll 是 doubly-linked list 的簡稱

於是資料結構會展現如下圖:

注意：

除了末端，第一個節點的 prev 指標內容也是 NULL。
prev 及 next 皆指向相鄰的節點本身。

嘗試撰寫 delete_node():

void dll_delete_node(struct list_head *l, struct dll_node *n)
{
    struct dll_node *prev = n->prev,
                    *next = n->next;
    
    if (next)
        next->prev = prev;
    
    // Delete and update where list_head points to,
    // which requires the list_head to be passed in.
    if (!prev) {
        l->first = next;
    } else {
        prev->next = next;
    }
}

可發現當我們要移除第一個節點時，必須做出額外的操作來更新 list_head 指向的節點，於是除了移除的目標之外，還必須傳入 list_head。

當我們用指標的指標改寫上述程式碼，將原本的 struct dll_node *prev 變更為 struct dll_node **pprev:

struct hlist_node { 
    struct hlist_node *next, **pprev;
}

則會形成以下的結構：

注意：

僅有末端指標內容是 NULL。
next 指向相鄰的節點本身，而 pprev 指向指著自身節點的指標。

則我們便可藉由下方程式碼來撰寫 delete_node()：

void hlist_delete_node(struct hlist_node *n)
{
    struct hlist_node *next = n->next;
                      **pprev = n->pprev;
	
    // Since there is always a pointer which points to node n,
    // no special case is needed to deal with.
    *pprev = next;
    if (next)
        next->pprev = pprev;
}

跟典型 doubly-linked list 的實作做比較，由於該實作的 prev 指標必須指向 struct dll_node 型別，導致第一個節點會出現指向 NULL 的狀況；而將其替換成指標的指標後，便可順利消除這個特例。

至此，我們理解到，hash list 是為雜湊表特製的鏈結串列，儘管雙向鏈結串列亦可實作雜湊表，但由於後者開頭和結尾需要各用 2 個指標，當 bucket 很大時，會增加記憶體開銷。

相較於 list_head 的兩個指標，hlist_head 僅需要保存一個指標，hlist_node 的 next 指向下個節點，但 pprev（指標的指標) 並不指向上個節點，而是指向上個節點的 next 指標，這樣設計的好處是，當要刪除的節點是首個節點，即可藉由 *pprev = next 直接修改指標的指向。

`Eddielin0926`

quiz2-4

先觀察原本函式的功能

bitmap 是要處理的資料，以 64 bits 為區間
bitmapsize 是總共有要處的資料大小
out 是結果存放的位置

在第一層迴圈中 bitset 會儲存目前處理資料，第二層的迴圈目的是要找到資料的位元是 1 的位置並且去除掉 1 後，將位置記錄在 out 中。

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

嘗試一個簡單的例子

bitmap[0] = 0x11
bitmapsize = 1

我們可以得到 bitmap 中 1 的數量以及 1 的位置

pos = 2
out = {0, 4}

接下來透過 __builtin_ctzll 將函式改寫

__builtin_ctzll 用來找到由低位往高位的第一個 1 中間會有幾個 0，因此可以用來取代重複判斷的 if ((bitset >> i) & 0x1) ，就能減少分支的次數，在硬體有支援的情況下可以加速運算，再來看 while 的條件是 bitset != 0，加上 __builtin_ctzll 的特性，因此我們可以知道，當我們找到 bitset 的 1 時，要將 1 去處除掉，才有辦法利用 __builtin_ctzll 計算 1 的位置。

#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 = bitset & -bitset;
            int r = __builtin_ctzll(bitset);
            out[pos++] = k * 64 + r;
            bitset ^= t;                           
        }
    }
    return pos;
}

當我們在思考如何去除掉某個位元的 1 時，第一個想法可能會是與一個在對應位置的 0 做 bitwise AND

bitset &= ~(1 << r)

但在這邊的做法利用了二補數來去除最低位元的 1。

bitset ^= bitset & -bitset

在我們剛剛的計算中，我們目標都是 bitset 中最低位的 1，例如 XXX100。
當我們對 bitset 做二補數計算時，最低位的 1 左邊的位元會是原本的補數，右邊則會與原本一樣。

$0110100_{2} \overset{取二補數}{\to} 1001100_{2} 0110100_{2} \land 1001100_{2} = 0000100_{2} 0110100_{2} \oplus 0000100_{2} = 0110000_{2}$

與原本的 bitset 做 XOR 就能將最右邊的 1 變成 0 了。

quiz2-1

對二個無號整數取平均值

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

a >> 1 和 b >> 1 代表將 a 和 b 個別除以 2，a & b & 1 用來檢查兩個數是不是都是奇數。

另一個對二個無號整數取平均值的實作。

uint32_t average(uint32_t a, uint32_t b)
{
    return (a & b) + ((a ^ b) >> 1);
}

我認為可以想像成全加器除二。

原本是 (a + b) >> 1，將 carry 提出來後就變成 (a & b) + ((a ^ b) >> 1)。

`william40614`, `millaker`

先分析原程式，參考〈解讀計算機編碼〉一文的「不需要分支的設計」一節提供的程式碼 min，改寫為以下程式碼: (其中 EXP4 和 EXP5 尚未實作)

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

運用 The XOR trick 提及的規律:

a ^ a = 0
a ^ 0 = a
a ^ ANY ^ ANY = a

關於 EXP5，只要 a < b 成立，也就是 1, 加上負號後得到 -1 (0xffffffff)，原本的表示式成為:

-1 ＆ (a ^ b) = (a ^ b)
a ^ a ^ b = 0 ^ b = b

可推得 max 是 b 。相反地，當 a > b 成立，後面一整項為 0，回傳值就會是 a。

`Tcc0403`

第 2 周測驗 3

分析程式碼

#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 (v);
    return u<<shift;
}

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 \times g c d (\frac{x}{2}, \frac{y}{2})$ because $2$ is a common divisor. Mulitplication with $2$ can be done with betwise 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.

以下分段說明：

if (!u || !v) return u | v;

$\to$ 對應至 GCD 演算法第 2 點

$g c d (x, 0) = x$ and $g c d (0, y) = y$ because everything divides 0.

若 u 和 v 中其中一數為 0 ，則直接回傳另一數

x | 0 會得到 x

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

$\to$ 對應至 GCD 演算法第 3 點

If x and y are both even, $g c d (x, y) = 2 \times g c d (\frac{x}{2}, \frac{y}{2})$ because $2$ is a common divisor. Mulitplication with $2$ can be done with betwise shift operator.

先取出u 和 v 之間屬於 $2^{n}$ 的公因數，shift 即為最大的 $n$

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

$\to$ 對應至 GCD 演算法第4 點

If x is even and y is odd, $g c d (x, y) = g c d (\frac{x}{2}, y)$ .

當 u 為偶數時，可以除以 $2$

do {
    while (!(v & 1))
        v /= 2;
    if (u < v) {
        v -= u;
    } else {
        uint64_t t = u - v;
        u = v;
        v = t;
    }
} while (v);

$\to$ 其中 while(!(v &1)) v /= 2; 對應至 GCD 演算法第 5 點

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.

可以透過迴圈不變性 (loop invariant) 來幫助解讀程式

u 為被除數
v 為除數

當除數 v為 0 時結束迴圈，被除數 u 為進入迴圈前 u 和 v 的最大公因數

事實上 u 在迴圈前不一定是被除數，因為先前透過 GCD 演算法第 4 點去除不必要的計算

return u << shift;

最後回傳最大公因數時，乘上原先取出屬於 $2^{n}$ 的公因數，可以透過左移達成

透過 `__builtin_ctz` 改寫程式

已知除法運算會耗費較多時間，我們可以利用 __builtin_ctz (編譯器會產生對應到現代微處理器的專門指令) 搭配上述針對二進位特性調整的演算法，減少除法的使用

改寫之前先透過 perf 分析程式，將一百萬組由 rand 函式生成的亂數傳入 gcd64 函式執行

$ gcc -g3 -O0 gcd.c -o gcd
$ perf record ./gcd
$ perf annotate

由上圖可以發現，花費 CPU 週期數最多的段落為迴圈當中的 v /= 2 運算，佔據約 28%

以下為改寫過後的程式

uint64_t gcd64_ctz(uint64_t u, uint64_t v)
{
    if (!u || !v) return u | v;
    int shift = __builtin_ctzll(u | v);
    u = u >> __builtin_ctzll(u);
    
    do {
        v = v >> __builtin_ctzll(v);
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (v);
    return u << shift;
}

透過 perf 分析前後差異

$ gcc -g -O0 gcdcmp.c -o gcdcmp
$ perf record ./gcdcmp
$ perf report

將同樣一百萬筆由 rand 函式所產生的亂數傳入 gcd64 和 gcd64_ctz 函式比較，發現改寫過後的版本花費時間幾乎是原來的一半

改進空間

透過 perf 分析改寫程式

$ gcc -g -O0 gcd_ctz.c -o gcd_ctz
$ perf record ./gcd_ctz
$ perf annotate

佔據花費時間最多的為分支指令 (如 jne)，其次是迴圈內部的減法運算

`kdnvt`

為什麼有 list_for_each_safe 還需要 list_for_each?

list_for_each 是 list.h 中定義的巨集，用來走訪 linked list 中的各個節點。

以下是實作方式：

#define list_for_each(pos, head) \
	for (pos = (head)->next; !list_is_head(pos, (head)); pos = pos->next)

程式的邏輯十分單純，判斷 pos 是不是等於 head 來當作結束條件，並在每次迴圈結尾讓 pos = pos->next 來走訪。但如果在走訪的過程中，改變了 pos->next ，就可能造成不可預期的行為。因此有了 list_for_each_safe 。

list_for_each_safe 會用到的地方，主要在走訪的過程中，會更改到當前節點（如將當前節點移出）的時候。

想要知道它是如何在更改節點的時候，仍然可以正確的走訪各個節點，就是直接看這個巨集的實作細節：

#define list_for_each_safe(pos, n, head) \
	for (pos = (head)->next, n = pos->next; \
	     !list_is_head(pos, (head)); \
	     pos = n, n = pos->next)

可以看到除了當前的節點 pos ，它還用了另一個指標 n 去指向下一個節點。當目前的節點執行完了，當會在迴圈的結尾讓 pos = n ，再讓 n 指向 pos->next 。如此一來，就算 pos 在走訪的過程被移出，也有 n 這個指標去暫存下一個節點的位址，所以可以安全的走訪所有節點。

若沒有要改變節點的連接方式，如 q_size 中走訪各節點被計算總數，則使用 list_for_each 就好。如果在這種情況下還使用 list_for_each_safe ，則要額外準備一個指標去暫存下一個節點，然而這個指標在走訪個過程中其實是不需要的。

`mickey30606`

如何將以下程式碼，修改成取得最接近且小於等於 2 的冪的值。

uint64_t next_pow2(uint64_t x)
{
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 8;
    x |= x >> 16;
    x |= x >> 32;
    return x+1;
}

方法一：我們只需要將目前最高位的 1 後面位元全部都變成 0 就可以得到我們想要的結果，而原本程式就已經將 x 後面位元全部都變成 1 ，所以我們只需要將 x 往右推移 1 並與自己進行 XOR 即可得到答案。

uint64_t next_pow2(uint64_t x)
{
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x |= x >> 32;
    return x ^ (x >> 1);
}

方法二：使用 __builtin_clzl 進行改寫，取得最高位的 1 前面有幾個 bit 之後，用 1 進行推移就可以得到答案。

uint64_t next_pow2(uint64_t x)
{
    return 1 << (63 - __builtin_clzl(x));
}

第 1,2 週課堂問答簡記

Uduru0522

Eddielin0926

quiz2-4

quiz2-1

william40614, millaker

Tcc0403