Feature #8707: Hash#reverse_each

• Status: Feedback
• Assignee: matz (Yukihiro Matsumoto)
• Target version: -

[Glass_saga (Masaki Matsushita)]

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)

[matz (Yukihiro Matsumoto)]

• Status changed from Open to Feedback

Do we really need it? What is use-cases?

Matz.

Matz: This is quite a significant performance improvement and therefore I think it is worthwhile.

[duerst (Martin Dürst)]

Hello Charlie,

On 2013/07/31 14:24, Charlie Somerville wrote:

Matz: This is quite a significant performance improvement and therefore I think it is worthwhile.

Only if the new method is actually used in practice.
That's why Matz is asking for use cases.

Regards, Martin.

[ko1 (Koichi Sasada)]

• Assignee set to matz (Yukihiro Matsumoto)

[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.delete k
    @hash[k] = v
  end

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

  def first
    @hash.first
  end

  def shift
    @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

[hsbt (Hiroshi SHIBATA)]

• Target version changed from 2.1.0 to 2.2.0

[trans (Thomas Sawyer)]

Can #reverse be an Enumerator?

[naruse (Yui NARUSE)]

• Target version deleted (2.2.0)

[bughit (bug hit)]

Do we really need it? What is use-cases?

When you have an ordered collection it seems self evident that you may need to iterate in reverse. This would for example back a performant last(n = 1) method (#12165)

Would you demand to know why one may want the last n elements of an array? These are both ordered collections, if last(n = 1) makes sense for one, it makes sense for the other.

Why is this closed with a status of "Feedback"?
It seems all feedback issues are labeled as closed which seems confusing.

[bughit (bug hit)]

Another point is that that hash.reverse_each already exists via enumerable, but with a highly suboptimal array conversion. If it didn't exist you could perhaps debate whether it should be added, but that's moot at this point. The only question here is whether hash.reverse_each should be a hidden perf land-mine or have an optimal implementation for a Hash. Seems like a no-brainer.

[nobu (Nobuyoshi Nakada)]

• Description updated (diff)