Ruby の JSON ライブラリ Oj のパフォーマンス改善を行いました

Development Division/Repro Team/Feature 1 Unit の Watsonです。Feature 1 Unit は Repro Tool の機能開発と保守を担っています。

弊社でも利用している Oj gem のパフォーマンス改善 PR を送った話と、その PR の内容について共有します。

ことのはじまり

以前、同僚が Ruby on Rails で JSON を返す REST API を作成した際、JSON のエンコード部分のパフォーマンス計測をしていました。JSON のエンコード方法は JSON.generate、ActiveSupport::JSON.encode、Oj gem を利用する方法など色々ありますが、私としては Oj gemのほうがパフォーマンス的にいいだろうからそちらを利用したほうが良いのではと思っておりました。

計測結果を拝見したら確かに json gem のほうが多少良い成績でした。当時の計測結果は以下の通りです。

Warming up --------------------------------------
ActiveSupport::JSON.encode
                         4.914k i/100ms
    Oj.dump (compat)    14.392k i/100ms
     Oj.dump (rails)     2.423k i/100ms
             to_json     4.650k i/100ms
  JSON.fast_generate    17.158k i/100ms
       JSON.generate    17.777k i/100ms
Calculating -------------------------------------
ActiveSupport::JSON.encode
                         49.934k (±12.6%) i/s -    245.700k in   5.000618s
    Oj.dump (compat)    144.938k (± 9.5%) i/s -    719.600k in   5.007513s
     Oj.dump (rails)     24.735k (± 6.7%) i/s -    123.573k in   5.019159s
             to_json     49.970k (±12.1%) i/s -    246.450k in   5.007978s
  JSON.fast_generate    166.513k (±20.0%) i/s -    772.110k in   5.082852s
       JSON.generate    167.300k (±19.6%) i/s -    799.965k in   5.238994s

Comparison:
       JSON.generate:   167300.4 i/s
  JSON.fast_generate:   166512.7 i/s - same-ish: difference falls within error
    Oj.dump (compat):   144938.2 i/s - same-ish: difference falls within error
             to_json:    49969.8 i/s - 3.35x  (± 0.00) slower
ActiveSupport::JSON.encode:    49934.0 i/s - 3.35x  (± 0.00) slower
     Oj.dump (rails):    24734.7 i/s - 6.76x  (± 0.00) slower

この結果をもとに当時採用したのは一番パフォーマンスのよかった JSON.generate でした。私が https://github.com/flori/json/pull/346 で速度改善したときには、まだ Oj のほうが速かったのでこの結果には割と衝撃を受けました。弊社では他でも Oj を使用しているところが多々あるためどうにかしたいなと思ったのが事の発端でした。

変更内容

Improve `Oj.dump` performance

もともと自前で 1 バイトずつコピーする処理となっていました。パフォーマンスを計測すると下図の for 文のところ自体が遅いようです。長い文字列が JSON 中にあるとこの for 文が大量に実行されます。

ldrb で str が示すアドレスから 1 バイト読み取っているところが遅く、メモリアクセスに時間が取られているようです。

C 言語の標準ライブラリに文字列をコピーする関数があるのでそちらを使用すれば for 文自体は消せそうです。また自前で実装するより標準ライブラリのほうが数バイト単位で処理されている等の最適化されている可能性が大いにあるため、そのような方針で改善を提案しました。

for (; '\0' != *str; str++) {
  *out->cur++ = *str;
}

の箇所だけ書き換えたかったのですが文字列長の計算を誤っているところがいくつかあり、あわせて直しているためぱっと見で変更が分かりにくいですね...。

使用したベンチマークコードでは、Oj.dump のパフォーマンスが 2.69 倍に改善されました。

Improve performance of `Oj.dump` with compat/rails mode

Oj.dump や Oj.load は様々なオプションが用意されていて、オプションは Hash として指定できます。指定されたオプションを parse する際に rb_funcall() という C 言語で Ruby のメソッドを実行する API を利用していたのですが、rb_funcall() は Ruby の VM を通り様々なチェックが入るためある程度遅い API となってます。

rb_funcall() 経由でHash#has_key? を呼び出していたのを、Ruby の C 言語ライブラリ向けの API を駆使して同等の仕組みを用意しました。

使用したベンチマークコードでは、Oj.dump(data, mode: :compat) のパフォーマンスが 1.4 倍に改善されました。

Improve `Oj.load` performance

Ruby の実装詳細を見ないと分からないのですが、Hash に値を格納する際に文字列をキーとしていると、キー文字列が freeze されてなければ複製しfreeze し利用するような内部実装になっています。

