Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

ヒープ割り当て

ヒープ割り当てはそれなりに高コストです。正確な詳細は使用中の アロケータによって異なりますが、各割り当て（および解放）では通常、 グローバルロックの取得、重要なデータ構造操作、 そして場合によってはシステムコールの実行が伴います。小さな割り当てが 大きな割り当てより必ずしも低コストであるとは限りません。どの Rust の データ構造や操作が割り当てを引き起こすかを理解しておく価値があります。 それらを避けることで、パフォーマンスを大幅に改善できる可能性があるためです。

Rust Container Cheat Sheet には一般的な Rust 型の可視化が掲載されており、 以降のセクションの優れた副読本になります。

プロファイリング

汎用プロファイラで malloc、free、および関連する関数がホットであると 示される場合、割り当て率を下げることや、代替アロケータを使用することを 試す価値がある可能性が高いです。

DHAT は割り当て率を下げる際に使用する優れたプロファイラです。 Linux と一部の他の Unix で動作します。ホットな割り当て箇所と その割り当て率を正確に特定します。正確な結果はさまざまですが、 rustc での経験では、実行された 100 万命令あたり 10 回の割り当てを 削減すると、測定可能なパフォーマンス改善（例: 約 1%）が得られることが 示されています。

以下は DHAT からの出力例です。

AP 1.1/25 (2 children) {
  Total:     54,533,440 bytes (4.02%, 2,714.28/Minstr) in 458,839 blocks (7.72%, 22.84/Minstr), avg size 118.85 bytes, avg lifetime 1,127,259,403.64 instrs (5.61% of program duration)
  At t-gmax: 0 bytes (0%) in 0 blocks (0%), avg size 0 bytes
  At t-end:  0 bytes (0%) in 0 blocks (0%), avg size 0 bytes
  Reads:     15,993,012 bytes (0.29%, 796.02/Minstr), 0.29/byte
  Writes:    20,974,752 bytes (1.03%, 1,043.97/Minstr), 0.38/byte
  Allocated at {
    #1: 0x95CACC9: alloc (alloc.rs:72)
    #2: 0x95CACC9: alloc (alloc.rs:148)
    #3: 0x95CACC9: reserve_internal<syntax::tokenstream::TokenStream,alloc::alloc::Global> (raw_vec.rs:669)
    #4: 0x95CACC9: reserve<syntax::tokenstream::TokenStream,alloc::alloc::Global> (raw_vec.rs:492)
    #5: 0x95CACC9: reserve<syntax::tokenstream::TokenStream> (vec.rs:460)
    #6: 0x95CACC9: push<syntax::tokenstream::TokenStream> (vec.rs:989)
    #7: 0x95CACC9: parse_token_trees_until_close_delim (tokentrees.rs:27)
    #8: 0x95CACC9: syntax::parse::lexer::tokentrees::<impl syntax::parse::lexer::StringReader<'a>>::parse_token_tree (tokentrees.rs:81)
  }
}

この例のすべてを説明することは本書の範囲外ですが、DHAT が割り当てに 関する豊富な情報を提供することは明らかなはずです。たとえば、割り当てが どこでどれくらいの頻度で発生するか、どれくらいの大きさか、どれくらいの 期間生存するか、どれくらいの頻度でアクセスされるかといった情報です。

Box

Box は最も単純なヒープ割り当て型です。Box<T> 値は、ヒープ上に 割り当てられた T 値です。

型を小さくするために、構造体の 1 つ以上のフィールドや enum のフィールドを Box 化する価値がある場合があります。（これについて詳しくは 型サイズ の章を参照してください。）

それ以外の点では、Box は単純であり、最適化の余地はあまりありません。

Rc/Arc

Rc/Arc は Box に似ていますが、ヒープ上の値には 2 つの参照カウントが 付随します。これらは値の共有を可能にし、メモリ使用量を削減する効果的な 方法になり得ます。

しかし、めったに共有されない値に使うと、本来はヒープ割り当てされなかった 可能性のある値をヒープ割り当てすることになり、割り当て率が増える可能性が あります。例。

Box とは異なり、Rc/Arc 値に対して clone を呼び出しても割り当ては 発生しません。代わりに、参照カウントを単にインクリメントするだけです。

Vec

Vec はヒープ割り当て型であり、割り当て回数の最適化や、無駄な領域の量の 最小化について大きな余地があります。これを行うには、その要素がどのように 格納されるかを理解する必要があります。

