DartのStringBufferとStringのパフォーマンス計測

本記事は、**[YUMEMI Flutter Advent Calendar 2023](https://qiita.com/advent-calendar/2023/yumemi-flutter) 6日目の記事です**

## 概要
FlutterやDartの学習を始めて少しすると「多くの文字列に対する結合を行う時は`StringBuffer`を使え!」という話を聞くと思います。

**Stringの文字結合 と StringBuffer ちゃんと使い分けられていますか?**

今回は、`String` classで文字列結合をした場合と、`StringBuffer`を使い文字列結合をした時のパフォーマンスの差を見ていこうと思います。


## StringBufferってなんぞや?

`StringBuffer`は、Dart SDKの中の組み込み型などが実装されている`dart:core`ライブラリの中にあるクラスです。`dart:core`ライブラリは自動でインポートされるため、明示的にインポートを書く必要はありません。

https://api.dart.dev/stable/3.1.3/dart-core/StringBuffer-class.html

API Docsを見てみると、`StringBuffer class`についての説明があります。

> **文字列を効率的に結合するためのクラス**
> 
> `write*()`関数を使い文字列の増分構築をできるようにします。`toString()`が呼ばれた時にのみ、文字列が1つに結合されます

### Docsの例を見てみる

```dart
final buffer = StringBuffer('DART');
print(buffer.length); // 4

buffer.write(' is open source');
print(buffer.length); // 19
print(buffer); // DART is open source

const int dartYear = 2011;
buffer
  ..write(' since ') // Writes a string.
  ..write(dartYear); // Writes an int.
print(buffer); // DART is open source since 2011
print(buffer.length); // 30
```

このように、`StringBuffer`に対して `write`メソッドをコールすることで、文字列を追加することができます。

## 実際のユースケース

Dart, Flutter SDKの中を辿って、`StringBuffer`がどのように使われているかを見て、逆説的にユースケースを考えてみましょう。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/489005/725caa17-a3f1-c342-8f55-404f332043ef.png)

思ったより、色々なところで使われていそうです。

### `List().join()`

特に、配列長で単純結合とStringBufferを使う形の使い分けはしていなさそうです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/489005/59ad1c1a-3b1d-914e-7297-69ba79f9c309.png)

### `Map<K, V>.toString()` 
`{}.toString()`は、内部的に`MapBase class`のstatic method `mapToString(Map<Object?, Object?> m)` を呼んでいたんですね。

すなわち、`{}.toString()`は`MapBase.mapToString({});`と同義ですね。(わざわざ後者を使うメリットは思いつきませんが...)

頭の中でこれを実行してみると、見慣れた出力になると思います。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/489005/bf8c7714-43ae-e5b2-e155-eced3e9c3b4c.png)

この他にも、base64, json, ascii, HttpException.toString() 等で利用されていました。

この例を見てもわかるように、List, Map, Set等の要素数の多い かつ、 要素数が事前に予測できない 場合に利用されている印象があります。


## じゃ、どのくらい速度差が出るんじゃ?

気になりますよね。 `StringBuffer class`をインスタンス化するのにかかるコスト と 単純に文字列結合するコストはどっちのほうが安価なのでしょうか?

:::note warn
筆者は数学や統計学に対する深い知見があるわけではないので、もしかしたら変な解釈をしているかもしれません。
予めご了承ください
:::


実際に検証してみましょう。

https://github.com/YumNumm/dart_string_buffer_benchmark.git

検証用のDartコード・可視化用のPythonスクリプトを用意しました。


#### Dartコード
コマンドライン引数から情報を読み取り、その情報をもとに ループを実行します。
実行後は、`benchmark.csv`へ結果を出力します。

ループ内の検証は、こんな感じです。
`type == BenchmarkType.string`の場合、 `String buffer`に対し、`buffer += "a";`を行い、
`type == BenchmarkType.stringBuffer`の場合、`StringBuffer buffer`に対し、`buffer.write("a")`を行います。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/489005/0f5160ac-cab3-64e7-af9b-67b9fbfcaf78.png)

#### Python3 スクリプト

Dartで出力したCSVを読み取り可視化を行います。
<!--
可視化の他に、 切片0の二次関数 $y = ax^2 + bx + 0$へ近似を行い、コンソールへ近似曲線の式・決定係数($R^2$)を出力します。
-->

### 事前準備

ソースをcloneして準備していきます

```bash
git clone https://github.com/YumNumm/dart_string_buffer_benchmark.git
cd dart_string_buffer_benchmark
############### Dart ###############
# download sdk (if using FVM)
fvm install

# AOT Compile Dart code
fvm dart compile exe ./bin/dart_string_buffer_benchmark.dart -o out

############### Python ###############
cd visualization
# Please install rye, Python package management tool
# ref: https://rye-up.com/
rye sync
```

### 試してみる

:::note info
特に記載がない限り、 MacBook Pro (2021, M1 Pro, 32GB) で行っているものとします。
いろんな常駐アプリが動いていますが 検証間では負荷に変動がないものとして無視します。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/489005/76e53575-b894-1e72-0373-76faca3d297f.png)
:::

事前準備でコンパイルしたバイナリを実行します。

