Feature #6177: array.cのrb_ary_equal()の高速化

• Status: Closed
• Assignee: Glass_saga (Masaki Matsushita)
• Target version: 2.0.0

[Glass_saga (Masaki Matsushita)]

できる限りVALUEの値の比較のみに留め、必要になったらrb_equal()を用いるという方針でrb_ary_equal()の高速化を試みました。
次のベンチマークを行ったところ、以下のような結果となりました。

require 'benchmark'

A = Array.new(100_0000){|n| n }
B = Array.new(1_0000){|n| n.to_s }
C = Array.new(1_0000){|n| n.to_s }

Benchmark.bm do |x|
x.report do
A == A.dup
end

x.report do
B == C
end
end

trunk(r35092):
user system total real
0.010000 0.000000 0.010000 ( 0.011711)
0.010000 0.000000 0.010000 ( 0.002169)

proposal:
user system total real
0.000000 0.000000 0.000000 ( 0.002257)
0.000000 0.000000 0.000000 ( 0.002307)

Fixnumのみで構成されたArrayの比較は従来の5倍ほどの速さになりました。
一方、rb_equal()による同値性の判定が必要となる場合でも性能の低下はありません。

patchを添付します。

[nobu (Nobuyoshi Nakada)]

=begin
先頭だけではなく、同一オブジェクトかどうかを常に先に調べるようにするとどうなるでしょうか。
=end

[Glass_saga (Masaki Matsushita)]

• File patch2.diff patch2.diff added

Nobuyoshi Nakada wrote:

先頭だけではなく、同一オブジェクトかどうかを常に先に調べるようにするとどうなるでしょうか。

最初の要素だけobject_idに依らない同値性の判定が必要なケース(先に添付したpatch.diffを適用したrubyにとって最悪のケース)を加えてベンチマークを取りました。
patch1は先に添付したpatch.diffを適用したもので、patch2は同一オブジェクトかどうかを常に先に調べるようにしたものです。

require 'benchmark'

A = Array.new(100_0000){|n| n }
B = Array.new(1_0000){|n| n.to_s }
C = Array.new(1_0000){|n| n.to_s }

Benchmark.bm do |x|
x.report do
A == A.dup
end

x.report do
B == C
end

A.unshift("hoge")
D = A.dup
D[0] = "hoge"

x.report do
A == D
end
end

trunk(r35092):
user system total real
0.010000 0.000000 0.010000 ( 0.011911)
0.000000 0.000000 0.000000 ( 0.002002)
0.000000 0.000000 0.000000 ( 0.011341)

patch1:
user system total real
0.000000 0.000000 0.000000 ( 0.002591)
0.000000 0.000000 0.000000 ( 0.002391)
0.010000 0.010000 0.020000 ( 0.011916)

patch2:
user system total real
0.000000 0.000000 0.000000 ( 0.002261)
0.010000 0.000000 0.010000 ( 0.002306)
0.010000 0.000000 0.010000 ( 0.002829)

patch1では先頭でobject_idに依らない同値性の判定が必要になるとtrunkと同程度に遅くなってしまいますが、
patch2ではそのような場合でも高速に動作しました。

patch2のdiffを添付します。

[nobu (Nobuyoshi Nakada)]

=begin
(({rb_equal()}))はメソッドを呼び出すので、その後では(({p1})),(({p2}))が有効である保証がありません。
=end

[nobu (Nobuyoshi Nakada)]

=begin
もう一点、(({&&}))ではなく(({||}))ではないでしょうか。
=end

[Glass_saga (Masaki Matsushita)]

• File patch3.diff patch3.diff added

Nobuyoshi Nakada wrote:

rb_equal()はメソッドを呼び出すので、その後ではp1,p2が有効である保証がありません。

patchを直し、rb_equal()を実行した後に互いのRARRAY_LENのチェックと
p1, p2の有効性のチェック、無効であれば有効なポインタを得る処理を入れました。
rb_ary_elt()を使えば簡潔に書けるのですが、以下のように遅くなってしまいました。

   user     system      total        real 

0.010000 0.000000 0.010000 ( 0.010842)
0.010000 0.000000 0.010000 ( 0.002842)
0.010000 0.000000 0.010000 ( 0.010345)

