深入理解計算機系統（二十）：數組分配和訪問

6 人贊了文章

目錄

1、數組的基本原則

2、指針運算

3、數組的嵌套

4、定長數組和變長數組

　　上一篇博客我們講解了彙編語言中過程（函數）的調用實現。理解數據如何在調用者和被調用者之間傳遞，以及在被調用者當中局部變數內存的分配以及釋放是最重要的。那麼這篇博客我們將講解數組的分配和訪問。

正文：

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
",&a[i]); } printf("數組大小為:%d
",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倍，而不能用一系列的移位和加法。在一些處理器中，乘法指令會消耗很長的指令周期，但是在這種情況下是不可避免的。