# [2020q1](http://wiki.csie.ncku.edu.tw/linux/schedule) 第 5 週測驗題
###### tags: `linux2020`

:::info
目的:
1. 檢驗學員對 **[bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)** 和 **[數值系統](https://hackmd.io/@sysprog/c-numerics)** 的認知;
2. 為日後理解 Linux 核心特定運算加速機制做準備;
:::

==[作答表單](https://forms.gle/VsXYbVND5wv7hD2U8)==

---

### 測驗 `1`

考慮到整數 `PAGE_QUEUES` 可能有以下數值:
* (1 or 2 or 3 or 4)
* (5 or 6 or 7 or 8) $\times$ (2^n^), 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 微架構](https://en.wikipedia.org/wiki/Sandy_Bridge)中，針對 64 位元整數的除法運算，會佔用 40 到 103 個處理器週期，運算成本仍屬沈重。
> 來源: [Agner Fog’s instruction tables](https://www.agner.org/optimize/instruction_tables.pdf)，第 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](https://kristerw.blogspot.com/2017/05/integer-division-is-slow.html)

==作答區==

CASE 至少該包含哪些數字: (複選)
* `(a)` 2
* `(b)` 3
* `(c)` 4
* `(d)` 5
* `(e)` 6
* `(f)` 7
* `(g)` 8
* `(i)` 9
* `(j)` 10

:::success
延伸問題:
1. 解釋程式運算原理，可搭配 Microsoft Research 的專案 [snmalloc](https://github.com/microsoft/snmalloc) 來解說;
* 對應的原始程式碼 [src/mem/sizeclass.h](https://github.com/microsoft/snmalloc/blob/master/src/mem/sizeclass.h#L54-L145)
2. 另一個記憶體管理器 [Hardened Malloc](https://www.whonix.org/wiki/Hardened_Malloc) 針對整數除法也有類似的加速機制，不過更加複雜，利用到 [third_party/libdivide.h](https://github.com/GrapheneOS/hardened_malloc/blob/master/third_party/libdivide.h)，請解釋和上述手法相似的部分;
3. Linux 核心原始程式碼也有類似技巧，例如 [do_div(): generic optimization for constant divisor on 32-bit machines](https://lore.kernel.org/patchwork/patch/614225/)，請搭配購新的 Linux 核心 (v5.5+) 來解說這類手法;
:::