前書き

9月～10月に開催されたISUCON10¹で利用しようと思って、ちまちま作ってたJSONのエンコーダです。
ISUCONの練習をISUCON9の予選を使って10万点が出るまで行ったんですが、最後の方はJSONエンコードが処理時間を大きく占めていて、削りたいなと思っていたのと、作ってみると面白そうだなというのでつくってみました。

ちなみに予選ではそもそもJSONがボトルネックになるところまでたどり着かず、本選ではJSONではなくprotobufだったということで結局一度も使わなかったです。

制約付き

ところで制約付きっていうのをタイトルに入れてるんですが、ISUCONでしか使わないっていう想定の上で複数の前提を置いた上でつくったためです。
具体的には

保守性は問わない
生成されたコードが読める
一部の仕様にしか対応しない
実際は例外がありうる場合でも発生しないという仮定をできるようにする
コード生成前にコードを多少書き換える必要がある²

などです。
ISUCONの予選が9/12、本選が10/3だったのに9/6につくり始めたのでジェネレータのコードの保守性とか使いやすさとかコーナーケースとかを結構削いでいます…。

ベンチマーク結果

下のほうがデータサイズが大きいです。
ベンチマーク内容

ConstantiateとConstantiateNonOptimizedについて

これらの違いは

実際は例外がありうる場合でも発生しないという仮定をできるようにする

この仮定を利用しているかどうかで、Constantiateでは例えばUUIDしか入らないとわかっているフィールドでは文字列のエスケープ処理をせずそのまま文字列コピーするようにしているのに対して、ConstantiateNonOptimizedではエスケープ処理がされています。

このような処理のスキップのオプションを以下の5つ用意しています。

noescape: エスケープをしない
omitnano: time.Timeのナノ秒を出力しない
small: 0～999であると仮定する
unsigned: 正の数しかとらないと仮定する
nonnil: ポインタ型でnilをとらないと仮定する

実際のプロダクトとかでは使えませんが、ISUCONなら仕様が変わらないので強い仮定を置くことができるので、このようなオプションを実装しました。

仕組み

生成されたコードを見るとほとんどわかるんですが、書き込む[]byteを使いまわしてメモリ確保を減らして、appendだけで文字列を構築することで命令数を減らすというのが大きな方針です。

このジェネレータは大きく三つの部分、1.コード生成部分、2.コード最適化部分、3.ライブラリ部分からできています。

コード生成部分

ソースコードのASTを読み込んで構造体やコメントの情報を取り出して、文字列でソースコードを生成しています。

コード最適化部分

コード生成をした後に一旦ASTで読み出して最適化をかけてます。
この最適化は複数のappendが並んでいるときに一つのappendにまとめるような処理をしています。

res = append(res, '{')
res = append(res, `"`...)
// 上が下に変換されます
res = append(res, `{"`...)

ライブラリ部分

生成されるコードで共通の関数が実装されてます。
文字列をエスケープしてappendする関数などがあります。

stringで扱うとコピーが多く走ってしまうので[]byteで基本扱う(golangでは文字列がimmutableのため)
条件分岐よりもmapのアクセス、さらにそれよりもsliceのアクセスのほうが速い

あたりの細かい処理の調整とかをしています。

終わりに

ちまちまと書いていたらもう12月になっていました…。
ベンチマーク結果だけ見るとよさそうな感じになってはいるんですが、実際に効果が出るかどうかわからないのと、おそらくgo routineの数が増えると十分に性能を発揮できない³ので、改善点はまだまだたくさんあるといった感じですね。
次回ISUCONに出るときにもしかしたらいくつか改善して使ってみるかもしれません。

http://isucon.net/archives/54704557.html 、チーム「がんもどき」で本選に出場して総合3位を取りました ↩
sliceやmapはそのままでは正常に動かず、type UserMap map[string]Userのように型をつくる必要があります ↩
今のところmutexを効率よく使う実装にしていないため。 ↩

Go制約付き高速JSONエンコーダージェネレータ

前書き