Optimizing Code

進入主題之前 | 專門術語 | 分析程式 | 32-bit 程式碼 | Alignment | 存取記憶體 | Opcode Prefixes| 運算元長度 |累加器 | Has Intel Gone RISC? | Pipeline | Pentium - Dual Pipelines

　

進入主題之前

在一頭栽入想要最佳化的程式碼之前,先確定幾件事情。首先,確定你有一個已經用某種高等語言寫好的有效率演算法。請記住,讓程式變快的,是演算法本身,最快的程式,並不是一個最佳化過的組合語言程式碼,但演算法不佳的程式。那些時常被執行的程式碼,尤其是程式當中被稱為"main loop"主迴圈的部份,才是我們要最佳化的重點,不要讓最佳化那些只被執行一次的程式碼成為我們的負擔（除非那些程式碼是非常耗時的）,因為實際上,程式速度的提昇,大都來自於主迴圈中那些被最佳化過後的程式碼。況且最佳化程式碼比起普通的寫程式,是很花費心思,時間和耐心的一件苦差事,所以只要在你必須去最佳化程式碼,以求得較佳程式效率的時候,才去做最佳化的工作。

專門術語

現在來討論一下在最佳化程式碼的過程中,一些常被提到的術語。首先,電腦有兩種cache : L1 cache and L2 cache。最佳化中很重要的一點就是你必須確定你有利用到這些cache的優點,尤其是L1 cache。這可能是相當困難的一件事,而另一種比較簡單的就是pipeline(管線)最佳化。486的CPU有一個pipeline,Pentium有兩個pipeline,但是如果要pipeline發揮速度的話,要依照一定的程序來做。現在有相當多的程式寫作技巧能夠做非常快的計算,例如說求絕對值...等等,因此從現在開始,我們將把衡量程式速度的單從毫秒(ms)換成clock cycle。一個clock cycle是一個處理器基本的時間單位,每個處理器因其速度不同,clock cycle的長度也會有差異。

1 clock cycle length = 1000/ Mhz nanoseconds

所以clock cycle的長度在一個 Pentium 100上是 10 ns,在Pentium Pro 200上是5 ns,依此類推。

分析程式

Intel CPU從Pentium以後有極佳的分析功能。Pentium以上的CPU都有一個 64-bit MSR ( Model Specific Register )用來計算從開機到現在經過了多少個clock。因此我們可以不用藉助外加的硬體來精確記算程式執行的時間,這真是一件相當完美的事。在執行了 RDTSC 指令後,現在的clock數目會存到以EDX:EAX 表示的 64 bit 值內( 高位在 EDX,低位在 EAX ),所以只要執行一個RDTSC,把 EAX 的值存起來( 不要管EDX,除非程式會跑上好幾年 )然後跑帶測的程式碼,再執行一個 RDTSC ,把新得到的 EAX 值減去舊的 EAX 值,就可以得到程式所花費的 clock 數目( 會有很小的誤差,大概是 12-20 個clock )

下面是一個例子

ITER EQU 10                                       ; number of iterations
OVERHEAD EQU 15                          ; 15 for Pentium, 17 for Pentium MMX

RDTSC MACRO                                  ; define RDTSC instruction
DB 0FH,31H
ENDM

.DATA

ALIGN 4
COUNTER DD 0                                 ; loop counter
TICS DD 0                                           ; temporary storage of clock
RESULTLIST DD ITER DUP (0)         ; list of test results

.CODE
BEGIN: MOV [COUNTER],0              ; reset loop counter

TESTLOOP:                                         ; test loop
;**************** Do any initializations here: ******
FINIT
;**************** End of initializations *************
    
RDTSC                                                ; read clock counter
MOV [TICS],EAX                               ; save count
CLD                                                     ; non-pairable filler

REPT 8
NOP                                                     ; eight NOP's to avoid shadowing effect
ENDM

;**************** Put instructions to test here: ************************
FLDPI                                                  ; this is only an example
FSQRT
RCR EBX,10
FSTP ST
;********************* End of instructions to test ************************

CLC                                                      ; non-pairable filler with shadow
RDTSC                                                  ; read counter again
SUB EAX,[TICS]                                  ; compute difference
SUB EAX,OVERHEAD                        ; subtract the clock cycles used by fillers etc
MOV EDX,[COUNTER]                       ; loop counter
MOV [RESULTLIST][EDX],EAX         ; store result in table
ADD EDX,TYPE RESULTLIST            ; increment counter
MOV [COUNTER],EDX                       ; store counter
CMP EDX,ITER * (TYPE RESULTLIST)
JB TESTLOOP                                      ; repeat ITER times

; insert here code to read out the values in RESULTLIST

32-bit 程式碼

