集合

最終你會想在程式中使用動態資料結構（亦即集合）。std 提供一組常見集合：Vec、String、HashMap 等。std 中實作的所有集合都使用全域動態記憶體配置器（亦即堆積）。

由於 core 定義上不含記憶體配置，因此這些實作在那裡不可用，但可在隨編譯器提供的 alloc 套件中找到。

如果你需要集合，堆積配置的實作並非唯一選擇。你也可以使用_固定容量_集合；其中一種實作可見於 heapless 套件。

在本節中，我們會探索並比較這兩種實作。

使用 alloc

alloc 套件隨標準 Rust 發行版一同提供。要匯入此套件，你可以直接 use 它，不需要 在 Cargo.toml 中宣告相依。

#![feature(alloc)]

extern crate alloc;

use alloc::vec::Vec;

要能使用任何集合，你首先需要用 global_allocator 屬性宣告程式所使用的全域配置器。你選擇的配置器必須實作 GlobalAlloc trait。

為了完整性並盡量讓本節自足，我們會實作一個簡單的指標遞增（bump pointer）配置器並將其作為全域配置器。然而，我們_強烈_建議你在程式中使用 crates.io 上久經考驗的配置器，而不是此配置器。

// 指標遞增配置器實作

use core::alloc::{GlobalAlloc, Layout};
use core::cell::UnsafeCell;
use core::ptr;

use cortex_m::interrupt;

// 適用於*單核心*系統的指標遞增配置器
struct BumpPointerAlloc {
    head: UnsafeCell<usize>,
    end: usize,
}

unsafe impl Sync for BumpPointerAlloc {}

unsafe impl GlobalAlloc for BumpPointerAlloc {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        // `interrupt::free` 是臨界區，讓我們的配置器可安全
        // 在中斷內使用
        interrupt::free(|_| {
            let head = self.head.get();
            let size = layout.size();
            let align = layout.align();
            let align_mask = !(align - 1);

            // 將起點移到下一個對齊邊界
            let start = (*head + align - 1) & align_mask;

            if start + size > self.end {
                // 空指標代表記憶體不足（OOM）
                ptr::null_mut()
            } else {
                *head = start + size;
                start as *mut u8
            }
        })
    }

    unsafe fn dealloc(&self, _: *mut u8, _: Layout) {
        // 此配置器從不釋放記憶體
    }
}

// 全域記憶體配置器的宣告
// 注意：使用者必須確保記憶體區域 `[0x2000_0100, 0x2000_0200]`
// 未被程式的其他部分使用
#[global_allocator]
static HEAP: BumpPointerAlloc = BumpPointerAlloc {
    head: UnsafeCell::new(0x2000_0100),
    end: 0x2000_0200,
};

除了選擇全域配置器之外，使用者還必須使用_不穩定_的 alloc_error_handler 屬性來定義如何處理記憶體不足（OOM）錯誤。

#![feature(alloc_error_handler)]

use cortex_m::asm;

#[alloc_error_handler]
fn on_oom(_layout: Layout) -> ! {
    asm::bkpt();

    loop {}
}

當上述一切就緒後，使用者終於可以使用 alloc 中的集合。

#[entry]
fn main() -> ! {
    let mut xs = Vec::new();

    xs.push(42);
    assert!(xs.pop(), Some(42));

    loop {
        // ..
    }
}

如果你用過 std 套件的集合，這些會很熟悉，因為實作完全相同。

使用 heapless

heapless 不需要任何設定，因為其集合不依賴全域記憶體配置器。只要 use 其集合並直接建立實例即可：

// heapless 版本：v0.4.x
use heapless::Vec;
use heapless::consts::*;

#[entry]
fn main() -> ! {
    let mut xs: Vec<_, U8> = Vec::new();

    xs.push(42).unwrap();
    assert_eq!(xs.pop(), Some(42));
    loop {}
}

你會注意到這些集合與 alloc 中的集合有兩個差異。

