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

Ruby高速化計画のその後。(ループ内で定数化するマクロの除去)

Programming Ruby Security & Programming camp 2009

進渉報告。
セキュリティ&プログラミングキャンプ2009で、自分はひたすらに、例のBignumと同様の問題の解決に勤しんでいました。


件の問題は、RBIGNUM_PTRだとか、RBIGNUM_LENだとかいうマクロが原因で起こってました。
(Rubyでフィボナッチ数列の演算が遅い問題についてのその後の考察。@解決編 - CanI’s Diary)
で、実は、これらのマクロに似たマクロが、他にもruby.hに定義されています。

  • Array
    • RARRAY_PTR
    • RARRAY_LEN
  • String
    • RSTRING_PTR
    • RSTRING_LEN
  • Struct
    • RSTRUCT_PTR
    • RSTRUCT_LEN

Rubyでそれぞれの型を表す構造体に、型の中身が埋め込まれる(省メモリのため)可能性があるものに、これらのマクロが用意されているようです。
というわけで、こいつらをループの外に出してやったら速くなるんじゃなかろうか、という考えの元、キャンプ中にarray.cと、string.cをHackし、約17%の高速化に成功しました。



が、
ここに、壮大な罠が隠されていたわけです。


今回は、その罠の数々を書き連ねてお茶を濁しつつ、広く解決策を募集しつつ、問題山積みでこんがらがった頭を整理しつつ…という企画でいこうと思います。

今回、変更を適用した関数一覧

  • Array
    • rb_ary_sample
    • rb_ary_shuffle_bang
    • rb_ary_times
  • String
    • rb_str_end_with
    • rb_str_split_m
    • rb_str_start_with
    • rb_str_times
  • Struct
    • make_struct
    • inspect_struct
    • rb_struct_aset_id
    • rb_struct_aref_id
    • rb_struct_getmember
    • rb_struct_set
    • recursive_eql
    • recursive_equal
    • recursive_hash

罠に嵌った関数一覧

  • Array
    • rb_ary_assoc
    • rb_ary_collect
    • rb_ary_collect_bang
    • rb_ary_combination
    • rb_ary_count
    • rb_ary_delete
    • rb_ary_drop_while
    • rb_ary_each
    • rb_ary_fill
    • rb_ary_hash
    • rb_ary_include
    • rb_ary_index
    • rb_ary_inspect
    • rb_ary_or
    • rb_ary_permutation
    • rb_ary_rassoc
    • rb_ary_reject_bang
    • rb_ary_reverse_each
    • rb_ary_rindex
    • rb_ary_select
    • rb_ary_take_while
  • String
    • rb_str_each_byte

他、数え切れないほど多数。


…圧倒的に、罠に嵌った方が多いですね。
Arrayとか特に。


今回、嵌った罠については、以下の記事が詳しいです。
Rubyist Magazine - Ruby の落とし方
軽く引用してみますと、

一般には、変更可能なオブジェクトについて C コード中でなんらかの仮定を行なっている状況で Ruby コードが動作してそのオブジェクトを変更しその仮定を崩せてしまうのが問題です。そうすると、Ruby コードから Segmentation fault を起こすことが可能になってしまう場合があります。

Ruby コードが実行される機会には、少なくとも次のケースがあります。

  • rb_yield してブロックを呼び出す
  • rb_funcall でメソッドを呼び出す
  • rb_equal でオブジェクトを比較すると == メソッドが呼び出される
  • Hash の key としてオブジェクトを使うと、hash メソッドおよび eql? メソッドが呼び出される
  • StringValue、StringValuePtr、StringValueCStr などを使うと、to_str が呼び出される
  • NUM2INT などのオブジェクトから整数への変換で to_int が呼び出される
  • 配列の内部にアクセスする場合には to_ary が呼び出される
  • I/O を行なうときにスレッドが切り替わって他のスレッドが動作する
  • rb_gc を呼び出して GC が行なわれるとき、finalizer が付加されているオブジェクトが削除されるとその finalizer が呼び出される
  • オブジェクトを作ったり配列の長さが変わるなどしてメモリの確保が起こると、GC が行なわれて finalizer が呼び出される
