[ruby-trunk - Feature #6177][Open] array.cのrb ary equal()の高速化

Ruby Development
1

Issue #6177 has been reported by Glass_saga (Masaki M.).

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

Author: Glass_saga (Masaki M.)
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を添付します。

2

Issue #6177 has been updated by nobu (Nobuyoshi N.).

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

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

Author: Glass_saga (Masaki M.)
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を添付します。

3

Issue #6177 has been updated by Glass_saga (Masaki M.).

File patch2.diff added

Nobuyoshi N. 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()の高速化

Author: Glass_saga (Masaki M.)
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を添付します。

4

Issue #6177 has been updated by nobu (Nobuyoshi N.).

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

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

Author: Glass_saga (Masaki M.)
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を添付します。

5

Issue #6177 has been updated by nobu (Nobuyoshi N.).

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

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

Author: Glass_saga (Masaki M.)
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を添付します。

6

Issue #6177 has been updated by nobu (Nobuyoshi N.).

Glass_saga (Masaki M.) 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()の高速化

Author: Glass_saga (Masaki M.)
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を添付します。

7

Issue #6177 has been updated by Glass_saga (Masaki M.).

File patch3.diff added

Nobuyoshi N. 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()の高速化

Author: Glass_saga (Masaki M.)
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を添付します。

8

Issue #6177 has been updated by mame (Yusuke E.).

Status changed from Open to Assigned
Assignee set to Glass_saga (Masaki M.)

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

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

–
Yusuke E. [email protected]

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

Author: Glass_saga (Masaki M.)
Status: Assigned
Priority: Normal
Assignee: Glass_saga (Masaki M.)
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を添付します。

9

Issue #6177 has been updated by Glass_saga (Masaki M.).

File patch4.diff added

Nobuyoshi N. wrote:

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

そのようです。

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

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

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

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

Author: Glass_saga (Masaki M.)
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を添付します。

10

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()の高速化

Author: Glass_saga (Masaki M.)
Status: Closed
Priority: Normal
Assignee: Glass_saga (Masaki M.)
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を添付します。

11

Issue #6177 has been updated by matz (Yukihiro M.).

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

Matz.

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

Author: Glass_saga (Masaki M.)
Status: Assigned
Priority: Normal
Assignee: Glass_saga (Masaki M.)
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を添付します。

12

Issue #6177 has been updated by Glass_saga (Masaki M.).

Status changed from Closed to Assigned

2012年11月3日 2:45 znz (Kazuhiro NISHIYAMA) [email protected]:

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

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

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

Author: Glass_saga (Masaki M.)
Status: Assigned
Priority: Normal
Assignee: Glass_saga (Masaki M.)
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を添付します。

13

Issue #6177 has been updated by Glass_saga (Masaki M.).

Status changed from Assigned to Closed

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

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

Author: Glass_saga (Masaki M.)
Status: Closed
Priority: Normal
Assignee: Glass_saga (Masaki M.)
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を添付します。