contributed by < 93i7xo2
>
Source: J06: fibdrv
追蹤 fibdrv 分支 - bignum。其中最複雜的邏輯應該是將數個位元組轉換至不同進制的字串輸出 apm_get_str
,有了這個函式,數值就能以位元組而非字串形式儲存。
fibonacci.c
要了解 fibonacci.c
的 Fast-doubling 實作方式,從一開始得到的關係式開始:
根據 Fibonacci 數列原始定義 F(0) = 0, F(1) = 1, F(2) = 1
,對應的虛擬碼如下:
可分成 4-6、7-9 行兩部份,前者作用為 ,後者為 。第一次迴圈由於一開始 a = 0; b = 1;
的關係,第 4-5 行沒有作用,結果會是 a = 1; b = 1;
,最後返回 a
,相當於從 開始進行 Fast-doubling。
而 bignum/fibonacci.c
實作不同於上方虛擬碼,少了減法,好處是擴展成大數運算只需要實作加法部份。如果從整理前的關係式開始推導:
以 代入
可得關係式:
對應的實作如下:
由於一開始的返回值 a1
已是 ,迴圈數相較於先前的虛擬碼少一。
接著實作在 fibdrv.c
運作時,透過 sysfs interface 切換 fib_sequence 對應的實作 (參考 bakudr18 fib_exec
的作法)
為了測量 user space 及 kernel space 所花費的時間,分別於:
client.c
加入 clock_gettime
量測在 user space 經過的時間
kernel space 以 ktime
紀錄計算時間,並新增 /sys/kernel/fibdrv/time
用以回傳時間
snprintf(3)
If the output was truncated due to this limit then the return value is the number of characters (excluding the terminating null byte) which would have been written to the final string if enough space had been available. Thus, a return value of size or more means that the output was truncated.
KYWeng 建議使用 scnprintf
取代 snprintf
。簡單的說,snprintf
返回值不一定是實際寫入的位元數,而是預期寫入的位元數,在不超過 buffer 大小情況下沒問題,在靠近邊界使用容易造成誤用,即使在 btrfs commit 還是可見這樣的討論。
用 utime - ktime 就能得到 kernel to user 和 user to kernel 的時間。
ktime
也是透過 sysfs interface 存取
測試兩種實作效能差異,實驗數據已使用下方統計方法去除極值,但不排除其他干擾效能分析的因素。能看到 fast doubling 效能上的優勢,在計算越後面的項差異越明顯。
若對母體 進行區間估計。在母體 已知的情況下,樣本平均 ,以區間形式來估計母體 ,特定信心水準的信賴區間為:
而在 未知的情況下用樣本標準差 代替。應該用 t-distribution,也就是:
若以 95% 信賴區間作為去除離群值的方法,來求樣本的 trimmed mean,參考 4ce43c4 改寫,原本保留 內數據的作法應該改為下方:
目前尚未找到使用 C.I. 作為 trimmed mean 的實例
實際做圖,細看 fibonacci 序列較小的數值會發現有些斷點,這是因為數值小運算快,量測精度不夠的情況下即使測量次數夠多,數據不會呈現理想的常態分佈,例如 [20, 20, 20, ..., 21, 21]
,去除離群值後只剩下空陣列無法取得平均,解法是實作大數運算後拉大 fibonacci 序列範圍,縮小圖上的斷點。
排除干擾的方法參照 KYG-yaya573142
isolcpus=7
)scaling_governor
固定運作頻率整合上述功能到 Makefile 裡:
並在 scripts/driver.py
內以統計方法去除極值。
Python 是最廣為人知有實作大數運算的工具,使用了多種方法來增進效能,以下就 Python 的實作 cpython 3.11 (commit a0bd9e
) 的 longobject.c 進行加乘法運算的 trace。預期目標:
讓 python 產生必須的 header file
執行完上述指令產生 pyconfig.h
,如果 IntelliSense 沒有識別到該檔,參考 IntelliSense for cross-compiling 設定c_cpp_properties.json
內的includePath
PyObject_VAR_HEAD
: 儲存 reference count、ob_size 的結構
ob_size
: ob_digit[]
長度,<0
表示 ob_digit
的值為負數。ob_digit
: 用以儲存無號整數,保留前面 1 位用做緩衝用於運算,若 digit
型態為 int16_t
那實際上只有 15 bits 可用長度為 0 的陣列是 GNU C extension - Arrays of Length Zero 的用法,作為 variable-length object 的 header,在 C90 不支援的情況下以長度為 1 的陣列存在,雖然結構上的大小有變,但使用上並無異。
In the absence of the zero-length array extension, in ISO C90 the contents array in the example above would typically be declared to have a single element. Unlike a zero-length array which only contributes to the size of the enclosing structure for the purposes of alignment, a one-element array always occupies at least as much space as a single object of the type. Although using one-element arrays this way is discouraged, GCC handles accesses to trailing one-element array members analogously to zero-length arrays.
為了避開長度為 1 的陣列造成 sizeof
無法取得預期的結構大小,使用 __builtin_offsetof
k_mul
)cpython 以 Karatsuba algorithm 作為乘法運算的基礎。轉貼 wiki 部份原理:
一開始假設 為 位以 為基底的數字, 且 ,可改寫如下:
接著乘積 可表示為
以上共 4 次乘法運算,Karatsuba 發現透過將 改寫成
可將乘法運算降低至3次。但 或是 都有大於或等於 的可能性,計算乘績前得先用 位儲存,於是繼續改寫
這樣的好處是 或是 均落在 ,我們可將 sign 分離出來個別處理,等同先做兩個 位的正數乘法再加上 sign,最重要的是結合成 只剩加法。
但 cpython 採取的是式 (1),採用 位儲存結果,並忽略各項:、、 加減造成的 overflow/underflow,理由很簡單,加減運算就像在輪盤上轉圈,反正最後出來一定是正確的值。
乘法實作分為
k_mul
:使用 Karatsuba,視情況退化成 x_mul
,也是最先呼叫的乘法函式。x_mul
:小學乘法上述的 在實作對應到 ,位數較小的一方為 。在進行 Karatsuba 計算前有一小段程式用來判斷是否退化成 x_mul
在 a=b
或是 a!=b
的情況下,a
的 ob_size
必須分別大於 140/70 才會進行 Karatsuba。假設 digit
為 uint16_t
,ob_size=71
,符合條件的數最小為 ,所以實際上用到的大多是 x_mul
。
之後就是一系列相關的函式
k_lopsided_mul
: 平衡版的 Karatsubakmul_split
: 指定切割位置,將 拆成低位和高位兩數v_iadd
/v_isub
: 輸入兩數,將另一數相加/相減至另一數上long_normalize
: 以線性從 MSD (Most significant digit) 掃描至 LSD,調整 ob_size
,但不釋放多餘記憶體,ob_size
會大於實際上所需通常是新物件預留給計算結果足大的空間所致。k_lopsided_mul
當 a、b 兩數大小差距懸殊,Karatsuba 切割出來的 ah = 0
,這樣的情況下進行計算無法得到實質上的效益。於是平衡版的 Karatsuba - k_lopsided_mul
因應而生,作法是將以較小的那方大小作為單位大小切割另一數,逐一將兩數以 Karatsuba 計算並累加。
v_iadd
& v_isub
由於 digit
設計上保留最前面的 MSB 作為 carry/borrow 的暫存,sign 在 size,倘若計算兩正數,則不必判斷兩數大小間接判斷是否 overflow/underflow,而是將最前面的 1 bit 直接傳遞下去,省去分支。v_iadd
、v_isub
則是採用上述作法,實作兩正數的一般小學加減法計算。
以 v_isub
發生借位時為例,假設 digit
宣告為 8 bit,x, y
為 digit 型態,儲存數字最大為 7 bit,計算 x - y
。發生借位時可將補上的 視為兩個 ,一個用來計算,一個代表 borrow 發生。
同理, v_iadd
發生進位時為,MSB 為 1。
實作如下
類似的函式還有 x_add
,差別如下
x_add
: 兩數相加,返回儲存結果的新物件v_iadd/v_isub
: 將另一數相加/相減至另一數上,不產生新物件,返回 carry/borrowx_mul
)a!=b
時,執行傳統的乘法運算,將 b
逐一乘上 a
的每一 digit
累加至 z
a==b
時,採取 Multiprecision Squaring。原理是透過觀察 a * a
有相同 partial sum,且在奇數欄有次方項出現,從而減少計算次數,最終減少約一半的乘法。
a
(n-digit),所需乘法
不了解 cpython 是如何管理記憶體管理的情況下,先以 malloc
創立 bn
物件,實測結果顯示效能劣於 bignum。
模仿 x_add
進位的方式,實作一個將以 10 除後的餘數傳遞至前一個 digit
的 10 進制轉換函式,每個 10 進位數值獨自佔用一個 digit
。理論上可顯示至 位。
fibdrv
大數運算將 cpython 整合進 fibdrv。
由於 assert()
和 BUG_ON()
功能相反,assert()
是條件不成立才 core dump,BUG_ON
是條件成立就 kernel panic,因此裡面的條件要改寫成相反的。
編譯時發現無法處理浮點運算,依據 I09 - kcalc 的指示改用定點數:
使用 __uint128_t
處理兩個 64 位元整數的運算,但無法編譯:
原因是 kernel 並不會用到 libgcc,所以要改寫防止編譯器呼叫到 libgcc 裡的函式。於是將 0.3010 拆成 2 個數先除後乘:
由於sysfs 分配的 buffer 大小只有 PAGE_SIZE,無法顯示 PAGE_SIZE
(4096) 位以後的數字
sysfs allocates a buffer of size (PAGE_SIZE) and passes it to the method.
最終的實作放在 fibdrv,fibonacci number 可透過以下方式讀取,計算很快,慢的是轉換成 10 進位顯示:
client.c
使用 read()
讀取字串,sz
是字串大小
修改測試文件 expected.txt
使其涵蓋到更大的數字