http://jp.rubyist.net/magazine/?0002-RubyCore#l5

と、あります。

今回の、ループ内で定数化するマクロを、ループの外に出すというHackは、
ループ内で、マクロの値が定数化することを仮定していますので、オブジェクトに何らかの変更が加わって、その仮定が崩れるとマズいわけです。


るびまで挙げられている任意のRubyコードが実行させる場合のうち、今回、嵌ったものは、rb_yieldと、rb_equalです。
(rb_yieldに関しては、キャンプ終了後、事前にささださんの方から指摘を受けていました。)

rb_yield

Array#eachに件のHackを以下のように施したのち、その下のスクリプトを実行すると、SEGVします。

rb_ary_each
VALUE
rb_ary_each(VALUE ary)
{
    VALUE *ptr;
    long i, len;

    RETURN_ENUMERATOR(ary, 0, 0);
    ptr = RARRAY_PTR(ary);
    len = RARRAY_LEN(ary);
    for (i=0; i<len; i++) {
	rb_yield(ptr[i]);
    }
    return ary;
}
script
#!/usr/bin/env ruby
ary = Array.new(1000)
ary.each{ ary.compact! }


block内で、任意のRubyコードが実行され、元のArrayに破壊的変更が加わったため、仮定が崩れSEGVしたわけです。

rb_equal

Array#==に件のHackを以下のように施したのち、その下のスクリプトを実行すると、SEGVします。

recursive_equal
static VALUE
recursive_equal(VALUE ary1, VALUE ary2, int recur)
{
    VALUE *ptr1, *ptr2
    long i, len;

    if (recur) return Qtrue; /* Subtle! */
    ptr1 = RARRAY_PTR(ary1);
    ptr2 = RARRAY_PTR(ary2);
    for (i=0; i<len; i++) {
	if (!rb_equal(ptr1[i], ptr2[i]))
	    return Qfalse;
    }
    return Qtrue;
}
script
#!/usr/bin/env ruby
$ary1 = Array.new(1000)
$ary2 = Array.new(1000)

obj = Object.new
def obj.==(obj2)
    $ary2.compact!
    true
end

$ary1[0] = obj
$ary1 == $ary2


rb_equalで使われる==メソッドは、ユーザーレベルで自由に再定義できるため、破壊的変更を加える任意のRubyコードを実行することも可能です。
よって、仮定が崩れ、SEGVします。


この他にも、rb_hashや、rb_inspectも同様の理由で危険です。
特に、拡張ライブラリを作る際などには注意が必要でしょう。

疑問

ArrayやStringでは、それぞれの元のArrayやStringに破壊的変更を加えることが可能でした。(〜!のメソッドを用いて)
一方、Structでは、
Ruby Reference Manual - るりま
等を見る限り、元のStructに破壊的変更を加えることは、無理そうです。


例えば、仮に、

#!/usr/bin/env ruby
s = Struct.new("STRUCT", :hoge, :fuga, :piyo).new("hoge","fuga","piyo")
s.each { |v|
    s = nil
    p v
}
p s

などといったコードを実行した時、SEGVせずに、以下のような出力を返します。

"hoge"
"fuga"
"piyo"
nil


もとのStructに変更が加わってないのですから当然です。
これは、件のHackをしても、しなくても同様の結果となります。(当然)


で、今回、自分は、これなら問題なさそうだとして、以下のようなコードを書きました。

struct.c : recursive_equal
static VALUE
recursive_equal(VALUE s, VALUE s2, int recur)
{
    VALUE *ptr, *ptr2;
    long i, len;

    if (recur) return Qtrue; /* Subtle! */
    ptr = RSTRUCT_PTR(s);
    ptr2 = RSTRUCT_PTR(s2);
    len = RSTRUCT_LEN(s);
    for (i=0; i<len; i++) {
	if (!rb_equal(ptr[i], ptr2[i])) return Qfalse;
    }
    return Qtrue;
}

