Rewrite Array#find in ruby

Inspired by https://bugs.ruby-lang.org/issues/20182 and https://github.com/ruby/ruby/pull/9533.

This PR provides a performance boost to Array#find when run using JIT
compilation. This is achieved by implementing Array#find in Ruby, which
the JIT compiler can optimise.

[PR#15189](https://github.com/ruby/ruby/pull/15189) added a C
implementation for Array#find instead of relying on Enumerable#find.
This PR extends this by adding a Ruby implementation.

I used the so_fasta benchmark to measure performance. No change in
interpreted performance before/after:

  $ benchmark-driver -e "~/.rubies/ruby-master/bin/ruby; ~/.rubies/ruby-array-find-native/bin/ruby" ../benchmark/so_fasta.rb
  Calculating -------------------------------------
                       ~/.rubies/ruby-master/bin/ruby   ~/.rubies/ruby-array-find-native/bin/ruby
              so_fasta                          0.393                                       0.393 i/s -       1.000 times in 2.543209s 2.545514s

  Comparison:
                           so_fasta
  ~/.rubies/ruby-master/bin/ruby:         0.4 i/s
  ~/.rubies/ruby-array-find-native/bin/ruby:         0.4 i/s - 1.00x  slower

With YJIT enabled Array#find is almost twice as fast:

  $ benchmark-driver -e "~/.rubies/ruby-array-find-native/bin/ruby; ~/.rubies/ruby-array-find-native/bin/ruby --yjit" ../benchmark/so_fasta.rb
  Calculating -------------------------------------
                       ~/.rubies/ruby-array-find-native/bin/ruby   ~/.rubies/ruby-array-find-native/bin/ruby --yjit
              so_fasta                                     0.393                                              0.770 i/s -       1.000 times in 2.547550s 1.298371s

  Comparison:
                           so_fasta
  ~/.rubies/ruby-array-find-native/bin/ruby --yjit:         0.8 i/s
  ~/.rubies/ruby-array-find-native/bin/ruby:         0.4 i/s - 1.96x  slower

1 files changed, 18 insertions, 0 deletions

diff --git a/array.rb b/array.rb
index 81beff0b1c..93ca4f3a3e 100644
--- a/array.rb
+++ b/array.rb
@@ -283,5 +283,23 @@ class Array
         alias filter select
       end
     end
+
+    if Primitive.rb_builtin_basic_definition_p(:find)
+      undef :find
+
+      def find(if_none_proc = nil) # :nodoc:
+        Primitive.attr! :inline_block, :c_trace
+
+        unless defined?(yield)
+          return Primitive.cexpr! 'SIZED_ENUMERATOR(self, 0, 0, ary_enum_length)'
+        end
+        _i = 0
+        value = nil
+        while Primitive.cexpr!(%q{ ary_fetch_next(self, LOCAL_PTR(_i), LOCAL_PTR(value)) })
+          return value if yield(value)
+        end
+        if_none_proc ? if_none_proc.call : nil
+      end
+    end
   end
 end