contributed by < laneser >
考慮以下對二個無號整數取平均值的程式碼:
改寫為
看到 a >> 1
就會直覺想到是結果相等於把 a
除以 2. 但會無條件捨去最後一個 bit.
因此 EXP1 應該就是彌補了 a
, b
都是無條件捨去的情況下,結果跟 (a + b) / 2
的差異。
也就是 EXP1 需要利用 a
, b
的最後一個 bit 產生一個彌補值,相當於 (a + b) / 2
跟 (a >> 1) + (b >> 1)
之間的差異。
所以可以列出 a
, b
最後一個 bit 跟我們期望的答案的真值表。
a lowest bit | b lowest bit | EXP1 result |
---|---|---|
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
那就很明顯是這兩個 bits 的 AND
結果。
所以答案就是 (a & 1) & (b & 1)
, 簡化為 a & b & 1
。
改寫為
題目要求只能用 AND
, OR
, XOR
三種 bitwise 運算子,也就意味著這三種方法跟 +
,-
有一定的關聯。只好求救 Google, 找到 Bitwise XORing two numbers results in sum or difference of the numbers, 提到
x + y = (x ^ y) + ((x & y) << 1)
, 這個等式就可以聯想到我們要求的答案是 (a + b) >> 1
, 所以將這個等式兩邊都除以 2, 也就是 bitwise 右移一位。(x + y) >> 1 = (x ^ y) >> 1 + (x & y)
, 這樣就跟我們要的答案非常接近了。EXP2
應該就是 a & b
, 而 EXP3
就是 a ^ b
.
嘗試解讀編譯器最佳化開啟的狀況,對應的組合語言輸出。
利用 gcc -S -O3 test1.c
可以得到每個 average 實作函式對應的組合語言輸出。
以下都移除 assembly directives, 因為那是給編譯器看的,按題目需求應該是專注於給 CPU 執行的指令 (instructions).
endbr64
根據 What does the endbr64 instruction actually do? 解釋為 End for branch 64 bit. 在後續的其他函式也都是一開始就執行這個指令,在這裡也可以解釋為 nop
, 沒有任何動作。
leal
這個指令是 load effactive address
的 64bits 版本,但常常用來取代 add
指令, What's the purpose of the LEA instruction? 可以理解為,為了支持高階語言的陣列功能,x86 指令集特別弄了這個,但被發現跟 add
有異曲同工之妙,但又比 add
好用。
總之在這裡,就意味著把傳進來的兩個參數 a
,b
, 分別放在 esi
,edi
這兩個暫存器內,直接加起來把結果存入 eax
暫存器。
shrl
很好理解,就是右移一個 bit. 把 eax
暫存器內容除以 2 的意思。
最後回傳值放在 eax
.
前兩行就是把 b-a
的結果放在 eax
, 再右移一個 bit. 最後加上 a
. 所以如果 b-a
的結果會 overflow, 那最後的結果也就不正確了。
第 4,7 行實作了 b >> 1
, 第 5,8 行實作了 a >> 1
, 而這兩個結果分別放在 eax
,edx
.
第 6,9 行實作了 a & b & 1
, 結果存放於 edi
.
最後 10,11 行把這三個結果加起來回傳。
(a & b) + ((a ^ b) >> 1)
前三行實作了 a & b
, a ^ b
, 分別放在 edi
,eax
.
接著再把 a ^ b
右移一個 bit.
最後加起來回傳。
include/linux/average.h
,探討其 Exponentially weighted moving average (EWMA) 實作,以及在 Linux 核心的應用先了解 EWMA 的定義:
\(S_t = \begin{cases} Y_0, & t = 0 \\ \alpha Y_t + (1 - \alpha) \cdot S_{t-1}, & t > 0 \end{cases}\)
average.h
定義了一個大 macro, 共有三個參數, 分別是
name
: 表示整個 macro 定義出來的一組 macro 以及 struct 的名稱。_percision
: 表示用多少個 bits 來表示內部儲存的小數部分。_weight_rcp
: 表示權重 \(\alpha\) 的倒數, \(\alpha=1 / weight\_rcp\)。接著就是拆解整個 macro 的每一部分:
表示這個 macro 會定義出一個 ewma_ 開頭, name
參數結尾的 struct, 內部只有一個 unsigned long internal.
在使用之前,需要先呼叫 ewma_##name##_init
這個 incline function.
會在 compiler 時期就檢查所有該檢查的參數,而真正的 code 只有 e->internal = 0
, 看來 linux kernel 傾向一切能夠在 compiler 時就能做的就盡量做,這樣可以最早發現問題,而且又確保了執行期的速度與正確性。
看到這裡我有個小疑問,難道這四行檢查碼會因為放在不同的 macro 當中而有所不同嗎?
看起來都一樣的程式為什麼要寫第二遍呢?
我想像中,只要寫一次,應該會在 compiler 時期就會發生錯誤警告了。
不過,做完檢查就只剩下一行, 也就是讀取值的時候直接把 internal
右移 _precision
這麼多個 bits 後回傳。
這個 macro 就是最主要的功能。
其中利用了 READ_ONCE
來讀取 e->internal
, 也利用 WRITE_ONCE
來寫入 e->internal
, 看來是為了避免在不同的 thread 當中存取所發生的問題。
另外 ilog2
函式看來也是個 macro 可以在 compiler time 就可以運算出 log2 的值。
算出 log2 的值就可以運用 bits 位移加速乘法以及除法運算。
為了避免 double evaluation, _preision
先指派給 precision
取值後再使用, macro 的世界都要小心翼翼的。
所以最後一行的意思是 (用 _val 取代 val << precision
)
e->internal = _val
e->internal = (internal*(_weight_rcp - 1) + _val)/_weight_rcp
探究這個 DECLARE_EWMA
在 linux kernel 當中的應用,最快的方法就是搜尋它被使用在哪裡。
以網路來說, 參考 sta_info.h 的註解說明, 這個是 average ACK signal 的意思, 在每次 ack 的時候都會更新一次.
Google 文章 說是用在估算 Round Trip Time (RTT), 相關資料在 RFC793 page 40 當中提到 Retransmission Timeout 需要動態被估算, 而且需要得到 RTT 這個資訊, 根據 這份簡報 提到
\[ \begin{align} EstimatedRTT = (1-g)(EstimatedRTT) + g(SampleRTT)\\ 0 ≤ g ≤ 1, usually\ g = .1\ or\ .2 \end{align} \]
這個公式就是 EWMA.
而 gpu 似乎是跟 DRM (Direct Rendering Manager) 有關.
改寫〈解讀計算機編碼〉一文的「不需要分支的設計」一節提供的程式碼 min,我們得到以下實作 (max):
既然是取比較大的值, 結果只會有兩種: a , b.
若是 a 比較大, 則結果應該類似 a ^ 0 = a, 若是 b 比較大, 結果應該類似 a ^ (a ^ b) = b.
所以 ((EXP4 & -(EXP5))
的結果應該會如下:
((EXP4 & -(EXP5)) = 0
((EXP4 & -(EXP5)) = (a ^ b)
這時可以想到 EXP4
應該是 a ^ b
, 而 -(EXP5)
應該如下:
-(EXP5) = 0b
使得 (a ^ b) & 0 = 0
-(EXP5) = 0xFFFFFFFF = -1
使得 (a ^ b) & 0xFFFFFFFF = (a ^ b)
因此 EXP5
就是 a < b
針對 32 位元無號/有號整數,撰寫同樣 branchless 的實作
不管 a , b 是否為 signed 或 unsigned, -(a < b)
的結果就是 signed int, 且為 0x000000 或者 0xFFFFFFFF 這兩種結果之一, 所以實作的方法是一樣的。
請在 Linux 核心原始程式碼中,找出更多類似 branchless 的實作手法。請善用 git log 檢索。
net/xfrm.h from commits
這裡的 if 是為了避免產生 u32 << 32 這種未定義的行為。
而且這次 commit 是從組合語言角度說明了 Branch savings: 1
.
Rework 64 bits shifts to avoid tests and branches - 但這個我真的看不懂
還有以前的一些紀錄在 git logs 裡面, 但目前的 linux kernel 似乎已經不存在了:
考慮以下 64 位元 GCD (greatest common divisor, 最大公因數) 求值函式:
改寫為以下等價實作:
在前幾個步驟都是根據 GCD 演算法,可以得到很好的理解。
就實作了兩個步驟:
這個步驟就是
3. if x, y are both even, \(gcd(x,y)=2*gcd(\frac{x}{2},\frac{y}{2})\)
在迴圈執行完畢的時候, !((u | v) & 1)
是 false, 意味著 (u | v)
的最後一個 bit 是 1, 也就是 u
或 v
其中一個是奇數. 或者兩者都是奇數。
而此時的 \(2^{shift}*gcd(u,v)\) 就是原本要求的 GCD。
接著的
以及
因為此時必定不會存在 u
, v
同時為偶數的狀況,所以其中一個是偶數就可以立刻把 2 這個非公因數
給剔除。
相當於演算法當中的
4. If x is even and y is odd, then \(gcd(x,y)=gcd(\frac{x}{2},y)\)
以及
5. If x is odd and y is even, then \(gcd(x,y)=gcd(x,\frac{y}{2})\)
最後迴圈中的
是利用輾轉相除法的原理,只是用了連續減法來找出相除的餘數結果。
輾轉相除法就是除到餘數為 0 就是答案。
最後一步 u = v
的時候, 就是餘數為 0 的時候,此時 uint64_t t = u - v
會讓 t
為 0, 然後被指派給 v
.
所以 COND
就是餘數 v
, 而 u
在這裡就是最後的那個最大公因數。
但要記得真正的答案是 \(2^{shift}*gcd(u,v)\) .
因此 RET
就是 u << shift
.
在 x86_64 上透過 __builtin_ctz 改寫 GCD,分析對效能的提升;
在理解了 __builtin_ctz
的意義後,顯然是針對
這樣的程式碼,可以直接等於
所以實作的程式碼為
可以連續呼叫後,計算耗費的時間來分析效能:
在我的環境中執行 1000000 次的結果為
大約快了 1.3 倍左右。
Linux 核心中也內建 GCD (而且還不只一種實作),例如
lib/math/gcd.c
,請解釋其實作手法和探討在核心內的應用場景。
lib/math/gcd.c 當中主要的 gcd 實作如下:
這段程式碼主要由 Zeng Zhaoxiu 所提的 commit 貢獻的.
他在這段 commit log 當中直接把 benchmark 的程式跟結果展示出來,比原本的速度快了很多。
提到了加速的主因,就是 %
這個求餘數在 CPU 指令集是用除法做的,即使是 x86 這樣的已經針對除法優化的 CPU, 用減法搭配檢查 2 的因數依舊快了 25%, 更別提 Alpha 或者 ARMv6 這種僅僅是利用 emulation code
來實作除法的 CPU. 加速效果更是明顯。
也提到了 __ffs
是利用 CPU 提供的指令,意義上等同 __builtin_ctz
的實作。
其中的 r & -r
讓我思考蠻久的,是把 r
跟 r
的二進位補數做 bitwise AND 運作,這會使得 r
僅保留從低位元數過來的第一個 1 bit,意義上就是 1 << __builtin_ctz(r)
.
剩下的部分就幾乎跟本次的測驗題目一樣了。
核心內對於 gcd 的應用場景
考慮以下程式碼:
改寫的程式碼如下:
其中第 9 行的作用是找出目前最低位元的 1,並紀錄到 t 變數。舉例來說,若目前 bitset 為 000101b,那 t 就會變成 000001b,接著就可以透過 XOR 把該位的 1 清掉,其他保留 (此為 XOR 的特性)。
請補完 EXP6
看到這裡剛好跟前一題在 linux kernel 中的 gcd 用到的 r & -r
好像。
所以就是 bitset & -bitset
.
舉出這樣的程式碼用在哪些真實案例中
Linux kernel gcd implement.
設計實驗,檢驗 ctz/clz 改寫的程式碼相較原本的實作有多少改進?應考慮到不同的 bitmap density;
執行結果
思考進一步的改進空間;
out[pos++] = (k << 6) + r;
來取代 out[pos++] = k * 64 + r;
也沒有比較快。閱讀 Data Structures in the Linux Kernel 並舉出 Linux 核心使用 bitmap 的案例;
以下是 LeetCode 166. Fraction to Recurring Decimal 的可能實作:
請補完
PPP = ? (表示式)
MMM = ? (巨集)
EEE = ? (表示式)
find
函式實作就像 Hash Map, 在 heads
當中用 key
去找到對應的 index
.
所以 int pos = find(heads, size, remainder);
當 pos >= 0
就是找到了循環的小數起點, 也就是之前出現過相同的餘數.
而 decimal
放的是之前算出來的餘數除法結果, 所以
就是要把非循環的數字放進 p, 直到之前找到的餘數為止, 所以 PPP
就跟 pos
這個數字有關, 這個迴圈應該要執行 pos
這麼多次, PPP
應該是 pos--
而 MMM(&node->link, EEE);
顯然就是沒找到的時候要建立 Hash Map, 此時就是把 &node->link
塞入 heads
這個 Hash Map, Hash function 就在 find
裡面的 int hash = key % size;
.
因此 MMM
就是 list_add
,
EEE
就是 &heads[remainder % size]
解釋上述程式碼運作原理,指出其中不足,並予以改進
fractionToDecimal
最不高興的就是只有 malloc
卻沒有 free
./* deal with negtive cases */
, 那麼 long long division = n / d;
就不會有負的問題
改為
decimal
, 而是直接輸出給結果, 找到重複的 reminder 的時候, 再來插入 (
跟 )
就好. 最後如下:
在 Linux 核心原始程式碼的 mm/ 目錄 (即記憶體管理) 中,找到特定整數比值 (即 fraction) 和 bitwise 操作的程式碼案例,予以探討和解說其應用場景
但這裡讓我學到 github 搜尋可以指定目錄, 像是搜尋 mm/ 目錄中的 fraction
alignof 是 GNU extension,以下是其可能的實作方式:
請補完上述程式碼,使得功能與 alignof 等價。
在只有定義一種 type t 的情況下, alignof
就是 t 的長度.
既然要算出 type t 的長度, 頭尾相減就是答案.
所以 M
表示的就是 type t 的變數: _h
,
而 X
表現的就是頭, 就是 0.
在 Linux 核心原始程式碼中找出 alignof 的使用案例 2 則,並針對其場景進行解說
__alignof__
找出 struct sockaddr
, 在定義 socket storage 的時候使用.__alignof__
強制在 compiler 時期就拒絕做出不合規格的 siginfo_t在 Linux 核心源使程式碼找出 ALIGN, ALIGN_DOWN, ALIGN_UP 等巨集,探討其實作機制和用途,並舉例探討 (可和上述第二點的案例重複)。思索能否對 Linux 核心提交貢獻,儘量共用相同的巨集
ALIGN, ALIGN_DOWN, ALIGN_UP 應該是在 align.h
考慮貌似簡單卻蘊含實作深度的 FizzBuzz 題目:
- 從 1 數到 n,如果是 3的倍數,印出 “Fizz”
- 如果是 5 的倍數,印出 “Buzz”
- 如果是 15 的倍數,印出 “FizzBuzz”
- 如果都不是,就印出數字本身
以下是利用 bitwise 和上述技巧實作的 FizzBuzz 程式碼: (bitwise.c)
作答區
KK1 = ? (變數名稱)
KK2 = ? (變數名稱)
KK3 = ? (表示式,不包含小括號)
按題意搭配 strncpy(fmt, &"FizzBuzz%u"[(9 >> div5) >> (KK3)], length);
length
應該
length
= 4length
= 4length
= 8length
= 2因此 KK1
給 div3
, KK2
給 div5
就會符合 length
的需求.
而 (9 >> div5) >> (KK3)
按需求則是
(9 >> div5) >> (KK3)
= 0(9 >> div5) >> (KK3)
= 4(9 >> div5) >> (KK3)
= 0(9 >> div5) >> (KK3)
= 8因此 9
要改為 8
, 然後 KK3
等於 div3 << 2
就會符合需求…
解釋上述程式運作原理並評估 naive.c 和 bitwise.c 效能落差
避免 stream I/O 帶來的影響,可將 printf 更換為 sprintf
分析 Faster remainders when the divisor is a constant: beating compilers and libdivide 一文的想法 (可參照同一篇網誌下方的評論),並設計另一種 bitmask,如「可被 3 整除則末位設為 1」「可被 5 整除則倒數第二位設定為 1」,然後再改寫 bitwise.c 程式碼,試圖運用更少的指令來實作出 branchless; 參照 fastmod: A header file for fast 32-bit division remainders on 64-bit hardware
研讀 The Fastest FizzBuzz Implementation 及其 Hacker News 討論,提出 throughput (吞吐量) 更高的 Fizzbuzz 實作
解析 Linux 核心原始程式碼 kernel/time/timekeeping.c 裡頭涉及到除法運算的機制,探討其快速除法的實作 (注意: 你可能要對照研讀 kernel/time/ 目錄的標頭檔和程式碼)
過程中,你可能會發現可貢獻到 Linux 核心的空間,請充分討論