contributed by < cwl0429
>
1
觀察下列程式碼
a >> 1
和 b >> 1
的功用都是將其除 2,此時會遇到最低位元遺失問題AND
,接著和 1 作 AND
,便可取得遺失的位元,因此 EXP1
為 a & b & 1
再觀察改寫後的程式碼,發現完全想不到該如何下手,於是嘗試用湊數字的方式,最後得出:
EXP2
為 a & b
EXP3
為 a ^ b
後來,參照了 laneser 的筆記,得知其實 x + y = (x ^ y) + ((x & y) << 1)
,而 (x + y) / 2
就等於 ((x ^ y) + ((x & y) << 1)) >> 1
也就是 (x & y) + ((x ^ y) >> 1)
因此得出:
EXP2
為 a & b
EXP3
為 a ^ b
先放一張來自 x64 文件的圖片,方便檢視暫存器的大小
接著嘗試理解下列四種 average 的組合語言,使用 gcc -S 1-1.c -O3 -fno-asynchronous-unwind-tables
生成
-O3
開啟編譯器最佳化第四層-fno-asynchronous-unwind-tables
過濾不必要的 .cfi
根據 Introduction to the leal instruction 的描述
Load effective address: leal S,D # D<–&S, where D must be a register, and S is a Memory operand.
leal looks like a mov instr, but does not access Memory. Instead, it takes advantage of the addressing circuitry and uses it to do arithmetic (as opposed to generating multiple arithmetic instructions to do arithmetic).
(ex) if edx holds the value of x:
leal (%eax),%ecx # R[%ecx]<–&(M[R[%eax]])# this moves the value stored in %eax to %ecx
The key is that the address of (M[ at address x ]) is x, so this is moving the value stored in %eax to %ecx; there is no memory access in this instruction's execution.
leal
會將 (%rdi,%rsi)
的值放至 %eax
,其間沒有 memory access 發生shrl
將 %eax
右移一位元,達成除 2 的效果movl
將 high
存入 %eax
subl
使 %eax
減 low
後,將 %eax
往右移一個 bitaddl
將結果相加並存放於 %eax
x
及 y
用 movl
讀至 %eax
及 %edx
andl
及 shrl
%edx
, %edi
及 %eax
相加,存放在 %eax
a
存入 %eax
,此時 %edi
及 %eax
為 a %esi
為 bandl
及 xorl
%eax
右移a & b
結果加至 eax
TODO..
2
觀察題目,若 a 較大,則需 return a ^ 0
才能成立,反之則需要 return a ^ (a ^ b)
才能回傳 b
到此根據老師的提示,便可猜出 EXP4
應為 a ^ b
剩下 EXP5
要決定回傳 a ^ 0
還是 a ^ (a ^ b)
a ^ 0
a ^ ((a ^ b) & 0x0)
a ^ (a ^ b)
a ^ ((a ^ b) & 0xFFFFFFFF)
所以得出 EXP5
為 a < b
無號數版本能和有號數幾乎一樣,更改回傳型態及參數型態即可
在 drivers/gpu/drm/radeon/r600_blit.c
Replace int2float() with an optimized version. We use
__fls() to find the most significant bit. Using that, the
loop can be avoided. A second trick is to use the
behaviour of the rotate instructions to expand
the range of the unsigned int to float
conversion to the full 32 bits in a branchless way.The routine is now exact up to 2^24. Above that, we truncate which is equivalent to rounding towards zero.
Signed-off-by: Steven Fuerst svfuerst@gmail.com
這份 commit 使用 branchless 的技巧優化了 int2float
主要優化的位置在第 12 行
新的 int2float
利用 __fls
找到 msb
的位置,再利用 ror
rotate 到正確位置,使我們不需判斷是否低於 2 ^ 24
3
GCD 演算法
參考老師提供的 GCD 演算法,這段程式碼實作了 1. 及 2. ,也就是 gcd(0, 0), gcd(x, 0) 及 gcd(0, y) 的情況
這是 3. 的情況,當二數的最低位元皆為 0 時,便將二數都除 2 並且紀錄除的次數,也就是 shift
的數值
這是 4. 的情況,當 x 為偶數時,gcd(x ,y) = gcd(x / 2, y)
最後這段則是 5. 的情況及 GCD 的原始算法
這邊需要找出 COND
及 RET
為何,觀察 COND
,得知其作用為中止 while 的判斷式,那根據 GCD
的原始定義,當兩數相減至其中一數為 0 時則中止,而且得知
COND
為 v
RET
需要回傳二數中剩餘非 0 的數,也就是 u
,但要注意在前面的 shift
代表了二數整除於 2 多少次數,所以需要將 u
左移 shift
次RET
為 u << shift
Built-in Function: int __builtin_ctz (unsigned int x)
Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined. 取自GNU
官方網站
__buildin_ctz
能取得 unsigned int x
從最低位元算起的連續 0-bits 個數,再回頭看 gcd_64
程式碼,得知主要想改善的部份為:
於是將相關操作改成 __buildin_ctz
後,得到以下實作:
接著利用 perf 進行效能測試
用亂數進行測試, N 的大小為 10000
使用以下命令進行測試
perf stat --repeat 10 ./1-3
gdb64
gdb64_ctz
可看出 ctz 的版本約快了 1.8910 倍
研究 ffs
的用途
ffs
— find first set bit in word
得知 ffs
能找到從右邊數起的第一個 1 位置,再根據維基百科的解釋, ffs
和之前題目用到的 ctz
的關係能用數學式子表示
在 x 不等於 0 的情況下
舉例來說, x = 0x11000000
則 ctz(x) = 6
而 ffs(x) = 7
但實際在 trace 此函式時,若是根據上述的定義,這個函式有機會進入無窮迴圈,才發現 __ffs
並不等於 ffs
於是重新翻了資料,找到 __ffs
實際定義的地方 asm-generic/bitops/__ffs.h
因此 __ffs
和 ctz
會回傳一樣的結果
另一個需要注意的地方是 r & -r
會保留從右往左數第一個為 1 的位元,其餘位元皆設定為 0
有趣的是,若將
r & -r
取 ,其實就會是ctz(r)
的結果
也學到教訓,找資料請盡量找第一手資料
解決上述兩點後,能觀察到這個版本的 GCD
和我們的版本差異為使用了 __ffs
進行加速,演算法相同
接著來探討 lib/math/gcd.c 實際的應用情境
利用 grep -r "#include <linux/gcd.h>"
列出有哪些檔案使用了 lib/math/gcd.c
,發現在 sound, net, drivers 等等都有用到 gcd,這邊我嘗試理解 linux/sound/soc/codecs/arizona.c
內 gcd 的用途
觀察目錄,發現 arizona.c
和音訊解碼有關