如果你不是採用 32-bit 的程式碼,那你現在最好趕快採用.16-bit 的程式碼相當的老舊,除非你是在寫切換真實模式到保護模式的程式。Pentium以上的CPU都是特別為 32-bit 程式碼設計的,而不是 16-bit 。32-bit 的程式碼對Pentium以上CPU而言,會得到比 16-bit 還要好的效率。

Alignment

Intel處理器的設計是以 dword 為單位來存取記憶體。所以在存取哪些不是 4的倍數記憶體位址的時候,會造成一些延遲。以組合語言為例,用 ALIGN 指令,像是 ALIGN 4 會強制所有資料( words,dwords,structs 等等)的起始位址都是4的倍數。最佳的 alignment 我想是 16 bytes,這是Pentium和Pentium Pro的最佳值,而且沒有嚴重的空間浪費。大部份的 C/C++ 編譯器都有設定 alignment大小的選項。alignment 是一個相當好的最佳化,因為你根本不用去改寫程式碼,然而,對於資料長度的控制還是要繼續進行的。

底下是各種資料長度和其最佳的 alignment 值

operand size	Pentium (MMX)	PPro and PII
1 (byte)	1	1
2 (word)	addr MOD 4 < 3	2
4 (dword)	4	4
6 (fword)	4	8
8 (qword)	8	8
10 (tbyte)	8	16

存取記憶體

當讀寫記憶體的時候,用 dword 為單位存取,可以得到最快的速度。

Opcode Prefixes

opcode 只是一些處理器要解碼的16進位數字。Intel為了要使新的處理器相容舊的指令集,就讓一些沒有意義的 opcode 代表 prefix,來分別新舊指令集,像0x66,0x0F 就是 prefixed opcode,這種特殊的解碼系統叫做 opcode prefixing。prefixed opcode 需要多一個clock來執行,因此要儘少使用。

運算元長度

在真實模式下,運算元的長度預定是 16-bit,所以 MOV BX, DX 的 opcode 是0x89D3, MOV EBX, EDX 的 opcode 是 0x6689D3,加上 0x66 的 prefix 來分別這兩種指令。

但在保護模式下,運算元的長度預定是 32-bit,MOV EBX,EDX 的 opcode 就不需要prefix,而 16-bit 的MOV BX,DX 就需要 prefix。

0Fh Prefix

以0Fh開頭的 opcode 會花費較多的 clock,要儘量少使用,比較常見的有:

MOVZX,MOVSX, PUSH FS, POP FS, PUSH GS, POP GS, LFS, LGS, LSS, SETcc, BT,BTC, BTR, BTS, BSF, BSR, SHLD, SHRD, IMUL reg,reg/mem

這些指令在 Pentium 上只能用 U-pipe 執行,所以較慢。

累加器

因為 8086 的設計者認為 AX 的使用較為頻繁,所以他們給了那些用到 AX 的指令較短的 opcode ,例如說 MOV,ADD。在古老的 8086 上,使用 AX 會比使用其他的暫存器來的快。但對現在的CPU由言,使用哪一個暫存器的速度都是一樣的,只不過使用 AX/EAX 的程式碼會少幾個 byte。

例如 ADD AX,0x0A 是 0x50A00 ,而 ADD DX.0x0A 是 0x81C20A00,多了一個byte。所以如果想要得到較短的程式碼,你可以多使用AX/EAX暫存器,但這並不會帶來多大的好處。

The CISC King's gone RISC?

Intel 的處理器近來有朝向 RISC 的概念發展。一些核心的指令執行的相當快速,並且利用到 pipeline 的優點。

以下是一些常用指令的列表,其中

reg        8個主要的暫存器EAX.EBX,ECX,EDX,ESI,EDI,EBP,ESP
mem     記憶體運算元
imm     常數值
acc       累加器AX/EAX

• 一般用途的 MOV: 只用到八個主要暫存器,沒有用到 seg,CRs,DRs,TRs等其他暫存器或者是記憶體 ---1 clock
• PUSH reg/imm ---1 clock
• POP, INC, DEC reg --- 1 clock.
• INC, DEC with mem --- 3 clocks.
• ADD, SUB, AND, OR, XOR, ADC, SBB reg, reg/imm ---1 clock.
• ADD, SUB, AND, OR, XOR, ADC, SBB reg, mem --- 2 clocks.
• ADD, SUB, AND, OR, XOR, ADC, SBB mem, reg/imm --- 3 clocks.
• LEA --- 1 clock.
• NOP --- 1 clock.
• XCHG acc, reg --- 1 clock.
• XCHG reg, reg --- 2 clocks.
• XCHG reg, mem --- 3 clocks.
• CMP, TEST reg, reg/imm --- 1 clock. ( CMP 實際上是沒有儲存結果的SUB )
• CMP, TEST mem, reg/imm --- 2 clocks. ( TEST 實際上是沒有儲存結果的AND )
• SHL, SHR, SAR, SAL reg, imm --- 1 clock.
• SHL, SHR, SAR, SAL mem, imm --- 3 clocks.
• RDTSC --- 6-7 clock cycles.

