【日积月累】优化小技巧
大家都来说说吧.........，我看到哪，说到哪......一.消除、减少分支的数量
非常好的优化技巧，偏底层。
通过应用setcc指令或奔腾处理器的条件转移指令(CMOV 或 FCMOVE)来削除分支。
比如下面这个c语言的例子：ebx = (A < B) ? CONST1 : CONST2;上面这个代码条件比较两个值,A 和 B. 如果为真(A<B)，则ebx置为CONST1;否则被置为CONST2.
下面这段汇编与上面的代码等同：cmp A, B ; condition
jge L30 ; conditional branch
mov ebx, CONST1
jmp L31 ; unconditional branch
L30:
mov ebx, CONST2
L31:对于上面的汇编，我们可以用setcc指令来替换jge，消除分支，以达到优化的目的，程序如下：xor ebx, ebx ;clear ebx
cmp A, B
setge bl ;When ebx = 0 or 1
;OR the complement condition
dec ebx ;ebx=00...00 or 11...11
and ebx, (CONST2-CONST1) ;ebx=0 or(CONST2-CONST1)
add ebx, min(CONST1,CONST2) ;ebx=CONST1 or CONST2注意一点,min(CONST1,CONST1)由常量CONST1,CONST2已定，比如min(6,8)=6;
当abs(CONST1-CONST2)为1,2,4,8时，另一种有趣的实现如下：xor ebx, ebx
mov eax, A
cmp eax, B
setge bl
lea ebx, 部分机器码如下：;=======================================================
00401000 >/\$A1 00304000 MOV EAX,DWORD PTR DS:
00401005|.3B05 04304000 CMP EAX,DWORD PTR DS:
0040100B|.7D 07 JGE SHORT good.00401014
0040100D|.BB 06000000 MOV EBX,6
00401012|.EB 05 JMP SHORT good.00401019
00401014|>BB 0E000000 MOV EBX,0E
;=======================================================
00401028|.33DB XOR EBX,EBX
0040102A|.A1 00304000 MOV EAX,DWORD PTR DS:
0040102F|.3B05 04304000 CMP EAX,DWORD PTR DS:
00401035|.0F9CC3 SETL BL
00401038|.4B DEC EBX
00401039|.83E3 08 AND EBX,8
0040103C|.83C3 06 ADD EBX,6
;=======================================================
0040104E|.33DB XOR EBX,EBX
00401050|.A1 00304000 MOV EAX,DWORD PTR DS:
00401055|.3B05 04304000 CMP EAX,DWORD PTR DS:
0040105B|.0F9DC3 SETGE BL
0040105E|.8D1CDD 06000000 LEA EBX,DWORD PTR DS:
;=======================================================再细化，比如对于上面的程序块，通过填充其他指令或nop，实现对齐，以达到性能峰值。
特别是对于核心模块。xor ebx, ebx ;clear ebx
mov eax,A
cmp eax, B
setl bl ;When ebx = 0 or 1
;OR the complement condition
dec ebx ;ebx=00...00 or 11...11
and ebx, (CONST2-CONST1) ;ebx=0 or(CONST2-CONST1)
add ebx, CONST1 ;ebx=CONST1 or CONST2 做到8字节对齐：xor ebx, ebx ;clear ebx
mov eax,A
nop
nop
cmp eax, B
setl bl ;When ebx = 0 or 1
;OR the complement condition
dec ebx ;ebx=00...00 or 11...11
and ebx, (CONST2-CONST1) ;ebx=0 or(CONST2-CONST1)
nop
add ebx, CONST1 ;ebx=CONST1 or CONST2 //-----------------------------------------------------
第二种方法是用"新"的指令CMOV,FCMOV来消除分支
比如测试ecx是否为0 test ecx,ecx
jne L20
mov eax,ebx
L20:可以换成： test ecx, ecx ; test the flags
cmoveq eax, ebx ; if the equal flag is set, move ebx to eax
L20:指令参考：http://www.cnblogs.com/itjin45/archive/2009/09/03/1559129.html
测试程序：.386
.model flat,stdcall
include user32.inc
include kernel32.inc
include msvcrt.inc
includelib user32.lib
includelib kernel32.lib
includelib msvcrt.lib
CONST1equ6
CONST2equ 14 ;7,8,10,14
.data
A dd 5;10
B dd 7
fmt db ' %d',0
szPausedb 'Pause',0
.code
;****************************
start:
;----------------------------
;ebx = (A < B) ? CONST1 : CONST2;
;**********法一**************
mov eax,A
cmp eax,B
jge L30
mov ebx,CONST1
jmp L31
L30:
mov ebx,CONST2
L31:
invoke crt_printf,offset fmt,ebx
;**********法二**************
xor ebx, ebx ;clear ebx
mov eax,A
cmp eax, B
setl bl ;When ebx = 0 or 1
;OR the complement condition
dec ebx ;ebx=00...00 or 11...11
and ebx, (CONST2-CONST1) ;ebx=0 or(CONST2-CONST1)
add ebx, CONST1 ;ebx=CONST1 or CONST2
invoke crt_printf,offset fmt,ebx
;**********法三**************
xor ebx, ebx
mov eax, A
cmp eax, B
setge bl ; or the complement condition
lea ebx,
invoke crt_printf,offset fmt,ebx
invoke crt_system,offset szPause
invoke ExitProcess,0
end start 下面这段文字很好理解，我就不翻译了，不经意看到gotoblas的kernel中提到了这个：
ATHLON performance tips
Now some information how to achieve peak performance on Athlon:
(1) The first and most important thing is that you must put three x86 instructions into packages
of exactly 8 bytes to make the decoders run as smooth as possible. Additionally these
packages must be 8 byte aligned. If one of these packages for example consists of three instruction but
only 7 bytes, you can use the REP prefix as natural code filler. If you already have two (longer) instructions
in one package and your next does not fit, use a suitable neutral x87 instruction ("nop", "fnop" see
Athlon manual) as code filler and move your instruction into the next block. Here some examples:
bad!
20 00000010 DD4038 fld qword
21 00000013 D8C9 fmul st0,st1
22 00000015 D8C1 fadd st0,st1
good!
26 00000020 DD4038 fld qword
27 00000023 D8C9 fmul st0,st1
28 00000025 F3 db 0F3H
29 00000026 D8C1 fadd st0,st1
good!
33 00000030 DC4C1818 fmul qword
34 00000034 DC4020 fadd qword
35 00000037 90 nop
(2) To keep instructions short and to achieve FP peak performance you MUST use 8 bit immediates only when
operating with memory operands. Otherwise it is not possible to put 1 fadd + 1 fmul + 1fld/fst into a
8 byte package. Example:
bad!
39 00000040 DD8038020000 fld qword
40 00000046 D8C9 fmul st0,st1
41 00000048 D8C1 fadd st0,st1
(3) In praxis it is not possible to achieve peak in 3dnow! because 3dnow! instructions are to long. Examples
45 00000050 0F6F01 movq mm0,
46 00000053 0F0FC1B4 pfmul mm0,mm1
47 00000057 0F0FD09E pfadd mm2,mm0
(4) Athlon's prefetch instructions are not compatible with Intel's. Athlon can only prefetch into L1 cache and it
is prefetch=prefetchnta=prefetcht0=prefetcht1=prefetcht2
(5) Athlon instruction scheduler is very aggressive and register renaming is very intelligent. Let them do
most work. It is not problem to initiate the calculation of a dependency chain like b=b*a and c=c+b in one cycle.
Additionally you can use 'a' in the next cycle without waiting that b=b*a is complete, because Athlon's
register renaming makes a copy of 'a' for you internally. Example:
Assuming our stack looks already like this:c0 c1 c2 c3 a0 <-top
If we want to calculate the following:
c0=c0+a0*b0
c1=c1+a0*b1
c2=c2+a0*b2
c3=c3+a0*b3
c0=c0+a0*b4
c1=c1+a0*b5
[...]
.. the pseudo assembly code would look like this (with stack view)
fld b0 c0c1c2c3a0b0
fmul b0,a0 c0c1c2c3a0b0
faddp c0,b0 c0c1c2c3a0
fld b1 c0c1c2c3a0b1
fmul b1,a0 c0c1c2c3a0b1
faddp c1,b1 c0c1c2c3a0
[...]
this code runs with peak performance which is clear when you take a look on how the instructions are scheduled by the CPU
cycle 0 >|
|
fld oo
fmul oooo
faddp oooo <- c0 calculated
fld oo
fmul oooo <- uses copy of original 'a0'
faddp oooo <- c1 calculated
fld oo
fmul oooo
faddp oooo <- c2 calculated
fld oo
fmul oooo
faddp oooo <- c3 calculated
fld oo
fmul oooo
faddp oooo
|<- in this cycle c0 is free again (see above) and exactly here the new c0 calculation starts
As you see this code needs only 6 stack registers to achieve peak performance. 一直没找到一个比较好的处理器中文资料，今天总算找到了一个，再结合Intel文档，很不错。
Intel Nehalem-EP首发深度评测(一)
Intel Nehalem-EP首发深度评测(二) (***)
强CPU20倍!正睿Tesla GPU计算系统评测!
Intel 32nm Westmere-EP处理器首发评测 这个帖子不错，也比较耐读。:b: Mark, 等有空儿时研读研读 我写了4个求一个数组最大值最小值的函数。
版本1：getMaxMin1， 普通写法，
版本2：getMaxMin_asm，使用C中嵌入汇编的用法，采用无跳转的cmovb 和 cmova 条件赋值指令
版本3: getMaxMin_MT2, 2线程求最大值最小值算法
版本4：getMaxMin_MT4，2线程求最大值最小值算法
CPU：Intel Core 2 Duo E8500 双核CPU， L2 cache 6M.
OS： Windows XP, 编译器 VC++6.0, release 模式编译
从运行结果来看，发现 cmov指令并没有提高性能，应该说intel的分支预测效果很好。下面是运行结果getMaxMin1 spend 0.006152 second on search max and min in 4194304 number
min=458,max=2147450654, from getMaxMin1
getMaxMin_asm spend 0.006186 second on search max and min in 4194304 number
min=458,max=2147450654, from getMaxMin1
getMaxMin_MT2 spend 0.003353 second on search max and min in 4194304 number
min=458,max=2147450654, from getMaxMin1
getMaxMin_MT4 spend 0.003441 second on search max and min in 4194304 number
min=458,max=2147450654, from getMaxMin1 这里给出C版和汇编版void getMaxMin1(DWORD *pData,int len,DWORD *min,DWORD *max)
{
int i;
*min=~0;
*max=0;
for (i=0;i<len;i++)
{
if ( pData > *max)
*max=pData;
if (pData< *min)
*min=pData;
}
}
void getMaxMin_asm(DWORD *pData,int len,DWORD *min,DWORD *max)
{
DWORD _min, _max;
__asm
{
mov esi, pData
mov ecx, len
lea edi,
mov eax, 0xffffffff //min
mov edx, 0 //max
loop_start:
cmp esi, edi
jge next10
cmp , eax
cmovb eax,
cmp , edx
cmova edx,
add esi, 4
jmp loop_start
next10:
mov _min, eax
mov _max, edx
}
*min=_min;
*max=_max;
} 有点意思，发现liangbch 与我的cpu一个型号，呵呵，我对第一个消除分支的测试了一下，发现有效果。(前后顺序不存在依赖关系)
结果：Elapsed time:0.124000 s
Elapsed time:0.094000 s
Elapsed time:0.094000 s测试代码:#include <stdio.h>
#include <time.h>
int main()
{
int i,j,ebx;
doublet1,t2,t3;
//测试1#################
j=2009;
t1=clock();
for(i=0;i<99990000;i+=2,j-=10)
{
ebx = (i < j) ? 6 : 8;
}
printf("Elapsed time: %f s\n",(clock()-t1)/CLOCKS_PER_SEC);
//测试2#################
j=2009;
t2=clock();
for(i=0;i<99990000;i+=2,j-=10)
{
// GetMaxAsm(i,j);
__asm
{
xor ebx, ebx
mov eax, i
cmp eax, j
setl bl
dec ebx
and ebx, 2
add ebx, 6
}
}
printf("Elapsed time: %f s\n",(clock()-t2)/CLOCKS_PER_SEC);
//测试3#################
j=2009;
t3=clock();
for(i=0;i<99990000;i+=2,j-=10)
{
// GetMaxAsm(i,j);
__asm
{
xor ebx, ebx
mov eax, i
cmp eax, j
setge bl
lea ebx,
}
}
printf("Elapsed time: %f s\n",(clock()-t3)/CLOCKS_PER_SEC);
system("Pause");
return 0;
} 刚刚查了下Intel CPU文档，发现可用SSE2指令 PMINUD, PMAXUD 求无符号整数最大最小值，用指令PMINSD, PMAXSD 求带符号整数最大最小值，有时间实现一下，看看速度如何。 PMINUD, PMAXUD不是 SSE2 指令吧？应该是 SSE4 指令了。