この記事の続きです。
自分のコードが遅い
ここずっと、アルゴ式というサイトでいろいろな問題に挑戦しています。このサイトは競うためものではないので、正答例や解説を読んだり、他人のコードを読むのが簡単です。
自分はRustで解いていますが、自分のコードが他人の書いたC++より何倍も実行時間が長いのがずっと気になっていました。RustはC++と遜色ないパフォーマンスが出せる言語だったはずです。自分のコードと、正答例、他人のC++コードを比較してみましたが、問題を解く部分のアルゴリズムはほぼ同じに見えました。そうであれば何がコードを遅くしているのでしょうか?
問題のコード
use std::collections::VecDeque; fn main() { #[allow(unused)] let _x: usize = scan_line()[0]; let _q: usize = scan_line()[0]; let mut scheduled_completion_times: VecDeque<usize> = VecDeque::new(); let mut completed_task_counter: usize = 0; for _ in 0.._q { let mut query = read_words().into_iter(); let op_id = query.next().expect("query has operation id"); let current_time: usize = query.next().unwrap().parse().unwrap(); match op_id.as_str() { "0" => { scheduled_completion_times.push_back(current_time + _x); } "1" => { while let Some(&s) = scheduled_completion_times.front() { if s <= current_time { completed_task_counter += 1; scheduled_completion_times.pop_front(); } else { break; } } println!("{}", completed_task_counter); } _ => unreachable!(), } } } fn read_line() -> String { let mut line = String::new(); std::io::stdin().read_line(&mut line).unwrap(); String::from(line.trim()) } #[allow(dead_code)] fn read_words() -> Vec<String> { read_line().split_whitespace().map(String::from).collect() } #[allow(dead_code)] fn scan_line<F>() -> Vec<F> where F: std::str::FromStr, { read_line() .split_whitespace() .flat_map(|s| s.parse::<F>()) .collect() }
プロファイリングしてみる
犯人探しに役立てるため、プロファイリングを行います。RustではCやC++と同じものが使えるようです。
cargo-flamegraph
を利用してみることにします。まずはインストールします。
$ cargo install flamegraph
新しくパッケージを作り、問題のコードを配置します。 ここで、大きめのテストケースをアルゴ式のサイトからダウンロードしておきます。
$ cargo new task889 && cd task889 $ cat > src/main.rs # コードをコピペ $ cp ~/Downloads/<テストケースのファイル名> ./testcase.txt
計測します。
$ env CARGO_PROFILE_RELEASE_DEBUG=true cargo flamegraph --freq 10000 < testcase.txt > /dev/null
出てきたflamegraph.svg
はこんな感じです。ブラウザで開くと、塗り分けられた四角形をクリックして拡大できます。縦軸がスタックで横軸が時間(正確にはサンプリングしたときに実行中だった関数の割合)です。
std::io::stdio::_print
関数とtask889::read_words
関数が、main
関数を実行中だった時間のほとんどを占めています。コードが遅い原因は入出力が怪しいことがわかりました。
事例を調べてみる
調べてみると、Rustは並行性を考慮してデフォルトではバッファリングを行なわないそうです。
また、競技プログラミング向けに高速で入力が可能なクレートがありました。このクレートはMITライセンスかつモジュール一つで構成されています。このモジュールと標準出力のバッファリングを自分のコードに導入すると、C++と同等の実行時間になりました。
fast_input
を読む
このクレートではStdin
のロックを取って入力をEOFまで読み、全てをVec<u8>
型でヒープに保持します。
また、入力を切り出すときはヒープに割り当てを行うような操作をせず、単にスライスを返すだけという設計になっています。
ここで自分のコードとfast_input
を比べてみます。
fn read_line() -> String { let mut line = String::new(); std::io::stdin().read_line(&mut line).unwrap(); String::from(line.trim()) } #[allow(dead_code)] fn read_words() -> Vec<String> { read_line().split_whitespace().map(String::from).collect() }
- 単語ごと/行ごとにヒープに割り当てを行っている。
- 入出力で明示的にロックを取っておらず、バッファリングもしないため、ロックとアンロックが大量に発生する。
問題はここにあったのです。
入力コードの刷新
MITライセンスとはいえ、fast_input
をそのまま使い続けるのはどうだろうかと感じ、こんな感じのコードを書きました。slurp
する型なので安直にSlurper
という名前です。もっと良い名前はあるでしょうか?
use std::cell::Cell; use std::io::{stdin, Read}; struct Slurper { str: String, pos: Cell<usize>, } impl Slurper { fn stdin() -> Self { let mut s = String::with_capacity(65536); stdin() .lock() .read_to_string(&mut s) .expect("read until EOF"); Self { str: s, pos: Cell::new(0), } } fn read_line(&self) -> &str { let start_pos = self.pos.get(); let mut current_pos = start_pos; while current_pos < self.str.len() && &self.str[current_pos..current_pos + 1] != "\n" { current_pos += 1; } self.pos.set(current_pos + 1); self.str[start_pos..current_pos].trim_end() } #[allow(dead_code)] fn read_word(&self) -> &str { let start_pos = self.pos.get(); let mut current_pos = start_pos; while current_pos < self.str.len() && &self.str[current_pos..current_pos + 1] != " " && &self.str[current_pos..current_pos + 1] != "\n" { current_pos += 1; } self.pos.set(current_pos + 1); self.str[start_pos..current_pos].trim_end() } #[allow(dead_code)] fn read_words(&self) -> Vec<&str> { self.read_line().split_ascii_whitespace().collect() } #[allow(dead_code)] fn scan_line<F>(&self) -> Vec<F> where F: std::str::FromStr, { self.read_line() .split_ascii_whitespace() .flat_map(str::parse::<F>) .collect() } }
このコードを導入して試してみると、その結果はfast_input
を使ったものやC++コードとほぼ同等になりました!
Vec<u8>
ではなくString
で保持しているせいか、ごく僅かに遅いですが十分でしょう。
collect
せずにイテレータを返してもいいかもしれません。
反省
実際には、かなりの試行錯誤とGoogle検索に頼り、構造的なアプローチが取れていませんでした。デバッグやプロファイリングの技術をもっと学ぶ必要がありそうです。
検索するなかで便利そうなツールを他にも見つけました。
- Hotspot
perfのプロファイリングデータを読んで視覚的に表示するツールです。 - KCachegrind
ValgrindのツールのCallgrindが出力したプロファイリングデータを読みこんで視覚的にコールグラフを見られるツールです。プロファイリングにも使えます。 - gprof2dot
いろいろなプロファイリングツールが出力したプロファイリングデータから、コールグラフなどを出力できるツールです。