數組簡介

　　如果各位猿友是一路跟著LZ看到這里的，那么數組的定義就非常簡單了，它就是一個相同數據類型的數據集合。數組存儲在一系列邏輯上連續的內存塊當中，之所以說是邏輯上連續，是因為整個內存或者說存儲器本身就是邏輯上連續的一個大內存數組。如果我們用Java語言的類型來表示我們的存儲器的話，可以看做是byte[] memory這樣的類型。

　　數組的定義非常簡單，它遵循以下這樣簡單的規則。

　　　T N[L];

　　這當中T表示數據類型，N是變量名稱，L是數組長度。這樣的聲明會做兩件事，首先是在內存當中開辟一個長為L*length(T)的內存空間（其中length(T)是指數據類型的字節長度），然后將這塊內存空間的起始地址賦給變量N。當我們使用N[index]去讀取數組元素的時候，我們會去讀N+index*length(T)的內存位置，這一點并不難理解。

指針操作數組

　　在C語言當中，*符號可以取一個指針指向的內存區域的值，而對于數組來說，*符號依然可以這樣做。因此，我們可以很輕松地想到，對于上面的聲明來說，*N就相當于N[0]，類似的，*(N+1)就相當于N[1]，以此類推。

　　在上面*(N+1)這樣的方式當中，我們其實對指針進行了運算，即對數組的起始地址N加了上1。在這一過程中，編譯器會幫我們自動乘上數據類型的長度（比如int為4），如此一來，我們的指針運算才算是正確了，比如對于*(N+1)來說，假設T為int類型，則 【實際地址（N+1）】 = N + 1 * 4。對于這一點，我們可以用以下這個小程序來驗證一下，從這個程序可以很明顯的看出來，當我們對指針進行加1操作的時候，實際的地址會被乘以數據類型的長度。

定長和變長數組

　　要理解定長和變長數組，我們必須搞清楚一個概念，就是說這個“定”和“變”是針對什么來說的。在這里我們說，這兩個字是針對編譯器來說的，也就是說，如果在編譯時數組的長度確定，我們就稱為定長數組，反之則稱為變長數組。

　　比如上圖當中的示例，就是一個定長數組，它的長度為10，它的長度在編譯時已經確定了，因為長度是一個常量。之前的C編譯器不允許在聲明數組時，將長度定義為一個變量，而只能是常量，不過當前的C/C++編譯器已經開始支持動態數組，但是C++的編譯器依然不支持方法參數。另外，C語言還提供了類似malloc和calloc這樣的函數動態的分配內存空間，我們可以將返回結果強轉為想要的數組類型。

　　接下來，LZ和各位一起分析一個有關數組的C程序，我們先來一個簡單的，也就是一個定長數組，我們看下在匯編級別是如何操作定長數組的。需要一提的是，由于數組的長度固定，所以有的時候編譯器會根據實際情況作出一些優化，以下是一個簡單的小程序。

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;
}

　　以上這個小程序的功能LZ就不介紹了，如果哪位猿友看不懂，請自覺面壁吧。下面我們來看下-S和-O1下的匯編代碼，如下所示。

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

　　LZ這里就不再一個一個介紹這些指令的作用了，如果各位猿友是一路看過來的，這些指令其實難不倒各位。我們主要來看下跟數組相關的地方。上面其實并沒有完全解釋清楚數組的賦值操作那一部分，但是后面求和的部分卻已經十分清楚了，現在LZ就幫各位串聯一下賦值的那部分。為了更加清晰，LZ廢話不多說，直接上圖。我們看下循環過程中是怎么計算的。

　　看了這個圖相信各位更加清楚程序的意圖了，開始將%ebp減去20是為了依次給數組賦值。這里編譯器用了非常變態的優化技巧，說真的，LZ編譯之前也沒想到。那就是編譯器發現了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指令所做的事。

　　搞清楚了上面定長數組的實現，我們會發現，定長數組可以做很多的優化，想象一下，如果上面的數組長度是不定的，編譯器還能算出15這個數值嗎。接下來我們就來看一個和上面的代碼幾乎一模一樣的程序，只不過這里將換成變長數組。

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

