[ruby-core:56508] [ruby-trunk - Feature #8707] Hash#reverse_each

Issue #8707 has been updated by funny_falcon (Yura Sokolov).


Hash in Ruby1.9+ is hash table + double linked list - this is classic structure for LRU cache.

Simple LRU cache could be build with:

    class LRU
      def initialize
        @hash = {}
      end

      def []=(k, v)
        @hash[k] = v
      end

      def [](k)
        if v = @hash.delete k
          @hash[k] = v
        end
        v
      end

      def pop_stale
        @hash.shift
      end
      
      # saves tail items until first stale item signaled
      def drop_stale
        save = true
        stale = []
        @hash.reverse_each{|k, v|
          unless save && yield(k, v)
            save = false
            v = @hash.delete k
            stale << [k, v]
          end
        }
        stale
      end
    end

So that, reverse_each is very critical to be fast at this point
----------------------------------------
Feature #8707: Hash#reverse_each
https://bugs.ruby-lang.org/issues/8707#change-41062

Author: Glass_saga (Masaki Matsushita)
Status: Feedback
Priority: Normal
Assignee: matz (Yukihiro Matsumoto)
Category: core
Target version: current: 2.1.0


Currently, {}.reverse_each calls Enumerable#reverse_each.
It will make array and its size can be large.
I made Hash#reverse_each to avoid array creation and performance improvement.

benchmark:

require "benchmark"

Size = 10000
HASH = Hash[*Array.new(Size) {|i| [i, true] }.flatten]

Benchmark.bmbm do |x|
  x.report("Hash#reverse_each") do
    300.times do
      HASH.reverse_each {|a, b|}
    end
  end
end

result:

trunk(r42256):
Rehearsal -----------------------------------------------------
Hash#reverse_each   1.210000   0.000000   1.210000 (  1.207964)
-------------------------------------------- total: 1.210000sec

                        user     system      total        real
Hash#reverse_each   0.950000   0.000000   0.950000 (  0.951069)

proposal: 
Rehearsal -----------------------------------------------------
Hash#reverse_each   0.600000   0.000000   0.600000 (  0.600242)
-------------------------------------------- total: 0.600000sec

                        user     system      total        real
Hash#reverse_each   0.450000   0.000000   0.450000 (  0.459006)


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