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

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

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

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

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

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

## 背景

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

https://qiita.com/maguro_tuna/items/003a19f782884a694f8f

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

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

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

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

## 注意書き

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

## 試した方法一覧

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

[`[T]::join()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.join) を使います。

```rust
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()`を使ってみます。

```rust
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×文字数`にしました）

```rust
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!()` を使って文字列にしてみます。数値の場合はこちらのほうが自然かもしれません。

```rust
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指定あり版です。

```rust
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()`](https://docs.rs/itertools/latest/itertools/trait.Itertools.html#method.join) を使います:

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

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

なお、`Itertools`には関数版の[`join()`](https://docs.rs/itertools/latest/itertools/fn.join.html)もあります。違いは`Iterator`そのものではなく`IntoIterator`を渡せることです。それ以外の違いはなさそうなので今回は割愛します。

## 測定方法

参考元の記事同様に、[bencher](https://docs.rs/bencher/latest/bencher/) を使って計測しました。

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

```rust
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 |

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/80237/42050989-6583-188d-1ad3-b4376eb964fe.png)

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

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

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

### `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()`の[ソースコード](https://docs.rs/itertools/0.10.5/src/itertools/lib.rs.html#2059)を見てみると、

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

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

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

```rust
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()`](https://docs.rs/itertools/latest/itertools/trait.Itertools.html#method.format) を使う
    * `Itertools::format()`は、まさに「`String`を経由せずにそのまま出力する」というのをそのままやってくれるイメージに近いです
    * 詳細はドキュメントとソースコードをご確認ください。

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

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

https://keens.github.io/blog/2017/10/05/rustdekousokunahyoujunshutsuryoku/

今回の場合、方法によって `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の中身のソースコードそのままコピペしたほうが（最適化が効いて？）速いという事象もありましたが）。

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

## 今回使ったソースコード

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

https://github.com/hiratasa/rust-int-join-bench

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