Transition complex objects to "too complex" shape

When an object becomes "too complex" (in other words it has too many
variations in the shape tree), we transition it to use a "too complex"
shape and use a hash for storing instance variables.

Without this patch, there were rare cases where shape tree growth could
"explode" and cause performance degradation on what would otherwise have
been cached fast paths.

This patch puts a limit on shape tree growth, and gracefully degrades in
the rare case where there could be a factorial growth in the shape tree.

For example:

```ruby
class NG; end

HUGE_NUMBER.times do
  NG.new.instance_variable_set(:"@unique_ivar_#{_1}", 1)
end
```

We consider objects to be "too complex" when the object's class has more
than SHAPE_MAX_VARIATIONS (currently 8) leaf nodes in the shape tree and
the object introduces a new variation (a new leaf node) associated with
that class.

For example, new variations on instances of the following class would be
considered "too complex" because those instances create more than 8
leaves in the shape tree:

```ruby
class Foo; end
9.times { Foo.new.instance_variable_set(":@uniq_#{_1}", 1) }
```

However, the following class is *not* too complex because it only has
one leaf in the shape tree:

```ruby
class Foo
  def initialize
    @a = @b = @c = @d = @e = @f = @g = @h = @i = nil
  end
end
9.times { Foo.new }
``

This case is rare, so we don't expect this change to impact performance
of most applications, but it needs to be handled.

Co-Authored-By: Aaron Patterson <[email protected]>

1 files changed, 38 insertions, 14 deletions

diff --git a/gc.c b/gc.c
index a10a2193e4..1a7f3ab095 100644
--- a/gc.c
+++ b/gc.c
@@ -2965,6 +2965,7 @@ rb_class_instance_allocate_internal(VALUE klass, VALUE flags, bool wb_protected)
     ROBJECT_SET_SHAPE_ID(obj, ROBJECT_SHAPE_ID(obj) + SIZE_POOL_COUNT);
 
 #if RUBY_DEBUG
+    RUBY_ASSERT(!rb_shape_obj_too_complex(obj));
     VALUE *ptr = ROBJECT_IVPTR(obj);
     for (size_t i = 0; i < ROBJECT_IV_CAPACITY(obj); i++) {
         ptr[i] = Qundef;
@@ -3451,7 +3452,11 @@ obj_free(rb_objspace_t *objspace, VALUE obj)
 
     switch (BUILTIN_TYPE(obj)) {
       case T_OBJECT:
-        if (RANY(obj)->as.basic.flags & ROBJECT_EMBED) {
+        if (rb_shape_obj_too_complex(obj)) {
+            RB_DEBUG_COUNTER_INC(obj_obj_too_complex);
+            rb_id_table_free(ROBJECT_IV_HASH(obj));
+        }
+        else if (RANY(obj)->as.basic.flags & ROBJECT_EMBED) {
             RB_DEBUG_COUNTER_INC(obj_obj_embed);
         }
         else if (ROBJ_TRANSIENT_P(obj)) {
@@ -4875,7 +4880,10 @@ obj_memsize_of(VALUE obj, int use_all_types)
 
     switch (BUILTIN_TYPE(obj)) {
       case T_OBJECT:
-        if (!(RBASIC(obj)->flags & ROBJECT_EMBED)) {
+        if (rb_shape_obj_too_complex(obj)) {
+            size += rb_id_table_memsize(ROBJECT_IV_HASH(obj));
+        }
+        else if (!(RBASIC(obj)->flags & ROBJECT_EMBED)) {
             size += ROBJECT_IV_CAPACITY(obj) * sizeof(VALUE);
         }
         break;
@@ -7297,14 +7305,23 @@ gc_mark_children(rb_objspace_t *objspace, VALUE obj)
 
       case T_OBJECT:
         {
-            const VALUE * const ptr = ROBJECT_IVPTR(obj);
-
-            uint32_t i, len = ROBJECT_IV_COUNT(obj);
-            for (i  = 0; i < len; i++) {
-                gc_mark(objspace, ptr[i]);
+            rb_shape_t *shape = rb_shape_get_shape_by_id(ROBJECT_SHAPE_ID(obj));
+            if (rb_shape_obj_too_complex(obj)) {
+                mark_m_tbl(objspace, ROBJECT_IV_HASH(obj));
             }
+            else {
+                const VALUE * const ptr = ROBJECT_IVPTR(obj);
 
-            rb_shape_t *shape = rb_shape_get_shape_by_id(ROBJECT_SHAPE_ID(obj));
+                uint32_t i, len = ROBJECT_IV_COUNT(obj);
+                for (i  = 0; i < len; i++) {
+                    gc_mark(objspace, ptr[i]);
+                }
+
+                if (LIKELY(during_gc) &&
+                        ROBJ_TRANSIENT_P(obj)) {
+                    rb_transient_heap_mark(obj, ptr);
+                }
+            }
             if (shape) {
                 VALUE klass = RBASIC_CLASS(obj);
 
@@ -7314,11 +7331,6 @@ gc_mark_children(rb_objspace_t *objspace, VALUE obj)
                     RCLASS_EXT(klass)->max_iv_count = num_of_ivs;
                 }
             }
-
-            if (LIKELY(during_gc) &&
-                    ROBJ_TRANSIENT_P(obj)) {
-                rb_transient_heap_mark(obj, ptr);
-            }
         }
         break;
 
@@ -8426,7 +8438,12 @@ gc_compact_destination_pool(rb_objspace_t *objspace, rb_size_pool_t *src_pool, V
         break;
 
       case T_OBJECT:
-        obj_size = rb_obj_embedded_size(ROBJECT_IV_CAPACITY(src));
+        if (rb_shape_obj_too_complex(src)) {
+            return &size_pools[0];
+        }
+        else {
+            obj_size = rb_obj_embedded_size(ROBJECT_IV_CAPACITY(src));
+        }
         break;
 
       case T_STRING:
@@ -10038,11 +10055,18 @@ gc_ref_update_array(rb_objspace_t * objspace, VALUE v)
     }
 }
 
+static void update_m_tbl(rb_objspace_t *objspace, struct rb_id_table *tbl);
+
 static void
 gc_ref_update_object(rb_objspace_t *objspace, VALUE v)
 {
     VALUE *ptr = ROBJECT_IVPTR(v);
 
+    if (rb_shape_obj_too_complex(v)) {
+        update_m_tbl(objspace, ROBJECT_IV_HASH(v));
+        return;
+    }
+
 #if USE_RVARGC
     uint32_t numiv = ROBJECT_IV_CAPACITY(v);