Rust の標準入出力は(何も考えないで使うと)遅い

tl; dr

  • Rust の標準入出力はデフォルトのままでは遅い.
  • 速度な必要なときは StdinLock 構造体を使う.

コードと実測の結果がこちらで確認できます.
http://arc079.contest.atcoder.jp/submissions/all?task_screen_name=arc079_a&language_screen_name=rust_1.7.0&status=AC&user_screen_name=tubo28
あるアルゴリズムの入力関数以外は同じ実装なのですが,実行時間がかなり違います.
最大で 6 桁の整数を 400,000 個読み込む処理の書き換えで,これだけの違いが出ていることになります.

情報元はこちら (標準入力の項以外も参考になります).
Rust Performance Pitfalls — Llogiq on stuff

ベンチマーク環境

以降のプログラムは全て次のような環境で実行しています.

プロセッサ : Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz
OS : Ubuntu 16.04 64bit
rustc --version : rustc 1.22.0-nightly (26015da01 2017-09-23)
gcc --version : gcc (Ubuntu 5.4.0-6ubuntu1~16.04.4) 5.4.0 20160609

Rust での標準入力

Rust で C 言語の scanf("%ud", &n) 相当の処理,すなわち標準入力から非負整数を一つ読み込む処理を書きたくなったとき,以下のように書くのがたぶん自然かと思います.

read.rs
// 簡単のためエラーハンドリングが雑なのはご理解ください

use std::io::*;
use std::str::*;

fn read<T: FromStr>() -> Option<T> {
    let stdin = stdin();
    let s = stdin.bytes().map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok()
}

fn main(){
    let mut acc: u32 = 0;
    while let Some(n) = read() {
        acc += n;
    }
    assert_eq!(acc, 30000000);
}

このプログラムに "1" を 30,000,000 個入力して,速度を測ってみます.

$ rustc read.rs -O && yes 1 | head -n 30000000 | time ./read
./read  3.64s user 0.02s system 99% cpu 3.663 total

一方同じことを C プログラムでやってみると…

read.c
#include <stdio.h>
#include <assert.h>

int main() {
    unsigned acc = 0;
    unsigned n;
    while (scanf("%ud", &n) == 1) {
        acc += n;
    }
    assert(acc == 30000000);
}
$ gcc read.c -O2 && yes 1 | head -n 30000000 | time ./a.out
./a.out  2.21s user 0.02s system 99% cpu 2.233 total

Rust では 3.64s かかっている一方,C では 2.21s で済んでいます.Rust の方が約 1.6 倍遅いことになります.

なぜ遅いのか

Rust では共有資源である標準入力に対するアクセスで競合を起こさないように,1 バイト読み込む度にロックとアンロックを繰り返しているのが遅い原因です.

そこで,次のように書き換えてみます.
lock() によって, stdin をロックした上でバッファリングするリーダーを実装した StdinLock 構造体が取得できます.

read2.rs
use std::io::*;
use std::str::*;

fn read<T: FromStr>(s: &mut StdinLock) -> Option<T> {
    let s = s.by_ref().bytes().map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok()
}

fn main(){
    let s = stdin();
    let mut s = s.lock();
    let s = &mut s;
    let mut acc: u32 = 0;
    while let Some(n) = read(s) {
        acc += n;
    }
    assert_eq!(30_000_000, acc);
}

同じように実行して時間を測ってみます.

./read2  2.16s user 0.00s system 99% cpu 1.826 total

2.16s に短縮されました.手元の環境ではなぜか何度実行しても C より早いです. (C でも getchar_unlocked を使うなどすれば同じくらいになる気がします.)

標準出力

ここでは面倒なので省略しますが標準出力も同じように高速化できます.詳しくは冒頭にあるリンク先の記事を見てください.

もっと速く

主旨から離れますが,毎回 String を経由しているのも律速なので,ナイーブに書くともっと速くなります (もちろん C でも同じようにすれば速くなると思います).型ごとに実装するのはつらいというトレードオフはありますが.

read3.rs
use std::io::*;

fn read(s: &mut StdinLock) -> u32 {
    s.by_ref().bytes().map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .fold(0, |a, x| (x as u8 - b'0') as u32 + a * 10)
}

fn main(){
    let s = stdin();
    let mut s = s.lock();
    let s = &mut s;
    let mut acc: u32 = 0;
    loop {
        let n = read(s);
        if n == 0 {
            break;
        }
        acc += n;
    }
    assert_eq!(30_000_000, acc);
}
./read3  1.03s user 0.00s system 99% cpu 1.038 total

もとの 28 % 程度にまで高速化されましたね!