Constant time class to class ancestor lookup

Previously when checking ancestors, we would walk all the way up the
ancestry chain checking each parent for a matching class or module.

I believe this was especially unfriendly to CPU cache since for each
step we need to check two cache lines (the class and class ext).

This check is used quite often in:
* case statements
* rescue statements
* Calling protected methods
* Class#is_a?
* Module#===
* Module#<=>

I believe it's most common to check a class against a parent class, to
this commit aims to improve that (unfortunately does not help checking
for an included Module).

This is done by storing on each class the number and an array of all
parent classes, in order (BasicObject is at index 0). Using this we can
check whether a class is a subclass of another in constant time since we
know the location to expect it in the hierarchy.

1 files changed, 7 insertions, 0 deletions

diff --git a/internal/class.h b/internal/class.h
index d4c1c72414..c6151299c7 100644
--- a/internal/class.h
+++ b/internal/class.h
@@ -47,6 +47,8 @@ struct rb_classext_struct {
     struct rb_id_table *callable_m_tbl;
     struct rb_id_table *cc_tbl; /* ID -> [[ci, cc1], cc2, ...] */
     struct rb_id_table *cvc_tbl;
+    size_t superclass_depth;
+    VALUE *superclasses;
     struct rb_subclass_entry *subclasses;
     struct rb_subclass_entry *subclass_entry;
     /**
@@ -117,6 +119,8 @@ typedef struct rb_classext_struct rb_classext_t;
 #define RCLASS_MODULE_SUBCLASS_ENTRY(c) (RCLASS_EXT(c)->module_subclass_entry)
 #define RCLASS_ALLOCATOR(c) (RCLASS_EXT(c)->allocator)
 #define RCLASS_SUBCLASSES(c) (RCLASS_EXT(c)->subclasses)
+#define RCLASS_SUPERCLASS_DEPTH(c) (RCLASS_EXT(c)->superclass_depth)
+#define RCLASS_SUPERCLASSES(c) (RCLASS_EXT(c)->superclasses)
 
 #define RICLASS_IS_ORIGIN FL_USER5
 #define RCLASS_CLONED     FL_USER6
@@ -125,6 +129,8 @@ typedef struct rb_classext_struct rb_classext_t;
 /* 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);
 void rb_class_remove_subclass_head(VALUE);
 int rb_singleton_class_internal_p(VALUE sklass);
 VALUE rb_class_boot(VALUE);
@@ -197,6 +203,7 @@ RCLASS_SET_SUPER(VALUE klass, VALUE super)
         rb_class_subclass_add(super, klass);
     }
     RB_OBJ_WRITE(klass, &RCLASS(klass)->super, super);
+    rb_class_update_superclasses(klass);
     return super;
 }