2025q1 第 6 週測驗題

目的: 檢驗學員對 bitops 及數值系統的認知

作答表單: 測驗 1
作答表單: 測驗 2, 3

測驗 `1`

延伸〈從模除偏差談亂數分布〉和第三份作業提到的「資訊理論和亂數產生器」，以下利用 select 系統呼叫開發類似 traceroute 的程式。

"route" 的發音是 [ruːt]，其動名詞的發音是 [ˈruː.t̬ɪŋ]

在高鐵列車上測試:

traceroute wiki.csie.ncku.edu.tw
traceroute to csiewiki.crboy.net (143.198.88.212), 64 hops max, 40 byte packets
 1  192.168.43.1 (192.168.43.1)  20.288 ms  4.597 ms  3.475 ms
 2  * * *
 3  * 10.11.209.0 (10.11.209.0)  63.282 ms  37.741 ms
 4  10.11.30.34 (10.11.30.34)  42.605 ms  33.470 ms  31.932 ms
 5  10.9.3.49 (10.9.3.49)  42.574 ms  36.358 ms  42.978 ms
 6  10.9.166.97 (10.9.166.97)  43.035 ms  45.007 ms  35.777 ms
 7  10.9.166.82 (10.9.166.82)  28.820 ms  28.158 ms  43.606 ms
 8  60-199-82-189.static.tfn.net.tw (60.199.82.189)  55.463 ms
    60-199-82-185.static.tfn.net.tw (60.199.82.185)  46.957 ms
    60-199-82-189.static.tfn.net.tw (60.199.82.189)  35.639 ms
...
21  143.198.88.212 (143.198.88.212)  251.091 ms  119.646 ms  100.241 ms

補完 traceroute.c (部分遮蔽)，使其運作符合預期。書寫規範：

AAAA, BBBB 為表示式，使用一致的程式碼排版風格，當存在多種可能時，採最小表示法，亦即，偏好 x + 1，而非 x + 2
CCCC 為十進位整數
DDDD 包含所處的函式名稱，運用 ASLR

測驗 `2`

求 $\log_{2} (a)$ 的值，其中 $a$ 為已知實數。將這個問題轉換成求指數形式:
$2^{x} = a$

也就是要知道 $a$ 能拆成多少個 $2$ 的冪相乘，只要把這些冪相加即可。

下面是可能做法：

把 $a$ 不斷除以 2，直到除不盡時剩下一個 $b$ ：
$2^{x} = a = 2^{1} \times 2^{1} \times 2^{1} \times 2^{1} \times b$

其中 $b$ 比 2 小，該怎麼把它表示成以 2 為底的冪呢？

因為指數函數 $f (x) = 2^{x}$ 的增量會以 $2$ 的冪形式跳動，故 $b$ 可以看成 $2^{α}$ 。同理，我們可觀察 $b^{2}$ 若大於 2，便可繼續遞迴。亦即：
$b = (b^{2})^{\frac{1}{2}} = (b^{2})^{1 / 2}$

架設 $b^{2} = c$ ，那就跟當初拆 $a$ 一樣，可將 $c$ 拆開：
$c = 2^{1} \times 2^{1} \times d$

同樣地
$d = (d^{2})^{\frac{1}{2}}$

再設 $d^{2} = e$ ，繼續跟 $a$ 相同的拆法，依此類推。這用遞迴概念去計算對數，不用查表，也不需要任何高等數學知識。

若底數不是 2，而是假設某個 $A$ ，做法也一樣：
$A^{x} = A^{1} \times A^{1} \times \dots \times b$

然後依照 $b = (b^{A})^{\frac{1}{A}}$ 的方式處理。接著將 $b^{A}$ 再遞迴拆解即可。

概念程式碼如下，可計算任意底數的對數： (部分遮蔽)

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

/* This function calculates log_base(@num) through a naive, recursive approach.
 * @acc denotes the recursion depth, which effectively controls precision.
 * e.g.,
 * - If @num >= @base, the result is 1 plus the log of (@num / @base).
 * - If @num < @base, the result is (1 / @base) times the log of (@num^@base).
 *
 * This process recurses @acc times, partitioning the logarithm into
 * integer and fractional parts step by step.
 *
 * NOTE: This work method is mainly for educational purposes, yielding
 * performance.
 */
double logarithm(double base, double num, int acc)
{
    /* Stop recursion once we have reached the desired depth */
    if (acc <= 0)
        return 0.0;

    /* If num is large enough to "remove" one whole unit of log at once */
    if (num >= base)
        return 1.0 + XXXX;

    /* Otherwise, multiply 'num' by itself 'base' times
     * (which is effectively num^base).
     */
    double tmp = 1.0;
    for (int i = 0; i < (int) base; i++)
        tmp *= num;
    return (1.0 / base) * YYYY;
}