　　可以看到，我們改了一下函數名稱，并給函數加了個參數n并將a變為變長數組，其它沒做任何改動。下面我們來看下-S和-O1下的匯編代碼，看看與定長數組的差距在哪里。

.file  "arr.c"
  .text
.globl sum
  .type  sum, @function
sum:
  pushl  %ebp
  movl  %esp, %ebp
  pushl  %esi
  pushl  %ebx
  subl  $16, %esp
  movl  8(%ebp), %ebx
  movl  %gs:20, %edx
  movl  %edx, -12(%ebp)
  xorl  %edx, %edx
  leal  30(,%ebx,4), %edx
  andl  $-16, %edx
  subl  %edx, %esp
  leal  15(%esp), %esi
  andl  $-16, %esi
  testl  %ebx, %ebx
  jle  .L2
  movl  $0, %ecx
  movl  $0, %edx
.L3:
  movl  %ecx, (%esi,%edx,4)
  addl  $1, %edx
  addl  $3, %ecx
  cmpl  %ebx, %edx
  jne  .L3
  movl  $0, %edx
.L4:
  addl  (%esi,%edx,4), %eax
  addl  $1, %edx
  cmpl  %ebx, %edx
  jne  .L4
.L2:
  movl  -12(%ebp), %edx
  xorl  %gs:20, %edx
  je  .L6
  call  __stack_chk_fail
.L6:
  leal  -8(%ebp), %esp
  popl  %ebx
  popl  %esi
  popl  %ebp
  .p2align 4,,1
  ret
  .size  sum, .-sum
  .ident  "GCC: (Ubuntu 4.4.3-4ubuntu5.1) 4.4.3"
  .section  .note.GNU-stack,"",@progbits

　　或許個別猿友看到這一段匯編代碼會大吃遺精，因為它看起來比定長數組要復雜太多，不管是長度還是其中的指令。LZ猜測，動態數組的復雜性可能也是動態數組出現較晚的原因，更何況動態數組還有緩沖區溢出的危險。

　　接下來LZ帶著各位猿友分步去看這一段匯編代碼，首先我們分析第一部分，包括了棧幀的建立、被調用者保存寄存器的備份以及棧內存的分配。它包括了以下幾個開頭的指令。

  pushl  %ebp
  movl  %esp, %ebp
  pushl  %esi
  pushl  %ebx
  subl  $16, %esp

　　LZ使用一幅圖來說明這個問題，我們來分別看看，在指令執行前后，寄存器以及存儲器的狀態。

　　上面的這一過程是比較正常的棧幀建立過程，如果各位猿友看過過程實現那一章的話，那么上面這個過程并不復雜，因此LZ這里就不多說廢話了，如果哪位猿友不清楚的話，可以去看看過程實現3.7的那一章。

　　接下來，我們看看比較復雜的一段代碼，這一段代碼的主要目的，是為動態數組分配內存。它們是如下的這些指令

movl  8(%ebp), %ebx
  movl  %gs:20, %edx
  movl  %edx, -12(%ebp)
  xorl  %edx, %edx
  leal  30(,%ebx,4), %edx
  andl  $-16, %edx
  subl  %edx, %esp
  leal  15(%esp), %esi
  andl  $-16, %esi

這一段代碼相對于上一段就復雜了一點，接下來LZ還是先上一個指令執行前后的圖，如下。

　　我們仔細對比一下左右兩張圖可以發現，這里面最主要的兩個值，就存在%edx和%esi寄存器當中。其中%edx的值是為數組分配的內存字節數，而%esi當中存儲的則是數組的起始地址。我們不難想到，對于一個int類型長度為n的數組，它占用的內存字節數肯定是4n。而這里特別的地方就是，為什么不直接分配4n個字節然后把棧頂作為數組起始位置，而是分配了(30+4n)&(-16)的字節，之后又把(%esp+15)&(-16)的位置作為數組的起始位置？

　　這個問題的答案就是：為了效率。

　　為了提高內存的讀取速度，一般都會將字節對齊，而針對棧內存的分配，則大部分會保持為16字節的倍數。比如，如果處理器總是一次性從存儲器中讀取16個字節，則地址必須為16的倍數才行，也就是說地址的后4位必須為0。這樣的話我們就好理解了，因為棧幀操作是從棧頂開始，直到幀指針或者備份著被調用者寄存器的內存位置為止（也就是上圖中局域變量區域的范圍），因此我們需要保證分配的字節數是16的倍數。