static int
hash_aset_str(st_data_t *key, st_data_t *val, struct update_arg *arg, int existing)
{
    if (!existing && !RB_OBJ_FROZEN(*key)) {
        *key = rb_hash_key_str(*key);
    }
    return hash_aset(key, val, arg, existing);
}

文字列が freeze されてなければ rb_hash_key_str() が呼び出されて、freeze した文字列を複製しキーとして利用してます。Oj でキー文字列を生成した直後に Ruby 内部でも同じ文字列を作成し直すのが無駄なため、Oj 内で事前に freeze しておくようにしてます。

使用したベンチマークコードでは、Oj.load のパフォーマンスが 1.26 倍に改善されました。

Improve performance of `Oj.load` with symbol_keys mode

Oj.load で symbol_keys オプションを有効にすると、返り値の Hash のキーが Symbol になります。この Symbol を作成するために rb_str_new() で文字列を生成し rb_str_intern() で Symbol に変換していました。rb_intern3() と ID2SYM() を組み合わせのほうが速かったので変更しました。

使用したベンチマークコードでは、Oj.load のパフォーマンスが 1.14 倍に改善されました。

Optimize parsing option args

Oj.dump や Oj.load は様々なオプションが用意されています。Hash#has_key? を使いながら、このオプションは使われているかチェックするという行為を全てのオプションに対して行ってました。Improve performance of Oj.dump with compat/rails mode で Ruby の C 言語ライブラリ向けの API を用いましたが、まだパフォーマンスの改善の余地がありました。

Hash#has_key? は Hash オブジェクト内のハッシュテーブルを走査してキーの有無をチェックし、これをオプション数分だけ行っていました。計算量としては O(n^2) となります。

この Pull Request では rb_hash_foreach() を用いて、ハッシュテーブルを走査しながらどのオプションが存在しているかチェックするように変更しました。この変更により計算量は O(n) に減ります。

使用したベンチマークコードでは、Oj.load のパフォーマンスが 1.1 倍、Oj.dump では 1.14 倍に改善されました。

Use `rb_sym2str()` to retrieve String object

rb_sym_to_s() で Symbol を文字列に変換していますが、内部でオブジェクトの複製処理が行われるためにパフォーマンスが良くありませんでした。rb_sym_to_s() を rb_sym2str() に置き換えて、無駄なオブジェクト生成を省いてます。

使用したベンチマークコードでは、Oj.dump のパフォーマンスがおおむね 1.4 倍に改善されました。

Use snprintf() of standard C library

Ruby 本体で snprintf() 関数が独自実装されているのですが、Oj で C 標準ライブラリの snprintf() を使っているつもりだったのに Ruby 独自実装の関数を利用しており、それが思いのほかパフォーマンスがよくありませんでした（Ruby 側で外部に見せないなど、どうにかならないもんでしょうか...）。

C 標準ライブラリの snprintf() を利用するように変更してます。

使用したベンチマークコードでは、Oj.dump のパフォーマンスがおおむね 1.3 倍に改善されました。

Use memcpy() of standard C library

snprintf() 同様に Ruby の独自実装をいつの間にか使用していてオーバーヘッドが発生していました。Ruby 側で外部に見せないなど、どうにかならないもんでしょうか…）

C 標準ライブラリの memcpy() を利用するように変更してます。

使用したベンチマークコードでは、Linux 上で実行したときに有意な差があるようでした。

Use SSE 4.2 due to scan string in read_str()

JSON を読み込む際に、フィールドの値が文字列の場合には " のペアとなるところがどこかをパースする必要があります。

Oj.load でJSON を読み込む際に " がどこかを 1 バイトずつパースしていたのを、SSE 4.2 命令を使用して 16 バイト毎まとめて行うようにしました。JSON 中に長い文字列が存在しているケースでは読み込みが速くなります。

128 バイトの文字列の場合には、1.2 倍程度にパフォーマンスが改善するようです。

この機能を有効にする際にはインストール時に --with-sse42 オプションを指定してください。

https://github.com/ohler55/oj/blob/develop/pages/InstallOptions.md

当初はデフォルトで有効にしたかったのですが、SSE 4.2 が搭載された CPU が登場したのが 2008 年でそれ以前の CPU を使用しているユーザーもまだまだ居るようでデフォルト有効は断念しました。

https://ja.wikipedia.org/wiki/ストリーミングSIMD拡張命令

まとめ

私が Oj に対していくつか行ってきたパフォーマンス改善の一部をご紹介しました。

私が Pull Request で示したベンチマークコードは実際のアプリケーションではあり得ないようなものばかりなので、いろいろベンチマークをとって検証していただけると幸いです。

