深入理解计算机系统(3.8)------数组分配和访问

  上一篇博客我们讲解了汇编语言中过程(函数)的调用实现。理解数据如何在调用者和被调用者之间传递,以及在被调用者当中局部变量内存的分配以及释放是最重要的。那么这篇博客我们将讲解数组的分配和访问。

1、数组的基本原则

  我们知道数组是某种基本数据类型数据的集合,对于数据类型 T 和整型常数 N,数组的声明如下:

T  A[N]

  上面的 A 称为数组名称。它有两个效果:

  ①、它在存储器中分配一个 L*N 字节的连续区域,这里 L 是数据类型 T 的大小(单位为字节)

  ②、A 作为指向数组开头的指针,如果分配的连续区域的起始地址为 xa,那么这个指针的值就是xa

  即当我们用 A[i] 去读取数组元素的时候,其实我们访问的是 xa+i*sizeof(T)。sizeof(T)是获得数据类型T的占用内存大小,以字节为单位,比如如果T为int,那么sizeof(int)就是4。因为数组的下标是从0开始的,当 i等于0时,我们访问的地址就是 xa

  比如对于如下数组声明:

   char A[12];
   char *B[8];
   double C[6];
   double *D[5];

  我们可以得到如下信息:注意由于B和D都是声明的数组,在IA32中,指针变量占用4个字节的内存空间。

  在比如如下代码:

#include <stdio.h>

int main(){
   int a[10];
   int i ;
   for(i = 0 ; i < 10 ; i++){
   	printf("%d\n",&a[i]);
   } 
   printf("数组大小为:%d\n",sizeof(a)); 
   return 0;
}

  打印结果为:

  从上面的我们也可以看出来,起始地址为 6356736,即a[0]的地址,往后面访问依次增加4个字节。

  在IA32中,存储器引用指令可以用来简化数组访问。比如对于上面的 int a[10],我们想访问 a[i],这时候 a 的地址存放在寄存器 %edx 中,而 i 存放在寄存器 %ecx 中。然后指令计算如下:

movl  (%edx,%ecx,4), %eax

  这会执行地址计算 xa+4i,读取这个存储器位置的值,并把结果存放在寄存器%eax中。

2、指针运算

  C语言允许对指针进行运算,而计算出来的值会根据该指针引用的数据类型的大小进行伸缩。

  也就是说,如果 P 是一个执行类型 T 的数据的指针,P 的值为 xp,那么表达式P+i 的值为 xp+L*i,这里 L 是数据类型T的大小。

  假设整型数组 E 的起始地址和整数索引 i 分别存放在寄存器 %edx 和 %ecx 中,下面是每个表达式的汇编代码实现,结果存放在 %eax 中。

  上面例子中,leal 指令用来产生地址,而 movl 用来引用存储器(除了第一种和最后一种情况,前者是复制一个地址,后者是复制索引);最后一个例子说明可以计算同一个数据类型结构中的两个指针之差,结果值是除以数据类型大小后的值。

3、数组的嵌套

  也就是数组的数组,比如二维数组 int A[5][3]。这个时候上面所讲的数组的分配和引用也是成立的。

  对于数组 int A[5][3],如下表示:

  我们可以将 A 看成是一个有 5 个元素的数组,而每个元素都是 3 个 int 类型的数组。

4、定长数组和变长数组

  要理解定长和变长数组,我们必须搞清楚一个概念,就是说这个“定”和“变”是针对什么来说的。在这里我们说,这两个字是针对编译器来说的,也就是说,如果在编译时数组的长度确定,我们就称为定长数组,反之则称为变长数组。

  比如int A[10],就是一个定长数组,它的长度为10,它的长度在编译时已经确定了,因为长度是一个常量。之前的C编译器不允许在声明数组时,将长度定义为一个变量,而只能是常量,不过当前的C/C++编译器已经开始支持动态数组,但是C++的编译器依然不支持方法参数。另外,C语言还提供了类似malloc和calloc这样的函数动态的分配内存空间,我们可以将返回结果强转为想要的数组类型。

  对于如下程序:

int main(){
    int a[5];
    int i,sum;
    for(i = 0 ; i < 5; i++){
        a[i] = i * 3;
    }
    for(i = 0 ; i < 5; i++){
        sum += a[i];
    } 
    return sum;
}

  我们加上 -O0 -S 变成汇编代码:

main:
    pushl    %ebp
    movl    %esp, %ebp//到此准备好栈帧
    subl    $32, %esp//分配32个字节的空间
    leal    -20(%ebp), %edx//将帧指针减去20赋给%edx寄存器
    movl    $0, %eax//将%eax设置为0,这里的%eax寄存器是重点
