contributed by < Risheng1128
>
1
延伸問題:
首先,討論以下程式碼
思考思路
low
的大小加上 high
到 low
之間距離的一半,因此可以得到一半的數字high
的大小,如以下程式碼
接著討論下一個程式碼
思考思路
a >> 1
和 b >> 1
分別為 a / 2
和 b / 2
,接著會發現如果只有 a >> 1 + b >> 1
,在某些情況下會有問題,例如: a = 3, b = 5
出來的結果不是 4
而是 3
1
時,兩數相加的時候 LSB 的位置會進位,但本題的範例是直接先都往右平移 1
,因此會把進位忽略掉,從這點可以推斷出 EXP1
是和進位有關,加上題目的提示,可以得到以下解答
EXP1 = a & b & 1
接下來是最後一種寫法
思考思路
EXP2
和 EXP3
都是 a
和 b
的某種運算 (OR
AND
XOR
)EXP2 = a & b
EXP3 = a ^ b
a + b = (a ^ b) + ((a & b) << 1)
的形式a + b
的寫法後平均就不難了,可以寫成以下的形式
(a + b)/2 = ((a ^ b) + ((a & b) << 1)) >> 1
→ (a & b) + ((a ^ b) >> 1)
參考 GCC Command Options ,裡面說明了 gcc 的各種最佳化及最佳化選項
採用以下的程式碼作為範例,希望可以探討編譯器不同優化產生的組合語言的差異
輸入命令 objdump -d -M att problem1.out > problem1.d
以下為各優化輸出的結果,由於只討論執行的指令並保持簡潔,這邊將地址的部份移除
-O0
優化-O0
: 不做優化
Do not optimize. This is the default.
首先會發現所有函式一開始都會有一樣的指令 endbr64
,參考 What does the endbr64 instruction actually do? ,可以得知 endbr64
算是一種安全機制,用來判斷跳躍的地址是否為合法的地址,一般可以視為 NOP
The ENDBRANCH (see Section 73 for details) is a new instruction that is used to mark valid jump target addresses of indirect calls and jumps in the program. This instruction opcode is selected to be one that is a NOP on legacy machines such that programs compiled with ENDBRANCH new instruction continue to function on old machines without the CET enforcement. On processors that support CET the ENDBRANCH is still a NOP and is primarily used as a marker instruction by the processor pipeline to detect control flow violations. The CPU implements a state machine that tracks indirect jmp and call instructions. When one of these instructions is seen, the state machine moves from IDLE to WAIT_FOR_ENDBRANCH state. In WAIT_FOR_ENDBRANCH state the next instruction in the program stream must be an ENDBRANCH. If an ENDBRANCH is not seen the processor causes a control protection exception (#CP), else the state machine moves back to IDLE state.
接著討論 line 10
可以參考 x86 Instruction Set Reference — SHR ,不過要注意參考文件是 intel syntax
,上述測試則是 AT&T syntax
SHR r/m32
: Unsigned divider/m32
by2
,1
time.
line 9
可以參考 x86 Instruction Set Reference — SUB ,指令如下所示
operation | src | dest |
---|---|---|
sub | -0x4(%rbp) | %eax |
dest = dest - src
line 15 16
可以參考 x86 Instruction Set Reference — AND ,指令如下所示
line | operation | src | dest |
---|---|---|---|
15 | and | -0x8(%rbp) | %eax |
16 | and | $0x1 | %eax |
dest = dest & src
-O1
優化
-O1
: Optimizing compilation takes somewhat more time, and a lot more memory for a large function.
With
-O
, the compiler tries to reduce code size and execution time, without performing any optimizations that take a great deal of compilation time.
可以發現 -O1
的程式比起 -O0
來的精簡許多,在 O0
時, a + b
是使用 ADD
執行,而 -O1
則是使用 LEA
作為算術運算使用, LEA
的說明可以參考 x86 Instruction Set Reference — LEA
從編譯結果看來, -O1
比起 -O0
省略多餘的 stack 運算,全部的指令都使用暫存器執行,最後將結果存到 %eax
回傳
-O2
優化
-O2: Optimize even more. GCC performs nearly all supported optimizations that do not involve a space-speed tradeoff. The compiler does not perform loop unrolling or function inlining when you specify
-O2. As compared to
-O, this option increases both compilation time and the performance of the generated code.
和 -O1
相比,兩者指令大致相同,但 -O2
在最後增加了指令 nopw 0x0(%rax,%rax,1)
,參考 What is the meaning of the data32 data32 nopw %cs:0x0(%rax,%rax,1) instruction in gcc inline asm? 後,得知加 NOP
的原因是為了 CPU pipeline 的最佳化,在 retq
後方增加沒有用的指令看起來像是浪費空間,但是這樣的操作可以讓 pipeline 直接執行而不需要清空再填滿,使執行速度上升
根據上述的程式碼,可以看到每段程式的 retq
後都會接上不同長度的 NOP
,這邊可以發現每次加上 NOP
的長度可以讓每段程式的起始地址對齊 16 bytes
另外發現一見特別的事,相較於 O1
優化,在 O2
產生 memory reordering 的現象
-O3
優化
-O3
: Optimize yet more.-O3
turns on all optimizations specified by-O2
and also turns on the-finline-functions
,-funit-at-a-time
and-frename-registers
options.
-O3
輸出結果-O3
和 -O2
的結果完全一樣,推論是程式碼不夠複雜,在 -O2
已經優化的差不多
EWMA (指數加權移動平均)是一種取平均的統計手法,並且使經過時間越久的歷史資料的權重也會越低,以下為 EWMA 的數學定義:
\(S_t = \left\{ \begin{array}{l} Y_0& t = 0 \\ \alpha Y_t + (1 - \alpha)\cdot S_{t-1}& t > 0 \\ \end{array} \right.\)
接著將上述的數學式展開,可以得到以下的結果
\(\begin{split} S_t &= \alpha Y_t + (1 - \alpha)\cdot S_{t-1} \\ &= \alpha Y_t + (1 - \alpha)(\alpha Y_{t-1} + (1 - \alpha)\cdot S_{t-2}) \\ &= \alpha Y_t + (1 - \alpha)(\alpha Y_{t-1} + (1 - \alpha)(\alpha Y_{t-2} + (1 - \alpha)\cdot S_{t-3})) \\ &= \alpha (Y_t + (1 - \alpha)Y_{t-1} + (1 - \alpha)^2Y_{t-2} + \ldots + (1 - \alpha)^kY_{t-k} + \ldots + Y_0) \end{split}\)
從結果可以得知第前 \(k\) 筆資料為 \((1 - \alpha)^kY_{t-k}\) 其加權為 \((1 - \alpha)^k\) 為指數的模樣,這也是為何這樣的手法被稱為 EWMA
To Do: 研讀中…
這邊歸納了在分析上述 Linux 核心原始程式碼時,不懂的巨集及函式
BUILD_BUG_ON
(位於 include/linux/build_bug.h)從註解的部份可以很清楚的知道, BUILD_BUG_ON
的功能主要是用來判斷是否中斷編譯,如果 condition
為 True
會中斷編譯,反之則會繼續進行編譯
__builtin_constant_p()
參考 Library Functions Manual __BUILTIN_CONSTANT_P(3) ,可以得知 __builtin_constant_p()
是用來決定 value 是否在編譯時期為 constant 的 GUN extension ,該函數也用到了所謂的 constant folding 優化技術
原文: The __builtin_constant_p() is a GNU extension for determining whether a value is known to be constant at compile time. The function is closely related to the concept of "constant folding" used by modern optimizing compilers.
如果 value
為 compile-time constant 的話, __builtin_constant_p()
回傳 1
,反之則回傳 0
BUILD_BUG_ON_NOT_POWER_OF_2()
可以得知 BUILD_BUG_ON_NOT_POWER_OF_2(n)
的功能是判斷 n
是否為 2
的次方,如果不是 2
的次方,則會中斷編譯,反之則是會繼續編譯
READ_ONCE()
及 WRITE_ONCE()
ilog2()
(位於 include/linux/log2.h)2
延伸問題:
首先,討論以下程式碼,程式目的為回傳比較大的值
思考思路
a
或 b
,首先看到回傳有一個 a ^
的過程,從老師給的參考連結 That XOR Trick ,發現以下 XOR 的特性
a ^ 0 = a
a ^ a ^ b = b
EXP4
和 -(EXP5)
經過 AND
後的結果
a
≥ b
,則 (EXP4) & -(EXP5) = 0
a
< b
,則 (EXP4) & -(EXP5) = a ^ b
EXP4
為 a
和 b
進行某種特別 bitwise 操作),可以先得出 EXP4
為 a ^ b
EXP4 = a ^ b
套回第 2
點的特性,可以得到更精簡的結果
a
≥ b
,則 EXP5 = 0
a
< b
,則 EXP5 = 1
EXP5 = a < b
EXP4 = a ^ b
EXP5 = a < b
無號數的實作和題目的程式碼相同,而有號數之間比較和無號數之間的比較相同,因此兩者的程式碼實作相同,如以下所示
如果是無號和有號的比較則需要特別注意,需要考慮到有號數會轉型成無號數,這邊參考了你所不知道的 C 語言: bitwise 操作,裡頭有更詳細的說明
在 Linux 中分別搜尋 branchless
及 branch-free
,以下為搜尋結果
上述程式碼看起來只是將 src
的資料複製到 dst
,從註解可以看到這樣的動作是要達到 branchless ,至於為什麼則還不清楚
3
延伸問題:
__builtin_ctz
改寫 GCD ,分析對效能的提升;首先分析以下程式碼,並回答 COND
及 RET
從老師附上的 GCD 演算法,讓我能更方便的拆解整個程式碼
- If both x and y are 0, gcd is zero gcd(0,0) = 0
- gcd(x,0) = x and gcd(0,y) = y because everything divides 0
上述敘述可以對應題目的程式碼
- If x and y are both even, gcd(x,y) = 2∗gcd(x/2,y/2) because 2 is a common divisor. Multiplication with 2 can be done with bitwise shift operator.
上述敘述表達如果兩數都是偶數的話,則可以先將公因數 2
提取出來,題目所對應的程式碼如下
- If x is even and y is odd, gcd(x,y) = gcd(x/2,y)
- On similar lines, if x is odd and y is even, then gcd(x,y) = gcd(x,y/2). It is because 2 is not a common divisor.
上述敘述則表達,如果兩數還有任一個是 2
的倍數的話,可以直接把該數的因數 2
除掉,且結果不會改變,對應的題目程式碼如下
最後則是輾轉相除法的實作,利用連續的減法直到餘數為 0
分析到這,大致已經了解整個程式邏輯,首先 COND
為結束迴圈的條件,從上述的第 2 行和第 6 行,可以看到以下的特性
u
< v
, 則 v -= u
u
≥ v
,則 v = u - v
由此可知 v
為每次迭代所產生的餘數,因此可以得知 COND = v
而 u
就是最大公因數,還要記得前面共同的公因數 2shift ,因此可以得知 RET = u << shift
__builtin_ctz
改寫 GCD參考 6.59 Other Built-in Functions Provided by GCC 裡有關於 __builtin_ctz()
的敘述,可以得知 __builtin_ctz()
回傳從 LSB 開始往左數,遇到第一個 1
bit 前一共有幾個 0
bit , x = 0
則是未定義的情況
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.
以下為改寫的 gcd 程式碼
接著可以開始分析兩者之間的效能
首先實作隨機產生 64 bit 無號數的程式碼
接著使用 gettime 計算時間,這邊新增以下的測試程式
接著由於在 Homework3 fibdrv
的環境設定裡,已經將 CPU 0
設定為待命,這邊的測試就由 CPU 0
執行,輸入命令 taskset 0x1 ./problem3.out > out
,以下為部份輸出結果
可以看到 gcd_ctz
明顯比 gcd
快了非常多,使用上述的第一筆資料做計算, gcd_ctz
約為 gcd
的 41.9528% ,提昇了將近 6 成的效能
接著使用 gnuplot 作圖
4
延伸問題:
ctz/clz
改寫的程式碼相較原本的實作有多少改進?應考慮到不同的 bitmap density;分析以下程式碼
思考思路
這題的思考主要是來自題目的提示
其中第 9 行的作用是找出目前最低位元的 1,並紀錄到 t 變數。
得知題目是要找到目前最低位元的 1
,接著參考老師給的連結 Introduction to Low Level Bit Hacks ,裡頭剛好有提到方法,如以下所示
Bit Hack #7. Isolate the rightmost 1-bit. y = x & (-x)
由上述特性,可以得到 EXP6 = bitset & -bitset
接著可以開始分析程式碼,最關鍵的部份如下
這邊使用 uint64_t bitmap[1] = 255
做測試
以下為結果,可以看到 255
為 1
的 bit 其位置都被儲存了起來,同時也可以得知,如果一個 bitmap 的 0
越多,則 improve
的執行會越快,呼應題目的敘述
若 bitmap 越鬆散 (即 1 越少),於是 improved 的效益就更高。
根據老師給的連結 bit array ,這邊可以找到一些應用
Bit arrays are used for priority queues, where the bit at index k is set if and only if k is in the queue; this data structure is used, for example, by the Linux kernel, and benefits strongly from a find-first-zero operation in hardware.
在 Linux kernel 搜尋 bitmap 後,可以找到一些和 bitmap 有關的檔案,其中有一個標頭檔都是 bitmap 的應用 ,位於 include/linux/bitmap.h ,以下節錄一些程式碼
5
延伸問題:
bool isNegative = numerator < 0 ^ denominator < 0;
搭配研讀 The simple math behind decimal-binary conversion algorithms參考166. Fraction to Recurring Decimal
首先,以下為題目用到儲存餘數的 linked list
程式碼主要架構是將所有的節點接在 hash table ,這樣在搜尋節點時速度較快
接著在每次迭代的時候會先找餘數是否已經重複,如以下程式碼,其中 pos
表示這是第幾位小數
如果沒有重複餘數的話,直接創一個資料並加在 hash table
最後附上完整的程式碼分析結果
首先發現判斷是否為負數的程式碼使用了 branch ,這邊的想法是不管怎麼樣都要使用正數轉換,不如就直接用絕對值的方式做修改,參考以前學員的筆記
接著是延伸問題有提示到的部份
判斷負號只要寫作
bool isNegative = numerator < 0 ^ denominator < 0;
最後就是記憶體釋放的問題,這邊實作了函式 free_ht()
用來釋放 hash table
接著修改函式 fractionToDecimal()
至於 result = malloc(size)
的部份,在主函式 main()
進行釋放記憶體的動作
以下為輸出結果,使用的範例參考 166. Fraction to Recurring Decimal
6
延伸問題:
__alignof__
的使用案例 2 則,並針對其場景進行解說ALIGN
, ALIGN_DOWN
, ALIGN_UP
等巨集,探討其實作機制和用途,並舉例探討 (可和上述第二點的案例重複)。思索能否對 Linux 核心提交貢獻,儘量共用相同的巨集首先解析以下的巨集
((struct { char c; t _h; } *)0
表示將地址 0x0
轉型成 (struct { char c; t _h; } *)
的型態(&((struct { char c; t _h; } *)0)->M)
表示取得成員 M
的地址(char *)(&((struct { char c; t _h; } *)0)->M)
將 M
的地址轉型成 (char *)
,目的在於等等計算時會以 1 為單位做計算(char *)(&((struct { char c; t _h; } *)0)->M) - (char *)X
最後減去 X
,得到 alignment這邊的話,M
很明顯不是 c
就是 _h
,由於這邊如果是選 c
的話, (char *)(&((struct { char c; t _h; } *)0)->c
這整串永遠都會是 0
,因此答案只能是 _h
得知了 M
為 _h
, 我們可以得知 (char *)(&((struct { char c; t _h; } *)0)->_h)
,為成員 _h
的地址,如果要計算需要的 alignment ,只要將該地址減去 struct
的 base address 即可,接著,可以看到巨集以 0x0
作為 struct
的 base address ,因此 X
可以合理推論為 0
M = _h
X = 0
7
延伸問題:
naive.c
和 bitwise.c
效能落差
printf
更換為 sprintf
bitwise.c
程式碼,試圖運用更少的指令來實作出 branchless;
過程中,你可能會發現可貢獻到 Linux 核心的空間,請充分討論
在解題之前可以先大致看一下整個程式運作的流程,首先就從變數 M3
M5
及函式 is_divisible()
開始
單從函式 is_divisible()
的實作,不好看出為什麼要這麼寫,不過搭配上 M3
和 M5
的宣告,我們可以得出題目是如何判斷是否整除
M3
和 M5
的手法一樣,都是用來分別判斷是否能被 3
和 5
整除
分析結果
M3
除以 3
表示以 3
為循環,而 +1
是為了要讓乘上 3
的倍數時會 overflow ,而產生一個很小的數M5
除以 5
表示以 5
為循環,而 +1
是為了要讓乘上 5
的倍數時會 overflow ,而產生一個很小的數is_divisible()
的實作手法,利用 overflow 判斷是否可以整除
M
為 M3
時,如果 n * M
產生 overflow 時,表示 n
可以被 3
整除,此時 n * M
是一個很小的數,因此 n * M <= M - 1
也就成立,回傳 true
M
為 M5
時,如果 n * M
產生 overflow 時,表示 n
可以被 5
整除,此時 n * M
是一個很小的數,因此 n * M <= M - 1
也就成立,回傳 true
false
接著可以來解題啦,開始分析 bitwise
的實作
發現這邊的題目有誤
從整個程式邏輯來看可以推論出 length
為需要印出的字串長度,加上題目的敘述對應函式的實作
整數格式字串 "%u" : 長度為 2 B "Fizz" 或 "Buzz" : 長度為 4 B "FizzBuzz" : 長度為 8 B
可以間單歸類出下面的表格
div3 |
div5 |
length (bytes) |
(8 >> div5) >> (KK3) |
---|---|---|---|
0 | 0 | 2 | 8 |
0 | 1 | 4 | 4 |
1 | 0 | 4 | 0 |
1 | 1 | 8 | 0 |
有了以上表格可以得到題目的答案
KK1
= div3
KK2
= div5
KK3
= div3 << 2
但經過觀察後,發現 KK1
和 KK2
對調也是可行的