#### 引数の説明

- `-m, --max`: 文字列結合の繰り返し回数
- `-s, --step`: 0 ~ {{ max }} までの分割数
- `-r, --repeat`: リピート回数

ちょっとわかりにくいですね

`-m 1000 -s 100 -r 10` にした場合、
0 ~ 1000までを100分割し、
```
0 (1000 / 100 * 0) 回の結合を 10 回行い平均算出, 
10 (1000 / 100 * 1) 回の結合を 10 回行い平均算出, 
20 (1000 / 100 * 2) 回の結合を 10 回行い平均算出, 
... 
1000(1000 / 100 * 100) 回の結合を 10 回行い平均算出
```

を行います。

では、実際に検証してみましょう。

#### `0~1000`回まで

```bash
# テスト
./out -m 1000 -s 100 -r 100

# 結果の移動
mv benchmark.csv visualization/

# 可視化
cd visualization![benchmark.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/489005/934a8fc4-17f3-13d3-a4fe-3e3454402e7f.png)

rye run python3 ./src/visualization/main.py  
```

![benchmark.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/489005/adbe950b-d9d9-b42b-f1bc-8765c408426c.png)


割とノイズが乗ってしまっていそうですが、そこは目をつぶって..
500ループの結合程度であれば、数十マイクロ秒程度の差しか出なさそうです。
ほぼ一次直線的な増加をしています。

#### `0~100`回まで
細かい部分を見ていきましょう

```bash
./out -m 100 -s 100 -r 100000  # 繰り返し回数を増やして StopWatch, ノイズの影響を小さく
```
![benchmark.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/489005/b074822b-10a3-9550-8edc-d9a9bdb69560.png)

0~1000回ループでも分かる通り、0~100回だと、数マイクロ秒の世界ですね。

ではもっと大きなループで検証してみましょう

#### `0 ~ 2^17 (= 0 ~ 131072)`回まで

```bash
./out -m $((2**17)) -s 100 -r 2 # 2^17 = 131072
```

![benchmark.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/489005/3d846c7d-4e12-494c-5303-20171ce4bd83.png)


だいぶ差が出てきました。
131,072回($2^{17}$回)になると、`BenchmarkType.string` すなわち 文字列の単純結合では、数百ミリ秒かかっています。グラフを見ても分かる通り、二次関数にほぼぴったりフィットする形で増加しています。
それに対し、`BenchmarkType.stringBuffer` すなわち、`StringBuffer.write()`では、ほぼ一定時間で終了しています。


## まとめ

- Dartで文字列結合を行う場合、$10^3 = 1,000$回程度であれば stringでもStringBufferでも十分無視できる範囲内である
  - 今回は検証で `a` のみの結合をテストしたため、実務で扱うような文字列の場合 また違う結果になる可能性があるので注意
  - 普段Flutterアプリを書いていて 扱う程度の配列長であれば、パフォーマンスより可読性を意識して使い分けたほうが良さそう
- 2の2桁乗オーダーになると、有意差出てくるので `StringBuffer`を使うべき


## 余談

まとめを書いた後に気になりました。

**string文字結合を もっと長い文字列で試したらどうなるのか....**

試すべし。

とりあえず、長い文字列ということで、`sha256(pubspec.yaml) = 783754a2904a9702470e9d0a850ce85cb89447b729fdc33428d27d58cbab3e5d` (256bit)を用意しました

ソースコードを書き変えて... (`feature/string-length-test` ブランチにソースコードを置いておきました)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/489005/af38a691-60fa-8386-38e4-bf4173b95fac.png)

```bash
./out -m (math pow 2,17) -s 10 -r 2   
```
(`-s 100 -r 10` で試してみたのですが、進捗が悪くなかなか時間がかかりそうです。
[僕がロボットになってしまいそうだったので](https://youtu.be/Q4gTV4r0zRs?si=pBZhLX0knyVetfPf)、`-s 10 -r 2`でやりました。


![benchmark.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/489005/782f0a92-4231-bc12-54ac-f5bdc2c99b1c.png)

ずいぶんと差が出ました。

<!--

文字列同士の結合では、毎回メモリ内の別のアドレスへ移していることを考えると、
1. loop回数が増えるごとに メモリI/O量が2次関数に沿って増加する -> 処理時間も2次関数的に増加する
2. 文字長が増えるごとに、メモリI/O量が1次関数に沿って増加する -> 処理時間も1次関数的に増加する

(メモリ転送量は、初項1, 公差[文字長], 項数[loop回数] の等差数列の総和になるので $\frac{n}{2}(2+(n-1)d) = \frac{1}{2}(1 + n^2d - nd)$ より、$n$: loop回数に対しては2次関数的増加、$d$: 文字長に対しては1次関数的増加だと考えました)

1. については、グラフから見てほぼ明らか
2. については、以下結果から裏付けられると思います。

|文字ビット数|loop回数|時間|
|---|---|---|
|8|131070|406.0835|
|256|131070|85796.1225|


$ 406.0835 \times \frac{256}{8} = 25989.344 $

$ 85,796 / 406 = 211.32 $



**ちゃうやん**
なにもわからん... ><



-->