読者です 読者をやめる 読者になる 読者になる

scala-zero-formatterのパフォーマンス改善と疑似Stage2対応

Scala

とりあえず動くものを~ということで0.1.0でリリースしていたのですが、ベンチマークをとったらさすがにJSON系ライブラリよりは速いものの、他のバイナリシリアライザに倍以上差をつけられる結果に「さすがに遅すぎる」と改善することにしました。

この記事を書いた時点では0.3.0が最新版です。

改善内容

  • foldLeft,、forearchからtailrec、while loopに
    • 初期は動くこと優先で高階関数を使っていた
    • が、 http://d.hatena.ne.jp/xuwei/20130709/1373330529 にもあるとおりtailrecやwhileのほうが早いので差し替え
    • 抽象化をそもそも想定していないのでとれる選択(読みづらいけど)
    • ちなみにこれだけでそこそこ速度が改善する
  • mutableなコレクションやnewBuilderの利用
    • var x = Hoge.emptyで変更するよりmutableコレクションから変換したほうが早い(そりゃそうだ)
  • Encoder, Decoderクラスを追加
    • mutableな設計に倒した
    • 余計な処理が少し減る
  • 一部のHListを自前のマクロに置き換え
    • foldLeftは遅い
  • fixed sizeなコレクションは個別にFormatterインスタンスを用意
    • 汎用的なやつだと毎回Array[Byte]のサイズチェックやコピーが挟まるので遅い
    • ので、サイズがわかっているものは最初に一括でリサイズして、配列のサイズチェックなしに書き込む

UnionやEnumには手を入れていないのであれらはまだ遅いままかも。

改善後のベンチマーク

以下てきとーベンチマーク。 てきとーなのであんまりフェアじゃないかも(とくにJSON系)。

https://github.com/pocketberserker/scala-zero-formatter-benchmarks/tree/a82d1ac5b72ac25599f9984bb0dfba5a48dea84d

sbt "jmh:run -i 10 -wi 10 -f 2 -t 1 benchmarks.EncodingBenchmark"

Benchmark                        Mode  Cnt        Score        Error  Units
EncodingBenchmark.encodeBarZ    thrpt   20  1324256.775 ± 82009.746  ops/s
EncodingBenchmark.encodeFooMZ   thrpt   20   518515.724 ±  8547.872  ops/s
EncodingBenchmark.encodeFooPB   thrpt   20  1650635.690 ± 24153.038  ops/s
EncodingBenchmark.encodeFooZ    thrpt   20  1402245.092 ± 69284.956  ops/s
EncodingBenchmark.encodeFoosA   thrpt   20     1356.404 ±    80.054  ops/s
EncodingBenchmark.encodeFoosC   thrpt   20     2157.034 ±   219.598  ops/s
EncodingBenchmark.encodeFoosMZ  thrpt   20    11213.833 ±  1080.450  ops/s
EncodingBenchmark.encodeFoosZ   thrpt   20    15255.728 ±  1111.828  ops/s
EncodingBenchmark.encodeIntsA   thrpt   20    10119.779 ±   894.966  ops/s
EncodingBenchmark.encodeIntsC   thrpt   20    14285.633 ±  1583.352  ops/s
EncodingBenchmark.encodeIntsMZ  thrpt   20    83462.462 ±  1648.580  ops/s
EncodingBenchmark.encodeIntsPB  thrpt   20   151786.501 ±  2536.334  ops/s
EncodingBenchmark.encodeIntsZ   thrpt   20   219506.973 ±  6170.565  ops/s

sbt "jmh:run -i 10 -wi 10 -f 2 -t 1 benchmarks.DecodingBenchmark"

Benchmark                        Mode  Cnt        Score        Error  Units
DecodingBenchmark.decodeBarZ    thrpt   20  7898101.929 ± 854734.733  ops/s
DecodingBenchmark.decodeFooMZ   thrpt   20   769205.462 ±  60756.223  ops/s
DecodingBenchmark.decodeFooPB   thrpt   20  1178288.024 ±  36754.823  ops/s
DecodingBenchmark.decodeFooZ    thrpt   20  1377253.293 ± 234093.569  ops/s
DecodingBenchmark.decodeFoosA   thrpt   20      796.463 ±    111.745  ops/s
DecodingBenchmark.decodeFoosC   thrpt   20     1607.345 ±     79.042  ops/s
DecodingBenchmark.decodeFoosMZ  thrpt   20    10599.926 ±   1889.855  ops/s
DecodingBenchmark.decodeFoosZ   thrpt   20    17261.595 ±    260.918  ops/s
DecodingBenchmark.decodeIntsA   thrpt   20     6230.473 ±    659.867  ops/s
DecodingBenchmark.decodeIntsC   thrpt   20    12751.050 ±    921.923  ops/s
DecodingBenchmark.decodeIntsMZ  thrpt   20    59862.336 ±   1785.270  ops/s
DecodingBenchmark.decodeIntsPB  thrpt   20   125009.494 ±   9799.178  ops/s
DecodingBenchmark.decodeIntsZ   thrpt   20    85695.355 ±  27599.620  ops/s

