Rust效能分析：堆疊與堆積中的陣列

陣列是處理多筆資料時常用的資料結構，它是一塊在記憶體中連續的空間，通常會利用元素的大小來將這塊空間切割成若干份來使用。舉例來說，一塊1KiB的記憶體空間，如果將它當作位元組(byte)陣列的話，可以存放1024個位元組資料(長度為1024)，第一個元素的記憶體位址如果是0，第二個元素就是1，第三個就是2。而如果我們將這塊1KiB的記憶體空間當作32位元整數陣列的話，此時它能存放256個32位元整數資料(長度為256)，第一個元素的記憶體位址如果是0，第二個元素就是4，第三個就是8，依此類推。程式的記憶體分為堆疊(stack)和堆積(heap)兩個區塊，陣列可以在這兩個區塊上使用，但是會有一些差異。

存在於堆疊中的陣列，其陣列長度必須要在編譯階段的時候就能知道(換句話說就是它只能是固定長度的陣列)，且那塊陣列空間會在程式執行階段時，在陣列所在的函數被呼叫的時候跟著該函數的堆疊空間一起被建立出來。也就是說如果某個函數中有使用到一個堆疊陣列，這個堆疊陣列所使用到的堆疊空間就會在這個函數的堆疊空間之內，也因此堆疊中的陣列有在同一個函數內才能夠存取得到。一個程式執行緒所能使用的堆疊空間是有限的，一般只有幾個MB，因此要謹慎使用，避免發生「堆疊溢出」(Stack Overflow)。

而存在於堆積中的陣列，其陣列長度不一定要在編譯階段的時候就決定好，且那塊陣列空間是在程式執行階段時，有進行「allocating」(配置)的動作，程式才會在當下去尋找堆積中有哪塊足夠大的連續空間能夠拿來作為陣列空間來使用，並取得這塊空間最一開始的記憶體位址。

不同的程式語言對於如何操作堆積有不同的實作方式，例如Java、Golang等使用了垃圾回收和索引範圍檢查等機制來管理堆積。這類的作法可以確保不同資料不會同時使用到重複的記憶體區塊，也確保不會因為程式碼的撰寫失誤而導致存取到配置區塊外的記憶體空間，甚至還可以確保資料在不會再被使用到的時候能夠將記憶體空間釋放出來給其它的資料使用。但也因此會讓CPU需要多做一些事情才能存取堆積，而導致堆積的效能比堆疊還要慢。Rust程式語言雖然有比上述提到的程式語言好一點，有利用強大的編譯檢查取代最吃資源的垃圾回收機制，但剩下的管理機制還是多少會影響到堆積的效能。

大致上了解堆疊中的陣列和堆積中的陣列的差異之後，來看看Rust程式語言內建的陣列型別吧！

Rust程式語言的陣列型別

[T; size]

以下程式，可以在堆疊中建立出一個長度為8的u8陣列，其型別為[u8; 8]。這種陣列的長度是不可變的。

let mut array: [u8; 8] = [0u8; 8];

Box<[T; size]>

以下程式，可以在堆積中建立出一個長度為8的u8陣列，其型別為Box<[u8; 8]>。這種陣列的長度是不可變的。

let mut array: Box<[u8; 8]> = {
    let v = vec![0u8; 8];

    let a = v.into_boxed_slice();

    unsafe {
        Box::from_raw(Box::into_raw(a) as *mut [u8; 8])
    };
}

或是用以下方式也行。不過這種方式有很大的問題，應避免使用，稍候會說明原因。

let mut array: Box<[u8; 8]> = Box::new([0u8; 8]);

Vec<T>

以下程式，可以在堆積中建立出一個長度為8的u8陣列，其型別為Vec<u8>。這種陣列的長度是可變的。

let mut array: Vec<u8> = vec![0u8; 8];

Box<[T]>

以下程式，可以在堆積中建立出一個長度為8的u8陣列，其型別為Box<[u8]>。這種陣列的長度是不可變的。

let mut array: Box<[u8]> = vec![0u8; 8].into_boxed_slice();

&[T]

Rust程式語言的切片其實也可以當成是陣列，但在本篇文章中先不討論這個。有關切片對陣列所造成的效能影響，可以在閱讀完這篇文章之後，再參考這篇文章：

未測先猜哪種陣列效能好

以上提到的[T; size]、Box<[T; size]>、Vec<T>、Box<[T]>這四種陣列，效能的差異究竟如何呢？以直覺來猜的話，存在於堆疊的[T; size]必定會比另外三者堆積中的陣列好。而Box<[T; size]>是在編譯階段就可以知道大小的陣列，它的效能應該也會比剩下的另外兩個好。再來是長度不可變的Box<[T]>，它的效能應該會比長度可變得Vec<T>好。

於是我們猜測出來的效能排名為：

實測看看？

為了驗證我們的猜測，就要實際寫一段程式來測試運算效能啦！這段程式可以在GitHub上取得：

由於Box<[T; size]>的部份有提到兩種產生方式，我們將第一種稱為Box<[T; size]>，第二種稱為Box<[T; size]>_2好了。針對這五種型別的建立速度和存取速度，我們來討論實際測試之後的結果吧！

建立速度

存取速度

結論

Box<[T; size]>_2的產生速度遠遠要比其它四種還來得慢，這是因為Box<[T; size]>_2的程式撰寫方式，是先在堆疊產生出陣列之後，再在堆積中配置陣列空間，然後把堆疊中陣列的資料複製過來的原因。繞了一大圈，太花時間了，而且陣列長度如果夠大的話也依然會發生堆疊溢出的問題。這就是為什麼最好不要用這種方式產生Box<[T; size]>的關係。

在堆疊中的陣列，如同我們預期地，無論在建立或是存取都比在堆積中的陣列還要來得快。然而，長度可變的Vec<T>存取效能是與長度不可變但在編譯階段就知道長度的陣列差不多的，甚至還比長度不可變的Box<[T]>還要好，這應該是編譯器優化的關係。

也就是說，為了達到良好的程式效能，當陣列夠小且可以在編譯的時候就知道長度的時候，我們應該要儘量使用[T; size]作為陣列型別；當資料量比較大或是無法在編譯時就知道長度的時候，我們直接使用Vec<T>來在堆積中產生長度可變的陣列即可，不需要再多此一舉地把它變成長度不可變的陣列。