论反汇编在时间常数优化中的应用

反汇编在常数因子优化中的应用程序优化是无止境的，其中常数因子也是决定程序运行快慢的关键之一。然而在竞赛中，渐进时间复杂度是人们关注的重点，而同样能够决定程序运行快慢的常数因子优化问题却缺乏重视。绪言在VisualC++语言环境下，从特定编译器生成的汇编代码出发，我探讨了反汇编在常数因子优化中的应用，并提出了若干优化改进方案。引例：关于memset函数的小实验已知memset函数为O(N)复杂度的语句。#includestring.hconstintTotal=1000000000;constintTime=你喜欢的合法的数值;charfield[Total/Time];inti,j;intmain(){for(;j10;j++)for(i=0;iTime;i++)memset(field,0,sizeof(field));return0;}你能直接答出Time值与运行速度的关系？观看右边的C++程序（假设计算机具有足够大的内存）012345678902468运行时间(秒)Time值的对数试验结果Debug模式Release模式分析可能你认为Time值不影响程序时间复杂度，因此对程序的速度无影响。Time值与运行速度的关系但是，当上机实验后，你会发现，Time值较大或较小时运行速度会变慢，这是为什么呢？#includestring.hconstintTotal=1000000000;constintTime=你喜欢的合法的数值;charfield[Total/Time];inti,j;intmain(){for(;j10;j++)for(i=0;iTime;i++)memset(field,0,sizeof(field));return0;}分析memset(table,0,sizeof(table));00401001xoreax,eax00401003movecx,9C40h00401008movedi,offsettable0040100Drepstosdwordptr[edi]Release模式下编译器对memset语句的处理如下Debug模式下编译器对memset语句的处理如下memset(field,0,sizeof(field));00411A6Bpush2710h00411A70push000411A72pushoffsetfield00411A77call@ILT+350(_memset)00411A7Caddesp,0Chmemset(field,0,sizeof(field));00411A6Bpush2710h00411A70push000411A72pushoffsetfield(4284E8h)00411A77call@ILT+350(_memset)00411A7Caddesp,0Chmemset(table,0,sizeof(table));00401001xoreax,eax00401003movecx,9C40h00401008movedi,offsettable0040100Drepstosdwordptr[edi]Windows分配内存第一层循环第二层循环额外汇编语句(pushcallretmovxor)真正作业(repstos)分析常数因子优化代码常数因子优化本质常数因子优化高级语言思路机器代码反汇编应用思想时间常数归类层次运算比例时间1.mov，lea数据移动运算1andorxornot逻辑运算add，sub加减法运算，test运算2.shl，shr，sal，sar位运算1.5~23.ptr取地址值，push+pop堆栈运算*2，jmp跳转运算44.mul，imul乘法55.div，idiv除法256.call+ret调用子函数+返回27数据分析一、关于调用常数因子的优化调用常数因子是指在函数调用过程中pushpop（有的编译器如VS.NET的cl用mov实现）和callret等汇编伪代码在调用过程中的耗费。虽然调用过程在Release模式下会被自动优化，但是在某些只提供Debug模式的竞赛环境中，我们该如何优化？所以本文主要阐述在Debug模式下的调用常数因子优化。我们常使用inline关键字对代码进行优化，但是，inline关键字对编译器的作用是提示性质的而不是强制性质的。测试调用的函数原形：inlinevoidswap(int&a,int&b){intt=a;a=b;b=t;}测试代码：swap(a,b);004133ADleaeax,[b]004133B0pusheax004133B1leaecx,[a]004133B4pushecx004133B5callswap(41158Ch)004133BAaddesp,8１、Debug模式1、不使用子函数2、使用宏定义１、Debug模式所以，在竞赛中应针对这个问题进行优化，这里本文提供了两种替代方案：inttmp;#defineswap(A,B)tmp=A,A=B,B=tmpintmain(){inta=3,b=4;swap(a,b);return0;}2、Release模式与Debug模式不同的是，在Release模式下，任何函数会被优先尝试作为inline函数，所以在代码中显式指定inline关键字仍然没有实际的作用。a++;0040105Baddeax,1swap(a,b);0040105Emovdwordptr[esp+8],eaxa*=b;printf(%d%d\n,a,i);return0;00401062imuleax,ecx测试voidswap(int&a,int&b){intt=a;a=b;b=t;}尽管没有inline关键字，在反汇编中已经看不到对swap的调用了正因为这样，在Debug模式和Release模式下，stl库的运行效率才会有巨大的差别。二、除法（求余）的优化(预备)预备知识：求余运算c=a%b等效于c=a-a/b*b但是，其内部实现直接使用除法的第二个返回值：a%=b;00411B53moveax,dwordptr[a]00411B56cdq00411B57idiveax,dwordptr[b]00411B5Amovdwordptr[a],edx除法指令idiv是一种比例时间很大的指令。编译器的设计者也知道这一点。所以大多数情况下编译器都能将常数除法转化为快得多的位运算。（注：编译器同样也会把特定的乘法转化为位运算，比如乘以２等）二、除法（求余）的优化比如，对于a/=2（a为32位整数）这句语句在Debug模式下的解释：a/=2;00411B4Fmoveax,dwordptr[a]00411B52cdq00411B53subeax,edx00411B55sareax,100411B57movdwordptr[a],eax这相对于执行idiv操作要快很多。但是，乘除法需要额外的特殊情况判断，如正负数、溢出等。这在代码中直接反映为冗余的汇编代码。所以，如果运算直接可用位运算代替，推荐使用位运算。但是，编译器的智能有很大的局限，比如在变量除变量时，编译器根本无法判断变量的特殊性，以至于编译器直接将语句翻译为div(idiv)操作。这样，如果除数有着特殊性，潜在的性能优化就没有被用到。二、除法（求余）的优化正确的方法是，判断出特殊性，使用手工的优化方式，如：优化后的代码：consta[]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096};c=b&(a[i]-1);d=e(i-1);原始代码：consta[]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096};c=b%a[i];d=e/a[i];二、除法（求余）的优化由于计算机内存是线性的，多维数组的元素在排列为线性序列后存入存储器，如下所示：0,00,10,20,31,01,11,21,32,02,12,22,33,03,13,23,3三、关于多维数组的性能优化0,00,10,20,31,01,11,21,32,02,12,22,33,03,13,23,3由于在结构上需要进行转换，多维数组的引址操作被翻译成了乘法操作。数组定义：a[10][10]Debug模式下，对数组的取值操作使用了imul运算（Release模式编译时会进行和乘法运算相同的优化）：returna[i][j];00411B6Fmoveax,dwordptr[i]00411B75imuleax,eax,28h00411B78leaecx,a[eax]00411B7Fmovedx,dwordptr[j]00411B85moveax,dwordptr[ecx+edx*4]三、关于多维数组的性能优化由于imul是一种比例时间较大的指令，如果能消去这一指令，便能够产生较大幅度的优化。三、关于多维数组的性能优化returna[i][j];00411B6Fmoveax,dwordptr[i]00411B75imuleax,eax,28h00411B78leaecx,a[eax]00411B7Fmovedx,dwordptr[j]00411B85moveax,dwordptr[ecx+edx*4]如果操作的变址方法固定（比如像宽度优先搜索，变址操作为+1,-1,+N,-N），那么用指针加减操作以及辅助记录就能获得更快的速度（消去了乘法操作）。定义表和指针：inttable[200][200];int*ptr,*ptr2;定义滑动常数：//East,South,West,Northconstgo[]={1,200,-1,-200};//假设ptr已赋值ptr2=ptr+go[0];00411A4Cmoveax,dwordptr[go]00411A51movecx,dwordptr[ptr]00411A57leaedx,[ecx+eax*4]00411A5Amovdwordptr[ptr2],edxreturn*ptr2;00411A60moveax,dwordptr[ptr2]00411A65moveax,dwordptr[eax]这样本来隐藏的乘法操作就被消去了。三、关于多维数组的性能优化这种操作被我称为指针的“行走”操作。使用这个优化有个条件，就是指针变化方式固定。让我们通过一个例子来了解这种优化的作用。三、关于多维数组的性能优化题意描述：在N*M的矩阵中，有一些障碍，有一个物体放在某个格子上。它会按照一个时间表向某一方向运动，一个时间单位移动１格。某一秒你可以让它运动，也可以让它静止。问物体最多能运动的长度。时间表由很多个时间片段构成，在每个时间片断中，物体将向同一方向运动。数据规模：50%的数据中，1≤N,M≤200，时间长度(T)≤200；100%的数据中，1≤N,M≤200，时间片段个数(K)≤200，时间长度(T)≤40000。例：adv1900(NOI2005)这道题有很多做法，其中最优做法是使用单调性降维。无论用什么方法，都必经一个关键步骤，这就是在不同的时间点间进行状态转移，并且，都要将这一步“批处理”化。最优做法的单调性降维，以及其他各式各样的优化，如堆和RMQ等，都是基于对这一步骤的渐进时间复杂度的优化。例：adv1900(NOI2005)但是，利用“行走”操作，我们完全可以另辟蹊径。基于此步骤具有的使用优化的典型特点：（1）位于循环最里层，直接影响运行速度；（2）大量使用对数组的变化方式固定的操作，可以用指针“行走”来优化。虽然最终还是使用“批处理化”的思想，但是这种方法没有把精力用在渐进复杂度的优化上，而转向到了具体的实现上。例：adv1900(NOI2005)本题的移动情况可以靠在移动前进行对变量的初始化实现。在某个时间段中对前面位置的询问可以用反方向“行走”实现。对于取址运算中的位运算，可以用强制转换指针的方法消去。对障碍判断的实现可以用统一变量格式实现。例：adv1900(