From 9bc73cd81f29ab9d8fb6e7bbae0322110ecd3faa Mon Sep 17 00:00:00 2001
From: nobu <nobu@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>
Date: Fri, 29 Sep 2017 07:43:22 +0000
Subject: 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
---
 test/ruby/test_array.rb | 44 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 44 insertions(+)

(limited to 'test/ruby')

diff --git a/test/ruby/test_array.rb b/test/ruby/test_array.rb
index 172ae5a647..93576470bd 100644
--- a/test/ruby/test_array.rb
+++ b/test/ruby/test_array.rb
@@ -224,6 +224,13 @@ class TestArray < Test::Unit::TestCase
     assert_equal(@cls[],     @cls[ 1, 2, 3 ]    & @cls[ 4, 5, 6 ])
   end
 
+  def test_AND_big_array # '&'
+    assert_equal(@cls[1, 3], @cls[ 1, 1, 3, 5 ]*64 & @cls[ 1, 2, 3 ]*64)
+    assert_equal(@cls[],     @cls[ 1, 1, 3, 5 ]*64 & @cls[ ])
+    assert_equal(@cls[],     @cls[  ]           & @cls[ 1, 2, 3 ]*64)
+    assert_equal(@cls[],     @cls[ 1, 2, 3 ]*64 & @cls[ 4, 5, 6 ]*64)
+  end
+
   def test_MUL # '*'
     assert_equal(@cls[], @cls[]*3)
     assert_equal(@cls[1, 1, 1], @cls[1]*3)
@@ -260,6 +267,18 @@ class TestArray < Test::Unit::TestCase
     assert_equal(@cls[1, 2, 3], @cls[1, 2, 3] - @cls[4, 5, 6])
   end
 
+  def test_MINUS_big_array # '-'
+    assert_equal(@cls[1]*64, @cls[1, 2, 3, 4, 5]*64 - @cls[2, 3, 4, 5]*64)
+    # Ruby 1.8 feature change
+    #assert_equal(@cls[1], @cls[1, 2, 1, 3, 1, 4, 1, 5]*64 - @cls[2, 3, 4, 5]*64)
+    assert_equal(@cls[1, 1, 1, 1]*64, @cls[1, 2, 1, 3, 1, 4, 1, 5]*64 - @cls[2, 3, 4, 5]*64)
+    a = @cls[]
+    1000.times { a << 1 }
+    assert_equal(1000, a.length)
+    #assert_equal(@cls[1], a - @cls[2])
+   assert_equal(@cls[1] * 1000, a - @cls[2])
+  end
+
   def test_LSHIFT # '<<'
     a = @cls[]
     a << 1
@@ -1837,6 +1856,31 @@ class TestArray < Test::Unit::TestCase
     assert_equal([obj1], [obj1]|[obj2])
   end
 
+  def test_OR_big_in_order
+    obj1, obj2 = Class.new do
+      attr_reader :name
+      def initialize(name) @name = name; end
+      def inspect; "test_OR_in_order(#{@name})"; end
+      def hash; 0; end
+      def eql?(a) true; end
+      break [new("1"), new("2")]
+    end
+    assert_equal([obj1], [obj1]*64|[obj2]*64)
+  end
+
+  def test_OR_big_array # '|'
+    assert_equal(@cls[1,2], @cls[1]*64 | @cls[2]*64)
+    assert_equal(@cls[1,2], @cls[1, 2]*64 | @cls[1, 2]*64)
+
+    a = (1..64).to_a
+    b = (1..128).to_a
+    c = a | b
+    assert_equal(c, b)
+    assert_not_same(c, b)
+    assert_equal((1..64).to_a, a)
+    assert_equal((1..128).to_a, b)
+  end
+
   def test_combination
     a = @cls[]
     assert_equal(1, a.combination(0).size)
-- 
cgit v1.2.3