K.Sasada's Home Page

Diary - 2015 October

研究日記

神無月

_6(Tue)

答え合わせ。

おっと、実時間だと、世代別 GC を、ちゃんと有効にしているやつと、あまり変わりませんね。

とありますが、system time が長いですよね。これ、システムからメモリを確保するために必要となる時間です、多分。800MB 以上ぶんどらないといけないですから。この場合、user 時間を比べて、GC の影響を見ておくのが良いでしょう。つまり、GC の影響は 1.64 sec - 1.47 = 0.17 sec。これが、GC による影響だとみることが出来ます。

まとめると、大ざっぱに

  • オブジェクトの生成 0.7 sec
  • GC 時間 0.2 sec

という感じです。潰すべきオーバヘッドはどちらか、というのは、わかりやすい。GC は本当に遅いんですかね。

あと、オブジェクトを 100M 個作っておいた、すぐあとのベンチマークでは、また違った様子ですね。これも、OS とのやりとりやら、GC とのやりとりを考えると、そこそこわかりやすい、かもしれません。


最近、考えるカラス、という番組を見て、凄いいいものだなぁ、などと思う。自分も、すぐに答えを見ちゃうんだけど。


中田さんが r52048 で文字列リテラルでの文字列生成を速くしてくれたおかげで、結果はこの通り。

ko1@frontier:~$ ruby -ve '
> require "benchmark"
> N = 20_000_000
> GC.start; GC.start # magic
> Benchmark.bm{|bm|
>   bm.report{N.times{str = "a"}}
>   bm.report{N.times{str = "a".freeze}}
>   bm.report{GC.disable; N.times{str = "a"}}
> }
> '
ruby 2.3.0dev (2015-10-06 trunk 52052) [x86_64-linux]
       user     system      total        real
   1.230000   0.000000   1.230000 (  1.228333)
   0.760000   0.000000   0.760000 (  0.763828)
   1.020000   0.190000   1.210000 (  1.200342)

1.6 sec -> 1.2 sec になったので、差は 0.4 sec。20ns / 1文字列。

まぁ、どんなに小さなオーバヘッドでも、あると気持ち悪い、ってのはわからないでも無いのですが。

_<img src=http://siliconangle.com/files/2011/08/matz.jpg>(Wed Oct 07 15:36:07 +0900 2015)

 <script>alert('Matz「XSS」')</script>

_5(Mon)

9月はポルトガルとかロシアとか行ってました。どちらも良いところでした。小学生並だな、これ。


文字列リテラルを freeze する、しない、の話で、色々と議論があります。遠藤さんの素晴らしいまとめ: ■ [Ruby] Ruby 3.0 の特大の非互換について

個人的には、松本さんが 3.0 で文字列リテラルを freeze するんだ! という堅い意思があり、それを目指すためならマジコメも移行パスとしてしょうがない、と思ってたんだけど、実は実験らしいので、そんなに硬い意思でもなかったらしい(まぁ、意固地に堅い意思でも困るのだが)。3.0 でそうならないなら、マジコメ嫌だなぁ。

この根本的な原因は Ruby が遅い、ということなので、多分私の職責の範囲内であると思われるので、この辺の「なぜ遅いのか」「どうすれば良いのか」という点についてまとめておきます。

■なぜ遅いのか

Ruby では、文字列リテラルは「文字列オブジェクト生成式」となります。なので、

2.times{p ''.object_id}

は、異なる object_id を表示します。これは、文字列が mutable であり、例えば 2.times{str = ''; str << 'foo'} みたいなことをした時、ちゃんと毎回 str が 'foo' になるようにするためです。

オブジェクト生成式ということは、オブジェクトを作ることになるので、

  • オブジェクトを生成するコスト
    • オブジェクト slot から1つ切り出すコスト
    • その slot を文字列にするために初期化するコスト
  • 十中八九、すぐ死ぬテンポラリオブジェク トになるので、GC 回数が増える、と言うコスト

という、この辺がオーバヘッドになります。

