summaryrefslogtreecommitdiff
path: root/range.c
diff options
context:
space:
mode:
authormrkn <mrkn@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2019-01-06 00:46:36 +0000
committermrkn <mrkn@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2019-01-06 00:46:36 +0000
commit6e1d498ac7cd6fcd18352a22d8a3e3ed19df9c6b (patch)
treea40eaa640e16c70ae53f00e88b9f635845e5d8a7 /range.c
parentbf6584b5d0f88377ed448612e1170716f6f7dc83 (diff)
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
Diffstat (limited to 'range.c')
-rw-r--r--range.c61
1 files changed, 61 insertions, 0 deletions
diff --git a/range.c b/range.c
index ac9affd8728..77b1d7b25d4 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));
}