Lazily allocate id tables for children

This patch lazily allocates id tables for shape children.  If a shape
has only one single child, it tags the child with a bit.  When we read
children, if the id table has the bit set, we know it's a single child.
If we need to add more children, then we create a new table and evacuate
the child to the new table.

Co-Authored-By: Matt Valentine-House <[email protected]>

1 files changed, 16 insertions, 0 deletions

diff --git a/test/ruby/test_shapes.rb b/test/ruby/test_shapes.rb
index 9525167d65..1d9159bac0 100644
--- a/test/ruby/test_shapes.rb
+++ b/test/ruby/test_shapes.rb
@@ -1,5 +1,7 @@
 # frozen_string_literal: false
 require 'test/unit'
+require 'objspace'
+require 'json'
 
 # These test the functionality of object shapes
 class TestShapes < Test::Unit::TestCase
@@ -28,6 +30,14 @@ class TestShapes < Test::Unit::TestCase
     end
   end
 
+  class OrderedAlloc
+    def add_ivars
+      10.times do |i|
+        instance_variable_set("@foo" + i.to_s, 0)
+      end
+    end
+  end
+
   class Example
     def initialize
       @a = 1
@@ -109,6 +119,12 @@ class TestShapes < Test::Unit::TestCase
     assert_predicate RubyVM::Shape.of(tc), :too_complex?
   end
 
+  def test_ordered_alloc_is_not_complex
+    5.times { OrderedAlloc.new.add_ivars }
+    obj = JSON.parse(ObjectSpace.dump(OrderedAlloc))
+    assert_operator obj["variation_count"], :<, RubyVM::Shape::SHAPE_MAX_VARIATIONS
+  end
+
   def test_too_many_ivs_on_obj
     obj = Object.new