よくある誤解として、文字列が破壊的変更を受けた時に mutable な文字列オブジェクトを都度作れば良い、というものがありますが、

  • (1) 文字列の中身(String オブジェクトがさらに持っている文字列バッファ)は、すでに CoW になっています。
  • (2) 文字列オブジェクト自体は、object_id の一意性を保つため、毎回オブジェクト slot を切り出す必要があります。

主に、(2) の理由から、「コスト」が生じることになります。なお、(1) で CoW と言っては居ますが、ある程度短い長さの文字列(32bit CPU の場合、12 文字、64bit の場合 24 文字)は、CoW の対象にならず、文字列オブジェクトそれ自身に埋め込まれますので、CoW 云々は関係なく、上記「その slot を文字列にするために初期化するコスト」に含まれます。まぁ、多分それ以上の長さの文字列を初期化するのと、ほぼ同程度のコストなので、あんまり気にしなくていいです。

■どうすれば良いか(すでに実装された案)

□(1) "文字列リテラル".freeze

この問題に対処するために、"foo".freeze が特別に最適化手法として、Ruby 2.0 で提供されました。

元々、Object#freeze は、そのオブジェクト自身を freeze して終了だったわけですが、"文字列リテラル"#freeze の場合だけ、"文字列リテラル"を毎回作らずに、freeze された同じ文字列オブジェクトを返す、というように意味が変更されました。元々「mutable だから毎回別のオブジェクトを返さないといけない」という話だったので、immutable なら、別に同じオブジェクトを返せば良いよね、という話です。

これが、遠藤さんの記事にある「社会的問題」を引き起こすとは、これを導入した時には誰も気づかなかった、というのが、興味深い話です。

ちなみに、実はもう少し賢いことをやっていて、複数の箇所で "foo".freeze というプログラムがあれば(ソースエンコーディングが同じであれば)、同一の文字列オブジェクトを使います。

p "foo".freeze.object_id #=> 5746430
p "foo".freeze.object_id #=> 5746430

これは、dup の逆なので、dedup といったりします。

□(2) Hash#["文字列リテラル"]

(多分)あまり知られていませんが、(多分)Ruby 2.2から、Hash オブジェクトに対して文字列リテラルでキーを指定した時、h["foo"] は h["foo".freeze] とコンパイルされるようになりました。実は、(多分)あまり知られていませんが、Hash のキーに渡す文字列オブジェクトは特別に freeze されます。

{"foo":1}.keys.each{|k| p k.frozen?} #=> true

key が変わっちゃ困るからですが、よく利用する文字列だけ ad-hoc に対応しているわけです。この frozen string の生成は、従来は Hash#[]= の中でやっていたことですが、(1) の最適化と同じ理由で、よく使うし、まぁ、先にやっておくといいよね、という話です。

この辺(1, 2)は、github の中の人(@tmm1, @charliesome) からの提案です。

□(3) 世代別GC

Ruby 2.1 から、私が言いふらしているので(多分)有名だろう、世代別 GC が導入されました。こういうテンポラリオブジェクトの回収にとくに有効だろうと思われます。

ただ、minor gc が major gc(従来の GC)よりも十分速くなったとはいえ、

  • mark(必要な領域を scan)
  • sweep(全領域を scan、回収)

というオーバヘッドがいかんせんかかります。

■既存の工夫がどれくらい効いているのか計測

少し、計ってみましょう。開発版の ruby 2.3.0dev (2015-09-14 trunk 48419) [x86_64-linux] を使ってみます。マシンは結構いいやつで、i7-4930K CPU @ 3.40GHz で Linux 3.13.0-62-generic 上です。

$ ruby -ve '
require "benchmark"
N = 20_000_000
Benchmark.bm{|bm|
  bm.report{N.times{str = "a"}}
  bm.report{N.times{str = "a".freeze}}
}
'
ruby 2.3.0dev (2015-10-05 trunk 52040) [x86_64-linux]
       user     system      total        real
   1.640000   0.000000   1.640000 (  1.640642)
   0.760000   0.000000   0.760000 (  0.765904)

凄いですね、実時間で 1.64/0.76 = 2.16 倍くらい速くなっています。ちなみに、世代別 GC を強制的に効かなくして、調査してみましょう。

