記録は作業の証

鉄道とコンピュータ

競技プログラミングにRustで参加するときに、なるべく高速で入出力する

この記事の続きです。

elderica.hatenablog.jp

自分のコードが遅い

ここずっと、アルゴ式というサイトでいろいろな問題に挑戦しています。このサイトは競うためものではないので、正答例や解説を読んだり、他人のコードを読むのが簡単です。

自分はRustで解いていますが、自分のコードが他人の書いたC++より何倍も実行時間が長いのがずっと気になっていました。RustはC++と遜色ないパフォーマンスが出せる言語だったはずです。自分のコードと、正答例、他人のC++コードを比較してみましたが、問題を解く部分のアルゴリズムはほぼ同じに見えました。そうであれば何がコードを遅くしているのでしょうか?

問題のコード

algo-method.com

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++と同じものが使えるようです。

nnethercote.github.io

qiita.com

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 はこんな感じです。ブラウザで開くと、塗り分けられた四角形をクリックして拡大できます。縦軸がスタックで横軸が時間(正確にはサンプリングしたときに実行中だった関数の割合)です。

gist.github.com

std::io::stdio::_print関数とtask889::read_words関数が、main関数を実行中だった時間のほとんどを占めています。コードが遅い原因は入出力が怪しいことがわかりました。

事例を調べてみる

調べてみると、Rustは並行性を考慮してデフォルトではバッファリングを行なわないそうです。

keens.github.io

codom.hatenablog.com

また、競技プログラミング向けに高速で入力が可能なクレートがありました。このクレートはMITライセンスかつモジュール一つで構成されています。このモジュールと標準出力のバッファリングを自分のコードに導入すると、C++と同等の実行時間になりました。

github.com

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
    いろいろなプロファイリングツールが出力したプロファイリングデータから、コールグラフなどを出力できるツールです。