jruby/jruby — pull request #1676 by grddev (2014-05-01 18:56:41+00:00)
Title: Empty hash optimization

While running some performance comparisons between MRI and JRuby, I realised that MRI (or at least new versions of) optimises access to empty hashes. For that purpose I implemented a small benchmark:

require 'benchmark'

N = 40_000
CHECK = 'x' * 20_000
OPERATIONS = [:[], :key?, :delete, :values_at]
SIZES = {
'empty' => { },
'small' => { 0 => 0, 1 => 1 },
}

class Detector
def hash
$hash_called = 1
end
end

puts RUBY_DESCRIPTION
Benchmark.bmbm(10) do |x|
OPERATIONS.each do |op|
SIZES.each do |name, hash|
$hash_called = 0
hash.send(op, Detector.new)
x.report("#{name}\##{op} #{$hash_called}") { N.times { hash.send(op, CHECK) } }
end
end
end

In addition to checking the performance of a few operations against an empty and a small Hash, it also tries the operation with a `Detector` instance, which has a side-effect in its `#hash` method in order to detect wether the method is actually called or not in the different Ruby versions I tested.

The pull request consists of two commits, one which implements the general performance tweak (which would certainly be enough for master) and another which strives to restrict the optimisation to the behaviour of the emulated MRI version. The solution is not perfect, but I'm also not sure it is even worthwhile to emulate the behaviour in this case. I strongly suspect that the number of times the `#hash` function is called is not part of any meaningful contract for `Hash`.

The JRuby behaviour without this pull request is in line with MRI 1.8.7, but is technically wrong for 1.9.3 and beyond (I don't have any versions between 1.8.7 and 1.9.3 to verify exactly when MRI implemented their change). Personally, I would vote for implementing the performance tweak independent of version, and potentially break an implementation relying on `#hash` side effects.

Below are results first for JRuby 1.7.2, and then after that MRI versions 1.8.7, 1.9.3, and 2.0.0 followed by their emulated counterparts with the pull request applied.

jruby 1.7.12 (1.9.3p392) 2014-04-15 643e292 on Java HotSpot(TM) 64-Bit Server VM 1.7.0_40-b40 [darwin-x86_64]

user system total real
empty#[] 1 3.190000 0.000000 3.190000 ( 3.199000)
small#[] 1 3.160000 0.010000 3.170000 ( 3.166000)
empty#key? 1 3.110000 0.010000 3.120000 ( 3.110000)
small#key? 1 3.150000 0.010000 3.160000 ( 3.160000)
empty#delete 1 3.230000 0.010000 3.240000 ( 3.241000)
small#delete 1 3.530000 0.010000 3.540000 ( 3.545000)
empty#values_at 1 3.370000 0.010000 3.380000 ( 3.402000)
small#values_at 1 3.260000 0.010000 3.270000 ( 3.253000)

ruby 2.0.0p451 (2014-02-24 revision 45167) [x86_64-darwin12.5.0]

user system total real
empty#[] 0 0.010000 0.000000 0.010000 ( 0.009584)
small#[] 1 0.740000 0.000000 0.740000 ( 0.746104)
empty#key? 0 0.010000 0.000000 0.010000 ( 0.005490)
small#key? 1 0.750000 0.000000 0.750000 ( 0.752317)
empty#delete 0 0.000000 0.000000 0.000000 ( 0.006898)
small#delete 1 0.780000 0.000000 0.780000 ( 0.788203)
empty#values_at 0 0.000000 0.000000 0.000000 ( 0.008107)
small#values_at 1 0.780000 0.010000 0.790000 ( 0.782744)

jruby 1.7.13-SNAPSHOT (2.0.0p195) 2014-05-01 68d4185 on Java HotSpot(TM) 64-Bit Server VM 1.7.0_40-b40 [darwin-x86_64]

user system total real
empty#[] 0 0.020000 0.000000 0.020000 ( 0.014000)
small#[] 1 3.170000 0.010000 3.180000 ( 3.178000)
empty#key? 0 0.010000 0.000000 0.010000 ( 0.008000)
small#key? 1 3.160000 0.010000 3.170000 ( 3.168000)
empty#delete 0 0.000000 0.000000 0.000000 ( 0.008000)
small#delete 1 3.080000 0.010000 3.090000 ( 3.090000)
empty#values_at 0 0.010000 0.000000 0.010000 ( 0.015000)
small#values_at 1 3.090000 0.010000 3.100000 ( 3.090000)

ruby 1.9.3p545 (2014-02-24 revision 45159) [x86_64-darwin13.1.0]

user system total real
empty#[] 0 0.830000 0.000000 0.830000 ( 0.827847)
small#[] 1 0.840000 0.000000 0.840000 ( 0.838575)
empty#key? 0 0.820000 0.000000 0.820000 ( 0.823376)
small#key? 1 0.800000 0.000000 0.800000 ( 0.799500)
empty#delete 1 0.800000 0.000000 0.800000 ( 0.804521)
small#delete 1 0.830000 0.010000 0.840000 ( 0.829005)
empty#values_at 1 0.830000 0.000000 0.830000 ( 0.835925)
small#values_at 1 0.810000 0.000000 0.810000 ( 0.812079)

jruby 1.7.13-SNAPSHOT (1.9.3p392) 2014-05-01 68d4185 on Java HotSpot(TM) 64-Bit Server VM 1.7.0_40-b40 [darwin-x86_64]

user system total real
empty#[] 0 0.010000 0.000000 0.010000 ( 0.010000)
small#[] 1 3.160000 0.010000 3.170000 ( 3.163000)
empty#key? 0 0.010000 0.000000 0.010000 ( 0.008000)
small#key? 1 3.130000 0.000000 3.130000 ( 3.136000)
empty#delete 1 3.160000 0.010000 3.170000 ( 3.176000)
small#delete 1 3.180000 0.010000 3.190000 ( 3.186000)
empty#values_at 0 0.020000 0.000000 0.020000 ( 0.020000)
small#values_at 1 3.160000 0.010000 3.170000 ( 3.176000)

ruby 1.8.7 (2013-06-27 patchlevel 374) [i686-darwin13.1.0]

user system total real
empty#[] 1 1.580000 0.000000 1.580000 ( 1.585427)
small#[] 1 1.660000 0.000000 1.660000 ( 1.663023)
empty#key? 1 1.620000 0.000000 1.620000 ( 1.624190)
small#key? 1 1.600000 0.010000 1.610000 ( 1.602030)
empty#delete 1 1.630000 0.000000 1.630000 ( 1.635427)
small#delete 1 1.710000 0.000000 1.710000 ( 1.711169)
empty#values_at 1 1.650000 0.000000 1.650000 ( 1.656964)
small#values_at 1 1.620000 0.000000 1.620000 ( 1.618939)

jruby 1.7.13-SNAPSHOT (ruby-1.8.7p370) 2014-05-01 68d4185 on Java HotSpot(TM) 64-Bit Server VM 1.7.0_40-b40 [darwin-x86_64]

user system total real
empty#[] 1 3.120000 0.000000 3.120000 ( 3.121000)
small#[] 1 3.100000 0.010000 3.110000 ( 3.110000)
empty#key? 1 3.070000 0.000000 3.070000 ( 3.076000)
small#key? 1 3.070000 0.010000 3.080000 ( 3.083000)
empty#delete 1 3.120000 0.000000 3.120000 ( 3.119000)
small#delete 1 3.030000 0.010000 3.040000 ( 3.036000)
empty#values_at 1 3.090000 0.000000 3.090000 ( 3.094000)
small#values_at 1 3.160000 0.010000 3.170000 ( 3.145000)