int main(int argc, char **argv)
{
    /* Check if we have enough command-line arguments */
    if (argc < 4) {
        fprintf(stderr, "Usage: %s <recursion_depth> <base> <num>\n", argv[0]);
        return 1;
    }

    /* Number of recursion layers (precision) */
    int acc = atoi(argv[1]);

    /* Base of the logarithm */
    double base = atof(argv[2]);

    /* Number whose logarithm is to be computed */
    double num = atof(argv[3]);

    /* Compute and print the result */
    double result = logarithm(base, num, acc);
    printf("%.18lf\n", result);

    return 0;
}

參考執行輸出:

 $ ./log2 100 2 4024
11.974414589805526532

作答規範:

XXXX 與 YYYY 為有效的 C 語言表達式，不包含空白
以最精簡的形式書寫
不包含 ; 或 ? 或 :

延伸問題:

解釋程式碼運作原理，並改寫為更有效的方式
使用定點數改寫，並探討其精確度
在 Linux 核心原始程式馬找出對數運算的程式碼，並探討至少其中二個應用案例

測驗 `3`

第二週教材系統軟體開發思維提到 Bloom filter，這利用雜湊函數，在不用走訪全部元素的前提，「預測」特定字串是否存於資料結構中。因此時間複雜度是 $O (1)$ ，而非傳統逐一搜尋的 $O (n)$ 。

建構：

n 個位元構成的 table
k 個雜湊函數: h₁ 、 h₂ … h_k
每當要加入新字串 s 時，會將 s 透過這 k 個雜湊函數各自轉換為 table index (範圍: 0 到 n - 1) ，所以有 k 個雜湊函數，就該有 k 個 index ，然後將該 table[index] 上的位元 set (即指定為 1)

此後若要檢查該字串 s 是否存在時，只需要再執行前述 k 個雜湊函數，並檢查是否所有的 k 個位元都是 set 即可

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

動畫: Cube Drone - Bloom Filters

但該做法存在錯誤率，例如原本沒有在資料結構中的字串 s1 經過雜湊函數轉換後得出的位元的位置和另一個存在於資料結構中的字串 s2 經過雜湊函數轉換後的結果相同，如此一來，先前不存在的 s1 便會被認為存在，這就是 false positive (指進行實用測試後，測試結果可能無法反映出真正的面貌或狀況)。

Bloom filter 一類手法的應用很常見。例如在社群網站 Facebook，在搜尋欄鍵入名字時，能夠在 20 億個註冊使用者 (2017 年統計資料) 中很快找到結果，甚至是根據與使用者的關聯度排序。

延伸閱讀:

Bloom Filter 實作方式

首先，建立一個 n 個位元構成的 table，並將每個位元初始化為 0。

我們將所有的字串構成的集合 (set) 表示為 S = { x₁, x₂, x₃, … ,x_n }，Bloom Filter 會使用 k 個不同的雜湊函數，每個雜湊函數轉換後的範圍都是 0 到 n-1 (為了能夠對應上面建立的 n 個位元構成的 table)。而對每個 S 內的 element x_i，都需要經過 k 個雜湊函數，一一轉換成 k 個 index。轉換過後，table 上的這 k 個 index 的值就必須設定為 1。

注意: 可能會有同一個 index 被多次設定為 1 的狀況

Bloom Filter 這樣的機制，存在錯誤率。若今天想要找一個字串 x 在不在 S 中，這樣的資料結構只能保證某個 x₁ 一定不在 S 中，但沒辦法 100% 確定某個 x₂一定在 S 中。因為會有誤判 (false positive) 的可能。

此外，資料只能夠新增，而不能夠刪除，試想今天有二個字串 x₁, x₂ 經過某個雜湊函數 h_i 轉換後的結果 h_i(x₁) = h_i(x₂)，若今天要刪除 x₁ 而把 table 中 set 的 1 改為 0，豈不是連 x₂ 都受到影響？

Bloom Filter 錯誤率計算

首先假設所有字串集合 S 裡面有 n 個字串，雜湊函數總共有 k 個，Bloom Filter 的 table 總共 m 位元。我們會判斷一個字串存在於 S 內，是看經過轉換後的每個位元都被 set 了，我們就會說可能這個字串在 S 內。但試想若是其實這個字串不在 S 內，但是其他的 a b c 等等字串經過轉換後的 index ，剛好涵蓋目標字串轉換後的 index，就造成了誤判這個字串在 S 內的情況。

