From a63f520971787aa7b32b27486e9a5bb732d2814e Mon Sep 17 00:00:00 2001
From: Kenta Murata <mrkn@users.noreply.github.com>
Date: Sat, 18 Jul 2020 23:45:00 +0900
Subject: Optimize Array#max (#3325)

The benchmark result is below:

|                |compare-ruby|built-ruby|
|:---------------|-----------:|---------:|
|ary2.max        |     38.837M|   40.830M|
|                |           -|     1.05x|
|ary10.max       |     23.035M|   32.626M|
|                |           -|     1.42x|
|ary100.max      |      5.490M|   11.020M|
|                |           -|     2.01x|
|ary500.max      |      1.324M|    2.679M|
|                |           -|     2.02x|
|ary1000.max     |    699.167k|    1.403M|
|                |           -|     2.01x|
|ary2000.max     |    284.321k|  570.446k|
|                |           -|     2.01x|
|ary3000.max     |    282.613k|  571.683k|
|                |           -|     2.02x|
|ary5000.max     |    145.120k|  285.546k|
|                |           -|     1.97x|
|ary10000.max    |     72.102k|  142.831k|
|                |           -|     1.98x|
|ary20000.max    |     36.065k|   72.077k|
|                |           -|     2.00x|
|ary50000.max    |     14.343k|   29.139k|
|                |           -|     2.03x|
|ary100000.max   |      7.586k|   14.472k|
|                |           -|     1.91x|
|ary1000000.max  |     726.915|    1.495k|
|                |           -|     2.06x|
---
 array.c | 113 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 106 insertions(+), 7 deletions(-)

(limited to 'array.c')

diff --git a/array.c b/array.c
index 7d1fdf2e34..5fed5e5788 100644
--- a/array.c
+++ b/array.c
@@ -6177,6 +6177,95 @@ rb_ary_union_multi(int argc, VALUE *argv, VALUE ary)
     return ary_union;
 }
 
+static VALUE
+ary_max_generic(VALUE ary, long i, VALUE vmax)
+{
+    RUBY_ASSERT(i > 0 && i < RARRAY_LEN(ary));
+
+    VALUE v;
+    for (; i < RARRAY_LEN(ary); ++i) {
+        v = RARRAY_AREF(ary, i);
+
+        if (rb_cmpint(rb_funcallv(vmax, id_cmp, 1, &v), vmax, v) < 0) {
+            vmax = v;
+        }
+    }
+
+    return vmax;
+}
+
+static VALUE
+ary_max_opt_fixnum(VALUE ary, long i, VALUE vmax)
+{
+    const long n = RARRAY_LEN(ary);
+    RUBY_ASSERT(i > 0 && i < n);
+    RUBY_ASSERT(FIXNUM_P(vmax));
+
+    VALUE v;
+    for (; i < n; ++i) {
+        v = RARRAY_AREF(ary, i);
+
+        if (FIXNUM_P(v)) {
+            if ((long)vmax < (long)v) {
+                vmax = v;
+            }
+        }
+        else {
+            return ary_max_generic(ary, i, vmax);
+        }
+    }
+
+    return vmax;
+}
+
+static VALUE
+ary_max_opt_float(VALUE ary, long i, VALUE vmax)
+{
+    const long n = RARRAY_LEN(ary);
+    RUBY_ASSERT(i > 0 && i < n);
+    RUBY_ASSERT(RB_FLOAT_TYPE_P(vmax));
+
+    VALUE v;
+    for (; i < n; ++i) {
+        v = RARRAY_AREF(ary, i);
+
+        if (RB_FLOAT_TYPE_P(v)) {
+            if (rb_float_cmp(vmax, v) < 0) {
+                vmax = v;
+            }
+        }
+        else {
+            return ary_max_generic(ary, i, vmax);
+        }
+    }
+
+    return vmax;
+}
+
+static VALUE
+ary_max_opt_string(VALUE ary, long i, VALUE vmax)
+{
+    const long n = RARRAY_LEN(ary);
+    RUBY_ASSERT(i > 0 && i < n);
+    RUBY_ASSERT(STRING_P(vmax));
+
+    VALUE v;
+    for (; i < n; ++i) {
+        v = RARRAY_AREF(ary, i);
+
+        if (STRING_P(v)) {
+            if (rb_str_cmp(vmax, v) < 0) {
+                vmax = v;
+            }
+        }
+        else {
+            return ary_max_generic(ary, i, vmax);
+        }
+    }
+
+    return vmax;
+}
+
 /*
  *  call-seq:
  *     ary.max                     -> obj
@@ -6210,6 +6299,7 @@ rb_ary_max(int argc, VALUE *argv, VALUE ary)
     if (rb_check_arity(argc, 0, 1) && !NIL_P(num = argv[0]))
        return rb_nmin_run(ary, num, 0, 1, 1);
 
+    const long n = RARRAY_LEN(ary);
     if (rb_block_given_p()) {
 	for (i = 0; i < RARRAY_LEN(ary); i++) {
 	   v = RARRAY_AREF(ary, i);
@@ -6218,13 +6308,22 @@ rb_ary_max(int argc, VALUE *argv, VALUE ary)
 	   }
 	}
     }
-    else {
-	for (i = 0; i < RARRAY_LEN(ary); i++) {
-	   v = RARRAY_AREF(ary, i);
-	   if (result == Qundef || OPTIMIZED_CMP(v, result, cmp_opt) > 0) {
-	       result = v;
-	   }
-	}
+    else if (n > 0) {
+        result = RARRAY_AREF(ary, 0);
+        if (n > 1) {
+            if (FIXNUM_P(result) && CMP_OPTIMIZABLE(cmp_opt, Integer)) {
+                return ary_max_opt_fixnum(ary, 1, result);
+            }
+            else if (STRING_P(result) && CMP_OPTIMIZABLE(cmp_opt, String)) {
+                return ary_max_opt_string(ary, 1, result);
+            }
+            else if (RB_FLOAT_TYPE_P(result) && CMP_OPTIMIZABLE(cmp_opt, Float)) {
+                return ary_max_opt_float(ary, 1, result);
+            }
+            else {
+                return ary_max_generic(ary, 1, result);
+            }
+        }
     }
     if (result == Qundef) return Qnil;
     return result;
-- 
cgit v1.2.3