Rustで数値を連結した文字列を作るときはItertools::joinが速い

Rustで数値を値に持つイテレータ（たとえば Iterator<Item=usize>）を文字列として連結したいことがあります（主に競プロとかで）。以下のようなイメージです:

# 空白区切りの文字列にする
[1, 2, 3, 4]
 => "1 2 3 4"

この際のパフォーマンスについて書いた記事が、ありそうなのになかった（見つけられなかった）ため、ちょっと手元で測ってみました。

結論を先に書くと、（少なくとも今回の測定条件の範囲内では）Itertools::join()を使うのが最適と思われます。

一方で、to_string()してcollect()してから[T]::join()を使う方法は（上記の方法よりは）遅いようです。

背景

きっかけは、以下のmaguro_tunaさんの記事を（改めて）拝見したことです:

こちらでは、文字列を値に持つイテレータから連結された文字列を得るときに Itertools::join を使うと遅く、Vec<_>にcollect()してから[T]::join()を使うのが速い、と結論づけられています。

一方で、数値を値に持つイテレータについて同様の実験をした記事は、少なくともぱっと見た感じでは見つけられませんでした。
競技プログラミングで「数列の値を空白区切りで出力する」などを行うことが多いので、個人的には数値の場合にどうなるかは気になるところです。

数値を扱う場合と文字列を扱う場合の大きな違いとして、数値に対して[T]::join()を使いたければ、一旦数値をStringなどに変換してやる必要があります。一方で、Itertools::join()はStringに変換せずに数値を直接渡せるので、そのあたりで違いが出てくるのではないかと思いました（詳しくはこの後のサンプルコードもご参照ください）

自分は過去に上記の記事を見て、なんとなく「 Itertools::join() は遅いんだな」というイメージだけ残ってしまっていましたが、先日改めてこの記事を見た際に、数値の場合だとどうなるのか気になり、測定してみました。

注意書き

パフォーマンスは測定環境や測定条件によって傾向が変わりうるので、個々のケースでの正確な結果が欲しい方はご自分で計測してください。
下記に詳述しますが、今回は競プロでよくある「10^5個程度の整数を出力する」という条件で計測しています。

試した方法一覧

A: to_string() してから collect() して join()

[T]::join() を使います。

fn to_string_and_join(values: &[usize]) -> String {
    values
        .iter()
        .map(|x| x.to_string())
        .collect::<Vec<_>>()
        .join(" ")
}

文字列の場合に最速だった方法に、数値から文字列への変換のためのto_string()を足したものです。

B: to_string()してからpush_str()を使ってfold() （capacity指定なし）

[T]::join() を使わずに自分で文字列を作ります。まずはcapacity指定なしで、to_string()とpush_str()を使ってみます。

fn fold_by_to_string_without_capacity(values: &[usize]) -> String {
    values
        .iter()
        .map(|s| s.to_string())
        .fold(String::new(), |mut acc, cur| {
            acc.push_str(&cur);
            acc.push_str(" ");
            acc
        })
}

C: to_string()してからpush_str()を使ってfold() （capacity指定あり）

capacity指定あり版です。（capacityの大きさは実際に使う値に合わせて調整します。今回は最大6桁の数値を使ったので、capacityは区切り文字と合わせて7×文字数にしました）

fn fold_by_to_string_with_capacity(values: &[usize]) -> String {
    values
        .iter()
        .map(|s| s.to_string())
        // 数値一つが最大6桁 + separator1文字で7文字
        .fold(String::with_capacity(7 * values.len()), |mut acc, cur| {
            acc.push_str(&cur);
            acc.push_str(" ");
            acc
        })
}

D: write!()を使ってfold() （capacity指定なし）

to_string()やpush_str()は使わずに、write!() を使って文字列にしてみます。数値の場合はこちらのほうが自然かもしれません。

fn fold_by_write_without_capacity(values: &[usize]) -> String {
    use std::fmt::Write;

    values.iter().fold(String::new(), |mut acc, cur| {
        write!(&mut acc, "{} ", cur).unwrap();
        acc
    })
}

E: write!()を使ってfold() （capacity指定あり）

capacity指定あり版です。

fn fold_by_write_with_capacity(values: &[usize]) -> String {
    use std::fmt::Write;

    values
        .iter()
        // 数値一つが最大6桁 + separator1文字で7文字
        .fold(String::with_capacity(7 * values.len()), |mut acc, cur| {
            write!(&mut acc, "{} ", cur).unwrap();
            acc
        })
}