當寫程式的時候,要盡量用那些 1-cycle 的指令,因為他們通過 pipeline 非常的平順。

Pipeline

pipeline 是微電腦設計的一個偉大發明。它讓處理器變成好像是一個生產線,一次同時有5個指令在執行,但是每個指令都在不同的執行階段。一般來說,一個指令的執行分為以下5個階段:

1. FETCH the next instruction.
2. DECODE that instruction.
3. CALCULATE memory addresses.
4. EXECUTE the opcode and store the results internally.
5. WRITEBACK the results to memory or registers as specified.

在比 486 老的處理器,每個指令在下個指令要開始執行以前,都要辛苦的執行和完成(從FETCH到WRITEBACK)。但這都已經是過去式了,有了 pipeline,當 opcode5 在 writeback 階段, opcode4 就正在 execute 階段,opcode3 就正在 calculate 階段,以此類推。

很明顯的,如果在這5個階段的指令都只花掉1個 clock,那 pipeline 會讓效能變大至少五倍,這是最理想的情況。

以下是一些 pipeline 的使用方法:

Guideline #1: Avoid AGI Stalls

計算一個位址花掉一個 clock (即使是非常"漂亮"的位址)。但是如果一個指令需要上一個指令的結果來計算位址,那麼整個 pipeline 就必須拖延一個 clock,這種延遲叫作 AGI (Address Generation Interlock),例如:

MOV EDI, 0xA0000
MOV [EDI], EAX
會遭遇到 AGI,因為 MOV [EDI],EAX 在把 EAX 寫到 [EDI] 之前,要先等 EDI 得到 0xA0000 的新值。

一個解決 AGI 的好方法,就是在會發生 AGI 的兩個相鄰指令中間插入一個和上下指令毫不相關的指令,以這個例子來說,變成

MOV EDI, 0xA0000
MOV EBX, ECX 〈---- 新加入的指令
MOV [EDI], EAX
就不會發生 AGI。

另一種發生 AGI 的情況是當前一個指令隱涵牽涉到 ESP( 像PUSH,POP,RET ),並且下一個指令也用到 ESP 的時候,例如:

POP EBX
MOV EAX, [ESP+12]
會發生AGI,但是
MOV EAX, [ESP+16]
POP EBX
並不會產生 AGI ,雖然他們的效用是一樣的。

唯一的例外是兩個連續的 PUSH 和 POP,這種組合並不會發生 AGI,但PUSH/POP 或 POP/PUSH 的組合就會。

Guideline #2: Avoid Repeated Register Usage

雖然每個程式設計者都趨向把所有有關連的程式碼寫在一起,但是 pipeline 卻完全不喜歡這樣, pipeline喜歡暫存器交互使用,甚至是兩個 "thread" 的程式碼(並不是真正的意思)。規則是 先讀後寫,不要 先寫後讀。所以

MOV EAX, EDX
MOV EDX, [ESP+12]
DX 先讀後寫,會工作的很好,但是

MOV EAX, EDX
MOV EBX, EAX

DX 先寫後讀,就會遭遇到一個 clock 的延遲,因為當 EBX 要被寫入時, EAX 的新值還未確定,所以 MOV EBX,EAX 就要多等一個 clock,這跟 pipeline 先讀後寫的特性( writeback 是第五個階段)有關

要避免這種常會碰到的問題,試著以

MOV EAX, EDX
MOV EBX, EDX

的形式來寫, pipeline 就不會產生任何的延遲

Guideline #3: Avoid Partial Register Usage

不要使用暫存器中 8-bit 或 16-bit 的部份,舉例來說

MOV AX, [EDI]
AND EAX, 0xFF00FF00
會遇到一個 clock 的延遲,還有

MOV AL, 03
MOV AH, [EDI+3]
這種使用到同一個暫存器不同部份的情形,也會產生一個 clock 的延遲,因為對處理器而言,使用一個暫存器的部份,就好像是使用整個 32-bit 的暫存器一樣。

Guideline #4: Avoid the Byte Register Anomaly

這是一種浪費一個額外 clock 的特殊情形。如果一個指令用到了 8-bit 暫存器,然後在兩個 clock 之內有指令用任何的 32-bit 暫存器存取記憶體,就會產生一個 clock 的延遲。例如

    
   MOV DL, 0x50            ; 1 cycle
   ADD EBX, ECX           ; 1 cycle
   MOV EAX, [EDI]         ; 2 cycles, because of the "MOV DL, 0x50"
    

