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.

3 files changed, 139 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;
diff --git a/benchmark/array_min.yml b/benchmark/array_min.yml
new file mode 100644
index 0000000000..53e5072b14
--- /dev/null
+++ b/benchmark/array_min.yml
@@ -0,0 +1,31 @@
+prelude: |
+  ary2 = 2.times.to_a.shuffle
+  ary10 = 10.times.to_a.shuffle
+  ary100 = 100.times.to_a.shuffle
+  ary500 = 500.times.to_a.shuffle
+  ary1000 = 1000.times.to_a.shuffle
+  ary2000 = 2500.times.to_a.shuffle
+  ary3000 = 2500.times.to_a.shuffle
+  ary5000 = 5000.times.to_a.shuffle
+  ary10000 = 10000.times.to_a.shuffle
+  ary20000 = 20000.times.to_a.shuffle
+  ary50000 = 50000.times.to_a.shuffle
+  ary100000 = 100000.times.to_a.shuffle
+  ary1000000 = 1000000.times.to_a.shuffle
+
+benchmark:
+  ary2.min: ary2.min
+  ary10.min: ary10.min
+  ary100.min: ary100.min
+  ary500.min: ary500.min
+  ary1000.min: ary1000.min
+  ary2000.min: ary2000.min
+  ary3000.min: ary3000.min
+  ary5000.min: ary5000.min
+  ary10000.min: ary10000.min
+  ary20000.min: ary20000.min
+  ary50000.min: ary50000.min
+  ary100000.min: ary100000.min
+  ary1000000.min: ary1000000.min
+
+loop_count: 10000
diff --git a/test/ruby/test_array.rb b/test/ruby/test_array.rb
index 2b48dcf308..46de8e08fc 100644
--- a/test/ruby/test_array.rb
+++ b/test/ruby/test_array.rb
@@ -1734,10 +1734,12 @@ class TestArray < Test::Unit::TestCase
   end
 
   def test_min
+    assert_equal(3, [3].min)
     assert_equal(1, [1, 2, 3, 1, 2].min)
     assert_equal(3, [1, 2, 3, 1, 2].min {|a,b| b <=> a })
     cond = ->((a, ia), (b, ib)) { (b <=> a).nonzero? or ia <=> ib }
     assert_equal([3, 2], [1, 2, 3, 1, 2].each_with_index.min(&cond))
+    assert_equal(1.0, [3.0, 1.0, 2.0].min)
     ary = %w(albatross dog horse)
     assert_equal("albatross", ary.min)
     assert_equal("dog", ary.min {|a,b| a.length <=> b.length })