【日积月累】优化小技巧

G-Spider

大家都来说说吧.........，我看到哪，说到哪...... 一.消除、减少分支的数量

通过应用setcc指令或奔腾处理器的条件转移指令(CMOV 或 FCMOVE)来削除分支。 比如下面这个c语言的例子：

1. ebx = (A < B) ? CONST1 : CONST2;

复制代码

上面这个代码条件比较两个值,A 和 B. 如果为真(A

1. cmp A, B ; condition
2. jge L30 ; conditional branch
3. mov ebx, CONST1
4. jmp L31 ; unconditional branch
5. L30:
6. mov ebx, CONST2
7. L31:

复制代码对于上面的汇编，我们可以用setcc指令来替换jge，消除分支，以达到优化的目的，程序如下：

1. xor ebx, ebx ;clear ebx
2. cmp A, B
3. setge bl ;When ebx = 0 or 1
5. ;OR the complement condition
6. dec ebx ;ebx=00...00 or 11...11
7. and ebx, (CONST2-CONST1) ;ebx=0 or(CONST2-CONST1)
8. 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时，另一种有趣的实现如下：

1. xor ebx, ebx
2. mov eax, A
3. cmp eax, B
4. setge bl
5. lea ebx, [ebx*(CONST2-CONST1)+CONST1]

复制代码

部分机器码如下：

1. ;=======================================================
2. 00401000 >/\$ A1 00304000 MOV EAX,DWORD PTR DS:[403000]
3. 00401005 |. 3B05 04304000 CMP EAX,DWORD PTR DS:[403004]
4. 0040100B |. 7D 07 JGE SHORT good.00401014
5. 0040100D |. BB 06000000 MOV EBX,6
6. 00401012 |. EB 05 JMP SHORT good.00401019
7. 00401014 |> BB 0E000000 MOV EBX,0E
8. ;=======================================================
9. 00401028 |. 33DB XOR EBX,EBX
10. 0040102A |. A1 00304000 MOV EAX,DWORD PTR DS:[403000]
12. 0040102F |. 3B05 04304000 CMP EAX,DWORD PTR DS:[403004]
14. 00401035 |. 0F9CC3 SETL BL
15. 00401038 |. 4B DEC EBX
16. 00401039 |. 83E3 08 AND EBX,8
18. 0040103C |. 83C3 06 ADD EBX,6
19. ;=======================================================
20. 0040104E |. 33DB XOR EBX,EBX
21. 00401050 |. A1 00304000 MOV EAX,DWORD PTR DS:[403000]
23. 00401055 |. 3B05 04304000 CMP EAX,DWORD PTR DS:[403004]
24. 0040105B |. 0F9DC3 SETGE BL
25. 0040105E |. 8D1CDD 06000000 LEA EBX,DWORD PTR DS:[EBX*8+6]
26. ;=======================================================

复制代码

再细化，比如对于上面的程序块，通过填充其他指令或nop，实现对齐，以达到性能峰值。 特别是对于核心模块。

1. xor ebx, ebx ;clear ebx
2. mov eax,A
3. cmp eax, B
4. setl bl ;When ebx = 0 or 1
5. ;OR the complement condition
6. dec ebx ;ebx=00...00 or 11...11
7. and ebx, (CONST2-CONST1) ;ebx=0 or(CONST2-CONST1)
8. add ebx, CONST1 ;ebx=CONST1 or CONST2

复制代码

做到8字节对齐：

1. xor ebx, ebx ;clear ebx
2. mov eax,A
3. nop
4. nop
5. cmp eax, B
6. setl bl ;When ebx = 0 or 1
7. ;OR the complement condition
8. dec ebx ;ebx=00...00 or 11...11
9. and ebx, (CONST2-CONST1) ;ebx=0 or(CONST2-CONST1)
10. nop
11. add ebx, CONST1 ;ebx=CONST1 or CONST2

复制代码

//----------------------------------------------------- 第二种方法是用"新"的指令CMOV,FCMOV来消除分支 比如测试ecx是否为0

1. test ecx,ecx
2. jne L20
3. mov eax,ebx
4. L20:

复制代码

可以换成：

1. test ecx, ecx ; test the flags
2. cmoveq eax, ebx ; if the equal flag is set, move ebx to eax
3. L20:

复制代码

指令参考：http://www.cnblogs.com/itjin45/archive/2009/09/03/1559129.html 测试程序：

1. .386
2. .model flat,stdcall
4. include user32.inc
5. include kernel32.inc
6. include msvcrt.inc
8. includelib user32.lib
9. includelib kernel32.lib
10. includelib msvcrt.lib
12. CONST1 equ 6
13. CONST2 equ 14 ;7,8,10,14
15. .data
16. A dd 5 ;10
17. B dd 7
18. fmt db ' %d',0
20. szPause db 'Pause',0
23. .code
24. ;****************************
25. start:
26. ;----------------------------
27. ;ebx = (A < B) ? CONST1 : CONST2;
28. ;**********法一**************
29. mov eax,A
30. cmp eax,B
31. jge L30
32. mov ebx,CONST1
33. jmp L31
34. L30:
35. mov ebx,CONST2
36. L31:
37. invoke crt_printf,offset fmt,ebx
38. ;**********法二**************
39. xor ebx, ebx ;clear ebx
40. mov eax,A
41. cmp eax, B
42. setl bl ;When ebx = 0 or 1
43. ;OR the complement condition
44. dec ebx ;ebx=00...00 or 11...11
45. and ebx, (CONST2-CONST1) ;ebx=0 or(CONST2-CONST1)
46. add ebx, CONST1 ;ebx=CONST1 or CONST2
48. invoke crt_printf,offset fmt,ebx
50. ;**********法三**************
51. xor ebx, ebx
52. mov eax, A
53. cmp eax, B
54. setge bl ; or the complement condition
55. lea ebx, [ebx*(CONST2-CONST1)+CONST1]
57. invoke crt_printf,offset fmt,ebx
61. invoke crt_system,offset szPause
62. invoke ExitProcess,0
64. end start

复制代码

G-Spider

下面这段文字很好理解，我就不翻译了，不经意看到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 [eax+7*8] 21 00000013 D8C9 fmul st0,st1 22 00000015 D8C1 fadd st0,st1 good! 26 00000020 DD4038 fld qword [eax+7*8] 27 00000023 D8C9 fmul st0,st1 28 00000025 F3 db 0F3H 29 00000026 D8C1 fadd st0,st1 good! 33 00000030 DC4C1818 fmul qword [eax+ebx+3*8] 34 00000034 DC4020 fadd qword [eax+4*8] 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 [eax+71*8] 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,[ecx] 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.

G-Spider

一直没找到一个比较好的处理器中文资料，今天总算找到了一个，再结合Intel文档，很不错。 Intel Nehalem-EP首发深度评测(一)　　 Intel Nehalem-EP首发深度评测(二)　 (***)　 强CPU20倍!正睿Tesla GPU计算系统评测! Intel 32nm Westmere-EP处理器首发评测

gxqcn

这个帖子不错，也比较耐读。

liangbch

Mark, 等有空儿时研读研读

liangbch

我写了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的分支预测效果很好。下面是运行结果

1. getMaxMin1 spend 0.006152 second on search max and min in 4194304 number
2. min=458,max=2147450654, from getMaxMin1
4. getMaxMin_asm spend 0.006186 second on search max and min in 4194304 number
5. min=458,max=2147450654, from getMaxMin1
7. getMaxMin_MT2 spend 0.003353 second on search max and min in 4194304 number
8. min=458,max=2147450654, from getMaxMin1
10. getMaxMin_MT4 spend 0.003441 second on search max and min in 4194304 number
11. min=458,max=2147450654, from getMaxMin1

复制代码

liangbch

这里给出C版和汇编版

1. void getMaxMin1(DWORD *pData,int len,DWORD *min,DWORD *max)
2. {
3. int i;
4. *min=~0;
5. *max=0;
6. for (i=0;i<len;i++)
7. {
8. if ( pData[i] > *max)
9. *max=pData[i];
10. if (pData[i]< *min)
11. *min=pData[i];
12. }
13. }
15. void getMaxMin_asm(DWORD *pData,int len,DWORD *min,DWORD *max)
16. {
17. DWORD _min, _max;
18. __asm
19. {
20. mov esi, pData
21. mov ecx, len
22. lea edi, [esi+ecx*4]
24. mov eax, 0xffffffff //min
25. mov edx, 0 //max
27. loop_start:
28. cmp esi, edi
29. jge next10
31. cmp [esi], eax
32. cmovb eax,[esi]
34. cmp [esi], edx
35. cmova edx,[esi]
37. add esi, 4
38. jmp loop_start
39. next10:
40. mov _min, eax
41. mov _max, edx
42. }
44. *min=_min;
45. *max=_max;
47. }

复制代码

G-Spider

有点意思，发现liangbch 与我的cpu一个型号，呵呵，我对第一个消除分支的测试了一下，发现有效果。(前后顺序不存在依赖关系) 结果：

1. Elapsed time:0.124000 s
2. Elapsed time:0.094000 s
3. Elapsed time:0.094000 s

复制代码

测试代码:

1. #include <stdio.h>
2. #include <time.h>
4. int main()
5. {
6. int i,j,ebx;
7. double t1,t2,t3;
8. //测试1#################
9. j=2009;
10. t1=clock();
11. for(i=0;i<99990000;i+=2,j-=10)
12. {
13. ebx = (i < j) ? 6 : 8;
14. }
15. printf("Elapsed time: %f s\n",(clock()-t1)/CLOCKS_PER_SEC);
17. //测试2#################
18. j=2009;
19. t2=clock();
20. for(i=0;i<99990000;i+=2,j-=10)
21. {
22. // GetMaxAsm(i,j);
23. __asm
24. {
25. xor ebx, ebx
26. mov eax, i
27. cmp eax, j
28. setl bl
29. dec ebx
30. and ebx, 2
31. add ebx, 6
32. }
33. }
35. printf("Elapsed time: %f s\n",(clock()-t2)/CLOCKS_PER_SEC);
39. //测试3#################
40. j=2009;
41. t3=clock();
42. for(i=0;i<99990000;i+=2,j-=10)
43. {
44. // GetMaxAsm(i,j);
45. __asm
46. {
47. xor ebx, ebx
48. mov eax, i
49. cmp eax, j
50. setge bl
51. lea ebx, [ebx*2+6]
52. }
53. }
55. printf("Elapsed time: %f s\n",(clock()-t3)/CLOCKS_PER_SEC);
57. system("Pause");
58. return 0;
59. }

复制代码

liangbch

刚刚查了下Intel CPU文档，发现可用SSE2指令 PMINUD, PMAXUD 求无符号整数最大最小值，用指令PMINSD, PMAXSD 求带符号整数最大最小值，有时间实现一下，看看速度如何。

gxqcn

PMINUD, PMAXUD 不是 SSE2 指令吧？应该是 SSE4 指令了。