　　如此一來，分配(30+4n)&(-16)個字節，就可以保證上圖中-24的位置到%esp依然是16的倍數。因為對于任意一個正整數i來講，都有i - 15 =< i&(-16) <= i，并且i&(-16)是16的倍數。因此對于(30+4n)&(-16)來說，就有以下結果。

4n + 15 =<(30+4n)&(-16) <= 4n + 30

　　這就保證了新分配的棧內存大小既是16的倍數，又能裝下n個整數，因為它大于4n。不過這里很明顯至少多了15個字節，這15個字節會被數組的起始地址消除掉。從圖中可以看出，數組的起始地址并不是從棧頂開始的（從%esi指向的位置開始），這是因為數組的起始地址等于(%esp+15)&(-16)，而不是%esp。這樣做的目的也是為了對齊，只不過這里是地址對齊，將數組的起始地址對齊到16倍數的位置。由上面的結論我們知道。

%esp =<(%esp+15)&(-16) <= %esp + 15

　　上面的地址保證了數組的起始地址不會逃出棧頂，這也是%esp要加上15的原因。由于數組的起始地址可能上移15位，因此原本預留的空間將可能再次縮小15個字節（位于%esi和%esp之間的那一小段）。因此我們就能得出實際可用的空間stack有如下范圍。

4n <= stack <= 4n + 15

　　這下各位就明白了，為什么4n要加上30，而不是加上15。是因為兩次與-16的“與”運算，可能讓空間浪費30個字節。所以加上30之后，就可以保證在滿足棧內局部變量長度和數組起始位置都為16的倍數的前提下，還能至少留出4n的空間供數組使用。

　　還有一點需要一提的是，上圖當中還出現了一個“金絲雀值”，這個家伙是為了防止棧緩沖區溢出。這當中的值是存儲器當中的一個隨機值，倘若這個值在函數返回時改變了，那么就代表緩沖區溢出了，就會終止程序的運行。

　　到此動態數組占用的內存區域就分配好了，接下來的就相對來說比較簡單了，基本上與定長數組是一樣的。下面是接下來所有的匯編代碼，LZ直接加入了詳細的注釋，相信各位猿友不難看懂。

testl  %ebx, %ebx//測試n是否大于0
  jle  .L2//如果n小于等于0，就跳過兩個循環，跳到L2
  movl  $0, %ecx//%ecx與定長數組中的%eax作用一樣，先初始化為0，后面逐漸+3賦給數組元素
  movl  $0, %edx//%edx就是i，這里是i=0
.L3:
  movl  %ecx, (%esi,%edx,4)//對于i=0的時候來說，這里則相當于a[0]=0，因為%esi是數組起始地址。對于i來說，這里則代表a[i]=%ecx，a[i]的地址為a+4*i。
  addl  $1, %edx//i自增
  addl  $3, %ecx//將%eax加3，對于i=0的時候來說，%ecx就是a[1]的值。對于i來說，%ecx就是a[i+1]的值。
  cmpl  %ebx, %edx//比較n和i
  jne  .L3//如果i和n不相等則繼續循環。
  movl  $0, %edx//再次將i清0，即i=0
.L4:
  addl  (%esi,%edx,4), %eax//%eax就相當于sum，這里其實就是sum = sum + a[i]，其中a[i]的地址為a+4*i。
  addl  $1, %edx//i自增
  cmpl  %ebx, %edx//比較n和i
  jne  .L4//如果n和i不相等則繼續循環
.L2:
  movl  -12(%ebp), %edx//取出金絲雀值
  xorl  %gs:20, %edx//比較金絲雀值是否改變
  je  .L6//如果金絲雀值與原來的值相等，則代表緩沖區沒溢出，跳到L6繼續執行。
  call  __stack_chk_fail//如果不相等，則代表緩沖區溢出，產生一個棧檢查錯誤。
