array.c: improve operations on small arrays

[Feature #13884]

Reduce number of memory allocations for "and", "or" and "diff"
operations on small arrays

Very often, arrays are used to filter parameters and to select
interesting items from 2 collections and very often these
collections are small enough, for example:

```ruby
SAFE_COLUMNS = [:id, :title, :created_at]

def columns
  @all_columns & SAFE_COLUMNS
end
```

In this patch, I got rid of unnecessary memory allocations for
small arrays when "and", "or" and "diff" operations are performed.

name             | HEAD  | PATCH
-----------------+------:+------:
array_small_and  | 0.615 | 0.263
array_small_diff | 0.676 | 0.282
array_small_or   | 0.953 | 0.463

name             | PATCH
-----------------+------:
array_small_and  | 2.343
array_small_diff | 2.392
array_small_or   | 2.056

name             | HEAD  | PATCH
-----------------+------:+------:
array_small_and  | 1.429 | 1.005
array_small_diff | 1.493 | 0.878
array_small_or   | 1.672 | 1.152

name             | PATCH
-----------------+------:
array_small_and  | 1.422
array_small_diff | 1.700
array_small_or   | 1.452

Author:    Dmitry Bochkarev <dimabochkarev@gmail.com>

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@60057 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

3 files changed, 51 insertions, 0 deletions

diff --git a/benchmark/bm_array_small_and.rb b/benchmark/bm_array_small_and.rb
new file mode 100644
index 0000000000..e53a6edae6
--- /dev/null
+++ b/benchmark/bm_array_small_and.rb
@@ -0,0 +1,17 @@
+MIN_SIZE = ENV.fetch('SMALL_ARRAY_MIN', 0).to_i
+MAX_SIZE = ENV.fetch('SMALL_ARRAY_MAX', 16).to_i
+ITERATIONS = ENV.fetch('SMALL_ARRAY_ITERATIONS', 100).to_i
+
+ARRAYS = (MIN_SIZE..MAX_SIZE).map do |size1|
+  (MIN_SIZE..MAX_SIZE).map do |size2|
+    [Array.new(size1) { rand(MAX_SIZE) }, Array.new(size2) { rand(MAX_SIZE) }]
+  end
+end
+
+ITERATIONS.times do
+  ARRAYS.each do |group|
+    group.each do |arr1, arr2|
+      arr1 & arr2
+    end
+  end
+end
diff --git a/benchmark/bm_array_small_diff.rb b/benchmark/bm_array_small_diff.rb
new file mode 100644
index 0000000000..9661ee48db
--- /dev/null
+++ b/benchmark/bm_array_small_diff.rb
@@ -0,0 +1,17 @@
+MIN_SIZE = ENV.fetch('SMALL_ARRAY_MIN', 0).to_i
+MAX_SIZE = ENV.fetch('SMALL_ARRAY_MAX', 16).to_i
+ITERATIONS = ENV.fetch('SMALL_ARRAY_ITERATIONS', 100).to_i
+
+ARRAYS = (MIN_SIZE..MAX_SIZE).map do |size1|
+  (MIN_SIZE..MAX_SIZE).map do |size2|
+    [Array.new(size1) { rand(MAX_SIZE) }, Array.new(size2) { rand(MAX_SIZE) }]
+  end
+end
+
+ITERATIONS.times do
+  ARRAYS.each do |group|
+    group.each do |arr1, arr2|
+      arr1 - arr2
+    end
+  end
+end
diff --git a/benchmark/bm_array_small_or.rb b/benchmark/bm_array_small_or.rb
new file mode 100644
index 0000000000..c58b5fd1ff
--- /dev/null
+++ b/benchmark/bm_array_small_or.rb
@@ -0,0 +1,17 @@
+MIN_SIZE = ENV.fetch('SMALL_ARRAY_MIN', 0).to_i
+MAX_SIZE = ENV.fetch('SMALL_ARRAY_MAX', 16).to_i
+ITERATIONS = ENV.fetch('SMALL_ARRAY_ITERATIONS', 100).to_i
+
+ARRAYS = (MIN_SIZE..MAX_SIZE).map do |size1|
+  (MIN_SIZE..MAX_SIZE).map do |size2|
+    [Array.new(size1) { rand(MAX_SIZE) }, Array.new(size2) { rand(MAX_SIZE) }]
+  end
+end
+
+ITERATIONS.times do
+  ARRAYS.each do |group|
+    group.each do |arr1, arr2|
+      arr1 | arr2
+    end
+  end
+end