如上述，Bloom Filter 存有錯誤機率，程式開發應顧及回報錯誤機率給使用者，以下分析錯誤率。

當我們把 S 內的所有字串，每一個由 k 個雜湊函數轉換成 index 並把 table[index] 設為 1，而全部轉換完畢時，table 中某個位元仍然是 0 的機率是 $(1 - \frac{1}{m})^{k n}$ 。

其中 $(1 - \frac{1}{m})$ 是每次雜湊函數轉換後，table 的某個位元仍然是 0 的機率。因為我們把雜湊函數轉換後到每個 index (而這個 index 會被 set) 的機率視為相等 (每單位是 $\frac{1}{m}$ )，所以用 1 減掉即為不會被 set 的機率。我們總共需要做 kn 次雜湊運算，所以就得到 $(1 - \frac{1}{m})^{k n}$ 。

由 $(1 - \frac{1}{m})^{m} \approx e^{- 1}$ 特性，可知
$(1 - \frac{1}{m})^{k n} = ((1 - \frac{1}{m})^{m})^{\frac{k n}{m}} \approx (e^{- 1})^{\frac{k n}{m}} \approx e^{- \frac{k n}{m}}$
這就是當全部字串轉換完畢時，某個位元還沒有被 set 的機率。

因此誤判的機率等同於全部經由 k 個雜湊轉完後的 k 位元已被其他人 set 的機率:
轉完後某個位元被 set 機率是: $1 - e^{- \frac{k n}{m}}$ ，因此某 k 位元被 set 機率為: $(1 - e^{- \frac{k n}{m}})^{k}$

如何選 k 值？

k: 多少個不同雜湊函數
m: table size 的大小

為確保錯誤率最小，也就是讓 $(1 - e^{- \frac{k n}{m}})^{k}$ 的值是最小。先把原式改寫成 $(e^{k l n (1 - e^{- \frac{k n}{m}})})$ ，我們只要使 $k \ln (1 - e^{- \frac{k n}{m}})$ 最小，原式就是最小值。可以看出當 $e^{- \frac{k n}{m}} = \frac{1}{2}$ 時，會達到最小值。因此 $k = l n 2 \frac{m}{n}$ 即能達到最小值。

Bloom Filter calculator 和 Bloom Filter calculator 2 這二個網站可以透過設定自己要的錯誤率與資料的多寡，得到 k 和 m 值。

Bloom Filter error rate 視覺化

縱軸是雜湊函數的數量、橫軸是 table size，並以錯誤率做為深淺來製圖，畫面中紫色線條為 $y = l n 2 \cdot \frac{x}{93827}$ ，其中 93827 為測試用的字典中項目數量。

我們想要最小的空間及執行速度，並符合可預測的錯誤率，於是期望的數值在可行域的左下角。

為了讓圖片不明顯的部分，能被看得清楚，將圖片轉為灰階後做直方圖均衡化

把此圖視為高線圖，可以發現山谷都在 $k = l n 2 \frac{m}{n}$ 上，而在這裡實際的意義就是錯誤率最小值發生在 $k = l n 2 \frac{m}{n}$ 與推導的結果相符。透過開四次方根把錯誤率之間的差距加大，再製圖，可更明顯看出上述的內容。

bloom.[ch] 是上述 Bloom filter 的實作，並利用 Check 進行測試，預期的執行輸出如下: (假設 malloc 不會遇到任何錯誤)

Running suite(s): Bloom Filter
100%: Checks: 6, Failures: 0, Errors: 0

安裝 Check 套件:

sudo apt-get install check

Bloom filter 程式碼 (部分遮蔽)

編譯和測試:

$ gcc -Wall -O2 -o bloom bloom.c test-bloom.c \
      -lcheck -lsubunit -lm -lpthread -lrt          
$ ./bloom

population count 簡稱 popcount 或叫 sideways sum，是計算數值的二進位表示中，有多少位元是 1，在一些場合下很有用，例如計算 0-1 稀疏矩陣 (sparse matrix)或 bit array 中非 0 元素個數、計算兩個字串的 Hamming distance。Intel 在 2008 年 11 月 Nehalem 架構的處理器 Core i7 引入 SSE4.2 指令集，其中就有 CRC32 和 popcount 指令，popcount 可處理 16-bit, 32-bit, 64-bit 整數。

對應到 C 程式的實作:

unsigned popcount_naive(unsigned v)
{
    unsigned n = 0;
    while (v)
        v &= (v - 1), n = -(~n);
    return n;
}