$ RUBY_GC_HEAP_OLDOBJECT_LIMIT_FACTOR=0.1 ruby -ve '
require "benchmark"
N = 20_000_000
Benchmark.bm{|bm|
  bm.report{N.times{str = "a"}}
  bm.report{N.times{str = "a".freeze}}
}
'
ruby 2.3.0dev (2015-10-05 trunk 52040) [x86_64-linux]
RUBY_GC_HEAP_OLDOBJECT_LIMIT_FACTOR=0.100000 (default value: 2.000000)
       user     system      total        real
   2.060000   0.000000   2.060000 (  2.065233)
   0.820000   0.000000   0.820000 (  0.812868)

世代別 GC で、2.06 -> 1.64 と、1.25 倍くらい速くなっているんですね。うーん、意外と効いてないな。

freeze しているのは、だいたい空ループと変わらないので、ちょっと確認してみましょう。

$ ruby -ve '
> require "benchmark"
> N = 20_000_000
> Benchmark.bm{|bm|
>   bm.report{N.times{str = "a"}}
>   bm.report{N.times{str = "a".freeze}}
>   bm.report{N.times{str = str}}
> }
> '
ruby 2.3.0dev (2015-10-05 trunk 52040) [x86_64-linux]
       user     system      total        real
   1.640000   0.000000   1.640000 (  1.639037)
   0.770000   0.000000   0.770000 (  0.765760)
   0.770000   0.000000   0.770000 (  0.770223)

なんと、str = str のほうが、若干遅いですね。びっくり。まぁ、気にするだけ無駄な速度差なので、同じくらい、と思いましょう。

あと、GC.disable をやってみて、GC の時間を排除してしまうとどうでしょうか。20M 個の文字列オブジェクトを作ると、大ざっぱに 20M * 40B (64bit CPUの場合)= 800MB なので、まぁ普通にテストできるでしょう。やってみましょう。

$ ruby -ve '
require "benchmark"
N = 20_000_000
Benchmark.bm{|bm|
  bm.report{N.times{str = "a"}}
  bm.report{N.times{str = "a".freeze}}
  bm.report{GC.disable; N.times{str = "a"}}
}
'
ruby 2.3.0dev (2015-10-05 trunk 52040) [x86_64-linux]
       user     system      total        real
   1.640000   0.000000   1.640000 (  1.642891)
   0.790000   0.000000   0.790000 (  0.788970)
   1.470000   0.150000   1.620000 (  1.614858)

おっと、実時間だと、世代別 GC を、ちゃんと有効にしているやつと、あまり変わりませんね。つまり、このマイクロベンチマークでは、世代別 GC のコストはほとんどなくて、ほぼ「文字列オブジェクトの生成」のコストだったことがわかります。ちなみに、マイクロベンチマークだから GC のコストが比較的低くすむことは、きちんと抑えておくべきでしょう。特定のオブジェクト(例えば、Thread とか Proc とか)が沢山あると、また結果は変わります。でも、文字列が 100M 個あるテストをやっても、あまり変わらなかったので、なんか世代別GCのために施した sweep の最適化スゲーな(自画自賛)。

~$ ruby -ve '
> require "benchmark"
> N = 20_000_000
> objs = 100_000_000.times.map{|i| i.to_s}
> GC.start; GC.start # magic
> Benchmark.bm{|bm|
>   bm.report{N.times{str = "a"}}
>   bm.report{N.times{str = "a".freeze}}
>   bm.report{GC.disable; N.times{str = "a"}}
> }
> '
ruby 2.3.0dev (2015-10-05 trunk 52040) [x86_64-linux]
       user     system      total        real
   1.420000   0.170000   1.590000 (  1.592681)
   0.770000   0.000000   0.770000 (  0.768226)
   1.450000   0.140000   1.590000 (  1.593101)

Rails って、何個くらい既存オブジェクトがあるんだろ。

このマシン上では、だいたいからループに 0.8 秒、オブジェクト生成含めて、ざっくり 1.6 秒とすると、オブジェクト生成だけで、0.8 秒となります。0.8 sec / 20M = 4.0e-08 = 40 ns。3.4GHz で、すごーく単純化して、1 cycle 1 命令と考えると、40 / (1/3.4) = 136 命令。もうちょっとなんとかなりそうな気がする。

