mrubyの文字列結合のパフォーマンスを改善する

先日、来る下記のイベントの資料でmrubyの文字列結合におけるメモリパフォーマンスについて記述し、それを社内で共有したところ、それをみた @matsumotory がmrubyにおける文字列結合は + での結合より、破壊的ではあるが <<のほうがパフォーマンスが良いということに気づいた。

valgrindで測定すると下記のような具合である。

# new.rb
a = "aaa"
b = "bbb"
100000.times do |n|
  a += b
end
$ sudo valgrind ./mruby new.rb
...
==2374== HEAP SUMMARY:
==2374==     in use at exit: 0 bytes in 0 blocks
==2374==   total heap usage: 102,786 allocs, 102,786 frees, 15,002,227,528 bytes allocated
# concat.rb
a = "aaa"
b = "bbb"
100000.times do |n|
  a << b
end
$ sudo valgrind ./mruby concat.rb
==2380== HEAP SUMMARY:
==2380==     in use at exit: 0 bytes in 0 blocks
==2380==   total heap usage: 2,780 allocs, 2,780 frees, 1,152,039 bytes allocated

メモリのアロケーションだけで比較すると13000倍くらいの差があることがわかります。これはなぜこのような挙動になるかというと、 + の実装であるmrb_str_plus<< の実装であるmrb_str_catの違いにある。mrb_str_plusは c = "a" + "b" の場合、まず c のメモリをmrubyの 文字列2文字分確保してから、 "a""b" をその領域にコピーする。対してmrb_str_catは "a" << "b"の場合、"a"のメモリ領域を mrb_realloc を利用して拡張し、そこに "b"をコピーするような挙動をする。

ようするに前者における c の領域分のメモリ確保の差が先のvagrindで13000倍程度あることになる。この挙動についてはCRubyにおいても同じなので、破壊的な変更が許容出来るのであれば積極的に << を活用したほうがパフォーマンスは上がるだろうと思う。

厳密にはGCが走った時点でcの領域は開放されるので、実使用メモリとは乖離があるが、アロケーションされるという事実は変わらない。

さて、本題なのだが、先の @matsumotory とのディスカッションの中で、mrb_str_catがreallocするのであれば、予めそのサイズがわかっていれば文字列のサイズを予め設定することで、realloc処理すらなくして、爆速に出来るのでは?という話になった。

mrubyにおいては、文字列や配列の長さとは別に capa というmrb_int型の変数でメモリ容量が管理されている。ここの必要数が予めわかっているのであれば設定しておけば良いので、capaのsetter,getterを開発した。

具体的な用途に関しては例えばHTTPレスポンスのように予めヘッダーでレスポンスボディのサイズがわかっているような場合に、capaをそのサイズで設定しておくことで、realloc処理を無くすことが出来る。

まずは必要なcapacityを調べる。処理速度で比較したいので、先程よりループ数を100倍程度にします。

a = "aaa"
b = "bbb"
10000000.times do |n| 
    a << b
end
puts a.capacity
# => 48234496

次に速度を計測します。

# time mruby/bin/mruby sample.rb
real    0m1.396s
user    0m1.376s
sys     0m0.012s

さて、この値をベースに、このようにcapacityを設定したコードで計測。

c = 48234496
a = "aaa"
b = "bbb"
a.capacity = c

10000000.times do |n|
  a << b
end
puts a.capacity
# time mruby/bin/mruby sample.rb
real    0m1.365s
user    0m1.324s
sys     0m0.028s

「あれっ・・・早くなってない・・・」(0.03秒)

本来ならここで爆速バンザーーーイとなって意気揚々とまとめでも書くのですが、なぜでしょう。

ltraceを利用してreallocの数を比較したところ、さほど差がないことがわかりました。

# capacity設定なし
$ ltrace -e realloc mruby/bin/mruby sample.rb 2>&1 |  wc -l
2787

# capacity設定あり
$ ltrace -e realloc mruby/bin/mruby sample.rb 2>&1 |  wc -l
2767

これは何故かと言うと、mrb_str_catがreallocする時に、 MRB_INT_MAX / 2 を超えない限りは、原則既存のcapaの2倍の値でreallocするから、そもそもあまりreallocが起きないことにあります。

ふむふむ良く出来てると思いましたが、もう少しサイズが大きい文字列を扱うときにはもっと効いてくると思うので、capacity設定使っていきましょう。