Feature #8707
closed
Added by Glass_saga (Masaki Matsushita) about 11 years ago.
Updated over 1 year ago.
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
- 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.
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.
- Assignee set to matz (Yukihiro Matsumoto)
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
- Target version changed from 2.1.0 to 2.2.0
Can #reverse
be an Enumerator?
- Target version deleted (
2.2.0)
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.
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.
- Description updated (diff)
Also available in: Atom
PDF
Like0
Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0