在排序问题中,我们必不可少的会用到交换操作。针对不同的语言,处理方式有所不同:或者单独写一个swap函数,或者直接在排序函数中实现交换操作。采用swap函数大多数人肯定会遇到不能交换的问题,其中的原理大家也应该都很清楚:swap函数交换的是局部变量,话虽如此,但具体的机制其实远不是如此简单。
要真正理解这个问题,就需要从程序的运行时刻环境来解释。一个程序在运行时内存会被划分成几部分:代码区、数据区、堆区和栈区。
生成的目标代码的大小在编译时刻就已经固定下来了,因此编译器可以将可执行目标代码放在一个静态确定的代码区。这个区通常位于存储的低端。类似地,程序的某些数据对象的大小或者全局变量可以在编译时刻知道,它们可以被放置在另一个称为静态区的区域中,该区域可以被静态确定。放置在这个区域的数据对象进行静态分配,是因为这些对象的地址可以被编译到目标代码中。
为了将运行时刻的空间利用率最大化,另外两个区域-----栈和堆被放在剩余地址空间的相对两端。这些区域是动态的,它们的大小会随着程序运行而改变。这两个区域根据需要向对方增长。栈区用来存放称为活动记录的数据结构,这些活动记录在函数调用过程中生成。有些数据的生命周期要比创造它的某此过程调用更长,这些数据通常被分配在堆区。局部变量在栈区中分配,和活动记录密切相关,所以我们只关注栈区。
当一个方法被调用时,编译器会为其在栈区中分配一块空间,作为该方法的活动记录。活动记录中包括方法的形式参数,局部变量等数据以及方法结束时的返回地址。在该方法的生命周期中,其操作除了涉及全局的访问之外都在该空间中。活动记录的分配是随着程序的运行而逐渐分配和回收的:遇到方法调用即为该方法分配空间创建活动记录,方法结束则回收空间。
下面以用C语言写的冒泡排序为例来分析活动记录的构造。源代码BubbleSort.c为:
#include<stdio.h> void swap(int*a,int* b)//正确的交换函数 { int temp=*a; *a=*b; *b=temp; } void swaps(inta,int b)//错误的交换函数 { int temp=a; a=b; b=temp; } voidBubbleSort(int a[],int length) { int i,j; for(i=length-1;i>1;i--) { for(j=0;j<i;j++) { if(a[j]>a[j+1])swap(&a[j],&a[j+1]); } } } int main() { int a[10]; int i; for(i=0;i<10;i++) { a[i]=rand()%100; } printf("---------------------------------------/n"); for(i=0;i<10;i++) { printf("%d ",a[i]); } printf("/n"); BubbleSort(a,10); printf("---------------------------------------/n"); for(i=0;i<10;i++) { printf("%d ",a[i]); } printf("/n"); }
用命令gcc –S BubbleSort.c生成源文件的部分汇编代码为:(注:此为AT&T汇编,源操作数和目的操作数与Intel汇编相反,细节请自行查阅)
.file "BubbleSort.c" .text .globl swap .type swap, @function swap: pushl %ebp ;%ebp保存父函数活动记录的基地址 movl %esp, %ebp ; %esp为当前函数活动记录基地址,保存在%ebp中 subl $16, %esp ;为当前函数的活动记录分配空间为16字节 movl 8(%ebp), %eax ;将&a存入eax movl (%eax), %eax ;将*a存入eax,我们可以看出指针操作就是间接寻址 movl %eax, -4(%ebp) ;将eax的值存入temp(temp=*a) movl 12(%ebp), %eax ;将&b存入eax movl (%eax), %edx ;将*b存入edx movl 8(%ebp), %eax ;将&a存入eax movl %edx, (%eax) ;将edx存入eax所指内存单元(*a=*b) movl 12(%ebp), %eax ;将&b存入eax movl -4(%ebp), %edx ;将temp存入edx movl %edx, (%eax) ;将edx存入eax所指内存单元(*b=*temp) leave ret .size swap, .-swap .globl BubbleSort .type BubbleSort, @function BubbleSort: pushl %ebp movl %esp, %ebp subl $24, %esp movl 12(%ebp), %eax ;将length放到eax中 subl $1, %eax ;eax=length-1 movl %eax, -4(%ebp) ;i=length-1 jmp .L6 .L10: movl $0, -8(%ebp) ;j=0 jmp .L7 .L9: movl -8(%ebp), %eax ;将j移到eax中 sall $2, %eax ;将j扩大四倍 addl 8(%ebp), %eax ;将数组的指针指向元素a[j],并将值放入eax movl (%eax), %edx ;将a[j]放到edx中 movl -8(%ebp), %eax ;将j移到eax中 addl $1, %eax ;j=j+1 sall $2, %eax ;将j扩大四倍 addl 8(%ebp), %eax ;将数组指针指向下一个元素a[j+1],并将值放入eax movl (%eax), %eax ;将a[j+1]放到eax中 cmpl %eax, %edx ;比较a[j]和a[j+1] jle .L8 movl -8(%ebp), %eax addl $1, %eax sall $2, %eax movl %eax, %edx addl 8(%ebp), %edx movl -8(%ebp), %eax sall $2, %eax addl 8(%ebp), %eax movl %edx,4(%esp) ;将edx (a[j])存入为swap的形式变量b分配的空间 movl %eax,(%esp) ;将eax(a[j+1])存入为swap的形式变量a分配的空间 call swap .L8: addl $1, -8(%ebp) .L7: movl -8(%ebp), %eax cmpl -4(%ebp), %eax jl .L9 subl $1, -4(%ebp) .L6: cmpl $1, -4(%ebp) jg .L10 leave ret
下面以swap函数的汇编代码来分析活动记录。在一般的机器中,栈都是由高地址向低地址变化,当执行swap时,由高地址向低地址为其形式参数和局部变量分配空间。首先是形式参数,在执行swap之前,编译器会按照输入参数的反向顺序为形式参数分配空间,我们所说的局部变量其实就是指的这个为形式参数分配的空间。函数执行分配空间,执行完毕释放空间,这就是局部变量的含义。然后再进入swap函数体,进入函数体第一步就是存函数的返回地址,这个过程由编译器隐式完成,在汇编代码中不存在。然后执行一个例程(the procedureprolog):pushl
%ebp movl %esp, %ebp,这两句的作用是保存调用者的活动记录的初始地址,当函数返回时,可以正确的跳到父函数的活动记录。最后才是为函数swap的局部变量分配空间。该空间的分配应该是采用回填方式分配,并不局限于函数中声明的变量个数,而是函数用到的空间。这些空间构成了swap函数的活动记录。
通过分析汇编代码,我们可以明白为什么基本类型做形参的swap函数不起作用,而指针的swap函数可以实现交换功能。我们在执行swap函数时,编译器会为该方法分配一部分空间,将形式参数放在这个空间中,而这个空间是和方法调用时的实参空间不同的,所以我们所有的修改就不会触及到实参。虽说swap结束后,形参的空间还存在,但是我们在高级语言级无法访问,也就无法获得swap交换之后的值。
基本类型不行,但是为什么指针就可以呢?虽说swap保存的不是实际的值,但是保存了实际变量的指针,这就意味着我们可以通过指针修改实参。象Java这种高级语言没有指针,怎样实现两数交换,一般可以采用的策略是将要交换的数声明为类的实例变量,这样就可以进行交换了。
至此,我们已经对swap函数的原理有了比较深刻的认识。我们不妨再深一步,对C语言的变量布局再通过实例分析一下:
#include<stdio.h> #define N 10 int a,b[N],*p;//全局变量 int add(inta,int b) { return a+b; } int main() { int a=3;//局部变量 a=add(a,a); printf("a=%d/n",a); }
汇编代码为:
.file "test.c" .comm a,4,4 ;全局变量会单独存放,放在静态区 .comm b,40,32 .comm p,4,4 .text .globl add .type add,@function add: pushl %ebp movl %esp,%ebp movl 12(%ebp),%eax movl 8(%ebp),%edx leal (%edx,%eax),%eax ;AT&T汇编,实现相加功能,将返回值放在eax中 popl %ebp ret .size add,.-add .section .rodata .LC0: .string "a=%d/n" ;字符串也会特殊处理 .text .globl main .type main,@function main: pushl %ebp movl %esp,%ebp andl $-16,%esp subl $32,%esp movl $3,28(%esp) ;局部变量a放在28(%esp),属于main的活动记录 movl 28(%esp),%eax movl %eax,4(%esp) movl 28(%esp),%eax movl %eax,(%esp) call add movl %eax,28(%esp) ;从eax中读取函数的返回值,返回值不单独分配空间 movl $.LC0,%eax movl 28(%esp),%edx movl %edx,4(%esp) movl %eax,(%esp) call printf leave ret
我们由swap函数遇到的问题入手,来分析C语言变量的分配问题,其他高级语言也有类似的特点。希望通过该文章,大家对底层变量的分配和高级语言之间的关系能更加了解。