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

反汇编在常数因子优化中的应用四川省成都七中周以苏

然而在竞赛中，渐进时间复杂度是人们关注的重点，而同样能够决定程序运行快慢的常数因子优化问题却缺乏重视。在VisualC++语言环境下，从特定编译器生成的汇编代码出发，我探讨了反汇编在常数因子优化中的应用，并提出了若干优化改进方案。程序优化是无止境的，其中常数因子也是决定程序运行快慢的关键之一。绪引例：关于memset函数的小实验已知memset函数为O(N)复杂度的语句。你能直接答出Time值与运行速度的关系？观看右边的C++程序（假设计算机具有足够大的内存）

分析可能你认为Time值不影响程序时间复杂度，因此对程序的速度无影响。Time值与运行速度的关系但是，当上机实验后，你会发现，Time值较大或较小时运行速度会变慢，这是为什么呢？

分析Time值较大时，我们可以从反汇编角度解释程序运行速度变慢的原因。（如下）Time值较小时程序运行速度慢的原因，我们可以用Windows进行内存分配需要时间这个理论来解释。

分析Release模式下编译器对memset语句的处理如下Debug模式下编译器对memset语句的处理如下

分析

常数因子优化代码常数因子优化本质常数因子优化高级语言思路机器代码反汇编应用思想

时间常数归类数据分析

调用常数因子是指在函数调用过程中pushpop（有的编译器如VS.NET的cl用mov实现）和callret等汇编伪代码在调用过程中的耗费。虽然调用过程在Release模式下会被自动优化，但是在某些只提供Debug模式的竞赛环境中，我们该如何优化？所以本文主要阐述在Debug模式下的调用常数因子优化。一、关于调用常数因子的优化

１、Debug模式我们常使用inline关键字对代码进行优化，但是，inline关键字对编译器的作用是提示性质的而不是强制性质的。测试调用的函数原形：inlinevoidswap(inta,intb){intt=a;a=b;b=t;}测试代码：

１、Debug模式1、不使用子函数2、使用宏定义所以，在竞赛中应针对这个问题进行优化，这里本文提供了两种替代方案：

2、Release模式与Debug模式不同的是，在Release模式下，任何函数会被优先尝试作为inline函数，所以在代码中显式指定inline关键字仍然没有实际的作用。测试voidswap(inta,intb){intt=a;a=b;b=t;}尽管没有inline关键字，在反汇编中已经看不到对swap的调用了正因为这样，在Debug模式和Release模式下，stl库的运行效率才会有巨大的差别。

二、除法（求余）的优化(预备)预备知识：求余运算c=a%b等效于c=a-a/b*b但是，其内部实现直接使用除法的第二个返回值：

除法指令idiv是一种比例时间很大的指令。编译器的设计者也知道这一点。所以大多数情况下编译器都能将常数除法转化为快得多的位运算。（注：编译器同样也会把特定的乘法转化为位运算，比如乘以２等）除法（求余）的优化12

二、除法（求余）的优化比如，对于a/=2（a为32位整数）这句语句在Debug模式下的解释：这相对于执行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];

三、关于多维数组的性能优化由于计算机内存是线性的，多维数组的元素在排列为线性序列后存入存储器，如下所示：

由于在结构上需要进行转换，多维数组的引址操作被翻译成了乘法操作。数组定义：a[10][10]Debug模式下，对数组的取值操作使用了imul运算（Release模式编译时会进行和乘法运算相同的优化）：三、关于多维数组的性能优化

三、关于多维数组的性能优化由于imul是一种比例时间较大的指令，如果能消去这一指令，便能够产生较大幅度的优化。如果操作的变址方法固定（比如像宽度优先搜