RubyInline関連のエントリを読んで、さらに高速化してみた
RubyInlineを使うと速くなるという記事を読みました。
10000個、'a'が続く二つの文字列のxorを取るのを1000回繰り返すという
プログラムになっています。
おそらく内容自体には意味はなくって、速度ベンチマーク的な意味合いでしょうか。
http://blog.netswitch.jp/articles/2007/03/12/rubyinlineがすごい
上記のURLの記事ではRuby1.8用のコードとなっています。
Ruby1.9対応されているエントリがありました。
Ruby1.9.1でRubyInline動かした - 学習する機械、学習しない人間 Next Generation
Ruby側のコードがxorになっていなかったので
以下が正しいのかと思います。
# rubyinline.rb def benchmark s = "a" * 10000 test = Test.new t = Time.now 1000.times{test.string_xor(s, s)} Time.now - t end class Test def string_xor(str1, str2) result = str1.clone str1.length.times do |i| #result[i] = str2[i] result[i] = (str1[i].ord ^ str2[i].ord).chr end result end end b1 = benchmark begin require 'inline' class Test inline do |builder| builder.c <<-EOF VALUE string_xor(VALUE str1, VALUE str2) { VALUE result = rb_str_new(RSTRING_PTR(str1), RSTRING_LEN(str1)); int i; for (i = 0; i < RSTRING_LEN(str1); i++) { RSTRING_PTR(result)[i] ^= RSTRING_PTR(str2)[i]; } return result; } EOF end end rescue LoadError end b2 = benchmark p b1/b2
実行してみました。
180.33020297117076
180倍とか。速いです＞＜
意図は特にありませんが、何か得られるかもしれませんので
さらにここから速くしたいと思います。
注目すべきはfor文の中です。
今回のコードの場合forループの回数が大きいのでforループの中を
削れば速くなるはずです。
注意:本当は計測、ボトルネックを定量的に発見するしてから高速化に着手するのが正しいやり方です。
forループの中を見るとRSTRING_LEN(str1)というマクロがありますが
forループ中でStringオブジェクトの長さは変わりませんから毎回評価しなくて良いですね。
1回評価したものをlenという変数にでも入れておいて後はそれを使いまわす事にしましょう。
(長くなるのでコード全文ではなく、inline部分だけ抜粋したものを載せておきます)
builder.c <<-EOF VALUE string_xor(VALUE str1, VALUE str2) { VALUE result = rb_str_new(RSTRING_PTR(str1), RSTRING_LEN(str1)); int i; int len; len = RSTRING_LEN(str1); for (i = 0; i < len; i++) { RSTRING_PTR(result)[i] ^= RSTRING_PTR(str2)[i]; } return result; } EOF
実行してみました。
203.87809890114823
良い感じにちょっとだけ速くなりました。
Ruby1.9対応の肝であるRSTRING_PTR()とRSTRING_LEN()は
include/ruby.hによると、以下のようなマクロになっています。
#define RSTRING_LEN(str) \ (!(RBASIC(str)->flags & RSTRING_NOEMBED) ? \ (long)((RBASIC(str)->flags >> RSTRING_EMBED_LEN_SHIFT) & \ (RSTRING_EMBED_LEN_MASK >> RSTRING_EMBED_LEN_SHIFT)) : \ RSTRING(str)->as.heap.len) #define RSTRING_PTR(str) \ (!(RBASIC(str)->flags & RSTRING_NOEMBED) ? \ RSTRING(str)->as.ary : \ RSTRING(str)->as.heap.ptr)
forループの中でflagsを判定しています。
文字列の長さが変わらない限り判定結果は変わりませんから
ループの中で判定すると遅くなります。
判定をループの外に出しましょう。
builder.c <<-EOF VALUE string_xor(VALUE str1, VALUE str2) { VALUE result = rb_str_new(RSTRING_PTR(str1), RSTRING_LEN(str1)); int i; int len; len = RSTRING_LEN(str1); if(RBASIC(result)->flags & RSTRING_NOEMBED){ for (i = 0; i < len; i++) { RSTRING(result)->as.heap.ptr[i] ^= RSTRING(str2)->as.heap.ptr[i]; } } else{ for (i = 0; i < len; i++) { RSTRING(result)->as.ary[i] ^= RSTRING(str2)->as.ary[i]; } } return result; } EOF
実行してみましょう。
332.5402662303343
forループがポインタ経由だと
最適化されていなかったようなので以下のようにしてみました。
builder.c <<-EOF VALUE string_xor(VALUE str1, VALUE str2) { VALUE result = rb_str_new(RSTRING_PTR(str1), RSTRING_LEN(str1)); int i; int len; char *desc,*src; len = RSTRING_LEN(str1); if(RBASIC(result)->flags & RSTRING_NOEMBED){ desc = &(RSTRING(result)->as.heap.ptr[0]); src = &(RSTRING(str2)->as.heap.ptr[0]); } else{ desc = &(RSTRING(result)->as.ary[0]); src = &(RSTRING(str2)->as.ary[0]); } for (i = 0; i < len; i++) { desc[i] = src[i]; } return result; } EOF
1203.205824119509
ぶっ。1200倍とか。
さらにさらに、forループの中を見るとSIMD命令が使えそうな感じになってますね。
私のマシンはCore2DuoでSSEユニットを搭載しているので
これを使わない手はありません。
builder.add_compile_flags '-ftree-vectorize'
builder.add_compile_flags '-ftree-vectorizer-verbose=3'
builder.c <<-EOF
VALUE
string_xor(VALUE str1, VALUE str2)
{
VALUE result = rb_str_new(RSTRING_PTR(str1), RSTRING_LEN(str1));
int i;
int len;
char *desc,*src;
len = RSTRING_LEN(str1);
if(RBASIC(result)->flags & RSTRING_NOEMBED){
desc = &(RSTRING(result)->as.heap.ptr[0]);
src = &(RSTRING(str2)->as.heap.ptr[0]);
}
else{
desc = &(RSTRING(result)->as.ary[0]);
src = &(RSTRING(str2)->as.ary[0]);
}
for (i = 0; i < len; i++) {
desc[i] = src[i];
}
return result;
}
EOF
以下のようなメッセージが出たら
SIMD命令を使うようにコンパイルされているらしいです。
note: LOOP VECTORIZED. note: vectorized 1 loops in function.
実行してみましょう。
1201.7791157108238
うーん、速くなりませんでした(測定誤差範囲内)
既にgccが最適化をしてくれているっぽいです。
わかった事
- RubyInlineは速くなるけど、読みにくくなる。
- Ruby1.9はオブジェクト埋め込みかどうかの判定が入っているのでちょっぴり遅い。
- その判定はCで書くとすっとばせて速くなる。スレッドを起こしている場合とかはちゃんと考えて作る必要がある。
- 文字列の長さが変わらない処理であればCで書いても、そんなに大変じゃない。
- 手元の環境のgccは勝手にSIMD命令を使うように最適化している様子。
今回やらなかった・できなかった事
5/16追記:
マクロを一旦展開しましたが、最後は展開しなくて良い形になっていたので
読みやすさからすると、以下で良いのでした。
builder.add_compile_flags '-ftree-vectorize'
builder.add_compile_flags '-ftree-vectorizer-verbose=3'
builder.c <<-EOF
VALUE
string_xor(VALUE str1, VALUE str2)
{
VALUE result = rb_str_new(RSTRING_PTR(str1), RSTRING_LEN(str1));
int i;
int len;
char *desc,*src;
len = RSTRING_LEN(str1);
desc = RSTRING_PTR(result);
src = RSTRING_PTR(str2);
for (i = 0; i < len; i++) {
desc[i] = src[i];
}
return result;
}
EOF
