Forum: Ruby-core [ruby-trunk - Feature #8707][Open] Hash#reverse_each

C042517d59bed4761cc88681bf71fca8?d=identicon&s=25 Glass_saga (Masaki Matsushita) (Guest)
on 2013-07-30 15:59
(Received via mailing list)
Issue #8707 has been reported by Glass_saga (Masaki Matsushita).

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

Author: Glass_saga (Masaki Matsushita)
Status: Open
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)
0ec4920185b657a03edf01fff96b4e9b?d=identicon&s=25 matz (Yukihiro Matsumoto) (Guest)
on 2013-07-31 05:48
(Received via mailing list)
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)
Bcb6acc9d0d9bef99e033b36c3d32ca9?d=identicon&s=25 Charlie Somerville (Guest)
on 2013-07-31 07:25
(Received via mailing list)
Matz: This is quite a significant performance improvement and therefore
I think it is worthwhile.
F52e87b92cafb1e8c6d155076b56ecff?d=identicon&s=25 "Martin J. Dürst" <duerst@it.aoyama.ac.jp> (Guest)
on 2013-07-31 09:22
(Received via mailing list)
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.
C4e88907313843cf07f6d85ba8162120?d=identicon&s=25 ko1 (Koichi Sasada) (Guest)
on 2013-08-09 12:34
(Received via mailing list)
Issue #8707 has been updated by ko1 (Koichi Sasada).

Assignee set to matz (Yukihiro Matsumoto)


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

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)
419b54e4b0c805f8ed671451ea536e19?d=identicon&s=25 Yura Sokolov (funny_falcon)
on 2013-08-10 11:19
(Received via mailing list)
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)
Eabad423977cfc6873b8f5df62b848a6?d=identicon&s=25 unknown (Guest)
on 2014-01-30 07:25
(Received via mailing list)
Issue #8707 has been updated by Hiroshi SHIBATA.

Target version changed from 2.1.0 to current: 2.2.0

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

* Author: Masaki Matsushita
* Status: Feedback
* Priority: Normal
* Assignee: Yukihiro Matsumoto
* Category: core
* Target version: current: 2.2.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)

---Files--------------------------------
patch.diff (7.55 KB)
45196398e9685000d195ec626d477f0e?d=identicon&s=25 Thomas Sawyer (7rans)
on 2014-04-11 20:24
(Received via mailing list)
Issue #8707 has been updated by Thomas Sawyer.


Can `#reverse` be an Enumerator?

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

* Author: Masaki Matsushita
* Status: Feedback
* Priority: Normal
* Assignee: Yukihiro Matsumoto
* Category: core
* Target version: current: 2.2.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)

---Files--------------------------------
patch.diff (7.55 KB)
This topic is locked and can not be replied to.