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)