Feature #18515: Add Range#reverse_each implementation

• Status: Closed
• Assignee: -
• Target version: -

[kyanagi (Kouhei Yanagita)]

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

[kyanagi (Kouhei Yanagita)]

• Description updated (diff)

[kyanagi (Kouhei Yanagita)]

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.

[Dan0042 (Daniel DeLorme)]

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.

[kyanagi (Kouhei Yanagita)]

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.

[kyanagi (Kouhei Yanagita)]

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

[kyanagi (Kouhei Yanagita)]

• Description updated (diff)

[kyanagi (Kouhei Yanagita)]

• Subject changed from Add Range#reverse_each implementation for performance to Add Range#reverse_each implementation

[matz (Yukihiro Matsumoto)]

I accept this as a performance improvement.

Matz.

[kyanagi (Kouhei Yanagita)]

• Status changed from Open to Closed

Applied in changeset git|3f5ec5c8661748afb9cc3cbf1aff113d602e1fad.

---

[DOC] Add NEWS about Range#reverse_each for beginless ranges [Feature #18515]