Feature #18515
closedAdd Range#reverse_each implementation
Description
PR is https://github.com/ruby/ruby/pull/5489 https://github.com/ruby/ruby/pull/8525
Current Range#reverse_each
uses Enumerable#reverse_each
which is implemented with #to_a
.
So we are virtually not able to use reverse_each
for a very large or beginless range, even if few elements are iterated on actually.
(1..2**100).reverse_each { |x| p x; break if x.odd? }
(..5).reverse_each { |x| p x; break if x == 0 }
(1..2**32).reverse_each.lazy.select { |x| Prime.prime?(x) }.take(3).to_a
This patch, implements Range#reverse_each
for Integer elements, enables these examples.
I think #reverse_each
for an endless range should raise an exception.
This is a different issue, so I'll create another ticket later.
-> posted: https://bugs.ruby-lang.org/issues/18551
Updated by kyanagi (Kouhei Yanagita) almost 3 years ago
- Description updated (diff)
Updated by kyanagi (Kouhei Yanagita) almost 3 years ago
In general, I think it would be better to improve #reverse_each
by using #pred
(predecessor; the inverse of #succ
) if the element has.
However, since integer ranges are used so often, I think it is acceptable to add specialized implementation to Range.
Updated by Dan0042 (Daniel DeLorme) almost 3 years ago
kyanagi (Kouhei Yanagita) wrote in #note-2:
In general, I think it would be better to improve
#reverse_each
by using#pred
(predecessor; the inverse of#succ
) if the element has.However, since integer ranges are used so often, I think it is acceptable to add specialized implementation to Range.
I agree with both of those statements, but Integer is the only class that has #pred, so in practice "using pred" and "specialized implementation for Integer" are the same thing. Maybe Date could benefit from having #pred (and by extension an optimized #reverse_each implementation) but I can't think of any other core classes to which this would apply.
Updated by kyanagi (Kouhei Yanagita) almost 3 years ago
Dan0042 (Daniel DeLorme) wrote in #note-3:
I agree with both of those statements, but Integer is the only class that has #pred, so in practice "using pred" and "specialized implementation for Integer" are the same thing.
Yes, that is exactly what you said.
If I propose #pred
-based Range#reverse_each
, I will propose Date#pred
too.
To find out my PR implementation (iterating integers directly) is worthwhile even if a #pred
-based implementation is introduced,
we will need to measure the performance. I'll try it later.
Updated by kyanagi (Kouhei Yanagita) about 1 year ago
Let's set aside #pred
for now to avoid going off track.
I have created a new pull request with a simpler implementation and closed the old one.
New PR: https://github.com/ruby/ruby/pull/8525
As benchmark results show, huge memory savings are achieved, especially for large Range
.
Execution speed is also increased.
prelude: |
rf_1 = 0..1
rf_1k = 0..1000
rf_1m = 0..1000000
big = 2**1000
rb_1 = big..big+1
rb_1k = big..big+1000
rb_1m = big..big+1000000
benchmark:
"Fixnum 1": rf_1.reverse_each { _1 }
"Fixnum 1K": rf_1k.reverse_each { _1 }
"Fixnum 1M": rf_1m.reverse_each { _1 }
"Bignum 1": rb_1.reverse_each { _1 }
"Bignum 1K": rb_1k.reverse_each { _1 }
"Bignum 1M": rb_1m.reverse_each { _1 }
Max resident set size (bytes)¶
master | PR | ratio | |
---|---|---|---|
Fixnum 1 | 13.910M | 14.877M | 1.069 |
Fixnum 1K | 14.778M | 14.762M | 0.998 |
Fixnum 1M | 28.770M | 14.025M | 0.487 |
Bignum 1 | 14.729M | 14.189M | 0.963 |
Bignum 1K | 14.074M | 13.582M | 0.965 |
Bignum 1M | 224.723M | 15.254M | 0.067 |
Iteration per second (i/s)¶
master | PR | ratio | |
---|---|---|---|
Fixnum 1 | 6.653M | 14.511M | 2.181 |
Fixnum 1K | 27.866k | 45.527k | 1.633 |
Fixnum 1M | 28.659 | 45.667 | 1.593 |
Bignum 1 | 3.534M | 4.635M | 1.311 |
Bignum 1K | 6.790k | 7.693k | 1.132 |
Bignum 1M | 5.720 | 7.532 | 1.316 |
Updated by kyanagi (Kouhei Yanagita) about 1 year ago
- Description updated (diff)
Updated by kyanagi (Kouhei Yanagita) about 1 year ago
- Subject changed from Add Range#reverse_each implementation for performance to Add Range#reverse_each implementation
Updated by matz (Yukihiro Matsumoto) about 1 year ago
I accept this as a performance improvement.
Matz.
Updated by kyanagi (Kouhei Yanagita) about 1 year ago
- Status changed from Open to Closed
Applied in changeset git|3f5ec5c8661748afb9cc3cbf1aff113d602e1fad.
[DOC] Add NEWS about Range#reverse_each for beginless ranges [Feature #18515]