Vec には、長さ、容量、ポインタという 3 つのワードが含まれます。容量が 非ゼロで、要素サイズが非ゼロの場合、そのポインタはヒープ割り当てされた メモリを指します。それ以外の場合、割り当てられたメモリは指しません。

Vec 自体がヒープ割り当てされていない場合でも、要素（存在し、サイズが 非ゼロの場合）は常にヒープ割り当てされます。非ゼロサイズの要素が存在する 場合、それらの要素を保持するメモリは必要以上に大きいことがあり、将来追加 される要素のための領域を提供します。存在する要素の数が長さであり、再割り 当てなしに保持できる要素の数が容量です。

ベクターが現在の容量を超えて成長する必要がある場合、要素はより大きな ヒープ割り当てにコピーされ、古いヒープ割り当ては解放されます。

Vec の成長

一般的な方法 （vec![] または Vec::new、または Vec::default）で作成された新しい空の Vec は、 長さと容量がゼロであり、ヒープ割り当ては不要です。個々の要素を Vec の 末尾に繰り返し push していくと、定期的に再割り当てが行われます。成長戦略は 仕様として定められていませんが、執筆時点では準倍増戦略を使用しており、 結果として容量は 0、4、8、16、32、64、というようになります。（実用上 多くの割り当てを避けられる ため、1 と 2 を経由する代わりに 0 から 4 へ 直接飛びます。）ベクターが成長するにつれて、再割り当ての頻度は指数関数的に 減少しますが、無駄になる可能性のある余剰容量の量は指数関数的に増加します。

この成長戦略は、成長可能なデータ構造としては典型的であり、一般的な場合には 妥当です。しかし、ベクターのおおよその長さが事前に分かっている場合は、 より良くできることがよくあります。ホットなベクター割り当て箇所（例: ホットな Vec::push 呼び出し）がある場合、その箇所で eprintln! を使用して ベクターの長さを出力し、その後（たとえば counts を使って）後処理を行い、 長さの分布を判断する価値があります。たとえば、多数の短いベクターがあるかも しれませんし、少数の非常に長いベクターがあるかもしれません。そして割り当て 箇所を最適化する最善の方法は、それに応じて異なります。

短い Vec

短いベクターが多数ある場合は、smallvec crate の SmallVec 型を使用できます。SmallVec<[T; N]> は Vec のドロップイン置換であり、SmallVec 自体の内部に N 個の要素を格納できます。そして、要素数がそれを超えるとヒープ割り当てに切り替わります。（vec![] リテラルも smallvec![] リテラルに置き換える必要があることにも注意してください。） 例 1, 例 2.

SmallVec は適切に使用すれば割り当て率を確実に下げますが、その使用がパフォーマンス向上を保証するわけではありません。通常の操作では、要素がヒープに割り当てられているかどうかを常に確認する必要があるため、Vec よりもわずかに遅くなります。また、N が大きい場合や T が大きい場合、SmallVec<[T; N]> 自体が Vec<T> よりも大きくなることがあり、SmallVec 値のコピーは遅くなります。いつものように、最適化が有効であることを確認するにはベンチマークが必要です。

短いベクターが多数あり、かつ その最大長を正確に知っている場合は、arrayvec crate の ArrayVec が SmallVec よりも適した選択肢です。ヒープ割り当てへのフォールバックが不要なため、少し高速です。 例.

より長い Vec

ベクターの最小サイズまたは正確なサイズがわかっている場合は、Vec::with_capacity、Vec::reserve、または Vec::reserve_exact を使用して特定の容量を予約できます。たとえば、あるベクターが少なくとも 20 個の要素を持つまで成長することがわかっている場合、これらの関数は単一の割り当てで少なくとも 20 の容量を持つベクターを即座に提供できます。一方、項目を 1 つずつ push すると、4 回の割り当て（容量 4、8、16、32）が発生します。 例.

ベクターの最大長がわかっている場合、上記の関数により、余分な領域を不要に割り当てないようにすることもできます。同様に、Vec::shrink_to_fit を使用して無駄な領域を最小限に抑えることができますが、再割り当てが発生する可能性がある点に注意してください。

String

String はヒープに割り当てられたバイト列を含みます。String の表現と操作は Vec<u8> のそれと非常によく似ています。成長や容量に関連する多くの Vec メソッドには、String::with_capacity など、String 用の同等のものがあります。

