Issue #6177 has been reported by Glass_saga (Masaki Matsushita). ---------------------------------------- Feature #6177: array.cのrb_ary_equal()の高速化 https://bugs.ruby-lang.org/issues/6177 Author: Glass_saga (Masaki Matsushita) Status: Open Priority: Normal Assignee: Category: core Target version: 2.0.0 できる限り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を添付します。
on 2012-03-20 04:08
on 2012-03-20 10:14
Issue #6177 has been updated by nobu (Nobuyoshi Nakada). 先頭だけではなく、同一オブジェクトかどうかを常に先に調べるようにするとどうなるでしょうか。 ---------------------------------------- Feature #6177: array.cのrb_ary_equal()の高速化 https://bugs.ruby-lang.org/issues/6177#change-24964 Author: Glass_saga (Masaki Matsushita) Status: Open Priority: Normal Assignee: Category: core Target version: 2.0.0 できる限り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を添付します。
on 2012-03-20 12:30
Issue #6177 has been updated by Glass_saga (Masaki Matsushita). File 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を添付します。 ---------------------------------------- Feature #6177: array.cのrb_ary_equal()の高速化 https://bugs.ruby-lang.org/issues/6177#change-24967 Author: Glass_saga (Masaki Matsushita) Status: Open Priority: Normal Assignee: Category: core Target version: 2.0.0 できる限り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を添付します。
on 2012-03-20 13:59
Issue #6177 has been updated by nobu (Nobuyoshi Nakada). rb_equal()はメソッドを呼び出すので、その後ではp1,p2が有効である保証がありません。 ---------------------------------------- Feature #6177: array.cのrb_ary_equal()の高速化 https://bugs.ruby-lang.org/issues/6177#change-24969 Author: Glass_saga (Masaki Matsushita) Status: Open Priority: Normal Assignee: Category: core Target version: 2.0.0 できる限り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を添付します。
on 2012-03-20 14:01
Issue #6177 has been updated by nobu (Nobuyoshi Nakada). もう一点、&&ではなく||ではないでしょうか。 ---------------------------------------- Feature #6177: array.cのrb_ary_equal()の高速化 https://bugs.ruby-lang.org/issues/6177#change-24970 Author: Glass_saga (Masaki Matsushita) Status: Open Priority: Normal Assignee: Category: core Target version: 2.0.0 できる限り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を添付します。
on 2012-03-20 15:35
Issue #6177 has been updated by Glass_saga (Masaki Matsushita). File 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を添付します。 ---------------------------------------- Feature #6177: array.cのrb_ary_equal()の高速化 https://bugs.ruby-lang.org/issues/6177#change-24972 Author: Glass_saga (Masaki Matsushita) Status: Open Priority: Normal Assignee: Category: core Target version: 2.0.0 できる限り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を添付します。
on 2012-03-20 16:24
Issue #6177 has been updated by 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)) じゃないでしょうか。 ---------------------------------------- Feature #6177: array.cのrb_ary_equal()の高速化 https://bugs.ruby-lang.org/issues/6177#change-24974 Author: Glass_saga (Masaki Matsushita) Status: Open Priority: Normal Assignee: Category: core Target version: 2.0.0 できる限り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を添付します。
on 2012-03-22 03:38
Issue #6177 has been updated by Glass_saga (Masaki Matsushita). File patch4.diff added Nobuyoshi Nakada wrote: >最も大きいのはrb_ary_elt()呼び出しのオーバーヘッドということのようですね。 そのようです。 >i != 0 なら常に (p1 != RARRAY_PTR(ary1)) じゃないでしょうか。 おっしゃる通りです… 凡ミスをやらかしてしまいました。 p1,p2が有効であるかどうかのチェックを止め、rb_equal()を呼び出したら有効なポインタを取得するようにしました。 ベンチマークの結果はpatch3.diffとほとんど変わりません。 ---------------------------------------- Feature #6177: array.cのrb_ary_equal()の高速化 https://bugs.ruby-lang.org/issues/6177#change-25035 Author: Glass_saga (Masaki Matsushita) Status: Open Priority: Normal Assignee: Category: core Target version: 2.0.0 できる限り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を添付します。
on 2012-03-29 19:34
Issue #6177 has been updated by mame (Yusuke Endoh). Status changed from Open to Assigned Assignee set to Glass_saga (Masaki Matsushita) 挙動が変わるわけでないならいいんじゃないですかね。 パッチ試してませんが見た感じいいような気がしました。 コミット権が貰えたら自分でどうぞ。#6173 もらえなかったら、どうしよう。 -- Yusuke Endoh <mame@tsg.ne.jp> ---------------------------------------- Feature #6177: array.cのrb_ary_equal()の高速化 https://bugs.ruby-lang.org/issues/6177#change-25408 Author: Glass_saga (Masaki Matsushita) Status: Assigned Priority: Normal Assignee: Glass_saga (Masaki Matsushita) Category: core Target version: 2.0.0 できる限り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を添付します。
on 2012-10-27 01:07
Issue #6177 has been updated by matz (Yukihiro Matsumoto). コミット権、さしあげます。cvs-admin at ruby-lang.org にssh2の公開鍵をgpgでサインして送ってください。 Matz. ---------------------------------------- Feature #6177: array.cのrb_ary_equal()の高速化 https://bugs.ruby-lang.org/issues/6177#change-31719 Author: Glass_saga (Masaki Matsushita) Status: Assigned Priority: Normal Assignee: Glass_saga (Masaki Matsushita) Category: core Target version: 2.0.0 できる限り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を添付します。
on 2012-11-02 18:46
Issue #6177 has been updated by 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
----------------------------------------
Feature #6177: array.cのrb_ary_equal()の高速化
https://bugs.ruby-lang.org/issues/6177#change-32246
Author: Glass_saga (Masaki Matsushita)
Status: Closed
Priority: Normal
Assignee: Glass_saga (Masaki Matsushita)
Category: core
Target version: 2.0.0
できる限り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を添付します。
on 2012-11-03 04:27
Issue #6177 has been updated by Glass_saga (Masaki Matsushita). Status changed from Closed to Assigned 2012年11月3日 2:45 znz (Kazuhiro NISHIYAMA) <redmine@ruby-lang.org>: > 以下のようにすると p1, p2 の操作で配列の範囲外にアクセスしてしまうようです。 > p1++ などのポインタ操作だけで参照までは行かなかったですが。 ご指摘ありがとうございます。 for文の継続条件に引っかかってくれるので実際に参照してしまう事はないのですが、不正なポインタを作ってしまうのは良くないですね。 修正します。 ---------------------------------------- Feature #6177: array.cのrb_ary_equal()の高速化 https://bugs.ruby-lang.org/issues/6177#change-32280 Author: Glass_saga (Masaki Matsushita) Status: Assigned Priority: Normal Assignee: Glass_saga (Masaki Matsushita) Category: core Target version: 2.0.0 できる限り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を添付します。
on 2012-11-03 04:29
Issue #6177 has been updated by Glass_saga (Masaki Matsushita). Status changed from Assigned to Closed r37438でrb_equal()後にArrayのサイズがiより小さくなっていない事をチェックするよう修正してコミットしました。 ---------------------------------------- Feature #6177: array.cのrb_ary_equal()の高速化 https://bugs.ruby-lang.org/issues/6177#change-32281 Author: Glass_saga (Masaki Matsushita) Status: Closed Priority: Normal Assignee: Glass_saga (Masaki Matsushita) Category: core Target version: 2.0.0 できる限り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を添付します。
Enable email notification
Enable multi-page viewPlease log in before posting. Registration is free and takes only a minute.
Existing account
(Switch to SSL-encrypted connection)
NEW: Do you have a Google/GoogleMail or Yahoo account? No registration required!
Log in with Google account | Log in with Yahoo account
Log in with Google account | Log in with Yahoo account
No account? Register here.