Project

General

Profile

Actions

Feature #6177

closed

array.cのrb_ary_equal()の高速化

Added by Glass_saga (Masaki Matsushita) about 10 years ago. Updated over 9 years ago.

Status:
Closed
Priority:
Normal
Target version:
[ruby-dev:45412]

Description

できる限り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を添付します。


Files

patch.diff (571 Bytes) patch.diff Glass_saga (Masaki Matsushita), 03/20/2012 12:08 PM
patch2.diff (575 Bytes) patch2.diff Glass_saga (Masaki Matsushita), 03/20/2012 08:29 PM
patch3.diff (834 Bytes) patch3.diff Glass_saga (Masaki Matsushita), 03/20/2012 11:34 PM
patch4.diff (764 Bytes) patch4.diff Glass_saga (Masaki Matsushita), 03/22/2012 11:37 AM

Updated by nobu (Nobuyoshi Nakada) about 10 years ago

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

Updated by Glass_saga (Masaki Matsushita) about 10 years ago

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

Updated by nobu (Nobuyoshi Nakada) about 10 years ago

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

Updated by nobu (Nobuyoshi Nakada) about 10 years ago

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

Updated by Glass_saga (Masaki Matsushita) about 10 years ago

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

Updated by nobu (Nobuyoshi Nakada) about 10 years ago

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)) じゃないでしょうか。

Updated by Glass_saga (Masaki Matsushita) about 10 years ago

Nobuyoshi Nakada wrote:

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

そのようです。

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

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

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

Updated by mame (Yusuke Endoh) about 10 years ago

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

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

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

--
Yusuke Endoh

Updated by matz (Yukihiro Matsumoto) over 9 years ago

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

Matz.

Actions #10

Updated by Anonymous over 9 years 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.


Updated by znz (Kazuhiro NISHIYAMA) over 9 years 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

Updated by Glass_saga (Masaki Matsushita) over 9 years ago

  • Status changed from Closed to Assigned

2012年11月3日 2:45 znz (Kazuhiro NISHIYAMA) :

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

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

Updated by Glass_saga (Masaki Matsushita) over 9 years ago

  • Status changed from Assigned to Closed

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

Actions

Also available in: Atom PDF