函式 popcount_naive() 利用不斷清除 LSB 直到輸入的數值 v 為 0。

v &= (v - 1) 的作用是將 LSB 設為 0 (reset LSB) 舉例來說，假設輸入數值為 20:

0001 0100  # 20          ; LSB in bit position 2
0001 0011  # 20 - 1
0001 0000  # 20 & (20 - 1)

類似的操作還有 x & -x，將 x 的 LSB 取出 (isolate LSB)

n = -(~n) 等同 n++，因為在二補數系統中，
$- n = \sim n + 1$
$- (\sim n) = n + 1$

因此 popcount_naive() 的執行時間取決於輸入數值中 1 (set bit) 的個數。可改寫為以下常數時間複雜度的實作:

unsigned popcount_branchless(unsigned v)
{
    unsigned n;
    n = (v >> 1) & 0x77777777;
    v -= n;
    n = (n >> 1) & 0x77777777;
    v -= n;
    n = (n >> 1) & 0x77777777;
    v -= n;

    v = (v + (v >> 4)) & 0x0F0F0F0F;
    v *= 0x01010101;                                     

    return v >> 24;
}

對於一個 32 bit 的無號整數，popcount 可以寫成以下數學式:

$p o p c o u n t (x) = x - ⌊ \frac{x}{2} ⌋ - ⌊ \frac{x}{4} ⌋ - . . . - ⌊ \frac{x}{2^{31}} ⌋$

假設 $x = b_{31} . . . b_{3} b_{2} b_{1} b_{0}$ ，先看看 $x [3 : 0]$ 4 個位元，用以上公式可以計算得:

$(2^{3} b_{3} + 2^{2} b_{2} + 2^{1} b_{1} + 2^{0} b_{0}) - (2^{2} b_{3} + 2^{1} b_{2} + 2^{0} b_{1}) - (2^{1} b_{3} + 2^{0} b_{2}) - 2^{0} b_{3}$

$⌊ \frac{x}{2} ⌋$ 相當於 C 表達式中 x >> 1

稍微改寫可得到:
$(2^{3} - 2^{2} - 2^{1} - 2^{0}) b_{3} + (2^{2} - 2^{1} - 2^{0}) b_{2} + (2^{1} - 2^{0}) b_{1} + 2^{0} b_{0}$

因此 popcount 的一般式可改寫為:
$p o p c o u n t (x) = \sum_{n = 0}^{31} (2^{n} - \sum_{i = 0}^{n - 1} 2^{i}) b_{n} = \sum_{n = 0}^{31} b_{n}$

因為 $2^{n} - \sum_{i = 0}^{n - 1} 2^{i} = 1$ ，只要對應的 $b_{n}$ 為 1，這個 bit 就會在 popcount 的總和中加一，剛好對應 popcount_naive()，因此映證上述數學式確實可計算出 population count。

且一個 32 位元無號整數最多有 32 個 1 (set bit)，剛好可用一個 byte 表示，所以可分成幾個區塊平行計算，最後再全部加總到一個 byte 中，進行避免檢查 32 次。

popcount_branchless 實作一開始以每 4 個位元 (nibble) 為一個單位計算 1 的個數，利用最初的公式計算 $x - ⌊ \frac{x}{2} ⌋ - ⌊ \frac{x}{4} ⌋ - ⌊ \frac{x}{8} ⌋$

關鍵的程式碼，逐行解釋:






