《2006年国家集训队论文_论反汇编在时间常数优化中的应用(PPT报告).pptx》由会员分享,可在线阅读,更多相关《2006年国家集训队论文_论反汇编在时间常数优化中的应用(PPT报告).pptx(29页珍藏版)》请在工友文库上搜索。
1、反汇编在常数因子优化中的应用,程序优化是无止境的,其中常数因子也是决定程序运行快慢的关键之一。,然而在竞赛中,渐进时间复杂度是人们关注的重点,而同样能够决定程序运行快慢的常数因子优化问题却缺乏重视。,绪言,在Visual C+语言环境下,从特定编译器生成的汇编代码出发,我探讨了反汇编在常数因子优化中的应用,并提出了若干优化改进方案。,引例:关于memset函数的小实验,已知memset函数为O(N)复杂度的语句。,你能直接答出Time值与运行速度的关系?,观看右边的C+程序 (假设计算机具有足够大的内存),分析,可能你认为Time值不影响程序时间复杂度,因此对程序的速度无影响。,Time值与运
2、行速度的关系,但是,当上机实验后,你会发现,Time值较大或较小时运行速度会变慢,这是为什么呢?,分析,Time值较大时,我们可以从反汇编角度解释程序运行速度变慢的原因。(如下),Time值较小时程序运行速度慢的原因,我们可以用Windows进行内存分配需要时间这个理论来解释。,分析,Release模式下编译器对memset语句的处理如下,Debug模式下编译器对memset语句的处理如下,分析,常数因子优化,代码常数因子优化,本质常数因子优化,高级语言,思路,机器代码,反汇编,应用思想,时间常数归类,数据分析,一、关于调用常数因子的优化,调用常数因子是指在函数调用过程中push pop(有的
3、编译器如VS.NET的cl用mov实现)和call ret等汇编伪代码在调用过程中的耗费。 虽然调用过程在Release模式下会被自动优化,但是在某些只提供Debug模式的竞赛环境中,我们该如何优化?所以本文主要阐述在Debug模式下的调用常数因子优化。,我们常使用inline关键字对代码进行优化,但是,inline关键字对编译器的作用是提示性质的而不是强制性质的。,测试调用的函数原形: inline void swap (int 测试代码:,、Debug模式,1、不使用子函数 2、使用宏定义,、Debug模式,所以,在竞赛中应针对这个问题进行优化,这里本文提供了两种替代方案:,2、Relea
4、se模式,与Debug模式不同的是,在Release模式下,任何函数会被优先尝试作为inline函数,所以在代码中显式指定inline关键字仍然没有实际的作用。,测试 void swap(int 尽管没有inline关键字,在反汇编中已经看不到对swap的调用了,正因为这样,在Debug模式和Release模式下,stl库的运行效率才会有巨大的差别。,二、除法(求余)的优化(预备),预备知识: 求余运算c=a%b等效于c=a-a/b*b但是,其内部实现直接使用除法的第二个返回值:,除法指令idiv是一种比例时间很大的指令。编译器的设计者也知道这一点。所以大多数情况下编译器都能将常数除法转化为快
5、得多的位运算。 (注:编译器同样也会把特定的乘法转化为位运算,比如乘以等),二、除法(求余)的优化,比如,对于a/=2(a为32位整数)这句语句在Debug模式下的解释:,这相对于执行idiv操作要快很多。但是,乘除法需要额外的特殊情况判断,如正负数、溢出等。这在代码中直接反映为冗余的汇编代码。所以,如果运算直接可用位运算代替,推荐使用位运算。,但是,编译器的智能有很大的局限,比如在变量除变量时,编译器根本无法判断变量的特殊性,以至于编译器直接将语句翻译为div(idiv)操作。这样,如果除数有着特殊性,潜在的性能优化就没有被用到。,二、除法(求余)的优化,正确的方法是, 判断出特殊性, 使用
6、手工的优化方式, 如:,优化后的代码: const a=1,2,4,8,16,32,64,128,256,512,1024,2048,4096; c=b,原始代码: const a=1,2,4,8,16,32,64,128,256,512,1024,2048,4096; c=b%ai; d=e/ai;,二、除法(求余)的优化,由于计算机内存是线性的,多维数组的元素在排列为线性序列后存入存储器,如下所示:,三、关于多维数组的性能优化,由于在结构上需要进行转换,多维数组的引址操作被翻译成了乘法操作。,数组定义:a1010 Debug模式下,对数组的取值操作使用了imul运算( Release模式编
7、译时会进行和乘法运算相同的优化):,三、关于多维数组的性能优化,由于imul是一种比例时间较大的指令,如果能消去这一指令,便能够产生较大幅度的优化。,三、关于多维数组的性能优化,如果操作的变址方法固定(比如像宽度优先搜索,变址操作为+1,-1,+N,-N),那么用指针加减操作以及辅助记录就能获得更快的速度(消去了乘法操作)。,这样本来隐藏的乘法操作就被消去了。,三、关于多维数组的性能优化,这种操作被我称为指针的“行走”操作。使用这个优化有个条件,就是指针变化方式固定。 让我们通过一个例子来了解这种优化的作用。,(真的很有用),三、关于多维数组的性能优化,题意描述: 在N*M的矩阵中,有一些障碍
8、,有一个物体放在某个格子上。它会按照一个时间表向某一方向运动,一个时间单位移动格。某一秒你可以让它运动,也可以让它静止。问物体最多能运动的长度。 时间表由很多个时间片段构成,在每个时间片断中,物体将向同一方向运动。 数据规模: 50%的数据中,1N, M200,时间长度(T)200; 100%的数据中,1N, M200,时间片段个数(K)200,时间长度(T)40000。,例:adv1900 (NOI2005),这道题有很多做法,其中最优做法是使用单调性降维。 无论用什么方法,都必经一个关键步骤,这就是在不同的时间点间进行状态转移,并且,都要将这一步“批处理”化。 最优做法的单调性降维,以及其
9、他各式各样的优化,如堆和RMQ等,都是基于对这一步骤的渐进时间复杂度的优化。,例:adv1900 (NOI2005),但是,利用“行走”操作,我们完全可以另辟蹊径。 基于此步骤具有的使用优化的典型特点: (1)位于循环最里层,直接影响运行速度; (2)大量使用对数组的变化方式固定的操作,可以用指针“行走”来优化。 虽然最终还是使用“批处理化”的思想,但是这种方法没有把精力用在渐进复杂度的优化上,而转向到了具体的实现上。,例:adv1900 (NOI2005),本题的移动情况可以靠在移动前进行对变量的初始化实现。 在某个时间段中对前面位置的询问可以用反方向“行走”实现。 对于取址运算中的位运算,可以用强制转换指针的方法消去。 对障碍判断的实现可以用统一变量格式实现。,例:adv1900 (NOI2005),例:adv1900 (NOI2005),下表展现了此方法与非“行走”优化方法的速度对比(Debug模式),表3:“行走”优化方法,表4:非“行走”优化方法,总结,汇编语言具有高速、高效的特点,并且它的细微差异,都会导致程序运行速度的一定的变化。,上述几个实例展现了反汇编在常数因子优化中的应用。 我相信,对汇编程序的分析与比较,能够使程序运行速度进一步提高,从而更快更好的解决实际问题。,欢 迎 提 问,Thank you,