もう一点、&&ではなく||ではないでしょうか。

いえ、これは&&が正しいです。
比較する各要素のVALUEの値が異なっていて、かつ#==によっても異なったオブジェクトであると判定されればQfalseを返します。

新しいpatchを適用してベンチマークを取ったところ、以下の結果となりました。

patch3:
user system total real
0.000000 0.000000 0.000000 ( 0.002276)
0.010000 0.000000 0.010000 ( 0.001847)
0.000000 0.000000 0.000000 ( 0.003058)

新しいpatchを添付します。

[nobu (Nobuyoshi Nakada)]

Glass_saga (Masaki Matsushita) wrote:

patchを直し、rb_equal()を実行した後に互いのRARRAY_LENのチェックと
p1, p2の有効性のチェック、無効であれば有効なポインタを得る処理を入れました。
rb_ary_elt()を使えば簡潔に書けるのですが、以下のように遅くなってしまいました。

最も大きいのはrb_ary_elt()呼び出しのオーバーヘッドということのようです
ね。

もう一点、&&ではなく||ではないでしょうか。

いえ、これは&&が正しいです。
比較する各要素のVALUEの値が異なっていて、かつ#==によっても異なったオブジェクトであると判定されればQfalseを返します。

たしかに。

新しいpatchを添付します。

i != 0 なら常に (p1 != RARRAY_PTR(ary1)) じゃないでしょうか。

[Glass_saga (Masaki Matsushita)]

• File patch4.diff patch4.diff added

Nobuyoshi Nakada wrote:

最も大きいのはrb_ary_elt()呼び出しのオーバーヘッドということのようですね。

そのようです。

i != 0 なら常に (p1 != RARRAY_PTR(ary1)) じゃないでしょうか。

おっしゃる通りです…
凡ミスをやらかしてしまいました。

p1,p2が有効であるかどうかのチェックを止め、rb_equal()を呼び出したら有効なポインタを取得するようにしました。
ベンチマークの結果はpatch3.diffとほとんど変わりません。

[mame (Yusuke Endoh)]

• Status changed from Open to Assigned
• Assignee set to Glass_saga (Masaki Matsushita)

挙動が変わるわけでないならいいんじゃないですかね。
パッチ試してませんが見た感じいいような気がしました。

コミット権が貰えたら自分でどうぞ。#6173
もらえなかったら、どうしよう。

--
Yusuke Endoh [e-mail]

[matz (Yukihiro Matsumoto)]

コミット権、さしあげます。cvs-admin at ruby-lang.org にssh2の公開鍵をgpgでサインして送ってください。

Matz.

• Status changed from Assigned to Closed
• % Done changed from 0 to 100

This issue was solved with changeset r37420.
Masaki, thank you for reporting this issue.
Your contribution to Ruby is greatly appreciated.
May Ruby be with you.

---

• array.c (recursive_equal): performance improvement.
  [ruby-dev:45412] [Feature #6177]

[znz (Kazuhiro NISHIYAMA)]

以下のようにすると p1, p2 の操作で配列の範囲外にアクセスしてしまうようです。
p1++ などのポインタ操作だけで参照までは行かなかったですが。

A = Array.new(3){|n| n.to_s }
B = A.dup
obj = Object.new
def obj.==(o)
A.clear
B.clear
GC.start
true
end
A[1] = obj
A == B

[Glass_saga (Masaki Matsushita)]

• Status changed from Closed to Assigned

2012年11月3日 2:45 znz (Kazuhiro NISHIYAMA) [e-mail]:

以下のようにすると p1, p2 の操作で配列の範囲外にアクセスしてしまうようです。
p1++ などのポインタ操作だけで参照までは行かなかったですが。

ご指摘ありがとうございます。
for文の継続条件に引っかかってくれるので実際に参照してしまう事はないのですが、不正なポインタを作ってしまうのは良くないですね。
修正します。

[Glass_saga (Masaki Matsushita)]

• Status changed from Assigned to Closed

r37438でrb_equal()後にArrayのサイズがiより小さくなっていない事をチェックするよう修正してコミットしました。