Optimize Array#min (#3324)

The benchmark result is below:

|                |compare-ruby|built-ruby|
|:---------------|-----------:|---------:|
|ary2.min        |     39.105M|   39.442M|
|                |           -|     1.01x|
|ary10.min       |     23.995M|   30.762M|
|                |           -|     1.28x|
|ary100.min      |      6.249M|   10.783M|
|                |           -|     1.73x|
|ary500.min      |      1.408M|    2.714M|
|                |           -|     1.93x|
|ary1000.min     |    828.397k|    1.465M|
|                |           -|     1.77x|
|ary2000.min     |    332.256k|  570.504k|
|                |           -|     1.72x|
|ary3000.min     |    338.079k|  573.868k|
|                |           -|     1.70x|
|ary5000.min     |    168.217k|  286.114k|
|                |           -|     1.70x|
|ary10000.min    |     85.512k|  143.551k|
|                |           -|     1.68x|
|ary20000.min    |     43.264k|   71.935k|
|                |           -|     1.66x|
|ary50000.min    |     17.317k|   29.107k|
|                |           -|     1.68x|
|ary100000.min   |      9.072k|   14.540k|
|                |           -|     1.60x|
|ary1000000.min  |     872.930|    1.436k|
|                |           -|     1.64x|

compare-ruby is 9f4b7fc82e.

1 files changed, 106 insertions, 7 deletions

diff --git a/array.c b/array.c
index 5fed5e5788..6ddc7e2817 100644
--- a/array.c
+++ b/array.c
@@ -6329,6 +6329,95 @@ rb_ary_max(int argc, VALUE *argv, VALUE ary)
     return result;
 }
 
+static VALUE
+ary_min_generic(VALUE ary, long i, VALUE vmin)
+{
+    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(vmin, id_cmp, 1, &v), vmin, v) > 0) {
+            vmin = v;
+        }
+    }
+
+    return vmin;
+}
+
+static VALUE
+ary_min_opt_fixnum(VALUE ary, long i, VALUE vmin)
+{
+    const long n = RARRAY_LEN(ary);
+    RUBY_ASSERT(i > 0 && i < n);
+    RUBY_ASSERT(FIXNUM_P(vmin));
+
+    VALUE a;
+    for (; i < n; ++i) {
+        a = RARRAY_AREF(ary, i);
+
+        if (FIXNUM_P(a)) {
+            if ((long)vmin > (long)a) {
+                vmin = a;
+            }
+        }
+        else {
+            return ary_min_generic(ary, i, vmin);
+        }
+    }
+
+    return vmin;
+}
+
+static VALUE
+ary_min_opt_float(VALUE ary, long i, VALUE vmin)
+{
+    const long n = RARRAY_LEN(ary);
+    RUBY_ASSERT(i > 0 && i < n);
+    RUBY_ASSERT(RB_FLOAT_TYPE_P(vmin));
+
+    VALUE a;
+    for (; i < n; ++i) {
+        a = RARRAY_AREF(ary, i);
+
+        if (RB_FLOAT_TYPE_P(a)) {
+            if (rb_float_cmp(vmin, a) > 0) {
+                vmin = a;
+            }
+        }
+        else {
+            return ary_min_generic(ary, i, vmin);
+        }
+    }
+
+    return vmin;
+}
+
+static VALUE
+ary_min_opt_string(VALUE ary, long i, VALUE vmin)
+{
+    const long n = RARRAY_LEN(ary);
+    RUBY_ASSERT(i > 0 && i < n);
+    RUBY_ASSERT(STRING_P(vmin));
+
+    VALUE a;
+    for (; i < n; ++i) {
+        a = RARRAY_AREF(ary, i);
+
+        if (STRING_P(a)) {
+            if (rb_str_cmp(vmin, a) > 0) {
+                vmin = a;
+            }
+        }
+        else {
+            return ary_min_generic(ary, i, vmin);
+        }
+    }
+
+    return vmin;
+}
+
 /*
  *  call-seq:
  *     ary.min                     -> obj
@@ -6362,6 +6451,7 @@ rb_ary_min(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, 0, 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);
@@ -6370,13 +6460,22 @@ rb_ary_min(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_min_opt_fixnum(ary, 1, result);
+            }
+            else if (STRING_P(result) && CMP_OPTIMIZABLE(cmp_opt, String)) {
+                return ary_min_opt_string(ary, 1, result);
+            }
+            else if (RB_FLOAT_TYPE_P(result) && CMP_OPTIMIZABLE(cmp_opt, Float)) {
+                return ary_min_opt_float(ary, 1, result);
+            }
+            else {
+                return ary_min_generic(ary, 1, result);
+            }
+        }
     }
     if (result == Qundef) return Qnil;
     return result;