會遇到延遲,但是交換第二行和第三行後

  
   MOV DL, 0x50             ; 1 cycle
   MOV EAX, [EDI]          ; 1 cycles
   ADD EBX, ECX            ; 1 cycle
   

就不會有延遲,因為已經過了兩個 clock

　

Guideline #5: Strategize with Multi-cycle Opcodes

固定的多週期指令,像是 CMC( complement carry flag, 2 cycles ),接下來的指令如果是兩個 clock 以上,會減少一個 clock 的執行時間,例如:

    MOV AX, DX               ; 2 clocks because it's a prefixed instruction
    CMC                              ; 2 clocks

能被換為

    CMC                             ; 2 clocks
    MOV AX, DX               ; 1 clock, because CMC already took 2

他們功用相同,但是後者快了一個 clock!( 這種情形只有在 486 的處理器 )

Pentium Dual Pipelines

486 處理器已經有一個非常好的 pipeline,但是 Intel 在 Pentium 處理器上又跨出了另一步-- Intel 在 Pentium 裡設計了兩個 pipeline。其中的一個叫 U-pipe,另一個叫 V-pipe, U-pipe 能夠執行每個指令,但並不一定要和 V-pipe 一起執行。然而這並不像如此聽來的嚇人,因為能讓兩個 pipeline 同時工作的指令,實在是少之又少。當兩個指令各進入一個 pipeline 時,這種情形叫做 "pairing"。而 Pentium optimizer ( 你?:-) )的一個主要目標,就是儘可能的產生 paring。

下列的指令在 U-pipe 和 V-pipe 都能產生 paring

add	sub	and	or
xor	cmp	test	dec
inc	lea	mov	pop
push	nop

這裡有一個例外:如果 TEST 有一個立即運算元( imm ),就不能產生 paring。

下列的指令只有在 U-pipe 執行才能產生 pair

adc	sbb	shl	shr
sal	sar	rol	ror
rcl	rcr

所有的旋轉指令( rol,ror,rcl,rcr )只有在 rol reg,1 的時候才能 pair

下列的指令只有在 V-pipe 執行才能產生 pair

jmp	call	jCC

jCC 代表所有的判斷跳躍( JNZ,JGE,JLE....等 )

當兩個指令 pair,代表他們同時執行,所以兩個 1 cycle 的指令實際上只花了一個 clock 的時間,底下是一個實例:

; void PutPxl(dword x, dword y, dword color);
; this is a 640x480 hicolor PutPxl, but use dwords for stack alignment
_PutPxl
   push ebp                      ; 1 
   mov ebp, esp               ; 1 - no pair 
   push es                         ; 0 
   push edi                        ; 1 

   mov ecx, [_GrxDsc]    ; 0 
   mov edi, [_FrmBuf]     ; 1 
   mov eax, [ebp+12]      ; 0 ; mov eax, 'y' 
   mov es, cx                    ; 2 np 

   shl eax, 7                     ; 1 U
   mov ecx, [ebp+8]        ; 0 ; mov ecx, 'x' 
   mov edx, eax               ; 1 np 
   shl eax, 2                     ; 1 np 
   add edi, ecx                 ; 0 
   add eax, edx                ; 1 
   add edi, eax                 ; 1 
   mov eax, [ebp+16]      ; 0 ; mov eax, 'color' 

   mov [es:edi], ax           ; 3 ; it's got 2 prefixes, segment and osize
                                           ; it pairs because it's in the U-pipe, but with a stall of 2

   pop edi                        ; 0 
   pop es                          ; 3 
   mov esp, ebp               ; 1 
   pop ebp                       ; 1 
   ret                                ; 3 ; near return takes 3 clocks

; 23 cycle PutPxl theoretically (I think; if I'm wrong notify me)
; end of PutPxl

由於指令的長度很不固定,程式碼在第一次執行的時候大都很難產生 pair。處理器通常都不知道如何去 pair 指令,直到程式第二次執行。因為程式執行後, L1 cache 會保留關於指令長度的資料。還有,第一次執行的時候,程式必須由記憶體內載入到 cache ,這可能比程式本身執行的時間還長。所以如果程式碼不是重複而且長度過大( cache的大小有限 ),那大概就不值得去最佳化。

要得到更多有關 Pentium 最佳化的資料,請參考 Paul Hsieh's Page 裡的Agner Fog's document ,不用多說,一個相當好的文件。

最佳瀏覽模式 1024 x 768 x 16 bit color with Netscape Communicator 4.0 or later.