ruby - 为什么有七个对象的新散列比六个长度的散列慢得多？

Question

我发现当我新建一个有七个对象的哈希比六个长度的哈希要慢得多。我知道散列的长度会影响性能。但我不知道为什么七是一个特殊的。

这里是基准代码(Ruby 2.2.3):

require 'benchmark/ips'

Benchmark.ips do |x|
  x.report(5) { { a: 0, b: 1, c: 2, d: 3, e: 4 } }
  x.report(6) { { a: 0, b: 1, c: 2, d: 3, e: 4, f: 5 } }
  x.report(7) { { a: 0, b: 1, c: 2, d: 3, e: 4, f: 5, g: 6 } }
  x.report(8) { { a: 0, b: 1, c: 2, d: 3, e: 4, f: 5, g: 6, h: 7 } }
  x.report(9) { { a: 0, b: 1, c: 2, d: 3, e: 4, f: 5, g: 6, h: 7, i: 8 } }

  x.compare!
end

打击就是结果:

Calculating -------------------------------------
                   5    65.986k i/100ms
                   6    63.966k i/100ms
                   7    30.713k i/100ms
                   8    28.991k i/100ms
                   9    27.115k i/100ms
-------------------------------------------------
                   5      1.243M (± 4.3%) i/s -      6.203M
                   6      1.202M (± 5.3%) i/s -      6.013M
                   7    373.366k (±13.7%) i/s -      1.843M
                   8    351.945k (± 8.8%) i/s -      1.768M
                   9    331.398k (± 8.2%) i/s -      1.654M

Comparison:
                   5:  1243005.5 i/s
                   6:  1202032.4 i/s - 1.03x slower
                   7:   373366.5 i/s - 3.33x slower
                   8:   351945.1 i/s - 3.53x slower
                   9:   331398.3 i/s - 3.75x slower

Answer 1

来自 Hash lookup in Ruby, why is it so fast? :

Ruby manages the size of the bins dynamically. It starts with 11 and as soon as one of the bins has 5 or more elements, the bin size is increased and all hash elements are reallocated to their new corresponding bin.

At some point you pay an exponentially increased time penalty while Ruby resizes the bin pool, but if you think about it, its worth the time since this will keep lookup times and memory usage as low as possible.

这意味着 bin 越多，在 bin 中查找特定键所花费的时间就越少。

希望它有助于理解行为。