算法合集之《论反汇编在时间常数优化中的应用》

2006年全国信息学冬令营讲座论反汇编在时间常数优化中的应用四川省成都七中 周以苏 摘要：本文阐述了时间常数优化的重要性，并且在Visual C+语言环境下，从特定编译器生成的汇编代码出发，探讨了反汇编在时间常数优化中的应用，提出了若干优化改进方案。关键字：C+ 反汇编 时间常数 优化程序的优化是无止境的。其中，时间常数是在相同时间复杂度下决定程序运行快慢的关键。然而在竞赛中，渐进时间复杂度是关注的重点，而同样能够决定程序运行快慢的时间常数优化问题却缺乏重视。本文阐述了时间常数优化的重要性，并且在Visual C+语言环境下，从特定编译器生成的汇编代码出发，探讨了反汇编在时间常数优化中的应用，提出了若干优化改进方案。一、基本概念汇编语言（Assembly language），是一种与硬体紧密相关的程序设计语言，是一种低级语言。汇编语言是机器语言的便于记忆和理解的符号化形式。由于汇编语言的各种语法规范互不兼容，本文以下部分以Intel语法为基础，并以使用Intel语法的Visual C+作为实验平台。汇编语言源程序是用伪代码创建的。一个伪代码是一条处理器可以理解的指令。例如： addadd指令把两个数加到一起。大部分伪代码带有参数 add eax, edxadd有两个参数。一个源参数，一个目标参数。它把源值加到目标值中，并把结果保存在目标中。参数有很多不同的类型，如：寄存器，内存地址，直接数值。下面的介绍以寄存器为例。有几种大小的寄存器：4位，8位，16位，32位（在MMX处理器中有更多的种类）。在16位程序中，你仅能使用4位、8位和16位的寄存器。在32位的程序中，你还可以使用32位的寄存器。一些寄存器是别的寄存器的一部分：例如，如果eax保存了值EA7823BBh，那么，它的子寄存器ax，ah和al也会保存其值的一部分，如下表所示： eax EA 78 23 BBax 23 BBah 23al BBax，ah，al是eax的一部分。eax是一个32位的寄存器（仅在386以上存在），ax包含了eax的低16位（2字节），ah包含了ax的高字节，而al包含了ax的低位字节。因而ax是16位的，al和ax是8位的。让我们来分析下面的代码： mov eax, 12345678h;Mov把一个值载入寄存器（注意：12345678h是一个十六进制值，因为h这个后缀。mov cl, ah;把ax的高字节移入cl sub cl, 10;从cl的值中减去10（十进制） mov al, cl;并把cl存入eax的最低字节 mov指令可以把一个值从寄存器，内存或直接数值移入另一个寄存器。在上面的例子中，eax包含了12345678h，然后ah的值（eax左数第三个字节）被复制入了cl中（ecx寄存器的最低字节）。然后，cl减10并移回al中（eax的最低字节） 关于汇编指令的其它基础知识，请参看相关的入门书籍。编译器(Compiler)，是将便于人编写，阅读，维护的高级计算机语言程序翻译为计算机能识别，运行的低级机器语言的程序。编译器将源程序（Source program）作为输入，翻译产生使用目标语言（Target language）的等价程序。源程序一般为高级语言（High-level language），如Pascal，C+等所写的程序，而目标程序则是机器能直接执行的目标代码（Object code），有时也称作机器代码（Machine code）。编译器友好(Compiler friendly)，是指所写的代码符合编译器的规范，其功能的完整性不依赖于特定编译器的特性或隐藏功能，因此具有通用性和兼容性。本文的结论不一定需要用汇编实现，因为嵌入汇编不是所有语言都能够支持的，况且这样做不是文章的本意。二、数据分析在特定的平台上，不同的汇编伪代码有着不同的执行速度。但是，每种功能的伪代码的相对执行速度是较为恒定的。比如，执行乘除法伪代码的时间一定大大长于执行加减法伪代码的时间。表1为Aoa1中8286系统各种伪代码的理论执行时间：表1：8286指令集的执行时间为了验证上表的结论以及探讨从反汇编角度对程序进行改进的可行性，本文对实际语句的运行情况进行了数据搜集。本文采用的实验环境如下：试验环境：软件：Windows XP sp2 050301-1519 MSVC+ 69514-335-0000007-18650硬件：Intel Pentium 4 CPU 2.66GHzDebug模式等同于非优化模式等同于不带参数进行编译Release模式等同于优化模式约等于G+中-O2优化注意：本文的某些结论并不适用于其他处理器、平台和编译器，需要再次进行测试。测试方法：在速度测试中，实验使用了一个基准的C+程序模版。#include #include clock_t start,finish;int a;int main() start=clock(); _asm mov ecx,2000000000 /实验次数testBegin: mov eax,10 mov ebx,10 cdq/这里插入实验语句 dec ecx jz testEnd jmp testBegintestEnd: finish=clock(); printf(%.3lf,double(finish-start)/CLOCKS_PER_SEC); return 0;本文对附录中Configure.in文件中引用的操作进行了测试。通过执行附录中的Python脚本，得出了表2的结果：表2：在测试环境下各个指令实际运行时间及比例测试操作平均用时相对用时比例EMPTY（无实验语句）2.29 0.00 0.0 NORMAL IMUL3.81 1.52 11.0 NORMAL IDIV25.94 23.65 171.2 NORMAL TEST2.43 0.14 1.0 NORMAL MOV2.29 0.00 (0.0)NORMAL ADD2.41 0.12 0.9 NORMAL INC3.05 0.76 5.5 NORMAL SUB2.41 0.12 0.9 NORMAL DEC3.05 0.76 5.5 NORMAL XOR2.35 0.06 0.4 NORMAL AND2.35 0.06 0.4 NORMAL SHL2.44 0.15 1.1 NORMAL SAR2.44 0.15 1.1 NORMAL SHR2.44 0.16 1.1 NORMAL NOT2.29 0.00 (0.0)NORMAL XCHG3.04 0.76 5.5 PTR MOV2.28 0.00 (0.0)PTR ADD3.05 0.76 5.5 PTR SUB3.05 0.76 5.5 PTR XOR3.05 0.76 5.5 PTR AND3.05 0.76 5.5 PTR XCHG67.39 65.10 471.2 JMP3.14 0.85 6.2 PUSH POP3.05 0.76 5.5 CALL RET JMP9.16 6.88 49.8 EMPTY(Verify)2.29 0.00 0.0 注：1、测试结果有误差，并且会随着操作系统、编译器和系统配置的变化而不同程度的波动。2、具体测试语句见附录Configure.in3、由于处理器对程序的执行并不是像想象中那样一句一句直接执行，其中还涉及到代码解释缓存、L1、L2变量长度(16,32)等因素的影响，本试验的数据只作为理论的近似。基于上面得到的结果，本文将各类语句时间常数归类为了下列6个层次（见表3）：表3：汇编语句速度分类层次运算比例时间1、 mov，lea（未进行测试）数据移动运算1and or xor not逻辑运算add，sub加减法运算，test置位运算（内部为sub运算）2、 shl，shr，sal，sar位运算1.523、 ptr取地址值（不是运算），push+pop堆栈运算*2，jmp跳转运算44、 mul，imul乘法55、 div，idiv除法256、 call+ret 调用子函数+返回27从这6个层次中，我们可以看到汇编代码执行的快慢程度，因此，如果我们能够从汇编角度出发，把比例时间较大的操作消去或转化为比例时间较小的操作组合，那么，我们就达到了对时间常数进行优化的目的。本文通过如下实例分析进一步说明了竞赛中反汇编在时间常数优化中的应用。三、实例分析3.1 关于memset函数的小实验已知memset函数为一个O(N)复杂度的语句。让我们先做一个小实验，观看下面的C+程序（假设计算机具有足够大的内存）：#include const int Total=1000000000;const int Time=一个你喜欢的合法的数值;char fieldTotal/Time;int i,j;int main()for (j=0;j10;j+)for (i=0;iTime;i+)memset(field,0,sizeof(field);return 0;先不忙运行这段程序。你能直接答出Time值与运行速度的关系吗？可能你认为Time值对速度无影响，因为程序的时间复杂度守恒。但是，当上机实验后，你会发现，在Time值为100000左右时程序运行最快，而Time值更小或更大时程序运行速度会显著降低，如下图所示：这是为什么呢？关于Time值较小时程序运行速度变慢的问题，我们可以用Windows进行内存分配需要时间这个理论来解释。当Time值变大时，由于循环和memset函数在时间常数上存在差异最终导致了运行速度的变慢。下面从反汇编角度证明Time值较大时程序运行速度变慢的理论。rep stos的指令速度很快，每次执行大概只占用1个单位的时间，而能完成填值和循环变量减1的操作，而循环需要使用对变量的赋值操作，还需要进行跳转，大概一次占用14个单位的时间，这样由于常数存在差异，所以导致了Time值较大时程序运行速度慢。为什么Debug模式和Release模式在右端存在效率差异呢？在C+语言中，我们把memset作为一个函数进行调用。但其实，系统中有专门的汇编伪代码实现相同的工作(rep stos)。例如，在Release模式下，编译器对memset进行了优化，编译为如下所示的汇编代码：memset(table,0,sizeof(table);00401001 xoreax,eax 00401003 movecx,9C40h 00401008 movedi,offset table (4072C8h) 0040100D rep stosdword ptr edi 在Debug模式下，虽然memset过程的核心也是rep stos，但由于memset是一个函数，系统将使用push+call+ret语句组合进行调用，所以实际消耗了更多的时间，最终导致了在Time值较大的时候程序运行时间较长。Debug模式下编译器对memset过程处理如下：memset(field,0,sizeof(field);00411A6B push2710h 00411A70 push0 00411A72 pushoffset field (4284E8h) 00411A77 callILT+350(_memset) (411163h) 00411A7C addesp,0Ch 在Debug模式下，memset的实现耗费了更多的常数复杂度，因此Debug模式时的运行曲线在右端高于Release模式。memset过程的实现（原代码）参见附录。上述分析可见，时间常数对程序的速度有一定的影响。通过memset不同的实现效率不同这个现象，我们可以发现，对程序进行优化是可能的。3.2 关于调用时间常数的优化调用时间常数是指在函数调用过程中push pop（有的编译器如VS.NET的cl用mov实现）和call ret等函数语句在调用过程中的耗费。调用过程在Debug和Release模式下有着截然不同的差别。下面分两部分分别叙述：Debug模式：我们常使用inline关键字对代码进行优化，但是，inline关键字对编译器的作用是提示性质的而不是强制性质的（在Visual Studio环境下是这样，在竞赛环境(GCC不带参数)下inline关键字为折衷模式：使用即编译为内联函数，不使用则编译为普通函数）。测试调用的函数原形：inline void swap(int&a,int&b)int t=a;a=b;b=t;测试代码：swap(a,b);004133AD leaeax,b 004133B0 pusheax 004133B1 leaecx,a 004133B4 pushecx 004133B5 callswap (41158Ch) 004133BA addesp,8转向经过下表：0041157D jmp_aligned_free_dbg (41B4D0h) 00411582 jmp_RTC_GetErrorFunc (416C30h) 00411587 jmpGetStringTypeW (425788h) 0041158C jmpswap (411B20h) 00411591 int3 00411592 int3 这样，程序的常数就因为额外的call+ret语句而变大了。不仅如此，微软为了方便建立断点进行程序的调试，在Debug模式下会在内存中创建跳转表，但是这进一步加大了程序的常数L。我们可以稍加想象。比如编译器对stl库函数的实现。stl库函数的C+代码实现中使用了大量的继承和重载，因此就算是一个简单的操作都要进行很多很多层的迭代（用反汇编模式调试对stl库函数的调用时可以很直观的理解这一点）。所以，在我们的程序中，应该针对这个问题进行优化。这里，我提供了两种替代方案：1、不使用子函数：这是最直接的方法。如果没有子函数，当然也就没有了调用的时间开销。但是，这样的程序会产生代码过长和调试纠错困难等问题，所以请酌情使用。2、使用宏定义：宏定义有很多的局限，比如只是机械展开，但是一些简单的，但又经常调用的功能，用宏定义实现就比用函数实现减少了调用操作的消耗。虽然不推荐在define块中定义变量（很可能会遇到难以估计的问题），但是用全局变量可以解决同样的问题。如下例就巧妙地解决了swap的临时变量问题。int tmp;#define swap(A,B) tmp=A,A=B,B=tmpint main()int a=3,b=4;swap(a,b);return 0;但是，宏定义也有很多不足，比如只是机械展开等，下面的代码可以展示什么叫做机械展开：代码：#include #include int getRand()int _t=rand();printf(Call getRand return %dn,_t);return _t;#define max(A,B) (A)(B)?(A):(B)int main()srand(543210);printf(Get the max value: %dn,max(getRand(),getRand();return 0;运行结果（恒定）：Call getRand return 4461Call getRand return 14545Call getRand return 3994Get the max value: 3994Release模式：与Debug模式不同的是，在Release模式下，任何函数会被优先尝试作为inline函数，所以在代码中显式指定inline关键字仍然没有实际的作用。测试void swap(int&a,int&b)int t=a;a=b;b=t;尽管没有inline关键字，在反汇编中已经看不到对swap的调用了a+;0040105B addeax,1 swap(a,b);0040105E movdword ptr esp+8,eax a*=b;printf(%d%dn,a,i);return 0;00401062 imuleax,ecx但是这并不是一个沮丧的消息，因为，在stl库中，几乎所有的函数都没有带inline关键字，尽管这样，这些函数都将被编译为内联函数。这就减少了call+ret带来的时间常数。正因为这样，在Debug模式和Release模式下，stl库的运行效率才会有巨大的差别。3.3 除法（求余）的优化求余运算c=a%b等效于c=a-a/b但是，其内部实现直接使用除法的第二个返回值：a%=b;00411B53 moveax,dword ptr a 00411B56 cdq 00411B57 idiveax,dword ptr b 00411B5A movdword ptr a,edx 所以求余运算的速度和对应的除法相等，优化方法也相似。按照上面测试的结果，除法指令idiv是一种比例时间很大的指令。编译器的设计者也知道这一点。所以大多数情况下编译器都能将常数除法转化为快得多的位运算。（注：编译器同样也会把特定的乘法转化为位运算，比如乘以等）比如，对于a/=2（a为32位整数）这句语句在Debug模式下的解释：a/=2;00411B4F moveax,dword ptr a 00411B52 cdq 00411B53 subeax,edx 00411B55 sareax,1 00411B57 movdword ptr a,eax 这相对于执行idiv操作要快很多。但是，乘除法需要额外的特殊情况判断，如正负数、溢出等。这在代码中直接反映为冗余的汇编代码。所以，如果运算直接可用位运算代替，推荐使用位运算。但是，编译器的智能有很大的局限L，比如在变量除变量时，编译器根本无法判断变量的特殊性，以至于编译器直接将语句翻译为idiv操作。这样，如果除数有着特殊性，潜在的性能优化就没有被用到。正确的方法是，判断出特殊性，使用手工的优化方式，如：原始代码：const a=1,2,4,8,16,32,64,128,256,512,1024,2048,4096;.c=b%ai;d=e/ai;优化后的代码：const a=1,2,4,8,16,32,64,128,256,512,1024,2048,4096;.c=b&(ai-1);d=e(i-1);3.4 关于多维数组的性能优化数组是高级语言中几乎必然具备的数据结构。数组将多个数据收集到一个变量中。单个索引号（用于一维数组）或者多个索引号（用于嵌套的数组或多维数组）引用数组中的数据。若要引用数组中的单个元素，可以使用后面跟数组索引（数组索引放在方括号 () 中）的数组标识符。若要引用整个数组，则只需使用数组标识符。将数据收集到数组中可简化数据管理。例如，通过使用数组，向函数传递参数时使用一个标识符便能够表示一组数据。多维数组在内存中是呈平坦展开的，如下图所示：有如下二维数组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,2由于在结构上需要进行转换，多维数组的引址操作在Debug编译时被翻译成了乘法操作。Release模式编译时会进行和乘法运算相同的优化。数组定义：a1010Debug模式下，对数组的取值操作使用了imul运算：return aij;00411B6F moveax,dword ptr i 00411B75 imuleax,eax,28h 00411B78 leaecx,aeax 00411B7F movedx,dword ptr j 00411B85 moveax,dword ptr ecx+edx*4 Release模式下，数组的取值操作被优化为了lea以及变址运算，这类似于乘法的优化：return aij;0040102E moveax,dword ptr esp+18h 00401032 leaedx,eax+eax*4 00401035 moveax,dword ptr esp+14h 00401039 addesp,0Ch 0040103C leaecx,eax+edx*2 0040103F moveax,dword ptr esp+ecx*4+10h由于imul是一种比例时间较大的指令，因此如果能在运算中消去这一指令，便能够产生较大幅度的速度的优化。所以，一种很巧妙的优化方式就产生了：如果操作的变址方法固定（比如像宽度优先搜索，变址操作为+1,-1,+N,-N），那么用type*指针加减操作以及辅助记录要更快一些（省去了乘法操作）。下面是实验的证实：数组定义：d1010使用操作取值：a=dij;00411B55 moveax,dword ptr i (42B694h) 00411B5A imuleax,eax,28h 00411B5D movecx,dword ptr j (42B690h) 00411B63 movedx,dword ptr eax+ecx*4+42B500h 00411B6A movdword ptr a (42B6A0h),edx使用指针取值：b=*dd;00411B8B moveax,dword ptr dd (42B69Ch) 00411B90 movecx,dword ptr eax 00411B92 movdword ptr b (42B698h),ecx对指针的滑动操作可以用一个常量数组定义或者用多段代码的方式实现，如下面所示：定义表和指针：int table200200;int*ptr,*ptr2;定义滑动常数：/East,South,West,Northconst go=1,200,-1,-200;使用时的代码：/假设ptr已赋值ptr2=ptr+go0;00411A4C mov eax,dword ptr go (42401Ch) 00411A51 mov ecx,dword ptr ptr (44F5E8h) 00411A57 lea edx,ecx+eax*4 00411A5A mov dword ptr ptr2 (4284E0h),edx return *ptr2;00411A60 mov eax,dword ptr ptr2 (4284E0h) 00411A65 mov eax,dword ptr eax这样本来隐藏的乘法操作就被消去了。这种操作被我称为指针的“行走”操作。使用这个优化有个条件，就是指针变化方式固定。让我们通过一个例子来了解这种优化的作用：例：adv1900 (NOI2005)题意描述：在N*M的矩阵中，有一些障碍，有一个物体放在某个格子上。它会按照一个时间表向某一方向运动，一个单位格。某一秒你可以让它运动，也可以让它静止。问物体最多能运动的长度。时间表由很多个时间片段构成，在每个时间片断中，物体将向同一方向运动。数据规模：50%的数据中，1N, M200，时间长度(T)200；100%的数据中，1N, M200，时间片段个数(K)200，时间长度(T)40000。这道题有很多的做法，其中最优的做法是使用单调性降维。无论用什么方法，在解决这道题的过程中，都必经一个关键的步骤，这就是在不同的时间点间进行的状态转移。在最优做法中，这一步被“批处理”化了，一次操作就能够完成一个时间段（多个不同的时间点）的转移。同样，其他各式各样的优化，如堆和RMQ等，也是基于“批处理”化的思想。但是，在有了上文的实验结论后，我们完全可以另辟蹊径，得到一种很“另类”的解决方法。这基于此步骤具有的使用优化的典型特点：位于循环最里层，直接影响运行速度；大量使用对数组的变化方式固定的操作，可以用指针“行走”来优化。具体实现参考附录。下面是该方法的速度与优化前的对比：表3：“行走”优化方法本题总得分100，有效用时3.594s。520KB0.797s正确9520KB0.484s正确8520KB0.734s正确7520KB0.547s正确6520KB0.703s正确5520KB0.234s正确4520KB0.047s正确3520KB0.016s正确2520KB0.016s正确1520KB0.016s正确0内存时间评测结果编号试题：adv1900 文件名：adv1900选手名称：withWalk表4：非“行走”优化方法本题总得分100，有效用时5.064s。520KB1.156s正确9520KB0.625s正确8520KB1.031s正确7520KB0.781s正确6520KB1.016s正确5520KB0.344s正确4520KB0.063s正确3520KB0.016s正确2520KB0.016s正确1520KB0.016s正确0内存时间评测结果编号试题：adv1900 文件名：adv1900选手名称：withoutWalk注：该表以毫秒为单位虽然和标准方法的速度(最大点0.3s)有很大差距，但是，使用这种方法，能够让几乎人人都能想出的“初级方法”在时限内通过所有测试！四、总结本文主要从C+语法的特定编译器生成的汇编代码以及各种汇编代码的速度角度探讨了各种操作的时间常数，并通过一些实例从反汇编角度分析了影响时间常数的原因，提出了优化改进方案。汇编语言，是最接近于计算机本质的程序设计语言。由于其特殊的性质，它也是最难掌握和最难调试的语言之一。但是，在很好的掌握和使用后，其高速、高效、简洁的优美性质也是一把削铁如泥的利刃。俗话说，万变不离其宗，高级语言究其本质也是用汇编语言实现的。所以，在对效率日益要求严格的今天，了解语言的“习性”是至关重要的。我相信，在了解了汇编语言的特性后，无论是一般的编程，还是在竞赛中，充分应用汇编语言的特性，一定能够使运行速度再上一个台阶，从而更快更好的解决实际问题。致谢：首先我要感谢张君亮老师多年来对我的悉心指导，为我的成长倾注了大量的心血；感谢电子科技大学的陈文宇老师对我论文的修改和建议；感谢班主任张建成老师对我的关心和支持；感谢闵可锐、白云峰、杨双、王凯同学与我的许多有益的讨论。【参考文献】1The art of assembly language2MSDN China (Visual C+ part)3National Olympaid in Informatics(NOI) 2005附录名称文件测试库(近似语句速度判定)另外一个测试由类似过程生成Visual Studio中的memset函数汇编实现Adv1900指针行走和未优化程序