例えば、Rails で文字列を 1 リクエストを何個作るかわかりませんが、例えば1万個だったとすると、40ns * 10_000 = 400 us = 0.4 ms。だいたいこんな感じのオーバヘッドでしょうか。多分、数千のオーダーだと思うんで(いや、もっと桁違いに多いのかな)、オブジェクト生成のコストは、そんな感じなんじゃないかな。これを気にする Rails アプリは、だいぶシビアな環境な気がします。

http://protected-journey-7206.herokuapp.com/ この単純な Rails アプリには、gc_tracer が仕込まれており、何アクセス目にGCがどんな状況で起こったか、というのを見ることが出来ます http://protected-journey-7206.herokuapp.com/gc_tracer。これを見ると、105 リクエスト目の GC の状況と 93 リクエスト目の状況を見て、その total_allocated_objects を見比べると、だいたい1リクエストに何個オブジェクト作っているかわかります(文字列に限りませんが、文字列は多分 majority でしょうかね)。

その結果を計算してみると、

 (2275575 - 2168216) / (105 - 93)
=> 8946

と、9,000オブジェクト生成していることになることになります。まぁ、試算的にはだいたいあってたって感じでしょうか。もっとまともなアプリだと、この数倍、数十倍作る様な気もしますので、アレですが。まぁ、数万くらいと考えると、4ms。ちょっと気にしたくなるコストかもしれません。

あと、GC のコストを考えてみると、世代別GC(2.1以降)は、GC のコストは殆ど(少なくともこの例では)かかっていないで、2.0 以前の full GC のコストは、2.0 - 1.6 = 0.4sec。オブジェクト生成コスト 0.8 sec の半分くらいかかっていたわけですね。そりゃ、遅いと言いたくなるのもわかる、かもしれない。1文字列生成にかかるGCコスト、と割ってみると、20ns。

ちなみに、ここで出しているのはマイクロベンチマークなので、大きなアプリだと、また相当性能は変わると思います。とくに生成時のコストには、キャッシュが全然あたらなくなるんじゃないかなーと思うので、こんなに素直にはいかない...と思ってたけど、そもそも GC.disable にしたらキャッシュあたらないことも多い(page 溢れたらキャッシュがあたらない)と思ったけど、連続領域で取っているから、やっぱり当たるってことかなぁ。でも、それは実アプリでもそれなりにあたりそうだから、だから、それなりに実際に即している、のだろうかな。

■どうすれば良いか(提案されている案)

Eric Wong が、上記 (2) Hash#["文字列リテラル"] の最適化を、さらに推し進めて、いろんなメソッドに対応しようぜ、という提案を、修正パッチとともに提案しています。

Feature #10423: [PATCH] opt_str_lit*: avoid literal string allocations

これは、よく知られた、freeze した文字列を与えても大丈夫なメソッドを先にリストしておき(これは、開発者が手でリストする)、そのメソッド呼び出しに文字列リテラルを渡そう、と言うときに、専用命令 opt_str_lit で渡して、もし見当違いなメソッドに渡そうとしてれば、ちゃんと文字列を作る、的なものです。

具体的には、こんな感じにコンパイルします。

  recv.known_method("foo")

#=> これを、こんなふうにコンパイルする

  if recv.method(:known_method).optimizible?
    str = "foo".freeze
  else
    str = "foo"
  end
  recv.known_method(str)

この例では変数を使っているけど、実際は VM のスタック上でこの操作をやるわけです。あと、method() メソッドは、本当は使わないで、ちゃんと VM が持ってるメソッド探索の機能を使います。

これ、ちゃんと動くんだけど、「よく知られた、freeze した文字列を与えても大丈夫なメソッド」を、ちゃんとメンテナンスしないといけなくて、その苦労に比べてどれくらいペイするのか、というのがアレで、現状見送っているところです。

他に、なんかあったかな。あるような気がするけど、見落としているかも。

■どうすれば良いか(ちゃんとした案)

