Project

General

Profile

Actions

Feature #18515

closed

Add Range#reverse_each implementation

Added by kyanagi (Kouhei Yanagita) over 2 years ago. Updated 7 months ago.

Status:
Closed
Assignee:
-
Target version:
-
[ruby-core:107285]

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

Actions #1

Updated by kyanagi (Kouhei Yanagita) over 2 years ago

  • Description updated (diff)

Updated by kyanagi (Kouhei Yanagita) over 2 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) over 2 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) over 2 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) 8 months 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
Actions #6

Updated by kyanagi (Kouhei Yanagita) 8 months ago

  • Description updated (diff)
Actions #7

Updated by kyanagi (Kouhei Yanagita) 8 months ago

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

Updated by matz (Yukihiro Matsumoto) 8 months ago

I accept this as a performance improvement.

Matz.

Actions #9

Updated by kyanagi (Kouhei Yanagita) 7 months ago

  • Status changed from Open to Closed

Applied in changeset git|3f5ec5c8661748afb9cc3cbf1aff113d602e1fad.


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

Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0Like0Like0Like0Like0