Use Hash#each_key instead of Hash#keys.each

[sferik]

Hash#keys.each allocates an array of keys; Hash#each_key iterates through the keys without allocating a new array. This is the reason why Hash#each_key exists.

This is a more comprehensive pull request that closes #17083.

Benchmark

require 'benchmark/ips'

HASH = Hash[*('aa'..'zz')]

def slow
  HASH.keys.each { |k| k }
end

def fast
  HASH.each_key { |k| k }
end

Benchmark.ips do |x|
  x.report('slow') { slow }
  x.report('fast') { fast }
end

slow 34702.1 (±9.8%) i/s - 172725 in 5.074038s
fast 46103.3 (±8.1%) i/s - 232512 in 5.076248s

[rafaelfranca]

Have you measured this case? I believe this will create fibers that may make it slower than the previous implementation.

[sferik]

Not yet. I will benchmark it now and remove this part of the commit if it is not performant.

[sferik]

@rafaelfranca Here’s the benchmark for this case. Looks to be about the same to me. Maybe slightly faster than before, but within the margin of error. Let me know if you prefer it the way it was before.

require 'benchmark/ips'

HASH = Hash[*('aa'..'zz')]

def slow
  HASH.keys.each_with_object({}) { |k, o|  o[k] = true }
end

def fast
  HASH.each_key.with_object({}) { |k, o|  o[k] = true }
end

Benchmark.ips do |x|
  x.report('slow') { fast }
  x.report('fast') { slow }
end

Ruby 2.1.2p95

slow 6299.5 (±33.7%) i/s - 26784 in 5.030937s
fast 7205.2 (±35.8%) i/s - 30912 in 5.105253s

[rafaelfranca]

Looks good this way

[fxn]

👍 each_key is concise and defined precisely for writing those loops in an efficient way. Good to merge in my view if CI is green.

[rafaelfranca]

For some reason build is red. Could you take a look?

[sferik]

@rafaelfranca There were a few cases where we were calling Hash#delete on keys inside an each block, which requires iterating on a separate object. I’ve reverted those cases and will push up the changes to force another build.

[robin850]

Thanks @sferik ! ❤️

[pkmiec]

For some reason I get opposite results from @sferik on ruby 2.1.2p95 for this particular benchmark,

                slow    66474.0 (±4.3%) i/s -     336042 in   5.064553s
                fast    49346.4 (±2.6%) i/s -     247884 in   5.026833s

For all other of these micro optimizations I tried, my benchmarks results match @sferik , but not this one. Not sure why. Has anyone ran this benchmark?

[mathieul]

@pkmiec I ran the same benchmark using ruby 2.1.3p242 and also get the opposite result:

            slow    50025.2 (±4.3%) i/s -     250128 in   5.009174s
            fast    39317.0 (±3.9%) i/s -     199545 in   5.083461s

I should also include similar results for 2.1.2-p95:

            slow    49820.7 (±4.9%) i/s -     251424 in   5.058657s
            fast    39323.8 (±3.9%) i/s -     197236 in   5.023135s

[sferik]

It’s possible I made a mistake. 😳

On CRuby 1.9.3p545 and 2.0.0p481 and JRuby 1.7.16, the fast method is faster. For some reason, this is reversed on Ruby 2.1.2. I’m going to dive in to the CRuby source code and try to figure out why.

[pkmiec]

@sferik I'm curious to find out the reason for this. Please let us know if you have a chance to figure it out.

[sferik]

If you compare the benchmark between MRI 2.1 and 2.0, the performance of Hash#each_key stayed the same but Hash#keys.each improved significantly between those two releases.

As far as I can tell, this improvement is a result of this change to use the RARRAY_CONST_PTR macro (via RARRAY_AREF) instead of RARRAY_PTR. By using a read-only pointer, it can avoid a write-barrier check. In Ruby 2.0.0, there’s obviously no write-barrier check, but there was a similar embed-flag check.

In theory, a similar optimization could be made in the rb_hash_each_key function in hash.c. This function calls the general-purpose rb_hash_foreach with each_key_i, which takes a key and a value (for consistency) but doesn’t do anything with the value. Not sure if the C-compiler is smart enough to optimize that away. The rb_hash_foreach function itself seems rather inefficient for this particular usage, creating a hash_foreach_arg struct. I’m guessing that’s the overhead that makes each_key relatively slower in Ruby 2.1.

Please keep in mind that I’m not a expert with C code, in general, or CRuby, in particular, so I may be reading this wrong.