Project

General

Profile

Actions

Feature #8707

closed

Hash#reverse_each

Added by Glass_saga (Masaki Matsushita) over 10 years ago. Updated 11 months ago.

Status:
Feedback
Target version:
-
[ruby-core:56270]

Description

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)

Files

patch.diff (7.55 KB) patch.diff Glass_saga (Masaki Matsushita), 07/30/2013 10:58 PM

Updated by matz (Yukihiro Matsumoto) over 10 years ago

  • Status changed from Open to Feedback

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

Matz.

Updated by Anonymous over 10 years ago

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

Updated by duerst (Martin Dürst) over 10 years ago

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.

Updated by ko1 (Koichi Sasada) over 10 years ago

  • Assignee set to matz (Yukihiro Matsumoto)

Updated by funny_falcon (Yura Sokolov) over 10 years ago

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

Updated by hsbt (Hiroshi SHIBATA) about 10 years ago

  • Target version changed from 2.1.0 to 2.2.0

Updated by trans (Thomas Sawyer) almost 10 years ago

Can #reverse be an Enumerator?

Actions #8

Updated by naruse (Yui NARUSE) about 6 years ago

  • Target version deleted (2.2.0)

Updated by bughit (bug hit) 11 months ago

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.

Updated by bughit (bug hit) 11 months ago

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.

Actions #11

Updated by nobu (Nobuyoshi Nakada) 11 months ago

  • Description updated (diff)
Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0