Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

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 % 程度にまで高速化されましたね!

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした