论反汇编在时间常数优化中的应用周以苏.docx
- 文档编号:14559583
- 上传时间:2023-06-24
- 格式:DOCX
- 页数:21
- 大小:97.60KB
论反汇编在时间常数优化中的应用周以苏.docx
《论反汇编在时间常数优化中的应用周以苏.docx》由会员分享,可在线阅读,更多相关《论反汇编在时间常数优化中的应用周以苏.docx(21页珍藏版)》请在冰点文库上搜索。
论反汇编在时间常数优化中的应用周以苏
论反汇编在时间常数优化中的应用
四川省成都七中周以苏
摘要:
本文阐述了时间常数优化的重要性,并且在VisualC++语言环境下,从特定编译器生成的汇编代码出发,探讨了反汇编在时间常数优化中的应用,提出了若干优化改进方案。
关键字:
C++反汇编时间常数优化
程序的优化是无止境的。
其中,时间常数是在相同时间复杂度下决定程序运行快慢的关键。
然而在竞赛中,渐进时间复杂度是关注的重点,而同样能够决定程序运行快慢的时间常数优化问题却缺乏重视。
本文阐述了时间常数优化的重要性,并且在VisualC++语言环境下,从特定编译器生成的汇编代码出发,探讨了反汇编在时间常数优化中的应用,提出了若干优化改进方案。
一、基本概念
汇编语言(Assemblylanguage),是一种与硬体紧密相关的程序设计语言,是一种低级语言。
汇编语言是机器语言的便于记忆和理解的符号化形式。
由于汇编语言的各种语法规范互不兼容,本文以下部分以Intel语法为基础,并以使用Intel语法的VisualC++作为实验平台。
汇编语言源程序是用伪代码创建的。
一个伪代码是一条处理器可以理解的指令。
例如:
add
add指令把两个数加到一起。
大部分伪代码带有参数
addeax,edx
add有两个参数。
一个源参数,一个目标参数。
它把源值加到目标值中,并把结果保存在目标中。
参数有很多不同的类型,如:
寄存器,内存地址,直接数值。
下面的介绍以寄存器为例。
有几种大小的寄存器:
4位,8位,16位,32位(在MMX处理器中有更多的种类)。
在16位程序中,你仅能使用4位、8位和16位的寄存器。
在32位的程序中,你还可以使用32位的寄存器。
一些寄存器是别的寄存器的一部分:
例如,如果eax保存了值EA7823BBh,那么,它的子寄存器ax,ah和al也会保存其值的一部分,如下表所示:
eaxEA7823BB
ax23BB
ah23
alBB
ax,ah,al是eax的一部分。
eax是一个32位的寄存器(仅在386以上存在),ax包含了eax的低16位(2字节),ah包含了ax的高字节,而al包含了ax的低位字节。
因而ax是16位的,al和ax是8位的。
让我们来分析下面的代码:
moveax,12345678h
;Mov把一个值载入寄存器(注意:
12345678h是一个十六进制值,因为h这个后缀。
movcl,ah
;把ax的高字节移入cl
subcl,10
;从cl的值中减去10(十进制)
moval,cl
;并把cl存入eax的最低字节
mov指令可以把一个值从寄存器,内存或直接数值移入另一个寄存器。
在上面的例子中,eax包含了12345678h,然后ah的值(eax左数第三个字节)被复制入了cl中(ecx寄存器的最低字节)。
然后,cl减10并移回al中(eax的最低字节)
关于汇编指令的其它基础知识,请参看相关的入门书籍。
编译器(Compiler),是将便于人编写,阅读,维护的高级计算机语言程序翻译为计算机能识别,运行的低级机器语言的程序。
编译器将源程序(Sourceprogram)作为输入,翻译产生使用目标语言(Targetlanguage)的等价程序。
源程序一般为高级语言(High-levellanguage),如Pascal,C++等所写的程序,而目标程序则是机器能直接执行的目标代码(Objectcode),有时也称作机器代码(Machinecode)。
编译器友好(Compilerfriendly),是指所写的代码符合编译器的规范,其功能的完整性不依赖于特定编译器的特性或隐藏功能,因此具有通用性和兼容性。
本文的结论不一定需要用汇编实现,因为嵌入汇编不是所有语言都能够支持的,况且这样做不是文章的本意。
二、数据分析
在特定的平台上,不同的汇编伪代码有着不同的执行速度。
但是,每种功能的伪代码的相对执行速度是较为恒定的。
比如,执行乘除法伪代码的时间一定大大长于执行加减法伪代码的时间。
表1为Aoa[1]中8286系统各种伪代码的理论执行时间:
表1:
8286指令集的执行时间
为了验证上表的结论以及探讨从反汇编角度对程序进行改进的可行性,本文对实际语句的运行情况进行了数据搜集。
本文采用的实验环境如下:
试验环境:
软件:
WindowsXPsp2050301-1519MSVC++69514-335-0000007-18650
硬件:
IntelPentium4CPU2.66GHz
Debug模式等同于非优化模式等同于不带参数进行编译
Release模式等同于优化模式约等于G++中-O2优化
注意:
本文的某些结论并不适用于其他处理器、平台和编译器,需要再次进行测试。
测试方法:
在速度测试中,实验使用了一个基准的C++程序模版。
#include
#include
clock_tstart,finish;
inta;
intmain()
{
start=clock();
__asm
{
movecx,2000000000//实验次数
testBegin:
moveax,10
movebx,10
cdq
//这里插入实验语句
dececx
jztestEnd
jmptestBegin
testEnd:
}
finish=clock();
printf("%.3lf",double(finish-start)/CLOCKS_PER_SEC);
return0;
}
本文对附录中Configure.in文件中引用的操作进行了测试。
通过执行附录中的Python脚本,得出了表2的结果:
表2:
在测试环境下各个指令实际运行时间及比例
测试操作
平均用时
相对用时
比例
EMPTY(无实验语句)
2.29
0.00
0.0
NORMALIMUL
3.81
1.52
11.0
NORMALIDIV
25.94
23.65
171.2
NORMALTEST
2.43
0.14
1.0
NORMALMOV
2.29
0.00
(0.0)
NORMALADD
2.41
0.12
0.9
NORMALINC
3.05
0.76
5.5
NORMALSUB
2.41
0.12
0.9
NORMALDEC
3.05
0.76
5.5
NORMALXOR
2.35
0.06
0.4
NORMALAND
2.35
0.06
0.4
NORMALSHL
2.44
0.15
1.1
NORMALSAR
2.44
0.15
1.1
NORMALSHR
2.44
0.16
1.1
NORMALNOT
2.29
0.00
(0.0)
NORMALXCHG
3.04
0.76
5.5
PTRMOV
2.28
0.00
(0.0)
PTRADD
3.05
0.76
5.5
PTRSUB
3.05
0.76
5.5
PTRXOR
3.05
0.76
5.5
PTRAND
3.05
0.76
5.5
PTRXCHG
67.39
65.10
471.2
JMP
3.14
0.85
6.2
PUSHPOP
3.05
0.76
5.5
CALLRETJMP
9.16
6.88
49.8
EMPTY(Verify)
2.29
0.00
0.0
注:
1、测试结果有误差,并且会随着操作系统、编译器和系统配置的变化而不同程度的波动。
2、具体测试语句见附录Configure.in
3、由于处理器对程序的执行并不是像想象中那样一句一句直接执行,其中还涉及到代码解释缓存、L1、L2变量长度(16,32)等因素的影响,本试验的数据只作为理论的近似。
基于上面得到的结果,本文将各类语句时间常数归类为了下列6个层次(见表3):
表3:
汇编语句速度分类
层次运算比例时间
1、mov,lea(未进行测试)数据移动运算1
andorxornot逻辑运算
add,sub加减法运算,test置位运算(内部为sub运算)
2、shl,shr,sal,sar位运算1.5~2
3、ptr取地址值(不是运算),push+pop堆栈运算*2,jmp跳转运算4
4、mul,imul乘法5
5、div,idiv除法25
6、call+ret调用子函数+返回27
从这6个层次中,我们可以看到汇编代码执行的快慢程度,因此,如果我们能够从汇编角度出发,把比例时间较大的操作消去或转化为比例时间较小的操作组合,那么,我们就达到了对时间常数进行优化的目的。
本文通过如下实例分析进一步说明了竞赛中反汇编在时间常数优化中的应用。
三、实例分析
3.1关于memset函数的小实验
已知memset函数为一个O(N)复杂度的语句。
让我们先做一个小实验,观看下面的C++程序(假设计算机具有足够大的内存):
#include
constintTotal=1000000000;
constintTime=一个你喜欢的合法的数值;
charfield[Total/Time];
inti,j;
intmain()
{
for(j=0;j<10;j++)
for(i=0;i
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 汇编 时间常数 优化 中的 应用