これに対して、こんなコードを実行したらSEGVするぜ!というのを見つけた方や、
これなら問題ないと思われた方は、コメントをいただけたら幸いです。

ちなみに

今回、私が高速化したものを適用し、以下のようなベンチマークを実行すると、この様な結果になります。

benchmark
#!/usr/bin/env ruby
require 'benchmark'

Benchmark.benchmark("",
                    18,
                    "\t%10.6u\t%10.6y\t%10.6t\n",
                    ">total:") { |x|

    #String#*
    x.report("String#*") {
        "string"*320000000
    }
    
    #String#split
    str = "string"*500000
    
    x.report("String#split") {
        str.split("str")
        str.split(//)
    }

    #String#start_with?
    argv = Array.new
    50000.times { |n| argv << n.to_s }

    x.report("String#start_with?") {
        1000.times { "str".start_with?(*argv) }
    }

    #String#end_with?
    x.report("String#end_with?") {
        5000000.times { "str".end_with?("ing") }
    }

    #Array#*
    x.report("Array#*") {
        ["a","r","r","a","y"]*50000000
    }

    ary1 = Array.new
    50000000.times { |n| ary1 << n }
    
    #Array#shuffle!
    x.report("Array#shuffle!") {
        ary1.shuffle!
    }

    #Array#sample
    x.report("Array#sample") {
        5000000.times { ary1.sample }
    }

    symbols = Array.new
    50000.times { |n| symbols << n.to_s.to_sym }
    hoge = Struct.new("HOGE", :"0", *symbols)
    fuga = hoge.new("fuga", *symbols)

    #Struct#[]
    x.report("Struct#[]") {
        50000.times { fuga[:"49999"] }
    }

    #Struct#[]=
    x.report("Struct#[]=") {
        50000.times { |n| fuga[n.to_s.to_sym] = n.to_s.to_sym }
    } 

    #Srruct#inspect
    x.report("Struct#inspect") {
        20.times { fuga.inspect }
    }

    #Struct#==
    piyo = fuga.clone
    x.report("Struct#==") {
        10000.times { fuga == piyo }
    }

    #Struct#eql?
    x.report("Struct#eql?") {
        500.times { fuga.eql?(piyo) }
    }

    #Struct#hash
    x.report("Struct#hash") { 
        100.times { fuga.hash }
    }

    #Struct_each
    x.report("Struct#each") {
        500.times{ fuga.each{} }
    }

    #Struct#each_pair
    x.report("Struct#each_pair") {
        500.times{ fuga.each_pair{} }
    }

    #Struct.select
    x.report("Struct#select") {
       500.times{ fuga.select{} }
    }
}

結果


右にいくほど早いです。
最大で約63%、全体で約8%の高速化となりました。
まぁ、超高速化したのが、Struct#==なので、SEGVするコードが見つかると一気に下がるんですが…

diff

trunk 25015とのdiffは、こんな感じです。以下に、置いてあります。
Friendpaste - master:trunk-25016

gist.githubだと全文載らないんだよなー。どうしてだろ。
バイト数制限とかあるのかな。

あと、

自分が大昔見つけたtypo

matrix.rb(revision v 1.13)にtypoを発見した。matrix.rb:686 'ii' is undefined. ii→iだな。

http://twitter.com/CanI_61st/status/1348183677

が、今頃修正されているのに気づいた。

lib/matrix.rb (determinant): Bug fix where determinant failed on some matrices [ruby-core:23597]

[ruby] Revision 24949


…ちゃんと報告しなくてごめんなさい。
こういうtypoとかってどこに報告すればいいんだろう。
MLに流せばいいのかな。…怖いです><


この高速化の修正も、ささださんからruby-devでやれといわれたので、Structが問題なさそうだったら、ruby-devに流れることになるだろうと思います。
怖いなぁ…(ぁ