Feature #6177

array.cのrb_ary_equal()の高速化

Added by Masaki Matsushita about 2 years ago. Updated over 1 year ago.

[ruby-dev:45412]
Status:Closed
Priority:Normal
Assignee:Masaki Matsushita
Category:core
Target version:2.0.0

Description

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

require 'benchmark'

A = Array.new(1000000){|n| n }
B = Array.new(1
0000){|n| n.tos }
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を添付します。

patch.diff Magnifier (571 Bytes) Masaki Matsushita, 03/20/2012 12:08 PM

patch2.diff Magnifier (575 Bytes) Masaki Matsushita, 03/20/2012 08:29 PM

patch3.diff Magnifier (834 Bytes) Masaki Matsushita, 03/20/2012 11:34 PM

patch4.diff Magnifier (764 Bytes) Masaki Matsushita, 03/22/2012 11:37 AM

Associated revisions

Revision 37420
Added by glass over 1 year ago

  • array.c (recursive_equal): performance improvement. [Feature #6177]

Revision 37438
Added by glass over 1 year ago

  • array.c (recursive_equal): fix not to make invalid pointers when self and other are resized to same size in #== of their elements. [Feature #6177]

History

#1 Updated by Nobuyoshi Nakada about 2 years ago

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

#2 Updated by Masaki Matsushita about 2 years ago

Nobuyoshi Nakada wrote:

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

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

require 'benchmark'

A = Array.new(1000000){|n| n }
B = Array.new(1
0000){|n| n.tos }
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を添付します。

#3 Updated by Nobuyoshi Nakada about 2 years ago

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

#4 Updated by Nobuyoshi Nakada about 2 years ago

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

#5 Updated by Masaki Matsushita about 2 years ago

Nobuyoshi Nakada wrote:

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

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

   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を添付します。

#6 Updated by Nobuyoshi Nakada about 2 years ago

Glass_saga (Masaki Matsushita) wrote:

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

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

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

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

たしかに。

新しいpatchを添付します。

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

#7 Updated by Masaki Matsushita about 2 years ago

Nobuyoshi Nakada wrote:

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

そのようです。

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

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

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

#8 Updated by Yusuke Endoh about 2 years ago

  • Status changed from Open to Assigned
  • Assignee set to Masaki Matsushita

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

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

Yusuke Endoh mame@tsg.ne.jp

#9 Updated by Yukihiro Matsumoto over 1 year ago

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

Matz.

#10 Updated by Anonymous over 1 year ago

  • 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. [Feature #6177]

#11 Updated by Kazuhiro NISHIYAMA over 1 year ago

以下のようにすると 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

#12 Updated by Masaki Matsushita over 1 year ago

  • Status changed from Closed to Assigned

2012年11月3日 2:45 znz (Kazuhiro NISHIYAMA) redmine@ruby-lang.org:

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

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

#13 Updated by Masaki Matsushita over 1 year ago

  • Status changed from Assigned to Closed

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

Also available in: Atom PDF