TBD、と書いているが、まともに書くと長いので箇条書きにてお茶を濁す。

  • 世代別GCをもう少し頑張る(shady を減らす。上記結果から、あまり効果はなし)
  • 文字列オブジェクト生成をもっと速くする
    • 文字列専用ヒープによる文字列生成コストの削減
    • putstring 命令用に投機的文字列生成
    • slot allocation を linked list じゃなくて bump allocation に
      • 部分的 compaction GC
    • スタックアロケーションによる slot 確保オーバヘッドの削減(本当に効くのかな?)
  • 文字列生成を不要に
    • メソッドキャッシュを利用したエスケープ解析および mutability/uniqueness の要不要の判断
    • on-stack replacement による脱最適化

いくつかアイデアあるけど、本当に 40ns のために頑張るべきなのか、というところも重要かもしれません。


もっと簡単なアイデアは無いかと string.c を見直してみると、

Index: string.c
===================================================================
--- string.c	(revision 52040)
+++ string.c	(working copy)
@@ -1250,11 +1250,18 @@
 VALUE
 rb_str_resurrect(VALUE str)
 {
+#if 0
     if (RUBY_DTRACE_STRING_CREATE_ENABLED()) {
 	RUBY_DTRACE_STRING_CREATE(RSTRING_LEN(str),
 				  rb_sourcefile(), rb_sourceline());
     }
     return str_duplicate(rb_cString, str);
+#endif
+    VALUE dup = str_alloc(rb_cString);
+    // str_replace(dup, str);
+    RBASIC(dup)->flags = RBASIC(dup)->flags | (RBASIC(str)->flags & (RSTRING_NOEMBED | RSTRING_EMBED_LEN_MASK | RUBY_ENC_CODERANGE_MASK | RUBY_ENCODING_MASK));
+    MEMCPY(RSTRING(dup)->as.ary, RSTRING(str)->as.ary, VALUE, 3);
+    return dup;
 }
 
 /*

こうすることで、1.7sec -> 1.3sec にすることが出来ました(上記とは別マシン。開発用 laptop)。25ns だな。

多分、穴があるので、もうちょっと見ないと駄目だと思うんだけど。


さらにもうちょっとやって、1.25sec。あんまり伸びなかった。

Index: gc.c
===================================================================
--- gc.c	(revision 52040)
+++ gc.c	(working copy)
@@ -1810,6 +1810,18 @@
     return newobj_of(klass, flags, 0, 0, 0);
 }
 
+
+VALUE
+rb_str_putstring(VALUE str)
+{
+    VALUE dup = newobj_of(rb_cString,
+			  T_STRING | (RGENGC_WB_PROTECTED_STRING ? FL_WB_PROTECTED : 0) |
+			  (RBASIC(str)->flags & (RSTRING_NOEMBED | RSTRING_EMBED_LEN_MASK | RUBY_ENC_
+						 CODERANGE_MASK | RUBY_ENCODING_MASK)),
+			  RANY(str)->as.values.v1, RANY(str)->as.values.v2, RANY(str)->as.values.v3);
+    return dup;
+}
+
 NODE*
 rb_node_newnode(enum node_type type, VALUE a0, VALUE a1, VALUE a2)
 {

gc.c の中でやるのがキモ(shared 周りがまだ足りないのは承知してます)。


$ ruby -ve '
require "benchmark"
N = 20_000_000

GC.start; GC.start # magic
a = b = "a"
Benchmark.bm{|bm|
  bm.report{N.times{str = a + b}}
}
'
ruby 2.3.0dev (2015-10-05 trunk 52041) [x86_64-linux]
       user     system      total        real
   2.210000   0.000000   2.210000 (  2.207660)

速いマシンにて。単純な文字列の連結で 2.2sec。0.8 sec がループとして、2.2-0.8=1.4sec。1回の文字列連結で、文字列生成のコストの約2倍くらい。どっちかというと、文字列リテラルよりも、こういう操作の方が多そうだから、文字列リテラル生成のオーバヘッドは気にするだけ無駄じゃないのかなぁ。

_naruse(Mon Oct 05 23:18:04 +0900 2015)

 「よく知られた、freeze した文字列を与えても大丈夫なメソッド」はrdocに書いておいて、それをビルド時に収集するとかですかね

Sasada Koichi / ko1 at atdot dot net
$Date: 2003/04/28 10:27:51 $