.L2:
    movl    %eax, (%edx)//将0放入帧指针减去20的位置?
    addl    $3, %eax//第一次循环时,%eax为3,对于i来说,%eax=(i+1)*3。
    addl    $4, %edx//将%edx加上4,第一次循环%edx指向帧指针-16的位置
    cmpl    $15, %eax//比较%eax和15?
    jne    .L2//如果不相等的话就回到L2
    movl    -20(%ebp), %eax//下面这五句指令已经出卖了leal指令,很明显从-20到-4,就是数组五个元素存放的地方。下面的就不解释了,直接依次相加然后返回结果。
    addl    -16(%ebp), %eax
    addl    -12(%ebp), %eax
    addl    -8(%ebp), %eax
    addl    -4(%ebp), %eax
    leave
    ret

  指令上面的注释已经很清楚了,下面我们看看循环过程是怎么计算的:

  看了这个图相信各位更加清楚程序的意图了,开始将%ebp减去20是为了依次给数组赋值。这里编译器用了非常变态的优化技巧,那就是编译器发现了a[i+1] = a[i] + 3的规律,因此使用加法(将%eax不断加3)代替了i*3的乘法操作,另外也使用了加法(即地址不断加4,而不使用起始地址加上索引乘以4的方式)代替了数组元素地址计算过程中的乘法操作。而循环条件当中的i<5,也变成了3*i<15,而3*i又等于a[i],因此当整个数组当中循环的索引i,满足a[i+1]=15(注意,在循环内的时候,%eax一直储存着a[i+1]的值,除了刚开始的0)的时候,说明循环该结束了,也就是coml和jne指令所做的事。

  弄清楚了定长数组,下面我们在看看变长数组。在GCC版本支持的 ISO C99中,允许数组的维度是表达式,在数组被分配的时候才计算出来。比如下面这个函数:

int var_ele(int n,int A[n][n],int i,int j) 
{
	return A[i][j];
}

  产生的汇编代码如下:

  如上图所示,在计算元素 i,j的地址为xa+4(n*i+j)。这个计算类似于定长数组的地址计算,不同的是:

  ①、由于加上了参数n,参数在栈上的地址移动了

  ②、用了乘法指令计算n*i(第4行),而不是leal指令计算3i。

  因此引用变长数组只需要对定长数组做一点改动,动态的版本必须用乘法指令对i扩展n倍,而不能用一系列的移位和加法。在一些处理器中,乘法指令会消耗很长的指令周期,但是在这种情况下是不可避免的。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏软件开发 -- 分享 互助 成长

C++ STL之deque的基本操作

前两篇博文中已经介绍了vector和list的两种容器,我们发现他们各有各的优缺点,vector在内存中连续存储,支持随机访问,但是查找和删除的效率比较低,而l...

1865
来自专栏程序员互动联盟

【答疑解惑】java中static关键字的作用

static方法 static方法一般称作静态方法,由于静态方法不依赖于任何对象就可以进行访问,因此对于静态方法来说,是没有this的,因为它不依附于任何对象,...

2867
来自专栏企鹅号快讯

Python序列元素计数的方法,你知道几种?

在Python脚本语言中,数据结构有许多种,常见的数据类型有:序列,映射与集合三大类型,其中序列又分为可变序列和不可变序列,可变序列有2类:列表(List)与字...

19310
来自专栏代码世界

Python之函数基础

1、函数的定义与调用 函数从大方针上考虑总共分为两种:一种是内置函数,另一种是自定义函数。今天主要讲的是自定义函数。 s = '金老板小护士' #len(s) ...

2689
来自专栏开源优测

python selenium2 - webelement操作常用方法

完整路径 C:\Python27\Lib\site-packages\selenium\webdriver\remote\webelement...

2755
来自专栏Golang语言社区

go 内置函数

Go 的内置函数不拥有前面提到的go的标准类型,因此内置函数不能作为一个函数值赋值给函数类型的变量。 close close用于关闭一个channel,使用c...

3095
来自专栏编程坑太多

js数组的拷贝赋值复制-你真的懂?

1793
来自专栏前端小叙

js数组push方法使用注意

js 数组的push方法,想必大家都知道是向数组末尾添加元素,但是有一个很关键的点需注意: 引自 MDN 返回值 当调用该方法时,新的 length 属性值将被...

2646
来自专栏Java学习网

Java面试中最常见的10个问题,Java底层知识,花点时间学习一下

1.什么是 Java 虚拟机?为什么 Java 被称作是“平台无关的编程语言”? Java 虚拟机是一个可以执行 Java 字节码的虚拟机进程。Java 源文...

2165
来自专栏青枫的专栏

c语言基础学习08_内存管理

============================================================================= 涉及...

821

扫码关注云+社区