2020q1 第 5 週測驗題

tags: linux2020

目的:

1. 檢驗學員對 bitwise 操作 和 數值系統 的認知;
2. 為日後理解 Linux 核心特定運算加速機制做準備;

作答表單

---

測驗 1

考慮到整數 PAGE_QUEUES 可能有以下數值:

• (1 or 2 or 3 or 4)
• (5 or 6 or 7 or 8)
  $\times$ (2ⁿ), n from 1 to 14

給定 size_t offset，試著將原本運算:

#include <stdint.h>
size_t blockidx = offset / PAGE_QUEUES;

由於 PAGE_QUEUES 的數值分佈已知，在整數除法時，可思考加速運算的機制。需要注意，某些硬體平台缺乏整數除法指令 (如 Arm Cortex-A8)，即使 Intel 公司出品的 Core 處裡器 Sandy Bridge 微架構中，針對 64 位元整數的除法運算，會佔用 40 到 103 個處理器週期，運算成本仍屬沈重。

來源: Agner Fog’s instruction tables，第 180 頁

於是我們可預先進行計算，從而避免整數除法指令的使用: (假設在 x86_64 硬體執行 GNU/Linux 並透過 gcc/clang 編譯)

#include <stdint.h>
#define ffs32(x)  ((__builtin_ffs(x)) - 1)
size_t blockidx;
size_t divident = PAGE_QUEUES;
blockidx = offset >> ffs32(divident);
divident >>= ffs32(divident);
switch (divident) {
    CASES
}

其中 CASE 可能形如:

    case 2: blockidx /= 2; 
        break;

這樣的組合，請用最少的 case-break 敘述做出同等 size_t blockidx = offset / PAGE_QUEUES; 效果的程式碼。

參考資料:

• Integer division is slow

作答區

CASE 至少該包含哪些數字: (複選)

• (a) 2
• (b) 3
• (c) 4
• (d) 5
• (e) 6
• (f) 7
• (g) 8
• (i) 9
• (j) 10

延伸問題:

1. 解釋程式運算原理，可搭配 Microsoft Research 的專案 snmalloc 來解說;
   • 對應的原始程式碼 src/mem/sizeclass.h
2. 另一個記憶體管理器 Hardened Malloc 針對整數除法也有類似的加速機制，不過更加複雜，利用到 third_party/libdivide.h，請解釋和上述手法相似的部分;
3. Linux 核心原始程式碼也有類似技巧，例如 do_div(): generic optimization for constant divisor on 32-bit machines，請搭配購新的 Linux 核心 (v5.5+) 來解說這類手法;