# [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`，試著將原本運算: ```cpp #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 編譯) ```cpp #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` 可能形如: ```cpp 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+) 來解說這類手法; :::