smallstr crate の SmallString 型は、SmallVec 型に似ています。

smartstring crate の String 型は、3 ワード分未満の文字を持つ文字列についてヒープ割り当てを回避する、String のドロップイン置換です。64 ビットプラットフォームでは、これは 24 バイト未満の任意の文字列であり、23 文字以下の ASCII 文字を含むすべての文字列が含まれます。 例.

format! マクロは String を生成するため、割り当てを実行することに注意してください。文字列リテラルを使用して format! 呼び出しを避けられる場合は、この割り当てを回避できます。 例. std::format_args や lazy_format crate が役立つ場合があります。

ハッシュテーブル

HashSet と HashMap はハッシュテーブルです。割り当ての観点では、それらの表現と操作は Vec のものに似ています。キーと値を保持する単一の連続したヒープ割り当てを持ち、テーブルが成長するにつれて必要に応じて再割り当てされます。成長や容量に関連する多くの Vec メソッドには、HashSet::with_capacity など、HashSet/HashMap 用の同等のものがあります。

clone

ヒープに割り当てられたメモリを含む値に対して clone を呼び出すと、通常は追加の割り当てが発生します。たとえば、空でない Vec に対して clone を呼び出すには、要素用の新しい割り当てが必要です（ただし、新しい Vec の容量が元の Vec の容量と同じであるとは限らないことに注意してください）。例外は Rc/Arc で、この場合 clone 呼び出しは参照カウントをインクリメントするだけです。

clone_from は clone の代替です。a.clone_from(&b) は a = b.clone() と等価ですが、不要な割り当てを回避できる場合があります。たとえば、ある Vec を既存の Vec の上に clone したい場合、次の例が示すように、可能であれば既存の Vec のヒープ割り当てが再利用されます。

#![allow(unused)]
fn main() {
let mut v1: Vec<u32> = Vec::with_capacity(99);
let v2: Vec<u32> = vec![1, 2, 3];
v1.clone_from(&v2); // v1 の割り当てが再利用される
assert_eq!(v1.capacity(), 99);
}

clone は通常割り当てを引き起こしますが、多くの状況で使用するのは妥当であり、コードをより単純にできることがよくあります。プロファイリングデータを使用して、どの clone 呼び出しがホットであり、回避する労力をかける価値があるかを確認してください。

Rust コードには、(a) プログラマーの誤り、または (b) 以前は必要だった clone 呼び出しを不要にするコードの変更により、不要な clone 呼び出しが含まれてしまうことがあります。必要に見えないホットな clone 呼び出しを見つけた場合、単純に削除できることがあります。 例 1, 例 2, 例 3.

to_owned

[ToOwned::to_owned] は多くの一般的な型に対して実装されています。これは通常 clone によって、借用データから所有データを作成するため、多くの場合ヒープ割り当てを引き起こします。たとえば、&str から String を作成するために使用できます。 [ToOwned::to_owned]: https://doc.rust-lang.org/std/borrow/trait.ToOwned.html#tymethod.to_owned

to_owned の呼び出し（および clone や to_string などの関連する呼び出し）は、所有されたコピーではなく、借用されたデータへの参照を構造体に保存することで回避できる場合があります。これには構造体へのライフタイム注釈が必要になり、コードが複雑になるため、プロファイリングとベンチマークによって価値があることが示された場合にのみ行うべきです。 例。

Cow

コードが、借用されたデータと所有されたデータが混在したものを扱う場合があります。エラーメッセージのベクターを想像してください。その一部は静的文字列リテラルで、一部は format! で構築されます。明らかな表現は、次の例に示すように Vec<String> です。

#![allow(unused)]
fn main() {
let mut errors: Vec<String> = vec![];
errors.push("something went wrong".to_string());
errors.push(format!("something went wrong on line {}", 100));
}

これには、静的文字列リテラルを String に昇格させるための to_string 呼び出しが必要であり、アロケーションが発生します。

代わりに Cow 型を使用できます。これは、借用されたデータまたは所有されたデータのいずれかを保持できます。借用された値 x は Cow::Borrowed(x) でラップされ、所有された値 y は Cow::Owned(y) でラップされます。Cow はさまざまな文字列、スライス、パス型に対して From<T> トレイトも実装しているため、通常は into も使用できます。（または Cow::from も使用できます。これは長くなりますが、型がより明確になるため、コードの可読性が高くなります。）次の例では、これらをすべてまとめています。

