競プロでは、どんなに非効率なコードを書いたとしても、要求された時間内に正しい答えが出せれば正義です。
なので、基本的には速いコードを書くことにそこまでこだわる必要はないです。
とは言っても速いコードを求めることは無意味ではなく、犯罪解法で計算量の悪いコードを押し通した結果、レートに直結することも稀にあります。
あとは単純に楽しいです。
AtCoderの過去問題やyosupo judgeのFastestを狙っているうちに、徐々に知見が溜まってきたので、思い出したものから雑多にメモしていきましょう。
より効率的なアルゴリズムを探す
あたりまえですが、小手先の高速化よりもまずはこれです。
効率の悪いアルゴリズムを時間をかけて異常最適化するより、効率の良いアルゴリズムをサクッと書いたほうが圧倒的な高速化が達成できます。
調べられる限り最良のアルゴリズムを選択したが、なおもパフォーマンスに満足行かないときは、高速化を目指しましょう。
プロファイリングをする
よく言われる話ですが、ボトルネックではない箇所の高速化を頑張っても、全体性能への影響は割合なりに薄いです。
1回きりの提出コードでいちいちプロファイリングするのはアホくさいですが、ライブラリの高速化では、なんかしらのツールを使ったプロファイリングから入ったほうがいいでしょう。
私は素人なので、とりあえずvalgrindでcallgrindとcachegrindを回して、なんか重たそうだなーと思った部分に手をつけています。
valgrindは使い方が簡単で、unsafe魔術に手を染めたときのメモリバグの発見に役立つmemcheckも使えるので、とても良いです。
使い始めはこのブログを参考にして、あとは公式のドキュメントとかを見ながら適宜欲しい機能を探しています。
Valgrindでコード解析してみる - CADDi Tech Blog
あとはLinuxの環境であればcargo flamegraphを使うのも良いと思います。
以前は使っていたのですが、依存しているperfがWSLでうまく動かないことがあって、valgrindに乗り換えました。生のLinuxではちゃんと動いていました。
アセンブリを読む
コードを読むだけでは、実際そのコードの何が問題で遅いのかよくわからないことが多々あります。
そのようなときはアセンブリを出力して読むのがいいかもしれません。
Rust以外でも通用する手段としては、objdumpを利用して実行ファイルを逆アセンブルする方法や、小さなコードならCompiler Explorerを使用する方法があります。
rustc, cargo rustcを使った方法としては、コンパイラオプションとして--emit asmを渡すことでも実現できます。
Command-line Arguments - The rustc book
多くの場合、Releaseビルドでの出力を見たいと思いますが、その場合はCargo.tomlで[profile.release]セクションにdebug = trueを設定しておかないと、デバッグ情報が失われて、なんのこっちゃとなるので注意してください。
（デバッグ情報レスで数万行のアセンブリを読解できるプロの方はこの限りではない）
ぶっちゃけ私は完璧にアセンブリを読み切れてないことが多いのですが、ざっくり「ここなんでインライン化されてないんだろうな」とか、「除算最適化されると思ってたけどされてないな」とか大雑把なアタリさえ付けばあとはコードを書いて試行錯誤できるので、方向性がわからなくなったときにとりあえず読んでみています。
入出力を高速化する
出力は特に何も考えずに標準のものを使うとかなり低速になります。入力はそこまで致命的ではないですが、多少伸びしろがあります。
yosupo judgeのMany A+Bの上位提出を見るなどして高速な入出力を手に入れましょう。
以下、それぞれについて概要だけ。
入力を高速化する
まず入力の話です。
AtCoderだとproconioを使っている人が多いかもしれませんが、これは最速の入力方法ではありません。特に数値入力の場合、パース処理に標準ライブラリを使っており、遅いです。
これはあらゆる入力に対処し、適切にエラーを処理する必要があるので仕方の無いことですが、競プロでは制約は厳格に守られるので、基本的に制約外の入力を気にする必要はありません。
4ケタ、8ケタ、16ケタなど、キリのいい桁数の数値には、まとめて (
は桁数)回の操作で数値へ変換する方法があります。
以下のような記事が役立ちそうです。
Parsing series of integers with SIMD
出力を高速化する
次に出力の話です。
有名な話ですが、print!/println!はたくさん実行される場合、めちゃくちゃ遅いです。
この理由と解決策は、標準ライブラリのドキュメントに書いてあります。
要は、出力開始前にstd::io::stdout().lock()でStdoutLockを取得し、write!/writeln!で書き込めばよいです。BufWriterによるバッファリングもしましょう。
proconio::fastoutはこれらを自動でやってくれるマクロなので、proconio::fastoutを使うのも効果的でしょう。
ただ、数値の出力の場合、まだ速くできます。文字列への変換が遅いからです。
1桁ずつバッファに押し込むのではなく、ルックアップテーブルを用いて数桁まとめてバッファに押し込むことで、割り算の回数やバッファコピーの回数を減らせます。
なるべく小さい型を使う
Rustで競プロをしている人々には、配列のアクセスにusizeしか使えないので何でもusizeで処理したり、オーバーフローによるミスを嫌ってi64で処理したりという人が多いと思います。
データ量が大したことなければこれでも問題ないですが、配列などで大量にデータを持つときは、パフォーマンスに大きな影響が出ます。
ランダムアクセス時にはキャッシュ効率が極端に悪くなりますから、データはなるべく小さくまとめるに越したことはありません。
シーケンシャルアクセスが主だとしても、自動ベクトル化の恩恵を受けづらくなるというデメリットもあります。
コンテスト中に気にしながら書くのは億劫かもしれませんが(私は億劫ではないです)、ライブラリの中では可能な限り小さい型を使うように気を配ってもいいかもしれません。
proconio::marker::Bytesを使う
proconioを使っている場合のみの話です。
proconio::input!を使って文字列を受ける方法は、
Stringのまま受けるproconio::marker::Charsを用いてVec<char>として受けるproconio::marker::Bytesを用いてVec<u8>として受ける
の3つあり、なんとなく2.の方法でVec<char>として受けている人はいると思います。
しかし、競プロで受ける入力のほとんどはASCII文字である一方、charは4byteのUnicode Scalar Valueなので、メモリの無駄です。
競プロで求められる文字操作は高々、比較、加減算、ケース変換・判定くらいだと思います。これらの操作は、すべてu8でも可能です。
メモリ効率が上がることによってパフォーマンスへの影響もあるので、どうしてもVec<char>がほしいとき以外はVec<u8>を使うのが良いかもしれません。
ちなみに、問題によってはStringのまま受けるのが最適なことも多いです。
Rustのstr/Stringはできることがかなり多く、配列操作で代替すると面倒なことでもメソッド1つで完結します。
str/StringはUTF-8文字列なので、ASCII文字しか含まない場合は文字列長分のバイト数しか消費せず、メモリにも優しいです。
スライスのソートにsort_unstableを使う
[T]や[T; N]やVec<T>などの型をソートする場面はかなり多いでしょう。
このとき、パッと目につくのはsortというメソッドだと思いますが、ソートをするにはsort_unstableというメソッドも使えます。
この2つのメソッドの違いは、安定ソートかそうでないかという点です。sort_unstableは安定ソートの制約を捨てているぶん、高速なアルゴリズムを採用しているようです。
競プロで安定ソートが必要な場面はほぼないため、可能な限りsort_unstableを使いましょう。
sort_by, sort_by_keyに対応するsort_unstable_by, sort_unstable_by_keyもあります。
大量のデータを含んだ配列をソートしたらあとはでなんかやるだけ、という問題は非常に多いです。
Rustのsort_unstableはC++のソートと比べても体感かなり速いので、このような問題はsort_unstableでしばくだけでFastestが取れることがしばしばあります。
コンパイル時計算をする
前計算ができる場面では、コンパイル時計算を活用しましょう。
入力の制約が小さく難易度が低い問題であれば、制約上あり得る入力に対するすべての解をコンパイル時計算し、実行時には入出力をするだけという状態にできます。
注意点としては、現在AtCoderで使えるRustバージョンでは、コンパイル時計算の評価上限が存在します。
なので、コンパイル時計算で前計算を行う際には定数倍も含めてなるべく計算量のよい処理を書くことが重要です。意外なことに、コンパイル時計算をするときのほうが、実行時計算をするときよりも計算量の点ではシビアです。
例えば、素数列挙には大抵の場合エラトステネスの篩で事足りますが、コンパイル時に素数列挙をするときは線形篩やアトキンの篩のような計算量の良い篩を使うことで、列挙の上限を大幅に増やすことができます。
Rust 1.82の時点ではPlaygroundで試す限り無限に評価できるようで、たぶん評価上限は撤廃されています。（ただしリントでエラーが出るので#[allow(..)]で外す必要がある）
ちょっと評価上限についてのドキュメントは見当たらなかったので、嘘ついてたら教えてください。
HashMap/HashSetを使わない
std::collections::HashMap/HashSetは遅いことで有名です。
標準ライブラリのドキュメントに書いてあることですが、ハッシュ関数としてHashDoS攻撃への耐性が高いアルゴリズムを採用していることが原因のようです。
HashMap in std::collections::hash_map - Rust
メモ化再帰をするときなど気軽に使いがちですが、状態数が多くなるとTLEすることもザラなので、[T]やVecで済ませることができないか検討しましょう。
ハッシュテーブルは一応での検索が可能なことになっていますが、場合によっては検索に
かかるはずの
std::collections::BTreeMap/BTreeSetのほうが高速なこともあるので、ライブラリで使うときは両方試してみて、いい感じなほうを採用するようにしたほうが良いでしょう。
AtCoder限定で通用する解決策としては、rustc_hash::FxHashMap/FxHashSetを使うという手があります。
これはrustcで使われているハッシュ関数を利用したハッシュテーブルで、実体としてはカスタムハッシャーを設定したstd::collections::HashMap/HashSetの型エイリアスです。
HashDoS耐性が標準のものより劣っているかわりに性能は高いです。標準ハッシュテーブルの型エイリアスでしかないので、APIは全く同じものが使えます。
可変なグローバル変数を持たない方法を考える
そもそもRustでは自然には可変なグローバル変数を扱うことはできないので、あまりグローバル変数を持とうと考えている人もいないと思いますが…
とはいっても、一応可変なグローバル変数を持つ方法はいくつかあって、主に
thread_local!とRefCellなどのスレッドセーフでない内部可変コンテナを使うstaticとMutex,RwLockなどのスレッドセーフな内部可変コンテナを使うAtomicI32などのプリミティブなアトミック型を使う- 妥協して
static mutを使う
4.の方法はスレッドセーフではないので読み書きともにunsafeが要求されます。ぶっちゃけ競プロでマルチスレッドをやる人は皆無なので、実用上さして問題にはならないでしょう。
ただ地味な問題点として、テストは何も設定しなければマルチスレッドで動作しますから、テストの結果が狂います。
これはテスト動作時のスレッド数を制御するパラメータで対処可能です。
Controlling How Tests Are Run - The Rust Programming Language
他の方法はすべてsafeで扱えますが、いずれもパフォーマンス上の問題があります。
1.は、体感ですが、thread_local!が遅いです。ソースコードを読んでもstd::thread::LocalKeyが何をしているのかよくわからなかったので、原因は不明です。RefCellと併用する場合はボローチェックも走ります。
2.は、(Linuxでは)内部的にAtomicU32へのCAS操作でロックを実施しているので、3.と同じくらいのコストがかかります。(ロックの取り合いになったら待ちが発生するので、もう少しコストがかかります)
3.は、アトミック命令を発行するので多少のコストはありますし、プリミティブ型に対応する型しかありません。
結局の所、可変なグローバル変数を持とうとすると、unsafeな方法か、safeだけどコストのかかる方法かしかないので、そもそも持たない方向で考えたほうが良いでしょう。
unsafeに夢を見過ぎない
Rustを書き始めると、やはり始めのうちはunsafeを忌避する傾向が強く、初心者の頃から「よーしじゃんじゃんunsafe使いまくるぜ！」みたいは人はほぼいないと思います。
ただ、それの裏返しというのか、safe Rustでできそうなことをやり尽くしてしまうと、「unsafe魔術に手を出せばもっとパフォーマンス改善できるのでは…？」という幻想を抱いてしまいます。（私だけですかね？）
この幻想は全く大ハズレでもないと思うのですが、無駄にunsafeを使ってもただコードが複雑化するだけで、さしてパフォーマンスが上がらないということは多々あります。
例として、まずはunwrap_uncheckedが挙げられます。
どう考えても失敗するわけないunwrapが大量に差し込まれているコードというのはあるあるで、これをunwrap_uncheckedに置き換えればパフォーマンスが上がるんじゃないか？という疑問が出てくるわけです。
これは正直誤差以上の差が生まれるのを見たことがありません。そもそもunwrapがボトルネックになる場面なんてほぼないので、まあ当然の結果かもしれません。
それからスライスや配列に対するget_uncheckedや生ポインタの使用です。
配列へのアクセスは常に境界チェックによって安全に保たれていますが、では境界チェックを省けばもっと早くなるんじゃないか？ということです。
これは大量の要素アクセスがある場合、確かに若干パフォーマンスが改善します。ただ、コードの見た目はグッチャグチャになるので、用法用量を考えるべきでしょう。
逆に意味あるunsafeの使用例としては、str::from_utf8_uncheckedがあります。
safeなバージョンとしてstr::from_utf8がありますが、これはstrの制約を守るため、与えたスライスがUTF-8バイト列として妥当かを検証します。
当然これには (
はバイト長) の計算量がかかりますが、与えられる文字列がASCII文字列の場合に検証はどう考えても不要でしょう。
str::from_utf8_uncheckedはスライスを検証せずにそのままstrとして扱うため、計算量はです。
から
への改善は劇的な改善になるので、これは意味がありそうです。
結局のところ、ちゃんと計測をしましょうということに尽きるのかもしれません。
#[target_feature(enable="...")]を使う
Conditional compilation - The Rust Reference
C++でQCFium法をやるときのpragmaのRust版みたいなものです。
ただし、Rustのtarget_featureは関数単位でしか使用できません。
C++などの他言語同様、ターゲット依存機能はコンパイラオプションでも有効化できますが、Rustはソースコード内からコンパイラオプションをイジることが(私が知る限り)できないので、ターゲット依存機能を強制的に有効化するにはtarget_featureを使用するしかありません。
使用可能な機能は以下のドキュメントから確認できます。
ほとんどのオンラインジャッジはAMD64でしょうから、x86 or x86_64の箇所を見てください。
Code generation - The Rust Reference
注意すべき点は、このアトリビュートをつけた関数は常にパフォーマンスが改善するわけではなく、場合によってはむしろ悪化する場合もあるという点です。
当たり前ですが、有効化した機能がそれほどうまく使えないような処理では、パフォーマンス向上はほぼありません。
また、target_featureを付加されている関数は、有効化されている機能が存在しないアーキテクチャでは実行できません。（ゆえにunsafeになる）
そのため、該当のアーキテクチャ以外も想定する関数内部でtarget_featureつきの関数を使用すると、その関数が小さな関数であってもインライン化できない場合があります。何度も使われる細かい関数はインライン化によってパフォーマンス向上が期待できますが、そのような関数に無駄にtarget_featureを付加すると、むしろパフォーマンス悪化につながるかもしれません。
アーキ固有命令を使用するときもそうですが、なんかうまくパフォーマンスが出ないなと思ったら、アセンブリを見てみるのが良いでしょう。
SIMDを自力で書く
巨大データにシーケンシャルな定形処理を延々やるような場合、SIMDが有効なことがあります。
多くの場合は#[target_feature(enable="...")]で満足できるレベルになりますが、ちょっと凝った処理をしようとするとコンパイラの最適化では対応できないこともあるため、手書きすればさらなる高速化を達成できるかもしれません。
Rustではstd::arch(core::arch)配下にアーキテクチャ固有命令があります。
それぞれ対象のアーキテクチャ以外では動作しないので、適宜#[cfg(target_arch="...")]でコードの有効/無効を切り替えてコードを書き分けます。
競プロで使う機会はたぶんないですが、ARMとかRISC-Vの命令も用意されています。
当たり前ですが、実行環境が使用する命令セットに対応している必要があります。Apple siliconでSSEやAVXはエミュレータとかを使わない限り当然動きません。
また、AMD64のCPUであっても、AVX2はよほど化石なCPUを使っていない限り動くでしょうが、AVX512は比較的新しいCPUでも対応していないことがあります。
AMD64向けには、std::arch::x86_64(core::arch::x86_64)配下に命令群が用意されています。
SIMD命令については、AVX2以前の命令は使用できますが、AVX512系の命令セットは現在でもまだunstableです。
unstableを使用するにはnightlyコンパイラが必要ですが、オンラインジャッジではstableのコンパイラが使われているでしょうから、普通にAVX512を使うことはできません。
どうしてもAVX512をオンラインジャッジ環境で使用したい場合は、バイナリ提出を行うしかないでしょう。
asm!マクロで直に命令を埋め込めば動くんじゃないかと思いましたが、zmmレジスタで入出力するのにavx512fが必要なので、コンパイルを通せませんでした。
あるいはコンパイル済のアセンブリをglobal_asm!で埋め込むとかですかね…やったことないので本当に動くかは不明です。
ドキュメントを読んでみると、とてつもない量の命令が書いてあってげんなりするかもしれませんが、ほとんどはAVX512系の命令なので、現状stableでは使えないものです。
Rustのドキュメントでフィルタをかける方法は知らないので、IntelのIntrinsics GuideでSSE family, AVX familyにフィルタをかけて眺めるのがよいでしょう。
私は専門家ではないので詳しいことはよくわかっていないのですが、レジスタの数が限られていることと、load/storeはまあまあ重たいことは意識しながら書いたほうが良いという感覚があります。
ある程度は最適化でよしなにやってくれますが、あまりにテキトーなコードを書くと、所々にload/storeが必要になってしまい、思ったようなパフォーマンスが出ません。
また、適切に#[target_feature(enable="...")]を付加しないと、コードをいくつかの関数に分割した際、うまくインライン化されず、関数を呼び出すごとにload/storeが走ってしまうというケースもあります。
あとがき
もっとネタがあると思って書き始めたんですが、意外に手持ちネタがなかったです。もっと色々見つけたら追記します。
なるべくちゃんと情報ソースは本文中に埋め込みましたが、ウソを書いていたら教えてください。
