Dedup superclass array in leaf sibling classes

Previously, we would build a new `superclasses` array for each class,
even though for all immediate subclasses of a class, the array is
identical.

This avoids duplicating the arrays on leaf classes (those without
subclasses) by calculating and storing a "superclasses including self"
array on a class when it's first inherited and sharing that among all
superclasses.

An additional trick used is that the "superclass array including self"
is valid as "self"'s superclass array. It just has it's own class at the
end. We can use this to avoid an extra pointer of storage and can use
one bit of a flag to track that we've "upgraded" the array.

3 files changed, 26 insertions, 24 deletions

diff --git a/class.c b/class.c
index ef3f8aac2e..0acac96022 100644
--- a/class.c
+++ b/class.c
@@ -259,17 +259,21 @@ rb_class_boot(VALUE super)
     return (VALUE)klass;
 }
 
-void
-rb_class_remove_superclasses(VALUE klass)
+static VALUE *
+class_superclasses_including_self(VALUE klass)
 {
-    if (!RB_TYPE_P(klass, T_CLASS))
-        return;
+    if (FL_TEST_RAW(klass, RCLASS_SUPERCLASSES_INCLUDE_SELF))
+        return RCLASS_SUPERCLASSES(klass);
 
-    if (RCLASS_SUPERCLASSES(klass))
-        xfree(RCLASS_SUPERCLASSES(klass));
+    size_t depth = RCLASS_SUPERCLASS_DEPTH(klass);
+    VALUE *superclasses = xmalloc(sizeof(VALUE) * (depth + 1));
+    if (depth > 0)
+        memcpy(superclasses, RCLASS_SUPERCLASSES(klass), sizeof(VALUE) * depth);
+    superclasses[depth] = klass;
 
-    RCLASS_SUPERCLASSES(klass) = NULL;
-    RCLASS_SUPERCLASS_DEPTH(klass) = 0;
+    RCLASS_SUPERCLASSES(klass) = superclasses;
+    FL_SET_RAW(klass, RCLASS_SUPERCLASSES_INCLUDE_SELF);
+    return superclasses;
 }
 
 void
@@ -303,17 +307,8 @@ rb_class_update_superclasses(VALUE klass)
             return;
     }
 
-    size_t parent_num = RCLASS_SUPERCLASS_DEPTH(super);
-    size_t num = parent_num + 1;
-
-    VALUE *superclasses = xmalloc(sizeof(VALUE) * num);
-    superclasses[parent_num] = super;
-    if (parent_num > 0) {
-        memcpy(superclasses, RCLASS_SUPERCLASSES(super), sizeof(VALUE) * parent_num);
-    }
-
-    RCLASS_SUPERCLASSES(klass) = superclasses;
-    RCLASS_SUPERCLASS_DEPTH(klass) = num;
+    RCLASS_SUPERCLASSES(klass) = class_superclasses_including_self(super);
+    RCLASS_SUPERCLASS_DEPTH(klass) = RCLASS_SUPERCLASS_DEPTH(super) + 1;
 }
 
 void
diff --git a/gc.c b/gc.c
index 1061b506bf..134100584c 100644
--- a/gc.c
+++ b/gc.c
@@ -3187,7 +3187,9 @@ obj_free(rb_objspace_t *objspace, VALUE obj)
         rb_class_remove_subclass_head(obj);
 	rb_class_remove_from_module_subclasses(obj);
 	rb_class_remove_from_super_subclasses(obj);
-	rb_class_remove_superclasses(obj);
+        if (FL_TEST_RAW(obj, RCLASS_SUPERCLASSES_INCLUDE_SELF)) {
+            xfree(RCLASS_SUPERCLASSES(obj));
+        }
 #if SIZEOF_SERIAL_T != SIZEOF_VALUE && USE_RVARGC
         xfree(RCLASS(obj)->class_serial_ptr);
 #endif
@@ -4620,7 +4622,9 @@ obj_memsize_of(VALUE obj, int use_all_types)
             if (RCLASS_CC_TBL(obj)) {
                 size += cc_table_memsize(RCLASS_CC_TBL(obj));
             }
-            size += RCLASS_SUPERCLASS_DEPTH(obj) * sizeof(VALUE);
+            if (FL_TEST_RAW(obj, RCLASS_SUPERCLASSES_INCLUDE_SELF)) {
+                size += (RCLASS_SUPERCLASS_DEPTH(obj) + 1) * sizeof(VALUE);
+            }
 #if !USE_RVARGC
 	    size += sizeof(rb_classext_t);
 #endif
@@ -10037,8 +10041,10 @@ update_class_ext(rb_objspace_t *objspace, rb_classext_t *ext)
 static void
 update_superclasses(rb_objspace_t *objspace, VALUE obj)
 {
-    for (size_t i = 0; i < RCLASS_SUPERCLASS_DEPTH(obj); i++) {
-        UPDATE_IF_MOVED(objspace, RCLASS_SUPERCLASSES(obj)[i]);
+    if (FL_TEST_RAW(obj, RCLASS_SUPERCLASSES_INCLUDE_SELF)) {
+        for (size_t i = 0; i < RCLASS_SUPERCLASS_DEPTH(obj) + 1; i++) {
+            UPDATE_IF_MOVED(objspace, RCLASS_SUPERCLASSES(obj)[i]);
+        }
     }
 }
 
diff --git a/internal/class.h b/internal/class.h
index c6151299c7..be2f703fc8 100644
--- a/internal/class.h
+++ b/internal/class.h
@@ -124,13 +124,14 @@ typedef struct rb_classext_struct rb_classext_t;
 
 #define RICLASS_IS_ORIGIN FL_USER5
 #define RCLASS_CLONED     FL_USER6
+#define RCLASS_SUPERCLASSES_INCLUDE_SELF FL_USER7
 #define RICLASS_ORIGIN_SHARED_MTBL FL_USER8
 
 /* class.c */
 void rb_class_subclass_add(VALUE super, VALUE klass);
 void rb_class_remove_from_super_subclasses(VALUE);
 void rb_class_update_superclasses(VALUE);
-void rb_class_remove_superclasses(VALUE);
+size_t rb_class_superclasses_memsize(VALUE);
 void rb_class_remove_subclass_head(VALUE);
 int rb_singleton_class_internal_p(VALUE sklass);
 VALUE rb_class_boot(VALUE);