2023q1 Homework2 (quiz2)

contributed by < yanjiew1 >

實驗環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
    CPU family:          6
    Model:               142
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            10
    CPU max MHz:         3400.0000
    CPU min MHz:         400.0000
    BogoMIPS:            3600.00

測驗 1

程式說明

一開始 x |= x >> 1; 中在此程式出現 7 次。即這段 64 bits 數值中，每一個 1 向右擴展 7 個 1 。

00...01000000000...000
      |
      v
00...01111111100...000

x |= x >> 8; ，因為前面的 x |= x >> 1; ，至此 x 裡的 1 已向右擴展 7 個，故有 8 個連續的 1，透過再跟 x >> 8 進行 or 運算，會把這些連續的 1 ，再向右擴展 8 個 1。 AAAA 填入 8

x |= x >> 16; 會把 16 個連續的 1 再向右擴展 16 個，會讓 x 變成有至少 32 個連續的 1 。

x |= x >> 32; 會把 32 個連續的 1 再向右擴展至 64 個，會讓 x 變成有至少 64 個連續的 1 。 BBBB 填入 32 。

最後會讓 x 中最高位的 1 擴展至最低位，變成 00...01111111111...111 。

因為這個函式的目的是要找下一個 2 的冪。只要再加上 1 ，即會讓這些 1 進位，變成下一個 2 的冪。故最後 return x + 1;。 CCCC 填入 x + 1

另外這個函式其實不完全正確。題目說「考慮 next_pow2 可針對給定無號 64 位元數值 x，找出最接近且大於等於 2 的冪的值」，故應該要在函式的開頭加入 x--; ，先把 x 減去 1 ，這樣才能讓原本就是 2 的冪的數值維持一致。

另外此作法，可簡化為：

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

用 `__builtin_clzll` 改寫

特別注意的是 __builtin_clzll 傳入的值若為 0 ，則為未定義行為，會產生不可預期的結果。故一開始的 if 條件判斷式即排除此狀況。

uint64_t next_pow2(uint64_t x)
{
    if (x <= 1)
        return 1;

    return 1 << (64 - __builtin_clzll(x - 1));
}

用 Compiler Explorer 來實驗，連結在此，的確有出現 bsrq 指令。

next_pow2:
        movl    $1, %eax
        cmpq    $1, %rdi
        jbe     .L1
        subq    $1, %rdi
        movl    $64, %ecx
        bsrq    %rdi, %rdi
        xorq    $63, %rdi
        subl    %edi, %ecx
        sall    %cl, %eax
        cltq
.L1:
        ret

Linux 核心範例

Linux 有關 2 的冪相關的程式在這裡 linux/include/linux/log2.h 。最接近上述的是 __roundup_pow_of_two 這個函式。但跟測驗的 next_pow2 不太一樣是，測驗是找「下一個 2 的冪」，也就是 4 的下一個 2 的冪會是 8 ，但 Linux kernel 裡的 __roundup_pow_of_two 是直接取大於等於輸入值且最接近輸入值的 2 的冪。

在 elixir.bootlin.com 這個網站裡搜尋使用到 __roundup_pow_of_two 的程式碼發現在許多的裝置驅動程式內用到。

Defined in 2 files as a function:

    include/linux/log2.h, line 55 (as a function)
    tools/include/linux/log2.h, line 47 (as a function) 

Referenced in 16 files:

    drivers/clk/clk-divider.c
        line 226
        line 244
        line 282 
    drivers/clk/sunxi/clk-sunxi.c, line 314
    drivers/clk/zynqmp/divider.c, line 59
    drivers/infiniband/hw/hfi1/chip.c
        line 14321
        line 14324 
    drivers/infiniband/hw/hfi1/init.c, line 433
    drivers/iommu/intel/dmar.c, line 1544
    drivers/iommu/intel/iommu.c, line 1505
    drivers/iommu/intel/irq_remapping.c, line 118
    drivers/iommu/intel/svm.c, line 201
    drivers/net/ipa/gsi_trans.c, line 150
    drivers/pci/msi/msi.c, line 303
    include/linux/log2.h, line 180
    net/mac80211/cfg.c, line 1155
    net/sunrpc/xprtrdma/verbs.c, line 857
    tools/include/linux/log2.h, line 157
    tools/perf/builtin-sched.c
        line 1904
        line 2290

測驗 2

程式說明

在這個 for 迴圈中，要串接由 1 到 n 的二進位數值至 ans 。其中 len 為目前 i 二進位數值所需要的位元數量。

for (int i = 1; i <= n; i++) {
    /* removing the rightmost set bit
     * e.g. 100100 -> 100000
     *      000001 -> 000000
     *      000000 -> 000000
     * after removal, if it is 0, then it means it is power of 2
     * as all power of 2 only contains 1 set bit
     * if it is power of 2, we increase the bit length
     */
    if (!(DDDD))
        len++;
    ans = (i | (EEEE)) % M;
}

其中，每次 i 進位時，即 i 為 2 的冪時，長度會多一個位元，故可用 i & (i - 1) 來判斷是否為 2 冪。

若 i 為 2 的冪，i 只會有一個位元是 1 ，而 i - 1 會讓這個位元變為 0 ，在這個位元的右邊變成全為 1 ，此時 i & (i - 1) 為 0
若 i 不為 2 的冪，則 i 會有多個 bit 是 1 ，那麼 i - 1 只會讓最右邊是 1 的位元變為 0 ，並讓此位元的右邊其他的位元變為 1 ， i & (i - 1) 就會讓 i 最右邊是 1 的位元變成 0 。