#![allow(unused)]
fn main() {
use std::borrow::Cow;
let mut errors: Vec<Cow<'static, str>> = vec![];
errors.push(Cow::Borrowed("something went wrong"));
errors.push(Cow::Owned(format!("something went wrong on line {}", 100)));
errors.push(Cow::from("something else went wrong"));
errors.push(format!("something else went wrong on line {}", 101).into());
}

これで errors は、追加のアロケーションを必要とせずに、借用されたデータと所有されたデータの混在を保持します。この例では &str/String を扱っていますが、&[T]/Vec<T> や &Path/PathBuf などの他の組み合わせも可能です。

例 1, 例 2。

データが不変である場合、上記のすべてが当てはまります。しかし、Cow は、変更が必要になった場合に、借用されたデータを所有されたデータへ昇格させることもできます。Cow::to_mut は所有された値への可変参照を取得し、必要に応じてクローンします。これは「clone-on-write」と呼ばれ、Cow という名前の由来です。

この clone-on-write の挙動は、&str のような借用されたデータがあり、それがほとんど読み取り専用だが、ときどき変更する必要がある場合に有用です。

例 1, 例 2。

最後に、Cow は Deref を実装しているため、内包するデータに対してメソッドを直接呼び出すことができます。

Cow を動作させるのは扱いづらいことがありますが、多くの場合、その労力に見合います。

コレクションの再利用

Vec のようなコレクションを段階的に構築する必要がある場合があります。通常は、複数の Vec を構築してから結合するよりも、単一の Vec を変更することでこれを行う方が適切です。

たとえば、複数回呼び出される可能性がある Vec を生成する関数 do_stuff がある場合:

#![allow(unused)]
fn main() {
fn do_stuff(x: u32, y: u32) -> Vec<u32> {
    vec![x, y]
}
}

代わりに、渡された Vec を変更する方がよい場合があります:

#![allow(unused)]
fn main() {
fn do_stuff(x: u32, y: u32, vec: &mut Vec<u32>) {
    vec.push(x);
    vec.push(y);
}
}

再利用可能な「workhorse」コレクションを保持しておく価値がある場合があります。たとえば、ループの各イテレーションで Vec が必要な場合、ループの外側で Vec を宣言し、ループ本体内で使用してから、ループ本体の最後で clear を呼び出すことができます（Vec の容量に影響を与えずに Vec を空にするため）。これにより、各イテレーションでの Vec の使用が他のイテレーションと無関係であるという事実がわかりにくくなる代わりに、アロケーションを回避できます。 例 1, 例 2。

同様に、繰り返し呼び出される 1 つ以上のメソッドで再利用するために、構造体内に workhorse コレクションを保持しておく価値がある場合もあります。

ファイルから行を読み取る

BufRead::lines を使うと、ファイルを 1 行ずつ簡単に読み取ることができます:

#![allow(unused)]
fn main() {
fn blah() -> Result<(), std::io::Error> {
fn process(_: &str) {}
use std::io::{self, BufRead};
let mut lock = io::stdin().lock();
for line in lock.lines() {
    process(&line?);
}
Ok(())
}
}

しかし、それが生成するイテレーターは io::Result<String> を返すため、ファイル内の各行ごとにアロケーションが発生します。

代替として、BufRead::read_line を使用するループ内で workhorse String を使う方法があります:

#![allow(unused)]
fn main() {
fn blah() -> Result<(), std::io::Error> {
fn process(_: &str) {}
use std::io::{self, BufRead};
let mut lock = io::stdin().lock();
let mut line = String::new();
while lock.read_line(&mut line)? != 0 {
    process(&line);
    line.clear();
}
Ok(())
}
}

これにより、アロケーションの回数は多くても数回、場合によっては 1 回だけに減ります。（正確な回数は、line を何回再アロケーションする必要があるかに依存し、それはファイル内の行の長さの分布に依存します。）

これは、ループ本体が String ではなく &str を扱える場合にのみ機能します。

例。

代替アロケーターの使用

コードを変更せずに、単に別のアロケーターを使用することで、ヒープアロケーションのパフォーマンスを向上させることも可能です。詳細については、Alternative Allocators セクションを参照してください。

リグレッションの回避

コードによって行われるアロケーションの数やサイズが意図せず増加しないようにするために、dhat-rs の heap usage testing 機能を使用して、特定のコードスニペットが期待される量のヒープメモリを割り当てることを確認するテストを書くことができます。