# 2020q1 隨堂測驗 (quiz5) contributed by < `Yu-Wei-Chang` > > [2020q1 第 5 週測驗題](https://hackmd.io/@sysprog/linux2020-quiz5) ### 測驗 `1` #### 程式運作原理 * 減少整數除法的開銷 * 根據 [Integer division is slow](https://kristerw.blogspot.com/2017/05/integer-division-is-slow.html) 的解釋，整數的除法在 Intel 架構上至多需要花費 103 cycles。 * 而此測驗題中的技巧是將除法的動作拆解成 `right bit shift (相當於除以 2)` + `整數除法`。 ``` E.g. Dividend / 24 --拆解--> (((Dividend / 2) / 2) / 2) / 3 相當於 (Dividend >> 3) / 3 ``` * 從 [Agner Fog’s instruction tables](https://www.agner.org/optimize/instruction_tables.pdf) 的表格中查詢到 `SHR` 指令只需要花 1 個 cycle 而已 (right bit shift 是不是對應到 SHR 的機器指令還需要查詢及證實...) * 承上述的例子，我們可以對`除數`的數值使用 GCC built-in function [__builtin_ffs(x)](https://gcc.gnu.org/onlinedocs/gcc-4.7.2/gcc/Other-Builtins.html#Other-Builtins) 就可以知道需要對`被除數`進行幾次 right bit shift。 ``` 24 (decimal) = 11000b __builtin_ffs(24) - 1 = 3 E.g. Dividend / 24 相當於 (Dividend >> __builtin_ffs(24) - 1) / 3 ``` * 由題目的條件 `PAGE_QUEUES` 的數值為 : * (1 or 2 or 3 or 4) * $(5 or 6 or 7 or 8) * (2^n),$ n from 1 to 14 上述數值在做完 right bit shift 後只會剩 $1_b$、$11_b$、$101_b$、$111_b$ 這幾種情況，而剩 1 就不用處理了，所以 switch case 中會有 3、5、7 這三種 case。 * [程式程式碼](https://github.com/Yu-Wei-Chang/Sysprog_2020q1_quiz5) ， 在進行大量的除法運算可以確認有使用位移來加速的狀況，程式執行時間較小。 ```shell $ ./speed_int_division Speed up, integer division. Time cost (us): 636971358 $ ./int_division Integer division. Time cost (us): 814048333 ``` ###### tags: `Linux核心課程筆記 - 隨堂測驗`