Zawsze warto przyjrzeć się kodowi wygenerowanemu przez gcc (gcc -S) i ręcznie
spróbować coś w nim poprawić. Czasami udaje się znowu nieco przyśpieszyć.
Ale nie poprawiaj czegoś tylko dlatego że tego nie rozumiesz, bo może się
to skończyć zawieszeniem programu.
Pora na oficjalne zalecenia Intela.
Procesor Pentium posiada dwie "pipelines" ( łańcuchy? kolejki? ) instrukcji
operujących an liczbach całkowitych,
tzw. U-potok i V-potok. W dalszej części tekstu pisząc "potok" będę miał
na myśli "pipeline". W każdym cyklu procesor sprawdza, czy może wykonać równocześnie
dwie instrukcje, i jeśli tak, to jedną z nich kieruje do U-potoku, a drugą do
V-potoku. Nie każda instrukcja może być wykonana w V-potoku, i nie każde dwie
instrukcje mogą być wykonane równocześnie. Jeśli zachodzi taka sytuacja,
procesor wykonuje tylko jedną instrukcję w U-potoku.
Oba potoki składają się z 5 faz : Prefetch (pobranie) (PF) Decode Stage 1
(dekodowanie) (D1) Decode Stage 2 (dekodowanie) (D2) Execute (wykonywanie) (E)
i Writeback (zapisywanie efektów instrukcji) (WB).
W fazie PF, jeżeli napotkana zostanie instrukcja rozgałęzienia (skoku warunkowego np.)
(ang. branch), to uruchamia się mechanizm przewidywania. Jeżeli mechanizm ten zawurokuje,
że prawdopodobnie rozgałęzienie nie będzie brane pod uwagę, instruktor pobiera następną
instrukcję, jeżeli zawyrokuje, że gałąź (skok będzie wykonany) będzie brana pod uwagę,
pobierana jest instrukcja z tej gałęzi. W razie pomyłki instrukcję wycofuje się,
powoduje to opóźnienie wykonania o : 3 cykle, jeśli instrukcja była wykonywana
w U-potoku, 4, jeśli wykonywana była w V-potoku, 3, jeśli było to wywołanie podprogramu
bądź skok bezwarunkowy.
Dodatkowo Pentium posiada potok zmiennoprzecinkowy. Potok ten jest 3-poziomowy.
najpierw wykonywana jest instrukcja w Potoku całkowitym, jeśli jest to instrukcja
zmiennoprzecinkowa kieorwana jest do potoku zmiennoprzecinkowego. Jeśli ta instrukcja
jest długa, to w czasie jej trwania może się wykonać instrukcja całkowitoliczbowa.
Identycznie, Pentium MMX posiada dodatkowy potok MMX-owy.
Bla, Bla. Co z tego wynika?
Po pierwsze, unikaj rozgałęzień w programie. Staraj się zastępowąć je instrukcjami
np SETcc bądź CMOVcc. Algorytm przewidywania skoków działa wspaniale wtedy, gdy w 90%
przypadków skok następuje w jedno miejsce, gdy skoki następują w kilka różnych miejsc
(jak na przykład dla instrukcji typu switch.. case) wydajność spada dramatycznie.
Dodatkowo intel na kilkudziesięciu stronach tłumaczy na czym polega algorytm
przewidywania skoków ale moja angielszczyzna jest zbyt kiepska bym ryzykował
tłumaczenie.
Po drugie, jeśli np. zapisujesz coś do AX i zaraz potem odczytujesz EAX
(zawsze jeśli coś zapisujesz od mniejszej części rejestru i zaraz potem go odczytujesz)
to pojawiają sięopóźnienia w programie (podobno min. 7 cykli).
Nawet, jeśli instrukcje odczytujące cały rejestr i jego
mniejsze części nie występują natychmiast po sobie, z powodu "out-of-order-execution",
czyli możliwością wykonywania instrukcji poza kolejnością, opóźnienia mogą się
również pojawić. W pentium Pro i Pentium II istnieje kilka przypadków, w których równocześnie
można się odwoływać do mniejszych części rejestru i całego rejestru. Mianowicie,
jeśli najpierw za pomocą xor lub sub wyzerujemy rejestr, możemy do niego zapisywać i zaraz
potem odczytywać. Przykład:
movb %al, $4
add %%eax,$24 //kara!
xor %eax,%eax
movb %al, $4
add %%eax, $24 //nie ma kary
xor %ah,%ah
movb %al, $4
add %%ax, $24 //nie ma kary
sub %eax,%eax
movb %al, $4
add %%eax, $24 //nie ma kary
Warto więc zawsze zerować rejestr jeśli najpierw zapisujemy do mniejszej części
a potem operujemy na większej.
Powinieneś starannie przemyśleć pętle. Np. dwie pętle operujące na tych samych danych
powinieneś poląćżyć w jedną.
for(.....)
{
a(i)=
}
for(...)
{
a(i)=..
}
=>
for(..) {a(i)=.. a(i)=...}
I na odwrót, jęsli to możliwe, rozdzielaj pętle w których operujesz na różnych danych,
by nie opróżniać cache'u.
for(..) { A(i)=.. b(i)=..} // za każdym razem co innego w cache'u
=>
for (..)
{A(i)=..}
for(..) {B(i)=..}
Staraj się "parować", łączyć w pary instrukcje, by móc równoczęśnie dwi wykonywać.
Zazwyczaj tą robotę powinien wykonać za Ciebie kompilator, gdy piszesz w C.
Unikaj długich, złożonych instrukcji, np LOOP, zmiast nich używaj sekwencji
prostszych instrukcji .
Czyść rejestry za pomocą xor reg, reg
Unikaj łądowania małej ilości danych i zaraz potem wielkich danych w ten sam
obszar pamięci (i na odwrót). Staraj się zawsze łądować dane o tym samym rozmiarze
i w ten sam sposób w te same obszry pamięci.
Zawsze pamietaj o odpowiednim wyrównywaniu danych. Zasadniczo zajmuje sie tym gcc, mozna zawsze wymusic odpowiednie wyrownanie za pomoca __attribute__((aligned(alignment)), albo tez za pomoca dyrektywy gas-a .align albo (lepiej) .balign alignment, fill_value, maximum_skipped_bytes (dwa ostatnie argumenty opcjonalne) lub .p2align potega_dwojki, fill_value,maximum_skipped_bytes. Magistrala pamieci jest 32-bitowa; tak wiec, zeyb sciagnac dowolna dana, sciagane sa CALE 32 bity. Jezeli wiec zmienna nie jest odpowiednia wyrownana (np. zajmuje 4 bajty, ale poczatek znajduje sie na adresie niepodzielnym przez cztery) to trzeba wykonac dwóch dostepow do pamieci, by ja sciagnac.
Zwracaj uwagę na algorytm przewidywania skoków. Te skoki, ktore pojawiaja sie czesciej, daj na poczatku petli. Najlepiej zas unikaj skokow i zastepuj je innymi, rownowaznymi instrukcjami. (np b=a?1:0 bedzie dla dobrych kompilatorow generowalo lepszy kod niz if (a>0) b=1; else b=0; - pomijajac sens przykladu :) ).
Ogólne reguły tyczące parowanie:
Na Pentium instrukcje nie są parowalne, jęsli jedna z nich jest dłuższa niż
8 opcodów. Na Pentium MMX pierwsza instrukcja nie może być dłuższa niż 11 opcodów
, a druga, w V potoku, dłuższa niż 7 opcodów.
Na Pentium nie są parowalne instrukcje z prefixami. Na MMX parowalne
są isntrukcje z prefixami OFh, 66h, 67h, ale tylko w V-potoku. Przy okazji,
te kody odnoszą się do jakich prefixów?
Obie instrukcje nie mogą równocześnie odwoływać się pośrednio lub bezpośrednio
do tych samych miejsc w pamięci lub rejestrów. (Z pewnymi wyjątkami- instrukcjami
PUSH i POP)
Obie instrukcje nie mogą równocześnie być w cache, chyba że pierwsza znich jest
jednobajtowa.
Instrukcje MMX nie mogą być parowalne z zmiennoprzecinkowymi.
Dwie instrukjce MUL nie są parowalne (tylko jedna jednostka do mnożenia)
Instrukce MMX przesuwające (shift instructions) nie są parowalne
jeżeli przeznaczenie jednej instrukcji MMX jest takie samo jak źródło drugiej,
instrukcje te nie są parowalne
Instrukcje MMX które operują na pamięci lub rejestrze całkowitoliczbowym
są wykonywalne tyko w U-potoku
Parowanie instrukcji / na razie tylko całkowitoliczbowe. Sorry.
Nie mam siły więcej. Jak ktoś zechce to listę poszerzę.
NP - Nie da się sparować, wykonuje się w U-potoku
PU - Da się sparować w U-potoku
PV - Da się sparować w V-potoku
UV - Da się sparować w obu potokach
Instrukcje Wejścia/Wyjścia nie dają się sparować.
AA - ASCII Adjust after Addition NP
AAD - ASCII Adjust AX before Division NP
AAM - ASCII Adjust AX after Multiply NP
AAS - ASCII Adjust AL after Subtraction NP
ADC - ADD with Carry PU
ADD - Add UV
AND - Logical AND UV
ARPL - Adjust RPL Field of Selector NP
BOUND - Check Array Against Bounds NP
BSF - Bit Scan Forward NP
BSR - Bit Scan Reverse NP
BSWAP - Byte Swap NP
BT - Bit Test NP
BTC - Bit Test and Complement NP
BTR - Bit Test and Reset NP
BTS - Bit Test and Set NP
CALL - Call Procedure (in same segment)
direct 1110 1000 : full displacement PV
register indirect 1111 1111 : 11 010 reg NP
memory indirect 1111 1111 : mod 010 r/m NP
CALL - Call Procedure (in other segment) NP
CBW - Convert Byte to Word NP
CWDE - Convert Word to Doubleword
CLC - Clear Carry Flag NP
CLD - Clear Direction Flag NP
CLI - Clear Interrupt Flag NP
CLTS - Clear Task-Switched Flag in CR0 NP
CMC - Complement Carry Flag NP
CMP - Compare Two Operands UV
CMPS/CMPSB/CMPSW/CMPSD - Compare String NP
CMPXCHG - Compare and Exchange NP
CMPXCHG8B - Compare and Exchange 8 Bytes NP
CWD - Convert Word to Dword NP
CDQ - Convert Dword to Qword
DAA - Decimal Adjust AL after Addition NP
DAS - Decimal Adjust AL after Subtraction NP
DEC - Decrement by 1 UV
DIV - Unsigned Divide NP
ENTER - Make Stack Frame for Procedure Parameters NP
HLT - Halt
IDIV - Signed Divide NP
IMUL - Signed Multiply NP
INC - Increment by 1 UV
INT n - Interrupt Type n NP
INT - Single-Step Interrupt 3 NP
INTO - Interrupt 4 on Overflow NP
INVD - Invalidate Cache NP
INVLPG - Invalidate TLB Entry NP
IRET/IRETD - Interrupt Return NP
Jcc - Jump if Condition is Met PV
JCXZ/JECXZ - Jump on CX/ECX Zero NP
JMP - Unconditional Jump (to same segment)
short 1110 1011 : 8-bit displacement PV
direct 1110 1001 : full displacement PV
register indirect 1111 1111 : 11 100 reg NP
memory indirect 1111 1111 : mod 100 r/m NP
JMP - Unconditional Jump (to other segment) NP
LAHF - Load Flags into AH Register NP
LAR - Load Access Rights Byte NP
LDS - Load Pointer to DS NP
LEA - Load Effective Address UV
LEAVE - High Level Procedure Exit NP
LES - Load Pointer to ES NP
LFS - Load Pointer to FS NP
LGDT - Load Global Descriptor Table Register NP
LGS - Load Pointer to GS NP
LIDT - Load Interrupt Descriptor Table Register NP
LLDT - Load Local Descriptor Table Register NP
LMSW - Load Machine Status Word NP
LOCK - Assert LOCK# Signal Prefix
LODS/LODSB/LODSW/LODSD - Load String Operand NP
LOOP - Loop Count NP
LOOPZ/LOOPE - Loop Count while Zero/Equal NP
LOOPNZ/LOOPNE - Loop Count while not Zero/Equal NP
LSL - Load Segment Limit NP
LSS - Load Pointer to SS 000 1111 : 1011 0010 : mod reg r/m NP
LTR - Load Task Register NP
MOV - Move Data UV
MOV - Move to/from Control Registers NP
MOV - Move to/from Debug Registers NP
MOV - Move to/from Segment Registers NP
MOVS/MOVSB/MOVSW/MOVSD - Move Data from String NP
to String
MOVSX - Move with Sign-Extend NP
MOVZX - Move with Zero-Extend NP
MUL - Unsigned Multiplication of AL, AX or EAX NP
NEG - Two's Complement Negation NP
NOP - No Operation 1001 0000 UV
NOT - One's Complement Negation NP
OR - Logical Inclusive OR UV
POP - Pop a Word from the Stack
reg 1000 1111 : 11 000 reg UV
or 0101 1 reg UV
memory 1000 1111 : mod 000 r/m NP
POP - Pop a Segment Register from the Stack NP
POPA/POPAD - Pop All General Registers NP
POPF/POPFD - Pop Stack into FLAGS or EFLAGS NP
Register
PUSH - PushOperand onto the Stack
reg 1111 1111 : 11 110 reg UV
or 0101 0 reg UV
memory 1111 1111 : mod 110 r/m NP
immediate 0110 10s0 : immediate data UV
PUSH - Push Segment Register onto the Stack NP
PUSHA/PUSHAD - Push All General Registers NP
PUSHF/PUSHFD - Push Flags Register onto the Stack NP
RCL - Rotate thru Carry Left
reg by 1 1101 000w : 11 010 reg PU
memory by 1 1101 000w : mod 010 r/m PU
reg by CL 1101 001w : 11 010 reg NP
memory by CL 1101 001w : mod 010 r/m NP
reg by immediate count 1100 000w : 11 010 reg : imm8 data PU
memory by immediate count 1100 000w : mod 010 r/m : imm8 PU
RCR - Rotate thru Carry Right
reg by 1 1101 000w : 11 011 reg PU
memory by 1 1101 000w : mod 011 r/m PU
reg by CL 1101 001w : 11 011 reg NP
memory by CL 1101 001w : mod 011 r/m NP
reg by immediate count 1100 000w : 11 011 reg : imm8 data PU
memory by immediate count 1100 000w : mod 011 r/m : imm8 PU
RDMSR - Read from Model-Specific Register NP
REP LODS - Load String NP
REP MOVS - Move String NP
REP STOS - Store String NP
REPE CMPS - Compare String (Find Non-Match) NP
REPE SCAS - Scan String (Find Non-AL/AX/EAX) NP
REPNE CMPS - Compare String (Find Match) NP
REPNE SCAS - Scan String (Find AL/AX/EAX) NP
RET - Return from Procedure (to same segment) NP
RET - Return from Procedure (to other segment) NP
ROL - Rotate (not thru Carry) Left
reg by 1 1101 000w : 11 000 reg PU
memory by 1 1101 000w : mod 000 r/m PU
reg by CL 1101 001w : 11 000 reg NP
memory by CL 1101 001w : mod 000 r/m NP
reg by immediate count 1100 000w : 11 000 reg : imm8 data PU
memory by immediate count 1100 000w : mod 000 r/m : imm8 PU
ROR - Rotate (not thru Carry) Right
reg by 1 1101 000w : 11 001 reg PU
memory by 1 1101 000w : mod 001 r/m PU
reg by CL 1101 001w : 11 001 reg NP
memory by CL 1101 001w : mod 001 r/m NP
reg by immediate count 1100 000w : 11 001 reg : imm8 data PU
memory by immediate count 1100 000w : mod 001 r/m : imm8 PU
RSM - Resume from System Management Mode NP
SAHF - Store AH into Flags NP
SAL - Shift Arithmetic Left same instruction as SHL
SAR - Shift Arithmetic Right
reg by 1 1101 000w : 11 111 reg PU
memory by 1 1101 000w : mod 111 r/m PU
reg by CL 1101 001w : 11 111 reg NP
memory by CL 1101 001w : mod 111 r/m NP
reg by immediate count 1100 000w : 11 111 reg : imm8 data PU
memory by immediate count 1100 000w : mod 111 r/m : imm8 PU
SBB - Integer Subtraction with Borrow PU
SCAS/SCASB/SCASW/SCASD - Scan String NP
SETcc - Byte Set on Condition NP
SGDT - Store Global Descriptor Table Register NP
SHL - Shift Left
reg by 1 1101 000w : 11 100 reg PU
memory by 1 1101 000w : mod 100 r/m PU
reg by CL 1101 001w : 11 100 reg NP
memory by CL 1101 001w : mod 100 r/m NP
reg by immediate count 1100 000w : 11 100 reg : imm8 data PU
memory by immediate count 1100 000w : mod 100 r/m : imm8 PU
SHLD - Double Precision Shift Left
register by immediate count 0000 1111 : 1010 0100 : 11 reg2 NP
memory by immediate count 0000 1111 : 1010 0100 : mod reg r/m NP
: imm8
register by CL 0000 1111 : 1010 0101 : 11 reg2 NP
reg1
memory by CL 0000 1111 : 1010 0101 : mod reg r/m NP
SHR - Shift Right
reg by 1 1101 000w : 11 101 reg PU
memory by 1 1101 000w : mod 101 r/m PU
reg by CL 1101 001w : 11 101 reg NP
memory by CL 1101 001w : mod 101 r/m NP
reg by immediate count 1100 000w : 11 101 reg : imm8 data PU
memory by immediate count 1100 000w : mod 101 r/m : imm8 PU
SHRD - Double Precision Shift Right
register by immediate count 0000 1111 : 1010 1100 : 11 reg2 NP
reg1 : imm8
memory by immediate count 0000 1111 : 1010 1100 : mod reg r/m NP
: imm8
register by CL 0000 1111 : 1010 1101 : 11 reg2 NP
reg1
memory by CL 0000 1111 : 1010 1101 : mod reg r/m NP
SIDT - Store Interrupt Descriptor Table Register NP
SLDT - Store Local Descriptor Table Register NP
SMSW - Store Machine Status Word NP
STC - Set Carry Flag NP
STD - Set Direction Flag NP
STI - Set Interrupt Flag
STOS/STOSB/STOSW/STOSD - Store String Data NP
STR - Store Task Register NP
SUB - Integer Subtraction UV
TEST - Logical Compare
reg1 and reg2 000 010w : 11 reg1 reg2 UV
memory and register 1000 010w : mod reg r/m UV
immediate and register1111 011w : 11 000 reg : immediate NP
immediate and accumulator 1010 100w : immediate data UV
immediate and memory 1111 011w : mod 000 r/m : NP
immediate data
VERR - Verify a Segment for Reading NP
VERW - Verify a Segment for Writing NP
WAIT - Wait 1001 1011 NP
WBINVD - Write-Back and Invalidate Data Cache NP
WRMSR - Write to Model-Specific Register NP
XADD - Exchange and Add NP
XCHG - Exchange Register/Memory with Register NP
XLAT/XLATB - Table Look-up Translation NP
XOR - Logical Exclusive OR UV