ans = (i | (EEEE)) % M; ，會把現有的 ans 先左移 len 個位元空出空間後，再把 i 串加上去。故可用 ans << len 來進行左移。

ans 雖然是模 M 後的結果，但仍不影響操作。因為 << len 實際上是乘上

2^{len}

，而 | 雖然為 or 運算，但因為 ans 左移後空下來的位置位元是 0 ，故在這裡其作用是加法。而對 ans 先乘加後再取餘數與先對 ans 取餘數再乘加，結果是一樣的。

使用 `__builtin_clz` 改寫

可以直接使用 32 - __builtin_clz(n) 來算出 i 需要幾個位元。

int concatenatedBinary(int n)
{
    const int M = 1e9 + 7;
    /* use long here as it potentially could overflow for int */
    long ans = 0;
    for (int i = 1; i <= n; i++) {
        int len = 32 - __builtin_clz(i);
        ans = (i | (ans << len)) % M;
    }
    return ans;
}

目前還沒想到怎麼改進 % (1e9 + 7) ，但應該可以透過減去某二個數字相乘來達到同樣的效果

測驗 3

此題介紹了 SWAR 軟體最佳化的技巧，以及它如何運用在計算 UTF-8 字串中，字的數目。詳細 bitwise 的操作可以看 quiz2 題目說明

此題 swar_count_utf8 函式，在 for 迴圈內，每次讀進 8 個位元組。透過 bitwise 操作，讓整個 64bit 的無號整數，值為 1 的位元數量等同於此 8 個位元組中，屬於 UTF-8 中後續位元組 (continuation byte(s)) 的數量。

size_t count = 0;
for (; qword != end; qword++) {
    const uint64_t t0 = *qword;
    const uint64_t t1 = ~t0;
    const uint64_t t2 = t1 & 0x04040404040404040llu;
    const uint64_t t3 = t2 + t2;
    const uint64_t t4 = t0 & t3;
    count += __builtin_popcountll(t4);
}

故迴圈執行完畢後， count 會存放字串中， (len & ~7) 後續位元組 (continuation byte(s)) 的數量。

接下來就是直接把 (len & ~7) 減去 count ，則得到了前 (len & ~7) 中， UTF-8 中字元的個數。故這裡 AAAA 可填入 3 。

count = (1 << AAAA) * (len / 8)  - count;

再來要處理最後的 (len & 7) 個位元組。最後一行判斷 (len & 7) 是否還有位元組未處理，若還有則呼叫 count_utf8 來處理。故這裡 BBBB 和 CCCC 可填入 7

count += (len & BBBB) ? count_utf8((const char *) end, len & CCCC) : DDDD;

效能比較

測試程式

我把二種實作放進我的測試程式中，用下列命令來編譯

$ gcc -O2 utf-8.c

測得結果為：

實作	花費時間 (cycles)
count_utf8	54378.65
swar_count_utf8	30444.72

swar_count_utf8 可得到較高的效能。

若用 gcc -O3 utf-8.c 來編譯，則 count_utf8 會比較快。此為編譯後的組合語言 count_utf8 ，用到很多 SIMD 指令且 swar_count_utf8 沒有利用 SIMD 指令(可能太複雜讓 GCC 不好進行最佳化)，這或許就是 count_utf8 比較快的關鍵。

Linux 核心的 UTF-8 和 Unicode

簡單搜尋了 Linux UTF-8 的實作，有以下位置

不過沒有看到核心有用到計算 UTF-8 中 Unicode 字元數量的部份。比較接近的是在 fs/unicode/utf8-norm.c 中的 utf8nlen ，但功能仍然不同。

測驗 4

觀察題目 pattern ，可以知道原始程式功能是判斷 16 bits 無號整數，其位元的組成是否符合正規表示式 1+0* 。

先觀察 -x ^ x 的特性。 -x 是取 2 的補數，即 ~x + 1 。當我們對一個數字取 2 的補數時，可以觀察到，此動作會把原本數字最右邊為 1 的位元其左邊所有位元反轉，例如：

   1011001100
=> 0100110100

又從 xor 真值表可知，若二位元相異，則其值為 1 反之為 0 。故 -x ^ x 中，輸出值中， x 最右邊為 1 的位元其所有左邊位元會是 1 ，其餘為 0 ，即：

   1011001100
=> 1111111000

接下來考慮二個 case ：

當 x 符合正規表示式 1+0* 時， -x ^ x 會恰好讓開頭 1 的位元數少一個，即 11110000 => 11100000 ，即 -x ^ x < x 。
當 x 不符合 1+0* 時，雖然輸出值中，對應回 x 中最右邊為 1 的位元所在位置變成 0 ，但是最右邊 1 的所有左邊位元都變成 1 ，例 1010100 => 1111000 故 -x ^ x > x 。

回到此題，跟據上面的觀察，我們可以填入 EEEE = -x ， FFFF = x 。

bool is_pattern(uint16_t x)
{
    const uint16_t n = EEEE;
    return (n ^ x) < FFFF;
}

2023q1 Homework2 (quiz2)

實驗環境

測驗 1

程式說明

用 __builtin_clzll 改寫

Linux 核心範例

測驗 2

程式說明

使用 __builtin_clz 改寫

測驗 3

效能比較

Linux 核心的 UTF-8 和 Unicode

測驗 4

Linux 核心的應用

Read more

2023q1 Homework7 (ktcp)

2023q1 Homework6 (quiz5)

2023q1 Homework5 (assessment)

2023q1 Homework6 (quiz6)

用 `__builtin_clzll` 改寫

使用 `__builtin_clz` 改寫