The Rust Performance Book
初版:2020年11月
著者:Nicholas Nethercote 他
翻訳者:Yuki Okushi
イントロダクション
(原文)
多くの Rust プログラムにおいて、パフォーマンスは重要です。
この本にはRustプログラムのパフォーマンス(速度とメモリ効率)を改善するための多くのテクニックが含まれています。コンパイルタイムセクションでは、Rust プログラムのコンパイルタイムを改善するためのいくつかのテクニックも紹介しています。この本で紹介しているテクニックの中には、ビルド設定を変更するだけのものもありますが、多くはコードを変更していくものです。
テクニックについては、完全に Rust 特有なものもありますし、他の言語で書かれたプログラムに(多くの場合ある程度の変更を加えつつ)適用できるものもあります。一般的なアドバイスセクションではどの言語でも使える一般的な基礎事項も紹介しています。とはいえ、この本ではほとんど Rust プログラムのパフォーマンスについて書かれており、プロファイリングや最適化についての一般的な用途向けのガイドを置き換えるものではありません。
この本では実用的で実績のあるテクニックに焦点を置いています。多くのテクニックにおいて、それが現実世界の Rust プログラムでどのように使われたかを示すプルリクエストやその他のソースへのリンクを載せています。
この本は中級者~上級者の Rust ユーザー向けに書かれています。初心者については他に学ぶことがたくさんあり、紹介するテクニックが役に立たないことも多いでしょう。
翻訳について
これは Apache License, Version 2.0 または MIT License で公開されている "The Rust Performance Book" を日本語に翻訳したものです。原文同様、翻訳された文章についても Apache License, Version 2.0 または MIT License にて公開します。
翻訳について、忠実な訳というよりはより自然な訳に傾けるよう心掛けています。できる限り原文の意図等を損なわないよう注意していますが必ずしも原文の内容と一致するものではないこと、また翻訳が誤っている・古くなっている場合があることに注意してください。もし翻訳に疑問を感じた場合には原文を参照することを推奨します。
現在はこちらのコミットまで翻訳されています。
翻訳に誤りがある場合
このリポジトリに issue を作成して報告するか、直接 PR を提出してください。
ベンチマーク
(原文)
ベンチマークとは、同じ働きを持つ 2 つ以上のプログラムのパフォーマンスを比較するものです。これは、例えば Firefox vs. Safari vs. Chrome のように、複数の異なるプログラムを比較することを指す場合もたまにあります。また、同じプログラムの異なる 2 つのバージョンを比較することを指す場合もあります。最後のケースは「この変更は速度に影響を与えたのか?」といった質問に答えるための根拠となり得ます。
ベンチマークは複雑なトピックであり、1 から 10 まで説明することはこの本では行わず、基本的な内容についてのみ紹介していきます。
初めに、測定するための負荷 (workload) が必要です。理想的には、プログラムの実際の使われ方を模した様々な負荷を用意したいところです。実際の入力を使った負荷が最善ですが、マイクロベンチマークやストレステストもある程度は役に立つでしょう。
次に、実際に負荷をかける方法が必要です。これは使用される測定基準にも影響します。Rust の組み込みのベンチマークテストはシンプルですが、不安定な機能を使っているため Nightly Rust でしか動作しません。bencher
クレートはそれを stable Rust でも動作するようにしたものです(訳注:bencher
は 2021 年 4 月現在、2018 年 1 月に公開された v0.1.5 が最新版となっており、積極的に開発されているものではないことに注意してください)。Criterion はそれらの代替となる、より洗練されたクレートです。また、カスタムベンチマークハーネスも利用できます。例えば、rustc-perf は Rust コンパイラのベンチマークに使われているハーネスです。
測定基準については、多くの選択肢があり、どのようなものが適切かは測定されるプログラムの性質に依存します。例えば、バッチ処理を行うプログラムに適切な測定基準は、インタラクティブなプログラムについて適切なものではないでしょう。実測時間はユーザーが体験するものと一致することがほとんどなので、明白な選択肢となります。しかし、実測時間は同時に大きなばらつきを持つものでもあります。特にメモリレイアウトの些細な変更が、一時的ではあるが影響の大きいパフォーマンス低下を起こすことがあります。そのため、サイクル数や命令数などの、ばらつきの少ない他の測定基準も合理的な代替案になり得ます。
複数の負荷の測定結果をまとめることも難しい課題です。様々な方法がありますが、これが絶対的に正解!という方法はありません。
良いベンチマークというのは難しいものです。そう言いつつ、特にプログラムの最適化を始めるときに、完璧なベンチマークをセットアップすることについてあまり気負うことはありません。普通のベンチマークでも何もしないよりは遥かに役に立ちます。また、測定しているものやその結果について先入観を持たないようにしてください。そして、プログラムのパフォーマンス特性について理解することで、時間をかけてベンチマーク結果を改善していくことができます。
ビルド設定
(原文)
正しいビルド設定をすることでコードを変更することなく Rust プログラムのパフォーマンスを最大化できます。
リリースビルド
最も大切な Rust パフォーマンスについてのアドバイスはシンプルですが、見落としがちなものです。つまり、パフォーマンスを必要とするときにはデバッグビルドよりもリリースビルドを使うようにしてください。リリースビルドを行うには、--release
フラグを Cargo に渡してください。
リリースビルドはデバッグビルドよりも とても 高速にプログラムを実行できます。デバッグビルドと比較して10-100倍高速化することもよくあります!
デバッグビルドはデフォルトの動作です。cargo build
や cargo run
、あるいは追加のフラグを渡さずに rustc
を実行したときはデバッグビルドが行われます。デバッグビルドはデバッグには向いているのですが、最適化はなされていません。
次のような、cargo build
実行時の出力の最後の行について考えてみましょう:
Finished dev [unoptimized + debuginfo] target(s) in 29.80s
[unoptimized + debuginfo]
はデバッグビルドが行われたことを示します。コンパイルされたコードは target/debug/
ディレクトリに置かれます。cargo run
も同様にデバッグビルドを行います。
リリースビルドはデバッグビルドよりもコードを最適化します。また、デバッグアサーションや整数のオーバーフローチェックなどのいくつかのチェックを無効化します。リリースビルドは、cargo build --release
、cargo run --release
、あるいは rustc -O
を実行することで行なえます(それ以外にも、rustc
には -C opt-level
のような最適化されたビルドのための複数のオプションがあります)。これはさらなる最適化のために、デバッグビルドよりもコンパイルに多くの時間がかかります。
次のような、cargo build --release
実行時の出力の最後の行について考えてみましょう:
Finished release [optimized] target(s) in 1m 01s
[optimized]
は、リリースビルドが行われたことを示します。コンパイルされたコードは target/release/
ディレクトリに置かれます。cargo run --release
も同様にリリースビルドを行います。
デバッグビルド(dev
プロファイル)とリリースビルド(release
プロファイル)のより詳細な違いについては、Cargoのプロファイルについてのドキュメントを参照してください。
リンク時最適化 (LTO)
リンク時最適化 (LTO) はビルド時間の増加を代償としてランタイムパフォーマンスを10-20%以上向上させる、プログラム全体に渡る最適化のテクニックです。任意の Rust プログラムでは、ランタイムとコンパイル時間のトレードオフに価値があるかを簡単に確かめることができます。
LTO を試してみる最もシンプルな方法は Cargo.toml
に次の行を追記して、リリースビルドを行うことです:
[profile.release]
lto = true
これにより、依存関係にあるすべてのクレートに渡って最適化を行う、"fat" LTO を実行できます。
あるいは、lto = "thin"
を Cargo.toml
に追記することで "thin" LTO を行うことができます。これはビルド時間をあまり増やすことなく、"fat" LTO と大体同じように最適化を行うという、控えめな形の LTO です。
lto
の設定と、異なるプロファイルに向けて特定の設定を有効化する方法については、Cargo の LTO についてのドキュメントを参照してください。
Codegen Units
Rust コンパイラは、並列コンパイルとそれによる高速化のために、クレートを複数の codegen unit に分割します。しかし、これは潜在的な最適化を損なう原因になることがあります。コンパイルタイムを犠牲にして、そのような潜在的な最適化をも行ってランタイムパフォーマンスを改善したい場合は、codegen unit の数を1
に設定できます:
[profile.release]
codegen-units = 1
codegen unit の数はヒューリスティックであり、少なく設定することでかえってプログラムを遅くする場合もあることに注意してください。
CPU 固有の命令を使う
もし旧式の、あるいは他の種類のプロセッサでの互換性についてあまり心配しなくてもいい場合には、特定の CPU アーキテクチャ固有の、最新の(そしておそらくは最速の)命令を生成するようコンパイルに指示できます。
例えば、rustc に -C target-cpu=native
を渡すことで、現在使用している CPU について最適な命令を使うことができます:
RUSTFLAGS="-C target-cpu=native" cargo build --release
これは、特にコンパイラがコード内にベクトル化の機会を見つけた場合には、大きな影響を与えます。
2022年7月現在、M1 Macs において -C target-cpu=native
を使用した際にすべての CPU 機能を検出できないという問題が存在します。この場合、-C target-cpu=apple-m1
を代わりに使用してください。
もし -C target-cpu=native
がうまく動作しているか不安な場合は、rustc --print cfg
と rustc --print cfg -C target-cpu=native
の出力を比較してみてください。これにより、CPUの機能が後者において正確に検出されているかを確認できます。もし検出できなかった場合には、-C target-feature
を使って特定の機能を対象にできます。
panic!
時に中断 (abort) する
パニックを捕捉したり巻き戻したりする必要がない場合には、パニック時には単に中断 (abort) するようコンパイラに指示できます。これはバイナリサイズを削減しわずかにパフォーマンスを向上させることがあります:
[profile.release]
panic = "abort"
プロファイルに基づく最適化 (PGO)
プロファイルに基づく最適化 (PGO) はプログラムをコンパイルしプロファイルデータを収集しながらサンプルデータをもとに実行し、プログラムの二度目のコンパイルをサポートするためにそのプロファイルデータを使用するという、コンパイルモデルです。
これはセットアップにある程度の労力を要する高度なテクニックですが、いくつかの状況では試す価値があります。詳細はrustc の PGO に関するドキュメントを参照してください。
Linting
(原文)
Clippy は Rust コード内のよくある間違いを捕捉する lint のコレクションです。これは、一般の Rust コードで実行するには素晴らしいツールです。また、パフォーマンスの最適化を損なう原因となるコードパターンに関する様々な lint を持っています。そのため、パフォーマンスについても手助けをしてくれます。
Clippy の基本
インストールできたら、実行するのは簡単です:
cargo clippy
パフォーマンスに関する lint のリストは この list から "Perf" 以外のすべてのグループを除外することで確認できます。
コードを高速化するだけでなく、パフォーマンスに関する lint は一般によりシンプルで慣用的なコードを提案してくれます。そのため、頻繁に実行されないようなコードでもその提案に従う価値があります。
型を禁止する
後続の章では、標準ライブラリにある特定の型を避け高速化をもたらす代替の型を使用した方がよい場合の説明があります。しかしそれら代替の型を使用する際、誤って標準ライブラリの型をどこかで使用してしまう、というケースが発生し得るでしょう。
Rust 1.55 で Clippy に追加された disallowed_types
lint を使用すれば、この問題を回避できます。例えば、標準のハッシュテーブルの使用を禁止する場合(理由についてはハッシュ化の章で説明されています)、clippy.toml
ファイルを用意し、以下の行を追記してください:
disallowed-types = ["std::collections::HashMap", "std::collections::HashSet"]
そして、Rust コード上で以下を宣言します:
#![allow(unused)] #![warn(clippy::disallowed_types)] fn main() { }
執筆時点で disallowed_types
が "nursery"(開発中)というグループにあるため上記の手順が必要となっています。グループは将来変更される可能性があります。
プロファイリング
(原文)
プログラムを最適化するときには、プログラムのどの部分がホット、つまりランタイムパフォーマンスに影響するほど頻繁に実行されていて、変更する価値があるかを見定める方法が必要です。これにはプロファイリングが最適です。
プロファイラー
(訳注:それぞれのプロファイラーについて特徴を把握しきれておらず、訳が伝わりにくくになっているものがあります。適宜原文を参照してください)
多くのプロファイラーを利用できますが、それぞれに得意・不得意があります。以下のリストはすべてのプロファイラーを網羅しているわけではありませんが、 Rust プログラム上でうまく動作することを確認しています:
- perf はハードウェアパフォーマンスカウンターを利用した、一般用途向けのプロファイラーです。Hotspot や Firefox Profiler は perf が記録したデータを閲覧するのに適しています。perf は Linux 上で動作します。
- Instruments は macOS 上で Xcode とともに配布される一般利用に適したプロファイラーです。
- AMD μProf は一般用途向けのプロファイラーです。 Windows 及び Linux 上で動作します。
- flamegraph はコードのプロファイルに perf または DTrace を使用し、フレームグラフの形式でその結果を表示する Cargo コマンドです。Linux および DTraceがサポートするすべてのプラットフォーム (macOS、FreeBSD、NetBSD、そしておそらく Windows) 上で動作します。
- Cachegrind 及び Callgrind はグローバル、関数ごと、あるいはソースコード行別の命令数カウントとシミュレートされたキャッシュ、そして分岐予測データを提供します。Linux といくつかの Unix システム上で動作します。
- DHAT はコードのどの部分が多くのアロケーションを起こしているか見つけたり、ピーク時のメモリ使用状況について把握したりすることに適しています。これはまた
memcpy
の頻繁な呼び出しを特定するためにも使われます。Linux 及びその他いくつかの Unix システム上で動作します。dhat-rs は、機能がやや貧弱で Rust コードに少し手を加える必要がありますが、すべてのプラットフォーム上で動作する実験的な代替クレートです。 - heaptrack 及び bytehound はヒーププロファイリングツールです。Linux 上で動作します。
counts
はアドホックなプロファイリングをサポートしています。これはeprintln!
文の使用と周波数ベースの後処理を組み合わせたもので、コードの一部についてドメイン固有な情報を把握するのに適しています。すべてのプラットフォームで動作します。- Coz は潜在的な最適化を測定するための 簡略化された (casual) プロファイリングを行います。coz-rs により Rust をサポートしています。 Linux 上で動作します。
Debug Info
リリースビルドを効果的にプロファイルするには、ソースコード行のデバッグ情報 (debug info) を有効化しなければならないことがあります。有効化するには、以下の行を Cargo.toml
に追記してください:
[profile.release]
debug = 1
debug
設定についての詳細な内容は Cargo のドキュメントを参照してください。
残念ながら、上記の手順を踏んでも標準ライブラリの詳細なプロファイリングデータを得ることはできません。これはリリースされている標準ライブラリはデバッグ情報を含んでいないためです。この問題を解決するには、コンパイラと標準ライブラリを自分でビルドする必要があります。以下を config.toml
に追記して、こちらに記載の手順に従ってください:
[rust]
debuginfo-level = 1
これは面倒ですが、場合によってはやってみる価値があるでしょう。
シンボルデマングリング
Rust はコンパイルされたコード中に関数名をエンコードするためのマングリングスキーマを持っています。もしプロファイラがこれに対応していない場合、出力に _ZN3foo3barE
や _ZN28_$u7b$$u7b$closure$u7d$$u7d$E
、_RMCsno73SFvQKx_1cINtB0_3StrKRe616263_E
のような、_ZN
や _R
から始まるシンボル名が含まれる可能性があります。これらは rustfilt
を使って手ずからデマングリングできます。
インライン化
(原文)
ホットでインライン化されていない関数の呼び出しはしばしば実行時間の無視できない部分を占めることがあります。それらの関数をインライン化することで、小さいですが簡単な高速化を図ることができます。
Rust の関数向けには4種類のインライン属性があります:
- なし: コンパイラ自身がその関数はインライン化されるべきなのかを判断します。これは最適化レベルや関数サイズなどに依存します。もしリンク時最適化を使っていない場合には関数がクレートを跨いでインライン化されることはありません。
#[inline]
: これはクレートの垣根を越えて関数がインライン化されるべきであることを示します。#[inline(always)]
: これはクレートの垣根を越えて関数がインライン化されるべきであることを 強く 示します。#[inline(never)]
: これは関数がインライン化されるべきでないことを 強く 示します。
インライン属性は関数がインライン化される/されないことを保証するものではありません。しかし実際には、#[inline(always)]
は例外的な場合を除きすべての場合においてインライン化を行います。
シンプルなケース
インライン化するのに最適な候補は (a) とても小さい、あるいは (b) 呼び出し場所 (call site) が1つである、といったような関数です。コンパイラはインライン属性がなくともそれらの関数を自身の判断でインライン化することがしばしばあります。ですが、コンパイラはいつも最適な選択をするわけではないので、属性の付与が時々必要となります。
Cachegrind は関数がインライン化されているかどうかを確かめるのに適したプロファイラーです。Cachegrind の出力を見てみてください。最初と最後の行がイベントカウントとしてマーク されていない 場合にのみ、関数がインライン化されていることが分かります。
例:
. #[inline(always)]
. fn inlined(x: u32, y: u32) -> u32 {
700,000 eprintln!("inlined: {} + {}", x, y);
200,000 x + y
. }
.
. #[inline(never)]
400,000 fn not_inlined(x: u32, y: u32) -> u32 {
700,000 eprintln!("not_inlined: {} + {}", x, y);
200,000 x + y
200,000 }
影響が予測できないこともあるため、インライン属性を追加した後には測定し直すべきです。時々、以前はインライン化されていた近くの関数がインライン化されなくなったことで、なんの効果もないことがあります。また、コードが遅くなることもあります。インライン化はコンパイル時間にも影響します。特に、関数の内部表現を複製する、クレートを跨ぐようなインライン化については多くの場合影響があります。
難しいケース
時々、巨大で複数の呼び出し場所を持つが、1つの呼び出し場所だけがホットな関数が生まれます。そのような場合、速度向上のためホットな呼び出し場所をインライン化しつつ、不要なコードの肥大化をさけるためにコールドな(ホットの逆で、稀にしか実行されない)呼び出し場所はインライン化したくないものです。これを処理する方法として、関数を、常にインライン化される (always-inlined) ものと決してインライン化されない (never-inlined) ものに分け後者から前者を呼ぶというものがあります。
例えば、この関数は:
#![allow(unused)] fn main() { fn one() {}; fn two() {}; fn three() {}; fn my_function() { one(); two(); three(); } }
下のように2つの関数に分けられます:
#![allow(unused)] fn main() { fn one() {}; fn two() {}; fn three() {}; // ホットな呼び出し場所ではこれを使う #[inline(always)] fn inlined_my_function() { one(); two(); three(); } // コールドな呼び出し場所 (ホットでない呼び出し場所) にはこれを使う #[inline(never)] fn uninlined_my_function() { inlined_my_function(); } }
ハッシュ化
(原文)
HashSet
と HashMap
は広く使われる2つの型です。デフォルトのハッシュアルゴリズムは指定されていませんが、執筆時点では SipHash 1-3 と呼ばれるアルゴリズムがデフォルトとなっています。このアルゴリズムは高い品質を持っており衝突に対する高い保護性能を持ちますが、その一方で特に整数のような短いキーについては遅いという特徴があります。
もしプロファイリングによりハッシュ化がホットであると判明し、HashDoS attacks がアプリケーションにおいて懸念にならない場合には、より高速なハッシュアルゴリズムを持つハッシュテーブルの使用により、大きな速度の改善ができます。
rustc-hash
はHashSet
やHashMap
の代替となるFxHashSet
やFxHashMap
を提供しています。ハッシュアルゴリズムは低品質ですが、特に整数キーの場合にはとても高速で、rustc 内の他のどのハッシュアルゴリズムよりも性能が優れています(fxhash
は同じアルゴリズムと型の実装を持ちますが、rustc-hash
に比べると古くあまりメンテナンスされていません)fnv
はFnvHashSet
及びFnvHashMap
型を提供しています。ハッシュアルゴリズムはrustc-hash
よりも高品質ですが、その分速度はやや劣りますahash
はAHashSet
及びAHashMap
を提供しています。ahash
のハッシュアルゴリズムはいくつかのプロセッサで利用可能な AES 命令をサポートしています
ハッシュ化のパフォーマンスがプログラムにおいて重要であれば、これらの代替案をいくつか試す価値があるでしょう。例えば、rustc では次の結果が得られました:
fnv
からfxhash
への移行は最大6%の高速化をもたらしましたfxhash
からahash
への移行の試みは 1-4%の速度低下という結果でしたfxhash
からデフォルトのハッシュアルゴリズムに戻す試みは4-84%の速度低下という結果でした!
FxHashSet
や FxHashMap
のような代替案を一般に採用することを決めた場合、ある場所で HashSet
や HashMap
を誤って使ってしまうということが容易に起こり得ます。clippy
を使用するとこの問題を回避できます。
いくつかの型はハッシュ化を必要としません。例えば、整数型を包んだ newtype があり、その値はランダムまたはランダムに近いものであるとします。そのような型の場合、ハッシュ化された値の分布は値自体のそれとさほど変わらないでしょう。こういうケースでは nohash_hasher
が役立つこともあります。
ハッシュ関数の設計は複雑なトピックであり、この本の範囲外です。ahash
のドキュメントには参考になる情報が載っています。
ヒープ割り当て
(原文)
ヒープ割り当て (heap allocation) には中程度にコストがかかります。その詳細は使用するアロケータに依存しますが、それぞれの割り当て(そして割り当て解除)はグローバルロックの取得、いくつかの些細でないデータ構造の操作、そして(場合によっては)システムコールを実行します。小さな割り当ては大きなものよりコストがかからないとは限りません。割り当てを避けることは大きくパフォーマンスを改善できることがあるため、どの Rust のデータ構造と命令が割り当てを引き起こすのか理解する価値があります。
Rust Container チートシートは一般的な 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
は最もシンプルなヒープに置かれる (heap-allocated) 型です。Box<T>
の値はヒープに置かれた T
の値です。
struct
や enum
の 1 つあるいはそれ以上のフィールドを box 化することで、型を小さくできる場合があります(この詳細については 型のサイズ というチャプターを参照してください)。
それ以外では Box
は簡潔で最適化の余地はあまりありません。
Rc
/Arc
Rc
/Arc
は Box
と似ていますが、ヒープ上の値は 2 つの参照カウントを持っています。これらの型は値の共有を可能にし、メモリ使用量を削減するための効果的な手段になり得ます。
しかし、めったに共有されないような値に使われると、ヒープに置かれないような値までヒープに置くことで割り当ての割合を大きくしてしまう恐れがあります。
Box
と異なり、Rc
/Arc
上で clone
を呼び出しても割り当ては行われません。代わりに、参照カウントをインクリメントします。
Vec
Vec
はヒープに置かれる型で、割り当ての数を最適化したり、無駄なスペースの量を最小化したりする大きな余地があります。このためにはその要素がどのように保持されるかについて理解しなければなりません。
Vec
には 3 つの要素があります。長さ、容量、そしてポインタです。ポインタは容量と要素の大きさが 0 でない場合にはヒープに置かれたメモリを指します。そうでない場合は、割り当てられたメモリを指すことはありません。
Vec
自体がヒープに置かれないとしても、その要素(存在していてサイズが0でない場合)はいつもヒープに置かれます。もしサイズが0でない要素が存在する場合、それらの要素を保持するメモリは、追加の要素のためのスペースを開けておくことにより、必要より大きくなっている場合があります。現在ある要素の数が長さとなり、再度割り当てることなく要素を置ける数というのが容量になります。
ベクタが現在の容量を増やす必要が出てきた場合、その要素はより大きなヒープ割り当てにコピーされ、古いヒープ割り当ては解放されます。
Vec
の増大
一般的な方法で (vec![]
、Vec::new
あるいは Vec::default
) 作られた新しい空の Vec
の長さと容量は 0 であり、ヒープ割り当てを必要としません。もし個々の要素をその Vec
の最後に繰り返し追加した場合、定期的に再割り当てが発生します。増大させる方法 (strategy) は指定されていませんが、執筆時では quasi-doubling strategy が採用されています。この方法では 0、4、8、16、32、64…、のように容量が遷移していきます(多くの割り当てを避けるため、これは 1 と 2 を飛ばして 0 から 4 へと容量を増やします)。ベクタが増大するにつれ、再割り当ての頻度は指数関数的に減っていきますが、無駄になる可能性のある余分な容量は指数関数的に増えていきます。
この増大の仕組みは要素を増やしていける一般用途向けのデータ構造では理にかなっているものですが、事前にベクタの長さが分かっている場合には、より効率的なことを行えます。ホットなベクタの割り当て場所(例:ホットな Vec::push
の呼び出しなど)がある場合は、そこでベクタの長さを出力するために eprintln!
を使い、その後長さの分布を見定めるために(counts
などを使って)後処理をする価値があります。例えば、たくさんの短いベクタがあったり、それよりすくない数のとても長いベクタがあったりするでしょう。割り当て場所を最適化する一番良い方法はその状況に大きく依存します。
短い Vec
もし短いベクタがたくさんある場合には、smallvec
クレートの SmallVec
型を使うことができます。SmallVec<[T; N]>
は Vec
の代替であり、N
個の要素を SmallVec
自身に保持できます。要素数がそれを越えた場合はヒープ割り当てに切り替わります(SmallVec
を使う場合、vec![]
を smallvec![]
に置き換える必要があることに注意してください)。
SmallVec
は適切に使えば割り当ての割合を確実に下げますが、その使用自体がパフォーマンスの向上を保証するものではありません。それは要素がヒープに置かれているかどうかを必ず確認するため、一般的な処理では Vec
よりもわずかに遅いです。また、N
や T
が大きい場合、SmallVec<[T; N]>
自身は Vec<T>
よりも大きくなることがあり、SmallVec
のコピーは Vec
より遅くなります。いつも通り、最適化に効果があるのか確認するためのベンチマークが必須です。
短いベクタがたくさんあり 加えて その最大長を正確に把握している場合、arrayvec
の ArrayVec
型は SmallVec
よりも優れた選択肢です。ヒープ割り当てへのフォールバックを必要とせず、SmallVec
よりもわずかに高速に動作します。
長い Vec
ベクタの最小の、あるいは実際の大きさをしっている場合、Vec::with_capacity
、Vec::reserve
、あるいは Vec::reserve_exact
を使って特定の容量を確保できます。例えば、あるベクタが少なくとも20個の要素を持つことが分かっている場合、これらの関数は直ちに1回の割り当てで少なくとも 20 の容量を持つベクタを生成します。対して一度に1つずつアイテムを挿入した場合には4回割り当てをします(容量について、4、8、16、そして 32)。
ベクタの最大長を知っている場合、上記の関数は不必要に余分なスペースを割り当てないでいいようにしてくれます。同様に、Vec::shrink_to_fit
は余分なスペースを最小化するために使えますが、再割り当てが必要となる場合があることに注意してください。
String
String
はヒープに置かれるバイト列を持ちます。String
の表現と操作は Vec<u8>
によく似ています。増大と容量に関する多くの Vec
メソッドと同等なものが String
にもあります。例えば String::with_capacity
などです。
smallstr
クレートの SmallString
型は SmallVec
型に似ています。
smartstring
クレートの String
型は std の String
の代替であり、3 語分以下の文字列についてヒープ割り当てを回避します。64-bit プラットフォーム上では、これは 23 以下の ASCII 文字を合わせたすべての文字列を含む、24 bytes 以下の任意の文字列となります。
format!
マクロは String
を生成する、つまり、割り当てを必要とすることに注意してください。文字列リテラルを使うことで format!
の呼び出しを避けられる場合、この割り当てを回避できます。std::format_args
や lazy_format
はこの問題を解決するのに役立つ可能性があります。
ハッシュテーブル
HashSet
や HashMap
はハッシュテーブルです。割り当てという文脈では、それらの表現や操作は Vec
のそれに似ています。それらはキーや値を保持しつつ単一の継続したヒープを割り当て、テーブルの拡大に必要となる限り再割り当てします。増大と容量に関する多くの Vec
のメソッドと同様のものが HashSet
/HashMap
にもあります。例えば、HashSet::with_capacity
などです。
Cow
時々、&str
のような、何らかの借用されたデータを使いたい場合があります。これは殆どの場合読み取り専用ですが、たまに変更する必要が出てきます。毎回そのデータをクローンするのは無駄が多いです。その代わりにCow
型を通して、借用/所有された両方のデータを表現できる、"clone-on-write" なセマンティクスを使うことができます。
通常、借用された値 x
から始めるときは、Cow::Borrowed(x)
を使って Cow
の中に x
を包みます。Cow
は Deref
を実装しているので、Cow
が持っているデータに対して不変 (non-mutating) なメソッドを直接呼び出せます。もし可変である必要がある場合には、Cow::to_mut
によって、必要に応じてクローンしつつ、所有されている値への可変参照を取得できます。
Cow
をうまく動かすのは難しいですが、試行錯誤する価値は十分あります。
clone
ヒープに置かれたメモリを含む値に対して clone
を呼び出すと、通常は追加の割り当てが発生します。例えば、空でない Vec
に対して clone
を呼び出すと、その要素の新しい割り当てが必要になります(新しい Vec
の容量は元のものと異なる可能性があることに注意してください)。例外は Rc
/Arc
で、clone
呼び出しは参照カウントをインクリメントするだけです。
clone_from
は clone
の代替です。a.clone_from(&b)
は a = b.clone()
と同等ですが、不必要な割り当てを避ける場合があります。例えば既存の Vec
をもとに Vec
を1つクローンしたい場合、可能であれば既存の 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's allocation is reused assert_eq!(v1.capacity(), 99); }
clone
は通常割り当てを発生させますが、多くの状況では利用することは理にかなっておりコードをシンプルにすることも多いです。プロファイリングデータを使ってどの clone
の呼び出しがホットで避けるために工夫する価値があるか確認してください。
時々、Rust コードには、(a) プログラマーのミス、(b) コードの変更により以前必要だった clone
呼び出しが不必要になった、などの理由で不必要な clone
呼び出しが含まれることもあります。もし必要そうでないホットな clone
の呼び出しを見つけた場合には、単純に削除できることもあります。
to_owned
ToOwned::to_owned
は多くの一般的な型に対して実装されています。これは借用されたデータから所有されたデータを作成します。一般的にはクローンが必要で、それによりしばしばヒープ割り当てが発生します。例えば、これは &str
から String
を作成するときに使われます。
時々、所有されたコピーでなく構造体にある借用されたデータへの参照を保持することで、to_owned
呼び出しを回避できることがあります。これは構造体にライフタイム注釈を必要とし、コードを複雑にします。そのため、プロファイリングやベンチマークでそうする価値があると分かった場合にのみ適用されるべきです。
コレクションを再利用する
Vec
のようなコレクションを段階的に作成しなければならない場合があります。この場合、複数の Vec
をつくってそれらを組み合わせるよりも、1つの 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
の使用がその他のイテレーションに関係がないということが分かりづらくなることと引き換えに、割り当てを避けることができます。
同様に、構造体の中に "workhorse" なコレクションを保持しておく価値がある場合もあります。これは繰り返し呼び出される 1 つ以上のメソッドの中で再利用されます。
代替となるアロケータを使用する
割り当ての多い Rust プログラムのパフォーマンスを向上させる別の手段として、デフォルトの(システム)アロケータを代替のものに置き換える、というものがあります。正確な影響は個々のプログラムと選ばれるアロケータに依存しますが、一般に大きな速度改善とメモリ使用量の削減をもたらします。各プラットフォームのシステムアロケータはそれぞれ長所短所を持っており、プラットフォームによってもその影響は異なります。また、異なるアロケータの使用はバイナリサイズにも影響します。
人気のある Linux/Mac 向け代替アロケータの 1 つに tikv-jemallocator
クレートを通して使える jemalloc があります。使用するには依存関係を Cargo.toml
に追記します:
[dependencies]
tikv-jemallocator = "0.4.0"
それから次の行を Rust コードのどこかに追記します:
#[global_allocator]
static GLOBAL: tikv_jemallocator::Jemalloc = tikv_jemallocator::Jemalloc;
tikv-jemallocator
は jemallocator
クレートのフォークです。tikv-jemallocator
は2021年12月現在、jemallocator
より新しいバージョンの jemalloc を使用しており、パフォーマンスがわずかに向上しています。
多くのプラットフォームで利用可能な代替アロケータとしてもう1つ挙げるとすれば、 mimalloc
を通して使える mimalloc があります。
リグレッションを避ける
コード上のアロケーション回数・サイズが意図せず増加していないことを保証するためには、dhat-rs のヒープ使用量テスト機能が便利です。これを使うことで、特定のコードスニペットが想定通りのヒープメモリ量を割り当てているかをテストで確かめられるようになります。
型のサイズ
(原文)
しばしばインスタンス化される型を縮小する(shrink)ことは、パフォーマンスの向上に寄与します。
例えば、もしメモリ使用量が高い場合、DHAT のようなヒーププロファイラーを使うと、ホットな割り当て位置(allocation points)とそれに付随する型を特定できます。それらの型を縮小することはピーク時のメモリ使用量を減らすことができ、またメモリへの頻繁なアクセスやキャッシュへの負担を減らすことでパフォーマンスを改善できる可能性があります。
それに加え、128 bytes より大きい Rust の型はインライン化されず memcpy
によってコピーされます。もしプロファイラー上で memcpy
の使用量が無視できないほど大きいことが分かった場合、DHAT の "copy profiling" モードを使えば、ホットな memcpy
呼び出しの位置やそれに付随する型について正確に把握できます。それらの型を 128 bytes 以下に縮小することで、memcpy
の呼び出しを避けメモリへのアクセスを減らすことができ、コードの高速化が期待できます。
型のサイズを測定する
std::mem::size_of
は byte 単位での型のサイズを教えてくれますが、しばしばその正確なレイアウトも知りたいことがあるでしょう。例えば、列挙型(enum)は1つの大きな列挙子により、驚くほど大きくなることがあります。
-Zprint-type-sizes
オプションはそれを正確に確認できます。このオプションは stable Rust では使用できず、代わりに nightly Rust を使う必要があります。これは Cargo を使った呼び出しの一例です:
RUSTFLAGS=-Zprint-type-sizes cargo +nightly build --release
また、以下は rustc を使った呼び出しの一例です:
rustc +nightly -Zprint-type-sizes input.rs
これにより、使用中のすべての型のサイズ、レイアウト、及びアラインメントの詳細を見ることができます。例えば下記の型について考えます:
#![allow(unused)] fn main() { enum E { A, B(i32), C(u64, u8, u64, u8), D(Vec<u32>), } }
-Zprint-type-sizes
オプションは下記に加え、いくつかの組み込み型についての情報も出力します:
print-type-size type: `E`: 32 bytes, alignment: 8 bytes
print-type-size discriminant: 1 bytes
print-type-size variant `D`: 31 bytes
print-type-size padding: 7 bytes
print-type-size field `.0`: 24 bytes, alignment: 8 bytes
print-type-size variant `C`: 23 bytes
print-type-size field `.1`: 1 bytes
print-type-size field `.3`: 1 bytes
print-type-size padding: 5 bytes
print-type-size field `.0`: 8 bytes, alignment: 8 bytes
print-type-size field `.2`: 8 bytes
print-type-size variant `B`: 7 bytes
print-type-size padding: 3 bytes
print-type-size field `.0`: 4 bytes, alignment: 4 bytes
print-type-size variant `A`: 0 bytes
出力を見ると以下のことが分かります:
- 型のサイズとアラインメント
- (列挙型の場合)判定式(discriminant)のサイズ
- (列挙型の場合)サイズ降順にソートされた各列挙子のサイズ
- すべてのフィールドのサイズ、アラインメント、そして順序(
E
のサイズを最小化するためにコンパイラがC
列挙子のフィールドを並び替えていることに注意してください) - すべてのパディングのサイズと場所
ホットな型のレイアウトが分かったら、それを縮小するために複数を手法をとることができます。
フィールドの順序
Rust コンパイラは、#[repr(C)]
が指定されてない限り、サイズを最小化するために、自動的に構造体と列挙型のフィールドをソートします。そのため、フィールドの順序について心配する必要はありません。ホットな型のサイズを最小化する方法は他にもあります。
より小さい列挙型
もし列挙型が大きな列挙子を持っている場合、1 つ以上のフィールドをボックス化することを検討しましょう。例えば、この型について:
#![allow(unused)] fn main() { type LargeType = [u8; 100]; enum A { X, Y(i32), Z(i32, LargeType), } }
こうできます:
#![allow(unused)] fn main() { type LargeType = [u8; 100]; enum A { X, Y(i32), Z(Box<(i32, LargeType)>), } }
これにより、A::Z
列挙子について余分なヒープ割り当てを必要とする代わりに、型のサイズを抑えることができます。A::Z
が比較的使われない場合には、パフォーマンスの向上をより期待できます。Box
は、特に match
パターンにおいて、A::Z
をやや扱いづらくすることにも注意してください。
より小さい整数
より小さい整数型を使用することで、型のサイズを縮小できる可能性は結構あります。例えば、インデックスに usize
を使うというのはよくあることですが、それを u32
、u16
、あるいは u8
型で保持しておいて使用するときに usize
へ型強制(coerce)してやるというのはそこそこな場面で合理的です。
ボックス化されたスライス
Rust のベクタには 3 つの要素があります。長さ、容量、そしてポインタです。もしあるベクタが将来変更されなさそうな場合、Vec::into_boxed_slice
を使って ボックス化されたスライス(boxed slice) に変換できます。ボックス化されたスライスには 2 つの要素のみあります。長さとポインタです。余っている容量を解放するため、再割り当てが発生し得ます。
#![allow(unused)] fn main() { use std::mem::{size_of, size_of_val}; let v: Vec<u32> = vec![1, 2, 3]; assert_eq!(size_of_val(&v), 3 * size_of::<usize>()); let bs: Box<[u32]> = v.into_boxed_slice(); assert_eq!(size_of_val(&bs), 2 * size_of::<usize>()); }
ボックス化されたスライスは、slice::into_vec
を使ってクローンや再割り当てをすることなくベクタに戻すことができます。
The boxed slice can be converted back to a vector with slice::into_vec
without any cloning or a reallocation.
ThinVec
ボックス化されたスライスの代替として thin_vec
クレートにある ThinVec
型が使用できます。これは機能的には Vec
と同等ですが、(もし存在する場合)長さと容量を要素として同じアロケーションに保存します。これは size_of::<ThinVec<T>>
が1つの値で表されることを意味します。
しばしば空になり得るベクタ型を持つ際、頻繁にインスタンス化される (oft-instantiated) 型の中で ThinVec
は良い選択肢となり得ます。また、ある列挙型の最も大きな列挙子が Vec
を含む場合、その列挙子を縮小するために使用できます。
リグレッションを避ける
そのサイズがパフォーマンスに影響を与えるほどある型がホットである場合は、それが誤ってリグレッションしないことを保証するために静的なアサーションを使うことをおすすめします。次の例は static_assertions
クレートのマクロを使っています:
// この型は頻繁に使われているので、意図せず型のサイズが大きくならないことを確かめる。
#[cfg(target_arch = "x86_64")]
static_assertions::assert_eq_size!(HotType, [u8; 64]);
ここでの cfg
属性は重要です。なぜならプラットフォームによって型のサイズが異なることがあるためです。アサーションを x86_64
(最も広く使われているプラットフォーム)に限定することは、実際のリグレッションを防ぐ上で十分役に立つでしょう。
標準ライブラリの型
(原文)
Box
、[Vec
]、Option
、Result
、そして Rc
/Arc
のような、よく使われる標準ライブラリの型のドキュメントを読むことは、パフォーマンスを向上させるのに使える面白い関数を見つけることに繋がります。
また、Mutex
、RwLock
、Condvar
、そして Once
のような、パフォーマンス向上という視点で他の標準ライブラリの型の代替となり得る型についても知っておくべきでしょう。
Box
Box::default()
という式は Box::new(T::default())
と同じ効果を持ちますが、コンパイラがそれをスタック上に構築しコピーするのではなく、ヒープ上に直接値を作成できるという点で高速になる場合があります。
Vec
Vec::remove
は特定のインデックスの要素を削除し後ろにある要素を 1 つずつ左にシフトさせます。計算量は O(n) です。対して、Vec::swap_remove
は特定のインデックスの要素を最後の要素と入れ替えつつ削除します。これは順序を保持しませんが、計算量は O(1) です。
Vec::retain
は Vec
から複数のアイテムを効果的に削除します。String
、HashSet
、そして HashMap
のような他のコレクション型にも同様のメソッドがあります。
Option
と Result
Option::ok_or
は Option
を Result
に変換します。もし Option
の値が None
だった場合には、ok_or
の引数が err
のパラメータとして渡されます。err
は先行評価されます。もしそのコストが大きい場合には代わりに Option::ok_or_else
を使用して、クロージャを通してそのエラーの値を遅延評価するようにすべきです。例えばこれは:
#![allow(unused)] fn main() { fn expensive() {} let o: Option<u32> = None; let r = o.ok_or(expensive()); // 常に `expensive()` として評価される }
このように変更すべきです:
#![allow(unused)] fn main() { fn expensive() {} let o: Option<u32> = None; let r = o.ok_or_else(|| expensive()); // 必要なときだけ `expensive()` として評価される }
Option::map_or
、Option::unwrap_or
、Result::or
、Result::map_or
、そして Result::unwrap_or
のような、似たような類似メソッドが他にもあります。
Rc
/Arc
Rc::make_mut
/Arc::make_mut
は "clone-on-write" なセマンティクスを提供し、Rc
/Arc
への可変参照を作成します。もし参照カウントが 1 より大きい場合には、所有権が一意であることを確保するために中の値をクローンします。そうでなければ、つまり参照カウントが 1 であれば、元の値を変更します。これらのメソッドは頻繁には必要になりませんが、場合によってはとても役に立ちます。
Mutex
、RwLock
、Condvar
、そして Once
parking_lot
クレートは上記の標準ライブラリの同期的な型よりも小さく、高速で、フレキシブルな代替実装を提供します。parking_lot
にある型の API とセマンティクスは標準ライブラリのそれらと似ていますが同じものではありません。
もし parking_lot
の型を広く使おうとした場合、いくつかの場所で間違って標準ライブラリの型を使ってしまう、ということが容易に起こり得ます。clippy
を使用するとこの問題を回避できます。
イテレータ
(原文)
collect
と extend
Iterator::collect
はイテレータを Vec
のようなコレクション型に変換します。これは通常割り当てを必要とします。もしコレクション型がその後再びイテレートされるだけなのであれば、collect
の呼び出しは避けるべきです。
上記の理由から、Vec<T>
よりも impl Iterator<Item=T>
といったイテレータ型を関数から返した方が多くの場合好ましいです。ただ、この記事で説明されているように、そういった返り値には追加のライフタイム注釈が必要となる場合があることに注意してください。
同様に、イテレータを Vec
にして append
を使うよりも、イテレータを使って既存のコレクション型(Vec
など)を拡張するために extend
を使った方が良いでしょう。
最後に、イテレータを書くときは、可能であれば Iterator::size_hint
か ExactSizeIterator::len
メソッドを実装した方が多くの場合好ましいです。その理由として、イテレータによって生成される要素数についての事前情報が手に入るため、イテレータを使う collect
や extend
といった呼び出しにおいてより小さな割り当てを行える、というものがあります。
チェイン
chain
はとても便利ですが、単一のイテレータより遅くなることがあります。可能であればホットなイテレータに対しては使用を避けるべきでしょう。
同様に、map
に続けて filter
を使うよりも、filter_map
を使用した方が高速になることがあります。
I/O
(原文)
ロック
Rust の print!
及び println!
マクロは呼び出しごとに標準出力をロックします。これらのマクロを繰り返し呼び出すときには、手ずから標準出力をロックした方が好ましいこともあります。
例えばこのコードを:
#![allow(unused)] fn main() { let lines = vec!["one", "two", "three"]; for line in lines { println!("{}", line); } }
このように変更するとより好ましいでしょう:
#![allow(unused)] fn main() { fn blah() -> Result<(), std::io::Error> { let lines = vec!["one", "two", "three"]; use std::io::Write; let mut stdout = std::io::stdout(); let mut lock = stdout.lock(); for line in lines { writeln!(lock, "{}", line)?; } // `lock` がドロップする際に標準出力はアンロックされる Ok(()) } }
このような繰り返し操作をする場合には、標準入力や標準エラー出力も同様にロックできます。
バッファリング
Rust のファイル I/O はデフォルトではバッファリングされていません。ファイルやネットワークソケットへの、小さいが繰り返し行われる読み書き処理を大量に行う場合は、BufReader
または BufWriter
を使ってください。これらは必要となるシステムコールの数を最小化しつつ入出力についてのインメモリバッファを管理します。
例えば、バッファされていない出力のあることのコードを:
#![allow(unused)] fn main() { fn blah() -> Result<(), std::io::Error> { let lines = vec!["one", "two", "three"]; use std::io::Write; let mut out = std::fs::File::create("test.txt").unwrap(); for line in lines { writeln!(out, "{}", line)?; } Ok(()) } }
このように変更できます:
#![allow(unused)] fn main() { fn blah() -> Result<(), std::io::Error> { let lines = vec!["one", "two", "three"]; use std::io::{BufWriter, Write}; let mut out = std::fs::File::create("test.txt")?; let mut buf = BufWriter::new(out); for line in lines { writeln!(buf, "{}", line)?; } buf.flush()?; Ok(()) } }
buf
がドロップした場合自動で強制的な出力 (flush) が行われるため、明示的な flush
の呼び出しは絶対に必要というわけではありません。しかし、暗黙的な呼び出しにおいては、強制的な出力で起きたエラーは無視されることになります。明示的な呼び出しではエラーは無視されません。
バッファリングは標準出力ともうまく動作するので、標準出力に対して多くの書き込みを行う際には手ずからロック 及び バッファリングを組み合わせて行うと良いでしょう。
入力を生バイト列 (raw bytes) として読み込む
組み込みの String
は内部で UTF-8 を使っています。そのため、入力を読み込む際には UTF-8 バリデーションのために小さいが0ではないオーバーヘッドが発生します。もし、例えば ASCII 文字を処理するときのように、UTF-8について何も考えなくていいようなバイト列入力だけを処理したい場合には、BufRead::read_until
を使用できます。
また、バイト指向のデータ行を読み込んだり、バイト文字列を処理したりするための専用のクレートがあります。
ログとデバッグ
(原文)
時々、ログやデバッグのためのコードがプログラムの速度を著しく低下させることがあります。ログやデバッグのためのコード自体が遅いこともあれば、データをそのようなコードに送るためのデータコレクションコードが遅いこともあります。ログやデバッグを行わない場合には、そのような目的のためのコードが不必要に使われていないかを確かめてください。
assert!
は常に実行されますが、debug_assert!
はデバッグビルド時にのみ実行されることを覚えておいてください。頻繁に呼び出されるが安全性のために必要なわけではないアサーションについては、debug_assert!
の使用を検討してください。
ラッパー型
(原文)
Rust は RefCell
や Mutex
のような、値に対して特別な働きを持つ様々なラッパー型を提供しています。そのような値へのアクセスは無視できない回数になることもあります。もしそのような複数の値が同時にアクセスされる場合には、それらを単一のラッパーに包んだ方が良いでしょう。
例えば以下のような構造体は:
#![allow(unused)] fn main() { use std::sync::{Arc, Mutex}; struct S { x: Arc<Mutex<u32>>, y: Arc<Mutex<u32>>, } }
このように表現した方が良いでしょう:
#![allow(unused)] fn main() { use std::sync::{Arc, Mutex}; struct S { xy: Arc<Mutex<(u32, u32)>>, } }
これがパフォーマンスの向上につながるかは、値への実際のアクセスパターンに依存します。
マシンコード
(原文)
頻繁にアクセスされる小さなコード片がある場合には、非効率な部分がないか生成されたマシンコードを調べる価値があるでしょう。Compiler Explorer というウェブサイトでは、そのような調査をするための素晴らしい環境が整っています。
関連して、core::arch
モジュールはアーキテクチャ固有の命令へのアクセスを提供しています。その多くは SIMD 命令に関するものです。
インデックス変数の範囲に対してアサーションを追加することで、ループ内の境界チェックを避けられる場合があります。これは高度なテクニックで、境界チェックが本当に取り除かれているか生成されたコードを確かめる必要があります。
並列処理
(原文)
Rustは安全な並列プログラミングのために素晴らしいサポートを提供しています。そのような並列処理は大きなパフォーマンス向上をもたらすことがあります。並列処理をプログラムに実装するには様々な方法がありますが、任意のプログラムについての最適な方法というのはそのプログラムの設計に大きく依存します。
並列処理についての詳細な説明はこの本の範囲外です。もしこのトピックに興味があれば、rayon
や crossbeam
のドキュメントから読み進めてみると良いでしょう。
バイナリサイズ
(原文)
コンパイルされた Rust のバイナリサイズを小さくしたい、という時があるでしょう。その際は、網羅的で有用なドキュメントが min-sized-rust
というレポジトリにあるため、そちらを参照してください。
汎用的なアドバイス
(原文)
この本のこれより前のセクションでは Rust 固有のテクニックについて解説してきました。このセクションでは一般的なパフォーマンスの基礎事項の簡潔な概要をいくつか紹介していきます。
Rust 自体のパフォーマンス
リリースビルドを使わないといったような明白な落とし穴を避ければ、Rust は一般的に良いパフォーマンスを発揮します。ときに、Python や Ruby のような動的型付け言語に慣れている場合にはこれが分かりやすいでしょう。
最適化する部分を見極める
最適化されたコードはそうでないコードよりも複雑で書くのに労力を要することも多いです。このような理由からホットなコードのみを最適化していく方が良いでしょう。
最も大きなパフォーマンス改善というのは、低レベルでの最適化よりもアルゴリズムやデータ構造の変更などによってもたらされることが多いものです。
現代的なハードウェア上での最適化
現代的なハードウェアでうまく動作するコードを書くというのは常に簡単というわけではありませんが、やってみる価値はあります。例えば、キャッシュミスや分岐予測の失敗を出来る部分で最小化してみてください。
小さな最適化を積み重ねる
ほとんどの最適化は小さなスピード改善という結果になりがちです。単一の改善では目を引くものでなくとも、それを十分な数積み重ねていけば大きなものになります。
いろんなプロファイラーを使ってみる
プロファイラーにはそれぞれ長所があります。複数使ってみるのが良いでしょう。
ホットな関数の最適化
もしプロファイリングで関数がホットであると分かった場合には、スピードを改善できる2つの一般的なやり方があります。
- (a): 関数を高速化する
- (b): 可能な限り呼び出しを避ける
愚直で遅い実装を潰していく
賢いスピードアップを図るよりも愚直な実装で遅い部分を潰していく方が多くの場合簡単です。
必要なときだけ評価する
必要でない限り何かを計算するのは避けましょう。遅延評価/オンデマンド評価 (on-demand computations) は改善につながることが多いです。
特殊・固有のケースについて処理する
複雑で一般的な実装は、共通する特別なケースに対する、よりシンプルなチェックにより避けられることが多いです。
Complex general cases can often be avoided by optimistically checking for common special cases that are simpler.
特に、小さなサイズが優位を占める場合、0~2個の要素を持つコレクションの処理はパフォーマンス改善につながることが多いです。
同様に、繰り返しのあるデータを処理する場合、共通の値についてコンパクトな表現を用いてまれな値についてはサブテーブルへとフォールバックするような実装をすることで、単純な形式のデータ圧縮を使用できます。
最もよくあるケースを優先する
コードが複数のケースに対処している場合、それぞれのケースの頻度を計測し、最もよくあるものを一番最初に処理しましょう。
局所性の高い探索 (lookup) を処理する場合、データ構造の先頭に小さなキャッシュを用意するとパフォーマンス改善につながることがあります。
コメントを書く
最適化されたコードは明白でない構造をしていることも多く、それを説明する、特にプロファイリングの測定結果を示すようなコメントを書くことが重要になります。例えば、「このベクタは99%の割合で0か1を要素として持つのでそれらのケースを先に処理してください」といったコメントは役に立つでしょう。
コンパイル時間
(原文)
この本は主に Rust プログラムのパフォーマンスを向上させることを対象としていますが、ここでは Rust プログラムのコンパイル時間を削減することを取り扱います。それは、多くの人が関心を持っているトピックであるためです。
リンク
コンパイル時間の大部分は実際にはリンク時間です。特に小さな変更を施した後にコンパイルし直すときは顕著です。プラットフォーム・ユースケース次第でデフォルトのものより高速なリンカを選択できます。
1つの選択肢は lld で、これは Linux 及び Windows 上で利用できます。
コマンドラインから lld を指定するには、ビルドコマンドの先頭に RUSTFLAGS="-C link-arg=-fuse-ld=lld"
を付け加えます。
(複数のプロジェクトのために)config.toml ファイルから lld を指定するには、次の行を追記します:
[build]
rustflags = ["-C", "link-arg=-fuse-ld=lld"]
Rust は lld の利用を完全にサポートしているわけではありませんが、Linux や Windows 上での殆どのユースケースで動作するはずです。lld の完全なサポートについてはこの GitHub Issue を参照してください。
もう1つの選択肢は mold で、これは現在 Linux 上でのみ利用できます。使用するには上記の lld の手順を mold に置き換えるだけです。
mold は多くの場合 lld よりも高速です。しかし比較的新しくすべての環境で動作するとは限りません。
インクリメンタルコンパイル
Rust コンパイラはインクリメンタルコンパイルをサポートしています。これはクレートをコンパイルし直すときの重複した作業を避けるものです。代償として、生成される実行可能ファイルの動作が少しだけ遅くなる場合があります。そのため、これはデフォルトではデバッグビルドでのみ有効になっています。リリースビルドでも同様に有効化したい場合には Cargo.toml
に次の行を追記してください:
[profile.release]
incremental = true
incremental
設定や異なるプロファイラについて特定の設定を有効化する方法など、詳細については Cargo のドキュメントを参照してください。
視覚化
Cargo はプログラムのコンパイルを視覚化する機能を持っています。timings
フラグを渡すことで有効化できます(Rust 1.60 以上の場合):
cargo build --timings
1.59 以下の場合はこちら:
cargo +nightly build -Ztimings
完了すると、HTML ファイルの名前が表示されます。そのファイルの web ブラウザで開いてください。HTML ファイルはプログラムに使われている様々なクレート間での依存関係を示すガントチャートを持っています。これはクレートグラフ中にどのくらいの並行性があるかを示し、コンパイルを直列化している大きなクレート群を分割すべきかを教えてくれます。詳細なグラフの読み方についてはこのドキュメントを参照してください。
LLVM IR
Rust はバックエンドに LLVM を採用しています。LLVM の実行は時としてコンパイル時間の大部分を占めることがあります。特に、Rust コンパイラのフロントエンドが中間表現 (IR) を大量に生成し LLVM がそれを最適化するのに時間を要している場合には顕著です。
これらの問題は cargo llvm-lines
により診断できます。このコマンドはどの Rust 関数が最も LLVM IR を生成しているかを表示するものです。巨大なプログラム中で何十回、あるいは何百回とインスタンス化されるため、ジェネリックな関数が重要なものとなることが多いです。
もしジェネリックな関数が中間表現を膨大にしている場合、いくつかの修正方法があります。もっともシンプルなものは関数を小さくすることです。
もう1つの方法は関数のジェネリックでない部分を、一度しかインスタンス化されない個別のジェネリックでない関数に移動することです。これが可能かどうかはジェネリックな関数の実装詳細に依存します。コード中での露出を最小化するため、ジェネリックでない関数はジェネリックな関数のインナー関数として書かれることが多いです。
- 例.
時々、Option::map
や Result::map_err
のようなよくあるユーティリティ関数が何度もインスタンス化されることがあります。そのような場合、同等の match
式に置き換えることでコンパイル時間を削減できます。
コンパイル時間における、上記のような変更の効果は通常小さいものですが、場合によっては大きな改善/改悪につながることもあります。