Feature #8707

Hash#reverse_each

Added by Masaki Matsushita almost 2 years ago. Updated about 1 year ago.

[ruby-core:56270]
Status:Feedback
Priority:Normal
Assignee:Yukihiro Matsumoto

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)

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

History

#1 Updated by Yukihiro Matsumoto almost 2 years ago

  • Status changed from Open to Feedback

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

Matz.

#2 Updated by Anonymous almost 2 years ago

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

On 30/07/2013, at 20:48, "matz (Yukihiro Matsumoto)" matz@ruby-lang.org wrote:

Issue #8707 has been updated by matz (Yukihiro Matsumoto).

Status changed from Open to Feedback

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

Matz.


Feature #8707: Hash#reverse_each
https://bugs.ruby-lang.org/issues/8707#change-40769

Author: Glass_saga (Masaki Matsushita)
Status: Feedback
Priority: Normal
Assignee:
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/

#3 Updated by Martin Dürst almost 2 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.

On 30/07/2013, at 20:48, "matz (Yukihiro Matsumoto)"matz@ruby-lang.org wrote:

Issue #8707 has been updated by matz (Yukihiro Matsumoto).

Status changed from Open to Feedback

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

Matz.


Feature #8707: Hash#reverse_each
https://bugs.ruby-lang.org/issues/8707#change-40769

Author: Glass_saga (Masaki Matsushita)
Status: Feedback
Priority: Normal
Assignee:
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/

#4 Updated by Koichi Sasada almost 2 years ago

  • Assignee set to Yukihiro Matsumoto

#5 Updated by Yura Sokolov almost 2 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

#6 Updated by Hiroshi SHIBATA over 1 year ago

  • Target version changed from 2.1.0 to current: 2.2.0

#7 Updated by Thomas Sawyer about 1 year ago

Can #reverse be an Enumerator?

Also available in: Atom PDF