コレクション

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

定義上、core はメモリ割り当てを含まないため、これらの実装はそこでは利用できませんが、コンパイラに同梱されている alloc クレートで利用できます。

コレクションが必要な場合でも、ヒープ割り当てされた実装だけが唯一の選択肢ではありません。固定容量 のコレクションを使うこともできます。そのような実装の 1 つは heapless クレートにあります。

このセクションでは、これら 2 つの実装を調べて比較します。

`alloc` を使う

alloc クレートは、標準の Rust ディストリビューションに同梱されています。このクレートをインポートするには、Cargo.toml ファイルで依存関係として宣言しなくても、直接 use できます。

#![feature(alloc)]

extern crate alloc;

use alloc::vec::Vec;

任意のコレクションを使えるようにするには、まず global_allocator 属性を使って、プログラムが使用するグローバルアロケータを宣言する必要があります。選択したアロケータは GlobalAlloc トレイトを実装している必要があります。

完全性のため、またこのセクションをできるだけ自己完結させるために、ここでは単純なバンプポインタアロケータを実装し、それをグローバルアロケータとして使います。ただし、このアロケータの代わりに、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 {
                // null ポインタは Out Of Memory 状態を示す
                ptr::null_mut()
            } else {
                *head = start + size;
                start as *mut u8
            }
        })
    }

    unsafe fn dealloc(&self, _: *mut u8, _: Layout) {
        // このアロケータはメモリを解放しない
    }
}

// グローバルメモリアロケータの宣言
// NOTE ユーザーは、メモリ領域 `[0x2000_0100, 0x2000_0200]` が
// プログラムのほかの部分で使われないことを保証しなければならない
#[global_allocator]
static HEAP: BumpPointerAlloc = BumpPointerAlloc {
    head: UnsafeCell::new(0x2000_0100),
    end: 0x2000_0200,
};

グローバルアロケータの選択に加えて、ユーザーは unstable な alloc_error_handler 属性を使って、Out Of Memory（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 のコレクションの間には、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<_, _>>）にコレクションを割り当てることも可能です。

トレードオフ

ヒープ割り当てされ、再配置可能なコレクションと、固定容量のコレクションのどちらを選ぶかを考える際には、以下を念頭に置いてください。

Out Of Memory とエラーハンドリング

ヒープ割り当てでは、Out Of Memory は常に起こり得るものであり、コレクションが成長する必要があるあらゆる場所で発生する可能性があります。たとえば、すべての alloc::Vec.push 呼び出しは OOM 状態を引き起こす可能性があります。したがって、一部の操作は 暗黙的に 失敗する可能性があります。一部の alloc コレクションは try_reserve メソッドを公開しており、コレクションを拡張する際の潜在的な OOM 状態を確認できますが、それらを積極的に使う必要があります。

heapless コレクションだけを使い、それ以外の用途でメモリアロケータを使用しないのであれば、OOM 状態は不可能です。その代わりに、コレクションの容量不足をケースごとに処理する必要があります。つまり、Vec.push のようなメソッドが返すすべての Result を処理しなければなりません。

OOM 障害は、たとえば heapless::Vec.push が返すすべての Result に対して unwrap する場合よりもデバッグが難しいことがあります。なぜなら、観測された障害発生箇所が、問題の原因となった箇所と 一致しない 可能性があるからです。たとえば、vec.reserve(1) ですら、アロケータがほぼ使い尽くされている場合には OOM を引き起こすことがあります。その原因が、ほかのコレクションによるメモリリークであることもあり得ます（メモリリークは safe 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 をできるだけ忠実に模倣しようとしていますが、明示的なエラーハンドリングがあるため、完全に同じになることはありません – この明示的なエラーハンドリングを過剰、あるいは煩雑すぎると感じる開発者もいるかもしれません。

Keyboard shortcuts

The Embedded Rust Book