第一，你必須事先宣告集合容量。heapless 集合不會重新配置，且容量固定；容量是集合型別簽名的一部分。在此例中，我們宣告 xs 容量為 8 個元素，也就是這個向量最多只能容納 8 個元素。這會在型別簽名中以 U8 表示（見typenum）。

第二，push 與許多其他方法會回傳 Result。由於 heapless 集合容量固定，所有插入元素的操作都有可能失敗。API 透過回傳 Result 來反映此問題，以表示操作是否成功。相較之下，alloc 集合會在堆積上重新配置以擴增容量。

截至 v0.4.x 版本，所有 heapless 集合都將元素內嵌存放。這意味著像 let x = heapless::Vec::new(); 這樣的操作會在堆疊上配置集合，但也可以將集合配置在 static 變數上，甚至放在堆積上（Box<Vec<_, _>>）。

取捨

在選擇可在堆積配置、可搬移的集合與固定容量集合時，請記住以下重點。

記憶體不足與錯誤處理

使用堆積配置時，記憶體不足總是有可能發生，且可能出現在集合需要成長的任何地方：例如所有 alloc::Vec.push 都可能引發 OOM。因此某些操作可能會_隱含_失敗。有些 alloc 集合提供 try_reserve 方法，讓你在擴充集合時檢查可能的 OOM 狀況，但你必須主動使用它們。

若你只使用 heapless 集合，且不把記憶體配置器用於其他用途，那麼 OOM 就不可能發生。取而代之，你必須逐案處理集合容量耗盡的情況。也就是說，你必須處理像 Vec.push 這類方法回傳的_所有_ Result。

OOM 失敗可能比在 heapless::Vec.push 回傳的所有 Result 上做 unwrap 更難除錯，因為觀察到的失敗位置可能_不_等於問題原因的位置。例如，如果配置器幾乎耗盡，即使 vec.reserve(1) 也可能觸發 OOM，原因可能是其他集合在洩漏記憶體（安全 Rust 也可能發生記憶體洩漏）。

記憶體使用

推論堆積配置集合的記憶體用量很困難，因為長生命週期集合的容量可在執行期變動。有些操作可能會隱含地重新配置集合並增加記憶體用量，有些集合提供像 shrink_to_fit 的方法，可能降低集合的記憶體使用量——最終是否實際縮減配置仍取決於配置器。此外，配置器可能還需處理記憶體碎片化，這會增加_表觀_記憶體用量。

另一方面，若你只使用固定容量集合、將大多數放在 static 變數中，並為呼叫堆疊設定最大大小，那麼連結器會在你嘗試使用超過實體可用記憶體時偵測到。

此外，堆疊上配置的固定容量集合會被 -Z emit-stack-sizes 旗標回報，這表示分析堆疊使用量的工具（如 stack-sizes）會將它們納入分析。

然而，固定容量集合_無法_縮小，這可能導致裝載率（集合大小與容量的比例）低於可搬移集合所能達到的程度。

最壞執行時間（WCET）

如果你在打造時間敏感或硬即時的應用程式，那麼你會非常在意程式各部分的最壞執行時間。

alloc 集合可以重新配置，因此可能增長集合的操作，其 WCET 也包含重新配置所需的時間，而這又取決於集合的_執行期_容量。這使得像 alloc::Vec.push 這樣的操作難以確定 WCET，因為它取決於使用的配置器與執行期容量。

另一方面，固定容量集合從不重新配置，因此所有操作都有可預測的執行時間。例如，heapless::Vec.push 以常數時間執行。

易用性

alloc 需要設定全域配置器，而 heapless 不需要。然而，heapless 需要你為每個實例化的集合選擇容量。

alloc 的 API 幾乎對每位 Rust 開發者都很熟悉。heapless 的 API 嘗試緊密模仿 alloc API，但因為明確的錯誤處理，它永遠不可能完全相同——有些開發者可能覺得明確的錯誤處理過於冗長或太繁瑣。