From: "Glass_saga (Masaki Matsushita)" <glass.saga@...>
Date: 2012-03-20T20:29:27+09:00
Subject: [ruby-dev:45414] [ruby-trunk - Feature #6177] array.cのrb_ary_equal()の高速化


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


-- 
http://bugs.ruby-lang.org/