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

本記事は、YUMEMI Flutter Advent Calendar 2023 6日目の記事です

概要

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

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

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

StringBufferってなんぞや?

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

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

文字列を効率的に結合するためのクラス

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

Docsの例を見てみる

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がどのように使われているかを見て、逆説的にユースケースを考えてみましょう。

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

List().join()

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

Map<K, V>.toString()

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

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

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

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

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

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

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

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

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

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

Dartコード

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

ループ内の検証は、こんな感じです。
type == BenchmarkType.stringの場合、 String bufferに対し、buffer += "a";を行い、
type == BenchmarkType.stringBufferの場合、StringBuffer bufferに対し、buffer.write("a")を行います。

Python3 スクリプト

Dartで出力したCSVを読み取り可視化を行います。

事前準備

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

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

試してみる

特に記載がない限り、 MacBook Pro (2021, M1 Pro, 32GB) で行っているものとします。
いろんな常駐アプリが動いていますが 検証間では負荷に変動がないものとして無視します。

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

引数の説明

• -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回まで

# テスト
./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  

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

0~100回まで

細かい部分を見ていきましょう

./out -m 100 -s 100 -r 100000  # 繰り返し回数を増やして StopWatch, ノイズの影響を小さく

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

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

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

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

だいぶ差が出てきました。
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 ブランチにソースコードを置いておきました)

./out -m (math pow 2,17) -s 10 -r 2   

(-s 100 -r 10 で試してみたのですが、進捗が悪くなかなか時間がかかりそうです。
僕がロボットになってしまいそうだったので、-s 10 -r 2でやりました。

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