コレクション

いずれは、プログラム内で動的なデータ構造（別名コレクション）を使いたいでしょう。 stdは、VecやString、HashMapといった、一般的なコレクションを提供しています。 stdで実装されている全てのコレクションは、グローバルな動的アロケータ（別名ヒープ）を使用します。

coreは、定義上、メモリアロケーションがないためコレクションの実装を使うことができません。しかし、コンパイラと共に配布されている安定化していないallocクレートの中にコレクションの実装があります。

もしコレクションが必要であれば、ヒープに割り当てる実装だけが選択肢ではありません。 サイズが固定されたコレクションを使うことができます。そのような実装はheaplessクレートの中にあります。

このセクションでは、コレクションの２つの実装を取り上げ、比較します。

`alloc`を使用

allocクレートは、標準のRust配布物に同梱されています。このクレートをインポートするには、 Cargo.tomlファイルに依存関係を宣言することなしに直接useします。

#![feature(alloc)]

extern crate alloc;

use alloc::vec::Vec;

コレクションを使うには、まず最初に、プログラム中のグローバルアロケータを宣言するglobal_allocatorアトリビュートを使う必要があります。選択したアロケータがGlobalAllocトレイトを実装することが求められます。

このセクションを可能な限り自己完結させるため、グローバルアロケータとして、単純にポインタを増加するだけのアロケータを実装します。しかしながら、あなたのプログラムではこのアロケータでなく、crates.ioから歴戦のアロケータを使用することを強くお勧めします。

// Bump pointer allocator implementation
// ポインタを増加するだけのアロケータ実装

extern crate cortex_m;

use core::alloc::GlobalAlloc;
use core::ptr;

use cortex_m::interrupt;

// Bump pointer allocator for *single* core systems
// *シングル*コアシステム用のポインタを増加するだけのアロケータ
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` is a critical section that makes our allocator safe
        // to use from within interrupts
        // `interrupt::free`は、割り込み内でアロケータを安全に使用するための
        // クリティカルセクションです。
        interrupt::free(|_| {
            let head = self.head.get();

            let align = layout.align();
            let res = *head % align;
            let start = if res == 0 { *head } else { *head + align - res };
            if start + align > self.end {
                // a null pointer signal an Out Of Memory condition
                // ヌルポインタはメモリ不足の状態を知らせます
                ptr::null_mut()
            } else {
                *head = start + align;
                start as *mut u8
            }
        })
    }

    unsafe fn dealloc(&self, _: *mut u8, _: Layout) {
        // this allocator never deallocates memory
        // このアロケータはメモリを解放しません
    }
}

// Declaration of the global memory allocator
// NOTE the user must ensure that the memory region `[0x2000_0100, 0x2000_0200]`
// is not used by other parts of the program
// グローバルメモリアロケータの宣言
// ユーザはメモリ領域の`[0x2000_0100, 0x2000_0200]`がプログラムの他の部分で使用されないことを
// 保証しなければなりません
#[global_allocator]
static HEAP: BumpPointerAlloc = BumpPointerAlloc {
    head: UnsafeCell::new(0x2000_0100),
    end: 0x2000_0200,
};

グローバルアロケータの選択とは別に、ユーザはメモリ不足（OOM）エラーの処理方法を、 安定化していないalloc_error_handlerアトリビュートを使って定義する必要があります。

#![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して、インスタンスを作成するだけです。

extern crate 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));
}

allocのコレクションとは違う点が2つあることに留意して下さい。

1つ目は、コレクションの容量を最初に宣言しなければならないことです。 heaplessコレクションは、再割り当てが発生せず、固定の容量になります。この容量はコレクションの型シグネチャの一部になります。上記の例では、xsは8要素の容量を持つように宣言しています。このベクタは最大で8つの要素を保持することができます。型シグネチャのU8（typenumを参照）がこのことを表しています。

2つ目は、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; Worst Case Execution Time）

時間制約のあるアプリケーションやハードリアルタイムアプリケーションを作成している場合、プログラムの様々な部分で最悪実行時間が気になるでしょう。

allocコレクションは再割り当てする可能性があるため、コレクションが拡大する操作の最悪実行時間は、コレクションが再割り当てされるのにかかる時間も含みます。コレクションが再割り当てされるかどうかは、実行時のコレクションの容量に依存します。このことは、alloc::Vec.pushといった操作の最悪実行時間の決定を難しくします。この操作の最悪実行時間は、使用するアロケータとコレクションの実行時容量との両方に依存するためです。

一方、固定容量のコレクションは再割り当てが発生しないため、全ての操作の実行時間が予測可能です。例えば、heapless::Vec.pushは定数時間で実行します。

使いやすさ

allocはグローバルアロケータの準備が必要ですが、heaplessはそうではありません。しかし、heaplessは、インスタンスを作成する各コレクションの容量を指定する必要があります。

alloc APIは、事実上、全てのRust開発者がなじみのあるものです。 heapless APIは、alloc APIに似せてはいますが、明示的なエラー処理のため、全く同じにはなりません。一部の開発者はこの明示的なエラー処理を、度が過ぎていたり、面倒すぎる、と感じるかもしれません。

The Embedded Rust Book