Fooが単発のcase classでFoosMap[String, Foo]intsVector[Int]です。 BarはZeroFormatter+フィールドをcats.Evalにしたものです(後述)。 AがArgonaut, Cがcirce、PBがScalaPB、MZがmsgapck4z、Zがscala-zero-formatterになります。

注意事項としては、元ネタのcirce-benchmarkはListだったのですが、ScalaPBのdecode用メソッド(mergeFromで調べよう)がVectorを使って生成してSeqをフィールドに持つようになっているので他のやつも合わせました。 あと、jmhの仕組み的にネストしたクラスが扱えないらしくScalaPBのベンチマークがとれていません。

ScalaPBは速いなぁ、というのがまず最初の感想ですね。 この中で唯一ジェネレータ系かつ生成されるコードがこれまた無駄がないので簡単なcase classであれば他を圧倒します。 sbtプラグインのおかげで10行程度(?)でプロジェクトの設定ができるし、gRPC対応してるしで、Scalaでの開発に限って言えばまず有力な候補に上がるの間違いなしです。

scala-zero-formatterはScalaPBと良い勝負をしているものの、バイナリサイズやIDLの利便性を考えるとどうなのでしょうねぇ。 後述のStage2あたりが差別化要因という話はありますが、さてはて。

msgpack4zはByteArrayOutputStreamを経由しているのがネックなのかな……あるいはベンチマークに使ったコードが微妙なのかも? これに関してはもう少し調査してみるつもりです。 でないとフェアじゃないので……。

JSON系が遅いのはしょうがない。 目的が異なる(?)ので、そもそもバイナリシリアライザと比較するものじゃない気がする。 ではなぜ比較したかといえば、circe-benchmarkをforkしたからなのでした。

ちなみにscodec-msgpackを比較対象にいれていないのは、そもそもスタックオーバーフローが解決できなかったという致命的な問題のせいです……なんとかしないと。

ScalaPBが早い理由

推測も混ざっているのでご注意ください。

  1. シリアライズの最初にバイナリサイズを計算
  2. サイズがわかっているので余計な操作が入らない
  3. scala-zero-foratterは「足りなくなったら増やす」戦略をとっているため随所でサイズチェックとArray[Byte]のコピーが発生する
  4. デフォルト値のときは何もしない
  5. 今回のベンチマークではそんなに関係ないけど一応
  6. ジェネレート時のインライン展開
  7. 生成されたコードのwriteTomergeFromに各フィールドのシリアライズ、デシリアライズ処理が手続き的に並んでいる
  8. 余計な呼び出しがないならそれだけ遅くならないということ
  9. このあたりでいくらか差が出る場合もある
  10. sun.misc.Unsafe?
    • 早いらしいという噂の彼
    • ScalaPBというよりは、JVM向けScalaPBランタイムが依存しているprotobuf-javaエンコードで使っている
    • とはいえ全体的な結果からするとあまり速さとは関係ない?(気のせい?)

scala-zero-formatterのStage2エミュレーション

ZeroFormatterの仕様には幾つかのStageがあります。 Stage2はObject、FixedSizeList、VariableSizeListのフィールドや要素のデシリアライズを遅延する仕様になっています。

で、これをScalaでどう実現するかですが……今回はとりあえずcats.Evalを使うことにしました。 ユーザが自前で定義する系なのでObjectや遅延リスト以外に適用して事故を起こす可能性もある……とはいえ、がんばらずにStage2の挙動を手に入れられるのでこれでいいかなーと。 equalsとかがまともに使えなくなる問題もありますが、比較したい時点で全部正格評価すべきだと思います。

バイナリのキャッシュ

C#のZeroFormatterにはバイナリをキャッシュして書き換えた部分以外はdeep copyする機構があって、これでシリアライズも省電力化することができます。 ZeroFormatterの仕様に存在しない仕組みとはいえ、こういう機能もできればscala-zero-formatterに欲しい……ということで、まずは単純にキャッシュするだけのAccessorというものを用意してみました。 case classの値が書き変わらないのであれば内部で溜め込んでいたバイナリをそのままシリアライズの結果として返します。 完全に横流し専用ですね。

そのうち部分更新の機能もサポートしたいのですが、ネストしたフィールドのcase classの変更をどうやって最上位のcase classにまで伝播させれば良いのかで詰まっていて当分先になりそうです……。 Lensを参考にしようと思っていましたがなかなかうまくいかないものですね。

まとめ

バイナリシリアライザのパフォーマンスチューニングは無限大に時間を消費するなーと。

とはいえ、もう少し何かできそうではあるので他言語版ともとも頑張ると思います。