陣列是處理多筆資料時常用的資料結構,它是一塊在記憶體中連續的空間,通常會利用元素的大小來將這塊空間切割成若干份來使用。舉例來說,一塊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]
[u8; 8]
let mut array: [u8; 8] = [0u8; 8];
Box<[T; size]>
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
Vec
let mut array: Vec<u8> = vec![0u8; 8];
Box<[T]>
Box<[u8]>
let mut array: Box<[u8]> = vec![0u8; 8].into_boxed_slice();
&[T]

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

未測先猜哪種陣列效能好

[T; size]Box<[T; size]>VecBox<[T]>[T; size]Box<[T; size]>Box<[T]>Vec

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

[T; size]Box<[T; size]>Box<[T]>Vec

實測看看?

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

Box<[T; size]>Box<[T; size]>Box<[T; size]>_2
建立速度
[T; size]Box<[T; size]>Vec, Box<[T]>Box<[T; size]>_2
存取速度
[T; size]Box<[T; size]>Box<[T; size]>_2VecBox<[T]>
結論
Box<[T; size]>_2Box<[T; size]>_2Box<[T; size]>
VecBox<[T]>
[T; size]Vec