n = (v >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;

n = (v >> 1) & 0x77777777 : 將輸入數值 v 除以 2，得到

⌊ \frac{v}{2} ⌋

b_31 b_30 b_29 b_28 ... b7 b6 b5 b4 b3 b2 b1 b0  // v
   0 b_31 b_30 b_29 ...  0 b7 b6 b4  0 b3 b2 b1  // (v >> 1) & 0x77777777

v -= n : 計算結果相當於 $v - ⌊ \frac{v}{2} ⌋$
n = (n >> 1) & 0x77777777 : 再對 n 除以 2，得到 $⌊ \frac{v}{4} ⌋$
v -= n : 計算出 $v - ⌊ \frac{v}{2} ⌋ - ⌊ \frac{v}{4} ⌋$
和 6. 重複同樣動作

最後這段結束後計算出 $v - ⌊ \frac{v}{2} ⌋ - ⌊ \frac{v}{4} ⌋ - ⌊ \frac{v}{8} ⌋$ ，得到每 4 個位元為一個單位中 set bit 的個數

v = (v + (v >> 4)) & 0x0F0F0F0F : 將每 4 個位元中 set bit 的個數加到 byte 中:

假設

B_{n}

代表第 n 個 nibble (4 位元) 中的數值

B7 B6 B5 B4 B3 B2 B1 B0  // v
 0 B7 B6 B5 B4 B3 B2 B1  // (v >> 4)

加總可得到:

// (v + (v >> 4))
B7 (B7+B6) (B6+B5) (B5+B4) (B4+B3) (B3+B2) (B2+B1) (B1+B0)

最後使用 0x0F0F0F0F 做 mask 可得

// (v + (v >> 4)) & 0x0F0F0F0F
0 (B7+B6) 0 (B5+B4) 0 (B3+B2) 0 (B1+B0)

v *= 0x01010101 : 在最後一道敘述中，將 v 乘上 0x01010101。寫成直式如下

                         0 A6  0 A4  0 A2  0 A0
                      x  0  1  0  1  0  1  0  1
---------------------------------------------------
                         0 A6  0 A4  0 A2  0 A0
                   0 A6  0 A4  0 A2  0 A0  0
             0 A6  0 A4  0 A2  0 A0  0
       0 A6  0 A4  0 A2  0 A0  0
---------------------------------------------------
                            ↑_______________________A6+A4+A2+A0

我們可發現期望輸出就在原本 $A_{6}$ 的位置 ( $2^{7}$ )，因此將 v 右移 24 bits 即為所求，剩下的位數會 overflow ，右移後不影響結果。

假設

A = B_{7} + B_{6}

B = B_{5} + B_{4}

C = B_{3} + B_{2}

D = B_{1} + B_{0}

, 根據分配律可得:

v * 0x01010101 = 
(A + B + C + D)  (B + C + D)      (C + D)          (D)
|<-- 1 byte -->|<-- 1 byte -->|<-- 1 byte -->|<-- 1 byte -->|

return v >> 24 : 最後得到的結果會放在 Most significant byte 中，因此向右位移 24 位元，即為所求的 popcount 值。

GCC 提供對應的內建函式:

__builtin_popcount(x): 計算 x 的二進位表示中，總共有幾個 1

使用示範：

int x = 5328; // 00000000000000000001010011010000
printf("%d\n",  __builtin_popcount(x)); // 5

兩個整數間的 Hamming distance 為其二進位的每個位元的差

Example :
1 (0 0 0 1)
4 (0 1 0 0)

hamming distance = 2

A $\oplus$ B	B = 0	B = 1
A = 0	0	1
A = 1	1	0

A ^ B　就為二進位中兩數字的每個位元的差，再透過　popcount() 就可以得到答案

int hammingDistance(int x, int y)
{
    return __builtin_popcount(x ^ y);
}

作答規範:

依循第一次作業指定的程式碼風格書寫，並採用最簡短的形式
AAAA 和 BBBB 是表示式，不得出現 % (modulo) 運算子，變數應當在 integer literal 前出現
CCCC 和 EEEE 是十進位整數，用最簡短的方式書寫
DDDD 是表示式
FFFF, GGGG, HHHH 為表示式 (不得出現 ; 字元)，應包含 popcount，小括號對 (即 ( 和 ) 構成的 pair) 的數量僅為 1，也就是函式呼叫所用
IIII 和 JJJJ 為表示式

由於 Bloom filter 的限制，後來出現一系列改進的替代選擇，例如 Meta 發展的 Ribbon Filter (用於 RocksDB)、空間使用率更高且支援 delete 操作的 Cuckoo filter、空間使用率較 Cuckoo filter 高的 Xor filter，以及進一步改良的 Binary Fuse Filters。

之前學員的筆記: Xor Filter 論文與實作、實作 XOR Filter 並改善

延伸問題:

解釋上述程式碼運作原理 (要從 Entropy 來解讀)，指出可改進之處並著手進行。
在 Linux 核心原始程式碼中找到 Bloom filter 的應用案例 (例如 eBPF) 並探討其運用方式。
雜湊函數的表現對於 Bloom filter 相當重要，請參照 Linux 核心的應用案例，說明其雜湊函數的選擇，並探討更換其他實作以有更好表現的可能。
評估引入 Bloom filter 的替代選擇到 Linux 核心。

2025q1 第 6 週測驗題

測驗 1

測驗 2

測驗 3

Read more

並行程式設計: Atomics 操作

你所不知道的 C 語言: linked list 和非連續記憶體

Linux 核心設計: 不只挑選任務的排程器

歐拉數 e: 描述連續變化的基石

測驗 `1`

測驗 `2`

測驗 `3`