F: Itertools::join

Itertools::join() を使います:

fn itertools_join(values: &[usize]) -> String {
    values.iter().join(" ")
}

コードは断トツで一番短いですね。
Itertools::join()の良いところはstd::fmt::Displayをimplしているものならなんでも使えることで、わざわざto_string()してやる必要はありません。

なお、Itertoolsには関数版のjoin()もあります。違いはIteratorそのものではなくIntoIteratorを渡せることです。それ以外の違いはなさそうなので今回は割愛します。

測定方法

参考元の記事同様に、bencher を使って計測しました。

念には念を期して最適化の影響を極力抑えるために、使用する配列は実行時に乱数を使って生成しました。値の個数は10^5個です。

const N: usize = 100000;

let mut rng = rand::thread_rng();
let values = (0..N).map(|_| rng.gen_range(0..1000000)).collect()

乱数の生成時間は実行時間には含めていません。また、生成はプログラムの最初に一回だけ行い、全ての手法で同一の配列が用いられるようにしました。

測定環境はWSL上のUbuntu20.04、Rustのバージョンは1.67.1です。

実際に使ったソースコードのリポジトリは記事末尾にあります。

結果

bencherで測定した、1回あたりの実行時間です。

#	手法	実行時間(ns)	測定誤差(ns)
A	to_string()+collect()+[T]::join()	3,940,039	+/- 567,790
B	to_string()+push_str()+fold() (capacity指定なし)	1,963,223	+/- 122,365
C	to_string()+push_str()+fold() (capacity指定あり)	2,024,358	+/- 154,632
D	write!()+fold()（capacity指定なし）	1,437,057	+/- 139,339
E	write!()+fold()（capacity指定あり）	1,391,923	+/- 145,342
F	Itertools::join()	1,265,368	+/- 100,257

[T]::join()を使った方法が最も遅く、一方で Itertools::join() を使った方法が最速だという結果になりました（2位との差は1ms以下なので、現実的にはほぼ同じと言っても良さそうですが）。

なぜこういう結果になったのか（推測）

以下は、あまり裏付けの取れていない推測になりますので、間違いがありそうであればご指摘ください

to_string()を使うと遅い理由

まず、to_string() を使う3つ（A～C）は、明らかにto_string()を使わないもの（D～F）よりも遅いです。おそらくですが、要素一つ一つごとにStringを生成するため、メモリ確保のオーバーヘッドが大きいのではないかと思われます。

A～Cでcollect()+[T]::join()が最も遅い理由

次に、to_string()を使う3つの中で、collect()してから[T]::join()を使う方法が2倍程度遅い理由も考えてみたんですが……こちらははっきりとは分からず……。ただ、いくつか試していて以下の手がかりが得られました:

• 数値ではなく文字列を使った場合、（maguro_tunaさんの実験と同様に）collect()してから[T]::join()を使う方法が最も速い
• しかし、元の値が文字列であっても、イテレータの処理中に .map(|s| s.to_string())をはさむ（つまり&strからStringに変換する）と、collect()してから[T]::join()を使った方法がpush_str()+fold()を使った方法よりも遅くなる
  • （元が&strの場合はStringに変換する意味は特にないですが）
• 個別に計測してみたところ、[T]::join()にかかる時間は全体に対してかなり少なく、to_string()してcollect()するところに時間がかかっている。

fold()を使った場合、「to_string()で新しいStringを生成する→push_str()して破棄する」の繰り返しになるので、一度に存在するStringは一つだけですが、一旦collect()した場合は大量のStringが一度に存在することになるので、メモリ使用量に違いが出そうです。これらの手がかりと合わせると、このあたりのメモリ使用量の違いが速度の違いの原因かもしれません。

D～FでItertools::join()が最も速い理由

僅差ではありますが、Itertools::join()を使うとto_string()を使わない3つの中で最速の結果が得られました（何回実験しても同様だったので、おそらく誤差ではないだろうと思います）。

こちらについては、Itertools::join()のソースコードを見てみると、

• イテレータの要素はwrite!()を使って書き込み、
• separator（今回は空白文字）についてはpush_str()を使って書き込む

となっていました。つまり、write!()が不要な部分についてはpush_str()を使って書き込んだほうが速いという仮説が立てられます。