.L6:
  leal  -8(%ebp), %esp//讓棧頂指向備份的%ebx，回收內存。
  popl  %ebx//還原備份的%ebx值
  popl  %esi//還原備份的%esi值
  popl  %ebp//恢復原來的幀指針
  .p2align 4,,1//對齊地址為16的倍數
  ret//函數返回

　　上面的這些指令相對來講就比前面的簡單了許多，相信各位猿友看注釋就能理解的八九不離十了，唯一特別一點的指令就是最后一個p2align指令。其實之前LZ也沒見過這個指令，但是從名字上也能大概看出來是干嘛的，不過最終LZ還是很快google到了這個指令的簡單說明。它會將地址對齊為16（也就是第一個參數4，表示2的4次方的意思）的倍數，并最多跳過1個字節（也就是最后的參數1）。如果對齊需要跳過多于1個字節，則會忽略這個指令。

異質結構與數據對齊

　　異質結構是指不同數據類型的數組組合，比如C語言當中的結構（struct）與聯合（union）。在理解數組的基礎上，這兩種數據結構都非常好理解。我們先來看一個結構的例子，比如下面的這個結構。

#include <stdio.h>

struct {
  int a;
  int b;
  char c;
} mystruct;

int main(){
  printf("%d\n",sizeof mystruct);
  
}

　　這是一個非常簡單的結構體，這個程序在LZ的32位windows系統上，輸出結果是12，或許有的猿友還可以得到10或者16這樣的結果?；蛟S有的猿友會奇怪，為什么不是4+4+1=9呢。

　　這正是因為上面我們提到過的對齊的原因，只不過這里的對齊不是地址對齊也不是棧分配空間對齊，而是數據對齊。為了提高數據讀取的速度，一般情況下會將數據以2的指數倍對齊，具體是2、4、8還是16，得根據具體的硬件設施以及操作系統來決定。

　　這樣做的好處是，處理器可以統一的一次性讀取4（也可能是其它數值）個字節，而不再需要針對特殊的數據類型讀取做特殊處理。在這個例子來說，也就是說在讀取a、b、c時，都可以統一的讀取4個字節。特殊的，這里0-3的位置用于存儲a，4-7的位置用于存儲b，8的位置用于存儲c，而9-11則用于填充，其中都是空的。

　　與結構體不同的是，聯合會復用內存空間，以節省內存，比如我們看下面這個例子。

#include <stdio.h>

union {
  int a;
  int b;
  char c;
} myunion;

int main(){
  printf("%d\n",sizeof myunion);
  
}

　　這段程序輸出的結果是4，依舊是LZ的32位windows操作系統的結果。這是因為a、b、c會共用4個字節，這樣做的目的不言而喻，是為了節省內存空間，顯然它比結構體節省了8個字節的空間。它與結構體最大的區別就在于，對a、b、c賦值時，聯合會覆蓋掉之前的賦值，而結構體則不會，結構體可以同時保存a、b、c的值。

　　對于結構體和聯合，LZ這里就不再列舉具體的例子了，如果各位掌握了數組的匯編級操作，那么這兩個各位猿友完全可以私底下自己分析了。對于對齊來說，LZ還想多說幾句。首先各位猿友要分清地址對齊、數據對齊和棧分配對齊的區別。另外一點就是地址對齊的大致規則，一般會依據數據類型的長度來對齊（比如int為4位對齊，double為8位對齊等等），但最低為2。不過這些都不是絕對的，比如double也可能會依據4位對齊，因此具體的對齊規則還是需要根據硬件設施和操作系統決定。

　　最后一點需要各位明白的是，對齊是在拿空間換時間，也就是說，對齊浪費了存儲空間，但提高了運行速度。這有點類似于算法的時間復雜度和空間復雜度，兩者大部分情況下總是矛盾的。

淺談數組與指針

　　從上面的匯編分析來看，我們可以很輕松的得到一個結論，那就是數組變量其實就是數組的起始地址，就像動態數組例子當中的%esi寄存器一樣，它代表著數組a變量，同時也是數組的起始地址。而對于指針的運算，在計算實際地址時，會根據數據類型進行伸縮，比如動態數組一例中，每次在取數組元素時，總有一個權重值是4（比如這個在上面出現過的內存地址(%esi,%edx,4)，它就是在讀取數組元素），這正是int類型的長度。

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持html5模板網。