range.c: optimize rb_range_last for int renage

This change improves the performance of Range#last method for a range
of integer.  This optimization directly computes only required values
only in a range instead of converting all values in the range to an
array.  The optimized implementation is 129-16.7k times faster than
the previous one in the benchmark result given below.

=== Benchmark Result ===

```
$ make benchmark ITEM=range_last COMPARE_RUBY=/Users/mrkn/.rbenv/versions/2.6.0/bin/ruby
generating known_errors.inc
known_errors.inc unchanged
/Users/mrkn/src/github.com/ruby/ruby/revision.h unchanged
/Users/mrkn/.rbenv/shims/ruby --disable=gems -rrubygems -I/Users/mrkn/src/github.com/ruby/ruby/benchmark/lib /Users/mrkn/src/github.com/ruby/ruby/benchmark/benchmark-driver/exe/benchmark-driver \
                    --executables="compare-ruby::/Users/mrkn/.rbenv/versions/2.6.0/bin/ruby -I.ext/common --disable-gem" \
                    --executables="built-ruby::./miniruby -I/Users/mrkn/src/github.com/ruby/ruby/lib -I. -I.ext/common  -r/Users/mrkn/src/github.com/ruby/ruby/prelude --disable-gem" \
                    $(find /Users/mrkn/src/github.com/ruby/ruby/benchmark -maxdepth 1 -name '*range_last*.yml' -o -name '*range_last*.rb' | sort)
Warming up --------------------------------------
  (1..1_000_000).last(100)       35.600 i/s -      36.000 times in 1.011239s (28.09ms/i)
 (1..1_000_000).last(1000)       36.204 i/s -      39.000 times in 1.077240s (27.62ms/i)
(1..1_000_000).last(10000)       36.470 i/s -      39.000 times in 1.069386s (27.42ms/i)
Calculating -------------------------------------
                           compare-ruby  built-ruby
  (1..1_000_000).last(100)       36.477    609.196k i/s -     106.000 times in 2.905950s 0.000174s
 (1..1_000_000).last(1000)       35.936     50.350k i/s -     108.000 times in 3.005321s 0.002145s
(1..1_000_000).last(10000)       35.641      4.602k i/s -     109.000 times in 3.058233s 0.023685s

Comparison:
               (1..1_000_000).last(100)
                built-ruby:    609195.7 i/s
              compare-ruby:        36.5 i/s - 16700.87x  slower

              (1..1_000_000).last(1000)
                built-ruby:     50349.7 i/s
              compare-ruby:        35.9 i/s - 1401.08x  slower

             (1..1_000_000).last(10000)
                built-ruby:      4602.1 i/s
              compare-ruby:        35.6 i/s - 129.12x  slower
```

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@66734 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

1 files changed, 61 insertions, 0 deletions

diff --git a/range.c b/range.c
index ac9affd872..77b1d7b25d 100644
--- a/range.c
+++ b/range.c
@@ -11,6 +11,7 @@
 
 #include "internal.h"
 #include "id.h"
+#include <assert.h>
 
 #ifdef HAVE_FLOAT_H
 #include <float.h>
@@ -1005,6 +1006,58 @@ range_first(int argc, VALUE *argv, VALUE range)
     return ary[1];
 }
 
+static VALUE
+rb_int_range_last(int argc, VALUE *argv, VALUE range)
+{
+    static const VALUE ONE = INT2FIX(1);
+
+    VALUE b, e, len_1, len, nv, ary;
+    int x;
+    long n;
+
+    assert(argc > 0);
+
+    b = RANGE_BEG(range);
+    e = RANGE_END(range);
+    assert(RB_INTEGER_TYPE_P(b) && RB_INTEGER_TYPE_P(e));
+
+    x = EXCL(range);
+
+    len_1 = rb_int_minus(e, b);
+    if (FIXNUM_ZERO_P(len_1) || rb_num_negative_p(len_1)) {
+        return rb_ary_new_capa(0);
+    }
+
+    if (x) {
+        e = rb_int_minus(e, ONE);
+        len = len_1;
+    }
+    else {
+        len = rb_int_plus(len_1, ONE);
+    }
+
+    rb_scan_args(argc, argv, "1", &nv);
+    n = NUM2LONG(nv);
+    if (n < 0) {
+        rb_raise(rb_eArgError, "negative array size");
+    }
+
+    nv = LONG2NUM(n);
+    if (RTEST(rb_int_gt(nv, len))) {
+        nv = len;
+        n = NUM2LONG(nv);
+    }
+
+    ary = rb_ary_new_capa(n);
+    b = rb_int_minus(e, nv);
+    while (n) {
+        b = rb_int_plus(b, ONE);
+        rb_ary_push(ary, b);
+        --n;
+    }
+
+    return ary;
+}
 
 /*
  *  call-seq:
@@ -1026,10 +1079,18 @@ range_first(int argc, VALUE *argv, VALUE range)
 static VALUE
 range_last(int argc, VALUE *argv, VALUE range)
 {
+    VALUE b, e;
+
     if (NIL_P(RANGE_END(range))) {
         rb_raise(rb_eRangeError, "cannot get the last element of endless range");
     }
     if (argc == 0) return RANGE_END(range);
+
+    b = RANGE_BEG(range);
+    e = RANGE_END(range);
+    if (RB_INTEGER_TYPE_P(b) && RB_INTEGER_TYPE_P(e)) {
+        return rb_int_range_last(argc, argv, range);
+    }
     return rb_ary_last(argc, argv, rb_Array(range));
 }