---
# System prepended metadata

title: 2020q1 隨堂測驗 (quiz5)
tags: [Linux核心課程筆記 - 隨堂測驗]

---

# 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核心課程筆記 - 隨堂測驗`