还能优化吗？

littlekevin

插入排序法

1. BRANCH_TAKEN MACRO
   
2.                 DB 3EH
   
3. ENDM
   
4. 
   
5. BRANCH_NOT_TAKEN MACRO
   
6.                 DB 2EH
   
7. ENDM
   
8. 
   
9. MAX_BYTE        EQU     0FFH
   
10. 
    
11. ;EBX:POINTER TO ARRAY
    
12. ;ECX:ARRAY LENGTH
    
13. INSERTIONSORT   PROC
    
14.                 LEA     ESI,[EBX+ECX]
    
15.                 PUSH    DWORD PTR [ESI]
    
16.                 PUSH    ESI
    
17.                 MOV     BYTE PTR [ESI],MAX_BYTE
    
18.                
    
19.                 SUB     ECX,2
    
20.                
    
21. LOOP1:          LEA     ESI,[EBX+ECX]
    
22.                 MOV     AL,[ESI]
    
23.                 JMP     LOOP2ENTRY
    
24.                
    
25. LOOP2:          MOV     [ESI],DL
    
26.                 ADD     ESI,1
    
27. LOOP2ENTRY:     MOV     DL,[ESI+1]
    
28.                 CMP     AL,DL
    
29. ENDLOOP2:       JA      LOOP2
    
30.                
    
31.                 MOV     [ESI],AL
    
32.                
    
33.                 SUB     ECX,1
    
34.                 BRANCH_TAKEN
    
35. ENDLOOP1:       JNC     LOOP1
    
36.                
    
37.                 POP     ESI
    
38.                 POP     DWORD PTR [ESI]
    
39.                 RET
    
40. INSERTIONSORT   ENDP

复制代码

仙剑魔

汇编厄...

littlekevin

是的...

acme_pjz

为什么 SUB     ECX,1 而不是 dec ecx？

还有就是那个BRANCH_TAKEN “3E”是什么汇编指令？还有那个数组除了长度为Length以外还要附加4字节的额外长度，是不是临时变量啊？如果临时变量不用复原的话那么Push和Pop好像都可以省略吧……

[ 本帖最后由 acme_pjz 于 2009-2-5 17:14 编辑 ]

littlekevin

sub ecx,1比dec ecx快。
branch_taken是指令前缀，告诉cpu如何预测分支。
那个不是临时变量..是减少分支的一个小技巧..

littlekevin

原来每个循环需要检测2次：比较大小和是否到最后一个元素

1. 
   
2. Do
   
3. ...
   
4. If j=num Then Exit Do
   
5. Loop While tmp>data(j+1)

复制代码

现在在数组最后加了一个255，是最大的byte
因此如果比较到最后一个就会停下来，因为任何byte都不会比255大

1. 
   
2. Do
   
3. ...
   
4. Loop While tmp>data(j+1)

复制代码

每次循环减少了一次判断，减少一个分支，而且这个分支不好预测（如果数组是排序好的则每次都不分支，如果数组是倒序则每次都分支）

PctGL

照你的思路也一定说 add 比 inc 快了。。。
还有比 inc,dec 更快的指令吗...

分支预测是基于cpu内部的状态标志，你的那个宏，说是技巧从哪里来的呢？
分支预测的是基于概率的，并不依赖某个指令的影响，jmp 指令同样执行分支预测

[ 本帖最后由 PctGL 于 2009-2-5 18:59 编辑 ]

littlekevin

不是指令..是前缀..intel的官方文档说的

add确实比inc快，因为inc不改变carry flag，可能会导致对前一个指令的错误依赖（false dependent）
add一个时钟周期可以执行4个，inc只能有2个

agner fog的intel优化指南：

[ 本帖最后由 littlekevin 于 2009-2-5 19:34 编辑 ]

littlekevin

intel官方文档，看第34页

PctGL

第3章第34页？ adc 那页？
没看到哪写着占用时钟周期的长度呢？

我发现语言学的xx了：

》add确实比inc快，因为inc不改变carry flag，可能会导致对前一个指令的错误依赖（false dependent）
inc 就是因为不影响标志位，所以对他本身的执行效率来讲也是有所增强的，而且很多时候我们需要的就是不影响标志位的操作，能被你解释成错误依赖。。。。

》add一个时钟周期可以执行4个，inc只能有2个
完全错误的说法
你对指令占用cpu时钟周期的理解正好颠倒了...而且怎么感觉你对80486的cpu不熟悉的样子

[ 本帖最后由 PctGL 于 2009-2-5 20:03 编辑 ]