diff options
author | mrkn <mrkn@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2019-01-06 00:46:36 +0000 |
---|---|---|
committer | mrkn <mrkn@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2019-01-06 00:46:36 +0000 |
commit | 6e1d498ac7cd6fcd18352a22d8a3e3ed19df9c6b (patch) | |
tree | a40eaa640e16c70ae53f00e88b9f635845e5d8a7 | |
parent | bf6584b5d0f88377ed448612e1170716f6f7dc83 (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
-rw-r--r-- | range.c | 61 |
1 files changed, 61 insertions, 0 deletions
@@ -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)); } |