---
# System prepended metadata

title: Linux 核心設計 Homework3 (lab3)

---

# Linux 核心設計 Homework3 (lab3)
contributed by < r34796Kevin >
## 簡介
實作Jserv老師的[Linux 核心設計 (Linux Kernel Internals)](http://wiki.csie.ncku.edu.tw/linux/schedule)的[作業3](https://hackmd.io/@sysprog/linux2021-fibdrv#J06-fibdrv),並且盡量完成作業的額外要求
- [x] 研讀上述 ==Linux 效能分析的提示== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
- [x] 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
- [x] 複習 C 語言 [數值系統](https://hackmd.io/@sysprog/c-numerics) 和 [bitwise operation](https://hackmd.io/@sysprog/c-bitwise)，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本;
- [x] 研讀 [KYG-yaya573142 的報告](https://hackmd.io/@KYWeng/rkGdultSU)，指出針對大數運算，有哪些加速運算和縮減記憶體操作成本的舉措？
- [ ] `lsmod` 的輸出結果有一欄名為 `Used by`，這是 "each module's use count and a list of referring modules"，但如何實作出來呢？模組間的相依性和實際使用次數 ([reference counting](https://en.wikipedia.org/wiki/Reference_counting)) 在 Linux 核心如何追蹤呢？
- [ ] 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 [POSIX Thread](https://en.wikipedia.org/wiki/POSIX_Threads) 的程式碼來確認。

- [x] 在 GitHub 上 fork [fibdrv](https://github.com/sysprog21/fibdrv)，目標是修正 Fibonacci 數計算的正確性 (現有實作存在缺陷，請指出)，隨後改善 `fibdrv` 計算 Fibinacci 數列的執行效率，過程中需要量化執行時間，可在 Linux 核心模組和使用層級去測量
    * 原本的程式碼只能列出到 Fibonacci(100) 而且==部分輸出是錯誤的數值==，請修改程式碼，列出後方更多數值 (注意: 檢查正確性和數值系統的使用)
    * 務必研讀上述 ==Linux 效能分析的提示== 的描述，降低效能分析過程中的干擾;
    * 在 Linux 核心模組中，可用 ktime 系列的 API;
    * 在 userspace 可用 [clock_gettime](https://linux.die.net/man/2/clock_gettime) 相關 API;
    * 善用統計模型，除去極端數值，過程中應詳述你的手法
    * 分別[用 gnuplot 製圖](https://hackmd.io/@sysprog/Skwp-alOg)，分析 Fibonacci 數列在核心計算和傳遞到  userspace 的時間開銷，單位需要用 us 或 ns (自行斟酌)
    * 嘗試解讀上述實驗的時間分佈，特別是隨著 Fibonacci 數列增長後，對於 Linux 核心的影響。可修改 VFS 函式，允許透過寫入 `/dev/fibonacci` 裝置檔案來變更不同的 Fibonacci 求值的實作程式碼。
    ![](https://i.imgur.com/7xyCUVO.png)
- [x] 逐步最佳化 Fibonacci 的執行時間，引入[費氏數列分析](https://hackmd.io/@sysprog/fibonacci-number) 提到的策略，並善用 [clz / ffs](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令 (Linux 核心有對應的包裝函式)，過程中都要充分量化
- [x] 嘗試研讀 [bignum](https://github.com/0xff07/bignum/tree/fibdrv) (`fibdrv` 分支) 的實作，理解其中的技巧並與你的實作進行效能比較，探討個中值得取鏡之處。
    * 原理和分析可見 [KYG-yaya573142 的報告](https://hackmd.io/@KYWeng/rkGdultSU)
## 實作
Fibonacci數列定義為
$$
F_{n}=F_{n-1}+F_{n-2}, \text{ where } F_{0}=0, F_{1}=1.
$$
```c=
static long long fib_sequence(long long k)
{
    /* FIXME: C99 variable-length array (VLA) is not allowed in Linux kernel. */
    long long f[k + 2];

    f[0] = 0;
    f[1] = 1;

    for (int i = 2; i <= k; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }

    return f[k];
}

```
```
r34796@r34796-PS63-Modern-8RC:~/kevin/linux2021/fibdrv$ git commit
Dangerous function detected in /home/r34796/kevin/linux2021/fibdrv/fibdrv.c
71:    sprintf(tmp, "%lld\n", runtime);

Read 'Common vulnerabilities guide for C programmers' carefully.
    https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml

```
### 排除效能分析上干擾因素
考量到[Processor affinity](https://en.wikipedia.org/wiki/Processor_affinity)，讓行程 (process) 在特定的 CPU 核心中持續執行，不受作業系統排程的干擾。
查看指定行程的處理器親和性，可使用 `taskset` 加上 `-p `參數再加上該行程的 `PID`（process ID）：
目前PID 1的行程可以被作業系統排程安排在CPU0~7上。
```
r34796@r34796-PS63-Modern-8RC:/etc/default$ taskset -cp 1
pid 1 目前的近似者清單：0-7

```
修改 `/etc/default/grub` 內的 `GRUB_CMDLINE_LINUX_DEFAULT`，加入 `isolcpus=7` 來指定編號 7 的核心不被排程器賦予任務，修改完成後需 `sudo update-grub` 來更新設定，重開機後即生效。
重新使用`taskset -cp 1`查看，目前PID 1的行程可以被作業系統排程安排在CPU0~6上。
```
r34796@r34796-PS63-Modern-8RC:~$ taskset -cp 1
pid 1 目前的近似者清單：0-6

```
#### 將程式固定在特定的 CPU 中執行
透過指定處理器親和性 (processor affinity，亦稱 CPU pinning)，可以將程式固定在特定的 CPU 中執行
```shell
$ sudo taskset -c 7 ./client
```

#### 抑制 [address space layout randomization](https://en.wikipedia.org/wiki/Address_space_layout_randomization) (ASLR)

```shell
$ sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
```
#### 針對 Intel 處理器，關閉 turbo mode
```shell
$ sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
```
### 實作效能分析
在 Linux 核心模組中，可用 ktime 系列的 API;我挪用`read function`來輸出上一次 fib 的執行時間。
```c=
static ssize_t fib_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
    ktime_t start = ktime_get();
    ssize_t re = fib_sequence(*offset);
    ktime_t end = ktime_get();
    ktime_t runtime = ktime_sub(end, start);

    char tmp[128];
    memset(tmp, 0, 128);
    snprintf(tmp, sizeof(tmp), "%lld\n", runtime);
    //    strncpy(buf,tmp,128);
    copy_to_user(buf, tmp, 128);

    return re;
}
```
在 userspace 可用 clock_gettime 相關 API;
```c=
for (int i = 0; i <= offset; i++) {
        struct timespec start, end;
        lseek(fd, i, SEEK_SET);
        clock_gettime(CLOCK_REALTIME, &start);
        sz = read(fd, buf, sizeof(buf));
        clock_gettime(CLOCK_REALTIME, &end);
        printf("Reading from " FIB_DEV
               " at offset %d, returned the sequence "
               "%lld.\n",
               i, sz);
        long long ut = (long long) (end.tv_sec * 1e9 + end.tv_nsec) -
                       (start.tv_sec * 1e9 + start.tv_nsec);
        //得到的執行時間寫進time.txt
        fprintf(fp, "%d %lld %lld\n", i, ut, atoll(buf));
    }

```
在[Linux man page](https://linux.die.net/man/3/clock_gettime)中提到
```
Sufficiently recent versions of GNU libc and the Linux kernel support the following clocks:

CLOCK_REALTIME
    System-wide realtime clock. Setting this clock requires appropriate privileges. 
CLOCK_MONOTONIC
    Clock that cannot be set and represents monotonic time since some unspecified starting point. 
CLOCK_PROCESS_CPUTIME_ID
    High-resolution per-process timer from the CPU. 
CLOCK_THREAD_CPUTIME_ID
    Thread-specific CPU-time clock. 
```
在這邊我使用`CLOCK_REALTIME`會產生不正確的結果如下：
![](https://i.imgur.com/DAb1Hod.png)
如果使用`CLOCK_MONOTONIC`可以修正這個問題：
![](https://i.imgur.com/QaObYjh.png)
### 撰寫script來幫助測量
針對 SMP IRQ affinity 進行設置，盡量避免 CPU 7 去處理 IRQ。
```scala=
CPUID=7
ORIG_ASLR=`cat /proc/sys/kernel/randomize_va_space`
ORIG_GOV=`cat /sys/devices/system/cpu/cpu$CPUID/cpufreq/scaling_governor`
ORIG_TURBO=`cat /sys/devices/system/cpu/intel_pstate/no_turbo`

sudo bash -c "echo 0 > /proc/sys/kernel/randomize_va_space"
sudo bash -c "echo performance > /sys/devices/system/cpu/cpu$CPUID/cpufreq/scaling_governor"
sudo bash -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"

#measure the performance of fibdrv
make all
make unload
make load
sudo taskset -c 7 ./client
gnuplot showtime.gp
make unload

# restore the original system settings
sudo bash -c "echo $ORIG_ASLR >  /proc/sys/kernel/randomize_va_space"
sudo bash -c "echo $ORIG_GOV > /sys/devices/system/cpu/cpu$CPUID/cpufreq/scaling_governor"
sudo bash -c "echo $ORIG_TURBO > /sys/devices/system/cpu/intel_pstate/no_turbo"



```
將`userspace`得到的時間減去`kernelspace`得到的時間，可以測量`System Call`的時間開銷，我測得的時間約為340ns。
![](https://i.imgur.com/NSYz6sw.png)
到這裡就能正確進行效能分析的實驗，然而儲存Fibonacci數列的資料型態為`long long`，只能儲存64位元的資料，因此F~92~之後的數值會產生overflow，於是接下來實作可以儲存任意精度的數值系統（Big Num）

## 大數運算
由於計算Fibonacci數列只會用到正整數運算，所以接下來的數值系統實作中運算子（加減乘除）都是針對正整數做運算。

### 資料結構
為了能夠儲存任意精度，定義一個資料結構`bigN`，`unsigned int *d`指向配置的記憶體位置，`int size`紀錄使用了幾個`unsigned int`來儲存數值。
```c=
typedef struct bigN {
    unsigned int *d;
    int size;  // lenths of array d
} bigN;

```
### bigN_to_string
有了資料結構後，要使我們儲存的資料有意義，要可以將儲存的資料轉換為看得懂的數值，實作一個function將`bigN`轉換成`string`。
若一個`bigN`使用了x個位元儲存資料，最多可以換算成$\ulcorner log_{10}(2^{x})\urcorner$位數，
e.g. 若一個`bigN`使用了8個位元儲存資料，最多可以儲存$2^{8}-1=255$也就是$\ulcorner log_{10}(255)\urcorner$ = 3位數。

```c=
char *bigN_to_string(bigN *src)
{
    // log10(x) = log2(x) / log2(10) ~= log2(x) / 3.322
    size_t len = (8 * sizeof(int) * src->size) / 3 + 2;
    char *s = (char *) kmalloc(len, GFP_KERNEL);
    char *p = s;

    memset(s, '0', len - 1);
    s[len - 1] = '\0';
    for (int i = src->size - 1; i >= 0; i--) {
        for (unsigned int mask = 1U << 31; mask; mask >>= 1) {
            /* binary -> decimal string */
            int carry = ((mask & src->d[i]) != 0);
            for (int j = len - 2; j >= 0; j--) {
                s[j] += s[j] - '0' + carry;  // double it
                carry = (s[j] > '9');
                if (carry)
                    s[j] -= 10;
            }
        }
    }
    // skip leading zero
    while (p[0] == '0' && p[1] != '\0') {
        p++;
    }
    memmove(s, p, strlen(p) + 1);

    return s;
}

```
二進位轉十進位的時候，使用一個`mask`一一取出most sinificant bit，取出下一個bit的時候要將之前的數值乘2才能正確解讀數值，e.g. 二進位數值1101 取出第一個bit 1，此時string儲存1，取出第二個bit 1，此時string應儲存$3 (1*2+1)$，取出第三個bit 0，此時string應儲存$6(3*2+0)$，取出第四個bit 1，此時string應儲存$13(6*2+1)$。
### bigN初始化
由於`bigN`是儲存記憶體位置，故需要搭配使用`bigNinit`函式配置記憶體位置以及數值。
```c=
bigN *bigNinit(unsigned int value)
{
    bigN *new = kmalloc(sizeof(bigN), GFP_KERNEL);
    new->d = kmalloc(sizeof(unsigned int), GFP_KERNEL);
    new->size = 1;
    new->d[0] = value;
    return new;
}
```
`value`為儲存的數值。

### 加法與減法
兩個`bigN`相加時有可能進位，故要先配置一個大小為`newsize`的記憶體位置來避免overflow。
實作兩個`uint32_t`相加的時候，可以用一個小技巧，用一個`uint64_t`來儲存結果，再使用mask跟位元移位來得到正確的32位元數值與它的進位。
```c=
void bigN_add(bigN *a, bigN *b, bigN *res)
{
    int newsize = MAX(a->size, b->size) + 1;  // To avoid overflow
    // printk("new size is %d",newsize);
    uint32_t *result = kmalloc(newsize * sizeof(uint32_t), GFP_KERNEL);

    memset(result, 0, sizeof(*result));

    uint64_t l = 0;
    for (int i = 0; i < newsize; i++) {
        uint32_t A = (a->size) > i ? a->d[i] : 0;
        uint32_t B = (b->size) > i ? b->d[i] : 0;
        l += (uint64_t) A + B;
        result[i] = l & 0xFFFFFFFF;
        l = l >> 32;
    }
    kfree(res->d);
    // Check the actual size and assign to bigN c

    if (result[newsize - 1] == 0) {
        // printf("a\n");
        newsize--;
        res->d = krealloc(result, newsize * sizeof(uint32_t), GFP_KERNEL);
        res->size = newsize;
    } else {
        // printf("b\n");
        res->d = result;
        res->size = newsize;
    }

    return;
}
```
減法的實作也差不多。
```c=
static void bigN_sub(bigN *a, bigN *b, bigN *c)
{
    bigN_comp(a, b);
    int newsize = MAX(a->size, b->size);
    unsigned int *result = kmalloc(newsize * sizeof(unsigned int), GFP_KERNEL);
    memset(result, 0, sizeof(*result));
    kfree(c->d);
    c->d = result;
    c->size = newsize;
    long long int carry = 0;
    for (int i = 0; i < c->size; i++) {
        unsigned int A = (i < a->size) ? a->d[i] : 0;
        unsigned int B = (i < b->size) ? b->d[i] : 0;
        carry = (long long int) A - B - carry;
        if (carry < 0) {
            c->d[i] = carry + (1LL << 32);
            carry = 1;
        } else {
            c->d[i] = carry;
            carry = 0;
        }
    }
    bigN_resize(c);
}
```
### 乘法
目前採用最簡單的 long multiplication，就像手算乘法一樣疊加上去，輔助函式 `bigN_mul_add `負責將每一行的計算結果疊加上去。
```c=
static void bigN_mul(bigN *a, bigN *b, bigN *c)
{
    int newsize = (a->size) * (b->size) + 1;  // avoid overflow
    unsigned int *result = kmalloc(newsize * sizeof(unsigned int), GFP_KERNEL);
    memset(result, 0, sizeof(*result));
    kfree(c->d);
    c->d = result;
    c->size = newsize;
    uint64_t l;
    for (int i = 0; i < a->size; i++) {
        for (int j = 0; j < b->size; j++) {
            uint32_t A = (a->size) > i ? a->d[i] : 0;
            uint32_t B = (b->size) > j ? b->d[j] : 0;
            l = (uint64_t) A * (uint64_t) B;
            bigN_mul_add(c, i + j, l);
        }
    }
    bigN_resize(c);
}
```
```c=
static void bigN_mul_add(bigN *c, int offset, uint64_t l)
{
    uint64_t carry = 0;
    for (int i = offset; i < c->size; i++) {
        carry += c->d[i] + (l & 0xFFFFFFFF);
        c->d[i] = carry;
        carry >>= 32;
        l >>= 32;
        if (!l && !carry)  // done
            return;
    }
}
```
### big num其他輔助函式
釋放bigN記憶體。
```c=
static void bigN_free(bigN *a)
{
    kfree(a->d);
    kfree(a);
    return;
}
```
交換兩個bigN的數值。
```c=
static void bigN_swap(bigN *a, bigN *b)
{
    bigN tmp = *a;
    *a = *b;
    *b = tmp;
    return;
}
```
比較兩個bigN的數值，並返回A=大的，B=小的。
```c=
static void bigN_comp(bigN *a, bigN *b)
{
    if (a->size > b->size) {
        return;
    } else if (a->size < b->size) {
        bigN_swap(a, b);
    } else {  // a->size = b->size
        int i = a->size - 1;
        // compare value
        if (a->d[i] < b->d[i]) {
            bigN_swap(a, b);
        }
    }
}
```
做加法或乘法時為了避免overflow會多分配記憶體空間，`bigN_resize`可以調整記憶體空間為剛剛好。
```c=
static void bigN_resize(bigN *a)
{
    int i = a->size - 1;
    while (a->d[i] == 0) {
        i--;
    }
    a->d = krealloc(a->d, (i + 1) * sizeof(uint32_t), GFP_KERNEL);
    a->size = i + 1;
}
```
### 實作大數版本的Fibonacci數列
有了數值系統之後，就可以實作大數版本的Fibonacci數列，先實作一般的Fibonacci運算。時間複雜度為O(n)。
```c=
static bigN *bigNfib_sequence(long long k)
{
    /* FIXME: use clz/ctz and fast algorithms to speed up */
    bigN *a = bigNinit(0);
    bigN *b = bigNinit(1);
    bigN *c = bigNinit(1);
    for (int i = 2; i <= k; i++) {
        bigN_add(a, b, c);  // a + b = c
        bigN_swap(a, b);
        bigN_swap(b, c);
    }
    // bigN_copy(b,ans);
    bigN_free(a);
    bigN_free(c);
    return b;
}
```
如此一來便可以正確計算$F_{92}$之後的數值，試著計算第500項得到的數字與[The first 1001 Fibonacci Numbers](http://www.fullbooks.com/The-first-1001-Fibonacci-Numbers.html)相同。
```
Reading from /dev/fibonacci at offset 500, returned the sequence 
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125.
```
### 實作大數版本的Fibonacci數列 (Fast Doubling)
研讀[Calculating Fibonacci Numbers by Fast Doubling ](https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling)後了解到還有一種方法可以時間複雜度O(logn)來計算Fibonacci數列。
Fibonacci數列定義為
$$
F_{n}=F_{n-1}+F_{n-2}, \text{ where } F_{0}=0, F_{1}=1.
$$
<!--
將上述推導寫成矩陣的形式就會變成
$$
                \begin{pmatrix}
                    F_{n+1} \\ F_{n}
                \end{pmatrix}
                = 
                \begin{pmatrix}
                    1 & 1 \\
                    1 & 0
                \end{pmatrix}
                \begin{pmatrix}
                    F_{n} \\ F_{n-1}
                \end{pmatrix}
$$

則 $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ 就是所謂的 ==Q-matrix==，可進一步改寫為:
$$
                \begin{pmatrix}
                    F_{n+1} & F_{n} \\
                    F_{n} & F_{n-1}
                \end{pmatrix} = 
                \begin{pmatrix}
                    1 & 1 \\
                    1 & 0
                \end{pmatrix}
                \begin{pmatrix}
                    F_{n} & F_{n-1} \\
                    F_{n-1} & F_{n-2}
                \end{pmatrix}\\
                = 
                \begin{pmatrix}
                    1 & 1 \\
                    1 & 0
                \end{pmatrix}^{2}
                \begin{pmatrix}
                    F_{n-1} & F_{n-2} \\
                    F_{n-2} & F_{n-3}
                \end{pmatrix}\\
                =
                 \begin{pmatrix}
                    1 & 1 \\
                    1 & 0
                \end{pmatrix}^{n-1}
                \begin{pmatrix}
                    F_{2} & F_{1} \\
                    F_{1} & F_{0}
                \end{pmatrix}\\
                =\begin{pmatrix}
                    1 & 1 \\
                    1 & 0
                \end{pmatrix}^{n} =Q^{n}
$$
繼續整理:
$$
        \begin{split}
        \begin{bmatrix}
         F_{2n+1} \\
         F_{2n}  
        \end{bmatrix} &=
        \begin{bmatrix}
         1 & 1 \\
         1 & 0  
        \end{bmatrix}^{2n}
        \begin{bmatrix}
         1 \\
         0 
        \end{bmatrix}\\ \\ &=
        \begin{bmatrix}
         1 & 1 \\
         1 & 0  
        \end{bmatrix}^n
        \begin{bmatrix}
         1 & 1 \\
         1 & 0  
        \end{bmatrix}^n
        \begin{bmatrix}
         1 \\
         0 
        \end{bmatrix}\\ \\ &=
        \begin{bmatrix}
        F_{n+1} & F_{n} \\
        F_{n} & F_{n-1}  
        \end{bmatrix}
        \begin{bmatrix}
        F_{n+1} & F_{n} \\
        F_{n} & F_{n-1}  
        \end{bmatrix}
        \begin{bmatrix}
         1 \\
         0 
        \end{bmatrix}\\ \\ &=
        \begin{bmatrix}
         F_{n+1}^2 + F_{n}^2\\
         F_{n}F_{n+1} + F_{n-1}F_{n} 
        \end{bmatrix}
        \end{split}
$$
        
因此可得:
$$
            \begin{split}
            F(2k) &= F(k)[2F(k+1) - F(k)] \\
            F(2k+1) &= F(k+1)^2+F(k)^2
            \end{split}
$$
-->
![](https://i.imgur.com/iVr3HPM.png)

接下來實作大數版本的Fast Doubling。
```c=
static bigN *bigN_fib_fdoubling(unsigned int n)
{
    // The position of the highest bit of n.
    // So we need to loop `h` times to get the answer.
    // Example: n = (Dec)50 = (Bin)00110010, then h = 6.
    //                               ^ 6th bit from right side
    unsigned int h = 0;
    for (unsigned int i = n; i; ++h, i >>= 1)
        ;
    bigN *f0 = bigNinit(0);
    bigN *f1 = bigNinit(1);
    bigN *a = bigNinit(1);
    bigN *b = bigNinit(1);
    bigN *f2k = bigNinit(1);
    bigN *f2k1 = bigNinit(1);

    for (unsigned int mask = 1 << (h - 1); mask; mask >>= 1) {
        /* F(2k) = F(k) * [ 2 * F(k+1) – F(k) ] */
        bigN_add(f1, f1, a);   // a = 2f1
        bigN_sub(a, f0, b);    // b = 2f1-f0
        bigN_mul(f0, b, f2k);  // f(2k)
        /* F(2k+1) = F(k)^2 + F(k+1)^2 */
        bigN_mul(f0, f0, a);   // a = f(k)^2
        bigN_mul(f1, f1, b);   // b = f(k+1)^2
        bigN_add(a, b, f2k1);  // f(2k+1)
        if (mask & n) {
            bigN_copy(f2k1, f0);
            bigN_add(f2k, f2k1, f1);
        } else {
            bigN_copy(f2k, f0);
            bigN_copy(f2k1, f1);
        }
    }
    bigN_free(f1);
    bigN_free(a);
    bigN_free(b);
    bigN_free(f2k);
    bigN_free(f2k1);
    return f0;
}
```
重新測量可以看到運行時間大幅減少，Iterative方法時間複雜度為O(n)，Fast Doubling方法時間複雜度為O(logn)。
![](https://i.imgur.com/LmwTRH5.png)

這邊已經大幅降低計算Fibonacci數列的時間，接下來在Fast Doubling方法下繼續做最佳化。
### 考慮到硬體加速的手法
許多現代處理器提供 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令，可搭配上述 [Fast Doubling](https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling) 手法運用:
```c=
    //unsigned int h = 0;
    //for (unsigned int i = n; i; ++h, i >>= 1);
    unsigned int h=32-__builtin_clz(n);
```
這樣可以更求出leading 1 bit在右邊數來第幾個bit。
![](https://i.imgur.com/XsVog19.png)
因為這個運算在整個大數版本的Fast Doubling演算法中佔比很小，所以得到的加速很小。

### 使用左移運算取代加法
Fast Doubling運算中需要求出2f1的運算可以使用左移運算取代。
```c=
//bigN_add_op(f1, f1, a);
bigN_ls(f1,a);
```
```c=
void bigN_ls(bigN* a, bigN* b)
{
    uint32_t mask =1<<31;
    int size = a->size;
    int overflow = 0;
    overflow = ((a->d[size - 1]) & mask) != 0 ;
    if(b->size < size ){
        if (overflow){
            size++;
        }
        b->size = size;
        uint32_t *result = kmalloc(size * sizeof(uint32_t), GFP_KERNEL);
        uint64_t l = 0;
        for (int i = 0; i < size; i++) {
            uint32_t A = (a->size) > i ? a->d[i] : 0;
            l =  ((uint64_t)A << 1) + l;
            result[i] = l & 0xFFFFFFFF;
            l >>= 32; 
        }
        kfree(b->d);
        b->d = result;
    }
    else if((b->size == size) && overflow){
        if (overflow){
            size++;
        }
        b->size = size;
        uint32_t *result = kmalloc(size * sizeof(uint32_t), GFP_KERNEL);
        uint64_t l = 0;
        for (int i = 0; i < size; i++) {
            uint32_t A = (a->size) > i ? a->d[i] : 0;
            l =  ((uint64_t)A << 1) + l;
            result[i] = l & 0xFFFFFFFF;
            l >>= 32; 
        }
        kfree(b->d);
        b->d = result;
    }
    else
    {
        uint64_t l = 0;
        for (int i = 0; i < b->size; i++) {
            uint32_t A = (a->size) > i ? a->d[i] : 0;
            l =  ((uint64_t)A << 1) + l;
            b->d[i] = l & 0xFFFFFFFF;
            l >>= 32; 
        }
    }
}
```
![](https://i.imgur.com/b3W72O1.png)
紫色的線段使用上了左移運算以及硬體支援的clz運算，得到了更進一步的加速。
### 引入memory pool
原本的運算上都直接分配一個新的記憶體空間，將舊的記憶體空間釋放，頻繁的這樣操作導致效能下降。例如：
```c=
unsigned int *result = kmalloc(newsize * sizeof(unsigned int), GFP_KERNEL);
memset(result, 0, sizeof(*result));
kfree(c->d);
c->d = result;
```
所以我重新寫過所有的運算，如果非必要(例如值會溢位)，否則都寫入原本分配的記憶體空間。
並且使用新的資料結構加入memory pool的概念
```c=
typedef struct bigN_op {
    unsigned int *d;
    int capacity;
    int size;  // lenths of array d
} bigN_op;
```
一開始就分配比較大的陣列給資料，減少值會溢位的情況。capacity紀錄總共可以使用的陣列，size紀錄目前的資料需要幾個unsigned int來儲存。
![](https://i.imgur.com/LSXL7cS.png)
在計算比較小的(200)Fibonacci數列計算效率可以有 **50%** 的提昇。
![](https://i.imgur.com/pzxEB36.png)
在計算比較大的(1000)Fibonacci數列計算效率也有 **20%** 的提昇。
(因為Fast Doubling方法時間複雜度為O(logn)，數列越大提昇越有限)。
在Iterative方法中也是50%的提昇。
![](https://i.imgur.com/7N1YG3c.png)

