數(shù)組簡介

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

　　數(shù)組的定義非常簡單，它遵循以下這樣簡單的規(guī)則。

　　　T N[L];

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

指針操作數(shù)組

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

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

定長和變長數(shù)組

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

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

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

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//到此準(zhǔn)備好棧幀
  subl  $32, %esp//分配32個字節(jié)的空間
  leal  -20(%ebp), %edx//將幀指針減去20賦給%edx寄存器？為什么？你能猜到嗎？
  movl  $0, %eax//將%eax設(shè)置為0，這里的%eax寄存器是重點
.L2:
  movl  %eax, (%edx)//將0放入幀指針減去20的位置？
  addl  $3, %eax//第一次循環(huán)時，%eax為3，對于i來說，%eax=(i+1)*3。
  addl  $4, %edx//將%edx加上4，第一次循環(huán)%edx指向幀指針-16的位置
  cmpl  $15, %eax//比較%eax和15？
  jne  .L2//如果不相等的話就回到L2
  movl  -20(%ebp), %eax//下面這五句指令已經(jīng)出賣了leal指令，很明顯從-20到-4，就是數(shù)組五個元素存放的地方。下面的就不解釋了，直接依次相加然后返回結(jié)果。
  addl  -16(%ebp), %eax
  addl  -12(%ebp), %eax
  addl  -8(%ebp), %eax
  addl  -4(%ebp), %eax
  leave
  ret

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

　　看了這個圖相信各位更加清楚程序的意圖了，開始將%ebp減去20是為了依次給數(shù)組賦值。這里編譯器用了非常變態(tài)的優(yōu)化技巧，說真的，LZ編譯之前也沒想到。那就是編譯器發(fā)現(xiàn)了a[i+1] = a[i] + 3的規(guī)律，因此使用加法（將%eax不斷加3）代替了i*3的乘法操作，另外也使用了加法（即地址不斷加4，而不使用起始地址加上索引乘以4的方式）代替了數(shù)組元素地址計算過程中的乘法操作。而循環(huán)條件當(dāng)中的i<5，也變成了3*i<15，而3*i又等于a[i]，因此當(dāng)整個數(shù)組當(dāng)中循環(huán)的索引i，滿足a[i+1]=15（注意，在循環(huán)內(nèi)的時候，%eax一直儲存著a[i+1]的值，除了剛開始的0）的時候，說明循環(huán)該結(jié)束了，也就是coml和jne指令所做的事。

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

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

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

.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

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

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

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

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

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

　　接下來，我們看看比較復(fù)雜的一段代碼，這一段代碼的主要目的，是為動態(tài)數(shù)組分配內(nèi)存。它們是如下的這些指令

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

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

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

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

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

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

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

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

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

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

4n <= stack <= 4n + 15

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

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

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

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

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

異質(zhì)結(jié)構(gòu)與數(shù)據(jù)對齊

　　異質(zhì)結(jié)構(gòu)是指不同數(shù)據(jù)類型的數(shù)組組合，比如C語言當(dāng)中的結(jié)構(gòu)（struct）與聯(lián)合（union）。在理解數(shù)組的基礎(chǔ)上，這兩種數(shù)據(jù)結(jié)構(gòu)都非常好理解。我們先來看一個結(jié)構(gòu)的例子，比如下面的這個結(jié)構(gòu)。

#include <stdio.h>

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

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

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

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

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

　　與結(jié)構(gòu)體不同的是，聯(lián)合會復(fù)用內(nèi)存空間，以節(jié)省內(nèi)存，比如我們看下面這個例子。

#include <stdio.h>

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

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

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

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

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

淺談數(shù)組與指針

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

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評論