Feature #8707
Hash#reverse_each
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
Updated by matz (Yukihiro Matsumoto) over 7 years ago
- Status changed from Open to Feedback
Do we really need it? What is use-cases?
Matz.
Updated by Anonymous over 7 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-40769Author: Glass_saga (Masaki Matsushita)
Status: Feedback
Priority: Normal
Assignee:
Category: core
Target version: current: 2.1.0Currently, {}.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
endresult:
trunk(r42256):
Rehearsal -----------------------------------------------------
Hash#reverse_each 1.210000 0.000000 1.210000 ( 1.207964)
-------------------------------------------- total: 1.210000secuser system total realHash#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.600000secuser system total realHash#reverse_each 0.450000 0.000000 0.450000 ( 0.459006)
Updated by duerst (Martin Dürst) over 7 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-40769Author: Glass_saga (Masaki Matsushita)
Status: Feedback
Priority: Normal
Assignee:
Category: core
Target version: current: 2.1.0Currently, {}.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
endresult:
trunk(r42256):
Rehearsal -----------------------------------------------------
Hash#reverse_each 1.210000 0.000000 1.210000 ( 1.207964)
-------------------------------------------- total: 1.210000secuser system total realHash#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.600000secuser system total realHash#reverse_each 0.450000 0.000000 0.450000 ( 0.459006)
Updated by ko1 (Koichi Sasada) over 7 years ago
- Assignee set to matz (Yukihiro Matsumoto)
Updated by funny_falcon (Yura Sokolov) over 7 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 7 years ago
- Target version changed from 2.1.0 to 2.2.0
Updated by trans (Thomas Sawyer) almost 7 years ago
Can #reverse
be an Enumerator?