ということで、追加で以下のような方法を試してみました:

fn fold_by_write_without_capacity2(values: &[usize]) -> String {
    values.iter().fold(String::new(), |mut acc, cur| {
        write!(&mut acc, "{}", cur).unwrap();
        acc.push_str(" ");
        acc
    })
}

これでItertools::join()同様のパフォーマンスが得られるはず……と思いきや……なんとItertools::join()よりも2割ほど速い結果が得られました。理由は正直よく分かりませんが、Itertools::join()のソースコードをまんまコピペして貼り付けてもItertools::join()よりも速い結果が得られたので、なにか最適化のされ方に違いが出ているのかもしれません（未確認）。

おまけ: そのまま出力する場合は？

ここまでは、文字列に変換する場合の話でしたが、そのまま標準出力/標準エラー出力/ファイルなどに出力する場合はどうでしょうか。

この場合、Stringを経由せずとも、以下のような方法が考えられます。

• print!("{} ", x) を繰り返す
  • 一番シンプルな実装です
• Itertools::format() を使う
  • Itertools::format()は、まさに「Stringを経由せずにそのまま出力する」というのをそのままやってくれるイメージに近いです
  • 詳細はドキュメントとソースコードをご確認ください。

イメージだと、Stringを経由しないほうが、なんとなく速そうな気もしてきます。

また、標準出力や標準エラー出力に出力する際には、ロックを事前に取得しておいたりBufWriterを併用することで高速化できるという話があります:

今回の場合、方法によって print!() を呼びだす回数が大きく異なるため、特にこれらと併用するかどうかによっても結果が変わってきそうです。

ということでこのあたりについても実験してみました。ソースコードは記事末尾のリンクをご確認ください。

プログラムからは標準エラー出力に出力することにして、リダイレクト先だけ変えて2パターン試しました。

パターン1: プログラムから標準エラー出力に出力して、シェル上で /dev/null にリダイレクト

#	手法	実行時間(ns)	測定誤差(ns)
A	Itertools::join()	1,195,036	+/- 48,551
B	print!()を繰り返す	13,602,785	+/- 765,611
C	Itertools::format()	11,973,362	+/- 872,450
D	Itertools::join()+ロックの事前取得+BufWriter	1,107,630	+/- 66,886
E	print!()を繰り返す+ロックの事前取得+BufWriter	1,348,952	+/- 44,944
F	Itertools::format()+ロックの事前取得+BufWriter	1,196,803	+/- 89,881

パターン2: プログラムから標準エラー出力に出力して、シェル上でファイルにリダイレクト

10^5個だとなかなか終わらなかったので、要素数を10^3個に減らしています。

#	手法	実行時間(ns)	測定誤差(ns)
A	Itertools::join()	38,436	+/- 15,055
B	print!()を繰り返す	2,086,873	+/- 176,147
C	Itertools::format()	2,460,641	+/- 188,707
D	Itertools::join()+ロックの事前取得+BufWriter	48,238	+/- 17,144
E	print!()を繰り返す+ロックの事前取得+BufWriter	51,036	+/- 18,943
F	Itertools::format()+ロックの事前取得+BufWriter	51,596	+/- 1,956

いずれのパターンでも、Itertools::join()を使う方法が最速でした（BufWriterと組みわせたほうがよいかには違いがありますが）。
また、Itertools::join()を使う場合、BufWriterの使用有無による違いが他の方法よりもずっと小さいことも特徴です（一回しかwriteln!()を呼ばないからでしょうか）。

いずれにしろ、Stringを経由しないほうが速そうというイメージは外れて、標準（エラー）出力へのprint!()やwrite!()の呼び出し回数を減らすほうが効いてきそうということのようです。

まとめ

結局のところ、文字列化するにしろそのまま出力するにしろ、Itertools::join()を使うのが大体速いということが分かりました（考察のところに書いた通り、joinの中身のソースコードそのままコピペしたほうが（最適化が効いて？）速いという事象もありましたが）。

一番簡潔な記法が（ほぼ）一番速いというのは、なかなか嬉しいです。

今回使ったソースコード

今回使ったソースコードは以下に置いてあります:

ベンチマークのソースコードは benches 配下にあります。 cargo bench でベンチを実行できます。
標準エラー出力版は feature/stderr ブランチにあります。