国家集训队2006论文集周以苏.ppt

反汇编在常数因子优化中的应用 四川省成都七中 周以苏 绪言 程序优化是无止境的，其中常数因子也是决定程序运行快慢的关键之一。 引例：关于memset函数的小实验 已知memset函数为O(N)复杂度的语句。 分析 可能你认为Time值不影响程序时间复杂度，因此对程序的速度无影响。 分析 Time值较大时，我们可以从反汇编角度解释程序运行速度变慢的原因。（如下） 分析 思路 一、关于调用常数因子的优化 调用常数因子是指在函数调用过程中push pop（有的编译器如VS.NET的cl用mov实现）和call ret等汇编伪代码在调用过程中的耗费。 虽然调用过程在Release模式下会被自动优化，但是在某些只提供Debug模式的竞赛环境中，我们该如何优化？所以本文主要阐述在Debug模式下的调用常数因子优化。 我们常使用inline关键字对代码进行优化，但是，inline关键字对编译器的作用是提示性质的而不是强制性质的。 1、不使用子函数 2、使用宏定义 2、Release模式 与Debug模式不同的是，在Release模式下，任何函数会被优先尝试作为inline函数，所以在代码中显式指定inline关键字仍然没有实际的作用。 二、除法（求余）的优化(预备) 预备知识： 求余运算c=a%b等效于c=a-a/b*b但是，其内部实现直接使用除法的第二个返回值： 除法指令idiv是一种比例时间很大的指令。编译器的设计者也知道这一点。所以大多数情况下编译器都能将常数除法转化为快得多的位运算。 （注：编译器同样也会把特定的乘法转化为位运算，比如乘以２等） 二、除法（求余）的优化 比如，对于a/=2（a为32位整数）这句语句在Debug模式下的解释： 二、除法（求余）的优化 正确的方法是， 判断出特殊性， 使用手工的优化方式， 如： 由于计算机内存是线性的，多维数组的元素在排列为线性序列后存入存储器，如下所示： 由于在结构上需要进行转换，多维数组的引址操作被翻译成了乘法操作。 由于imul是一种比例时间较大的指令，如果能消去这一指令，便能够产生较大幅度的优化。 这种操作被我称为指针的“行走”操作。使用这个优化有个条件，就是指针变化方式固定。 让我们通过一个例子来了解这种优化的作用。 题意描述： 　　　在N*M的矩阵中，有一些障碍，有一个物体放在某个格子上。它会按照一个时间表向某一方向运动，一个时间单位移动１格。某一秒你可以让它运动，也可以让它静止。问物体最多能运动的长度。 　　　时间表由很多个时间片段构成，在每个时间片断中，物体将向同一方向运动。 数据规模： 　　50%的数据中，1≤N, M≤200，时间长度(T)≤200； 　　100%的数据中，1≤N, M≤200，时间片段个数(K)≤200，时间长度(T)≤40000。 这道题有很多做法，其中最优做法是使用单调性降维。 无论用什么方法，都必经一个关键步骤，这就是在不同的时间点间进行状态转移，并且，都要将这一步“批处理”化。 最优做法的单调性降维，以及其他各式各样的优化，如堆和RMQ等，都是基于对这一步骤的渐进时间复杂度的优化。 本题的移动情况可以靠在移动前进行对变量的初始化实现。 在某个时间段中对前面位置的询问可以用反方向“行走”实现。 对于取址运算中的位运算，可以用强制转换指针的方法消去。 对障碍判断的实现可以用统一变量格式实现。 例：adv1900 (NOI2005) 下表展现了此方法与非“行走”优化方法的速度对比(Debug模式) 总结 汇编语言具有高速、高效的特点，并且它的细微差异，都会导致程序运行速度的一定的变化。 * * 然而在竞赛中，渐进时间复杂度是人们关注的重点，而同样能够决定程序运行快慢的常数因子优化问题却缺乏重视。 在Visual C++语言环境下，从特定编译器生成的汇编代码出发，我探讨了反汇编在常数因子优化中的应用，并提出了若干优化改进方案。 #include string.h const int Total=1000000000; const int Time=你喜欢的合法的数值; char field[Total/Time]; int i,j; int main() { for (;j10;j++) for (i=0;iTime;i++) memset(field,0,sizeof(field)); return 0; } 你能直接答出Time值与运行速度的关系？ 观看右边的C++程序 （假设计算机具有足够大的内存） Time值与运行速度的关系 但是，当上机实验后，你会发现，Time值较大或较小时运行速度会变慢，这是为什么呢？ #include string.h const int Total=10000