Oj で使われているベンチマーク用の JSON データを利用して、私がコントリビュータとして参加する前のバージョンと計測比較すると以下のような結果となりました。

require 'bundler/inline'
gemfile do
  source 'https://rubygems.org'
  gem 'benchmark-ips'
  gem 'oj'
  gem 'json'
end

puts "** Oj version #{Oj::VERSION} **"

json = <<-JSON
{"a":"Alpha","b":true,"c":12345,"d":[true,[false,[-123456789,null],3.9676,
["Something else.",false],null]],"e":{"zero":null,"one":1,"two":2,"three":
[3],"four":[0,1,2,3,4]},"f":null,"g":{"json_class":"One::Two::Three::Empty"},
"h":{"a":{"b":{"c":{"d":{"e":{"f":{"g":null}}}}}}},"i":[[[[[[[null]]]]]]]}
JSON

data = JSON.parse(json)

Benchmark.ips do |x|
  x.time = 15
  x.report('Oj.dump')          { Oj.dump(data) }
  x.report('Oj.dump [compat]') { Oj.dump(data, mode: :compat) }
  x.report('Oj.dump [rails]')  { Oj.dump(data, mode: :rails) }
  x.report('JSON.generate')    { JSON.generate(data) }
end

** Oj version 3.12.0 **
Warming up --------------------------------------
             Oj.dump    82.385k i/100ms
    Oj.dump [compat]    46.825k i/100ms
     Oj.dump [rails]    39.500k i/100ms
       JSON.generate    46.167k i/100ms
Calculating -------------------------------------
             Oj.dump    803.805k (± 4.4%) i/s -     12.111M in  15.098053s
    Oj.dump [compat]    475.288k (± 2.5%) i/s -      7.164M in  15.083240s
     Oj.dump [rails]    399.021k (± 1.6%) i/s -      6.004M in  15.050832s
       JSON.generate    524.814k (± 1.5%) i/s -      7.895M in  15.045897s

** Oj version 3.16.1 **
Warming up --------------------------------------
             Oj.dump   100.777k i/100ms
    Oj.dump [compat]    80.836k i/100ms
     Oj.dump [rails]    63.639k i/100ms
       JSON.generate    52.857k i/100ms
Calculating -------------------------------------
             Oj.dump      1.021M (± 1.6%) i/s -     15.318M in  15.013966s
    Oj.dump [compat]    799.301k (± 0.9%) i/s -     12.045M in  15.070040s
     Oj.dump [rails]    631.748k (± 2.2%) i/s -      9.482M in  15.016747s
       JSON.generate    520.715k (± 1.6%) i/s -      7.823M in  15.027047s

環境
- OS: Manjaro Linux x86_64
- Kernel: 6.6.2-1-MANJARO
- CPU: AMD Ryzen 9 7940HS
- Compiler: gcc 13.2.1
- Ruby: ruby 3.2.2 (2023-03-30 revision e51014f9c0) [x86_64-linux]

JSON.generate より Oj.dump のパフォーマンスが上回り、かなりの Pull Request を送ったかいがありました。弊社でよく使用している Oj.dump(data, mode: :compat) のモードでだいぶ改善できたので満足度が高いです。

One more thing ~ さらなる高速化にむけて

Ruby の Float オブジェクトを文字列に変換する処理が遅いことを把握してます。

Ruby では歴史的で今となっては古い dtoa 実装を利用してます。

https://github.com/ruby/ruby/blob/master/missing/dtoa.c

JavaScript 内部で float を多用するためか、近年この変換処理を高速に行うアルゴリズムが出てきてます。

このアルゴリズムを Ruby で使うと、Float を文字列に変換するパフォーマンスが 4 倍ほどに向上しそうなことまで把握してます。

$ ruby -v benchmark.rb
ruby 3.2.2 (2023-03-30 revision e51014f9c0) [x86_64-linux]
Warming up --------------------------------------
          Float#to_s   247.825k i/100ms
     FastFloatString     1.052M i/100ms
Calculating -------------------------------------
          Float#to_s      2.549M (± 0.7%) i/s -     12.887M in   5.056726s
     FastFloatString     10.472M (± 0.7%) i/s -     52.611M in   5.024229s

Comparison:
     FastFloatString: 10472007.8 i/s
          Float#to_s:  2548594.9 i/s - 4.11x  slower

https://github.com/Watson1978/fast_float_string

Oj.dump で Float を文字列に出力するケースが世の中にどれくらいあるだろうか、できれば Ruby の Float#to_s に対してこのアルゴリズムを適用したいなどと思いを巡らせて... 作業がとまってます。