Fast Load Patch for ruby

fast_load.patch

diff --git a/load.c b/load.c
index b0e6f16..4c98dbb 100644
--- a/load.c
+++ b/load.c
@@ -69,6 +69,17 @@
     return GET_VM()->loading_table;
 }
 
+/* This searches `load_path` for a value such that
+     name == "#{load_path[i]}/#{feature}"
+   if `feature` is a suffix of `name`, or otherwise
+     name == "#{load_path[i]}/#{feature}#{ext}"
+   for an acceptable string `ext`.  It returns
+   `load_path[i].to_str` if found, else 0.
+
+   If type is 's', then `ext` is acceptable only if IS_DLEXT(ext);
+   if 'r', then only if IS_RBEXT(ext); otherwise `ext` may be absent
+   or have any value matching `%r{^\.[^./]*$}`.
+*/
 static VALUE
 loaded_feature_path(const char *name, long vlen, const char *feature, long len,
 		    int type, VALUE load_path)
@@ -77,7 +88,7 @@
     long plen;
     const char *e;
 
-    if(vlen < len) return 0;
+    if(vlen < len+1) return 0;
     if (!strncmp(name+(vlen-len),feature,len)){
 	plen = vlen - len - 1;
     } else {
@@ -88,23 +99,22 @@
 	    return 0;
 	plen = e - name - len - 1;
     }
+    if (type == 's' && !IS_DLEXT(&name[plen+len+1])
+     || type == 'r' && !IS_RBEXT(&name[plen+len+1])
+     || name[plen] != '/') {
+	return 0;
+    }
+    /* Now name == "#{prefix}/#{feature}#{ext}" where ext is acceptable
+       (possibly empty) and prefix is some string of length plen. */
+
     for (i = 0; i < RARRAY_LEN(load_path); ++i) {
 	VALUE p = RARRAY_PTR(load_path)[i];
 	const char *s = StringValuePtr(p);
 	long n = RSTRING_LEN(p);
 
-	if (n != plen ) continue;
-	if (n && (strncmp(name, s, n) || name[n] != '/')) continue;
-	switch (type) {
-	  case 's':
-	    if (IS_DLEXT(&name[n+len+1])) return p;
-	    break;
-	  case 'r':
-	    if (IS_RBEXT(&name[n+len+1])) return p;
-	    break;
-	  default:
-	    return p;
-	}
+	if (n != plen) continue;
+	if (n && strncmp(name, s, n)) continue;
+	return p;
     }
     return 0;
 }
@@ -152,6 +162,25 @@ struct loaded_feature_searching {
     }
     features = get_loaded_features();
     for (i = 0; i < RARRAY_LEN(features); ++i) {
+	/* This loop searches `features` for an entry such that either
+	     "#{features[i]}" == "#{load_path[j]}/#{feature}#{e}"
+	   for some j, or
+	     "#{features[i]}" == "#{feature}#{e}"
+	   Here `e` is an "allowed" extension -- either empty or one
+	   of the extensions accepted by IS_RBEXT, IS_SOEXT, or
+	   IS_DLEXT.  Further, if `ext && rb` then `IS_RBEXT(e)`,
+	   and if `ext && !rb` then `IS_SOEXT(e) || IS_DLEXT(e)`.
+
+	   If `expanded`, then only the latter form (without
+	   load_path[j]) is accepted.  Otherwise either form is
+	   accepted, *unless* `ext` is false and an otherwise-matching
+	   entry of the first form is preceded by an entry of the form
+	     "#{features[i2]}" == "#{load_path[j2]}/#{feature}#{e2}"
+	   where `e2` matches /^\.[^./]*$/ but is not an allowed extension.
+	   After a "distractor" entry of this form, only entries of the
+	   form "#{feature}#{e}" are accepted.
+	*/
+
 	v = RARRAY_PTR(features)[i];
 	f = StringValuePtr(v);
 	if ((n = RSTRING_LEN(v)) < len) continue;
diff --git a/array.c b/array.c
index 524553a..e98cbb7 100644
--- a/array.c
+++ b/array.c
@@ -305,6 +305,22 @@
     return Qfalse;
 }
 
+/* This can be used to take a snapshot of an array (with
+   e.g. rb_ary_replace) and check later whether the array has been
+   modified from the snapshot.  The snapshot is cheap, though if
+   something does modify the array it will pay the cost of copying
+   it. */
+VALUE
+rb_ary_shared_with_p(VALUE ary1, VALUE ary2)
+{
+    if (!ARY_EMBED_P(ary1) && ARY_SHARED_P(ary1)
+     && !ARY_EMBED_P(ary2) && ARY_SHARED_P(ary2)
+     && RARRAY(ary1)->as.heap.aux.shared == RARRAY(ary2)->as.heap.aux.shared) {
+	return Qtrue;
+    }
+    return Qfalse;
+}
+
 static VALUE
 ary_alloc(VALUE klass)
 {
diff --git a/include/ruby/intern.h b/include/ruby/intern.h
index 3f03d4d..410259d 100644
--- a/include/ruby/intern.h
+++ b/include/ruby/intern.h
@@ -57,6 +57,7 @@
 void rb_ary_free(VALUE);
 void rb_ary_modify(VALUE);
 VALUE rb_ary_freeze(VALUE);
+VALUE rb_ary_shared_with_p(VALUE, VALUE);
 VALUE rb_ary_aref(int, VALUE*, VALUE);
 VALUE rb_ary_subseq(VALUE, long, long);
 void rb_ary_store(VALUE, long, VALUE);
diff --git a/hash.c b/hash.c
index 06d0ce9..9d44a73 100644
--- a/hash.c
+++ b/hash.c
@@ -1103,7 +1103,7 @@ struct shift_var {
  *
  */
 
-static VALUE
+VALUE
 rb_hash_clear(VALUE hash)
 {
     rb_hash_modify_check(hash);
diff --git a/include/ruby/intern.h b/include/ruby/intern.h
index 410259d..efcd7f8 100644
--- a/include/ruby/intern.h
+++ b/include/ruby/intern.h
@@ -460,6 +460,7 @@
 VALUE rb_hash_lookup2(VALUE, VALUE, VALUE);
 VALUE rb_hash_fetch(VALUE, VALUE);
 VALUE rb_hash_aset(VALUE, VALUE, VALUE);
+VALUE rb_hash_clear(VALUE);
 VALUE rb_hash_delete_if(VALUE);
 VALUE rb_hash_delete(VALUE,VALUE);
 typedef VALUE rb_hash_update_func(VALUE newkey, VALUE oldkey, VALUE value);
diff --git a/load.c b/load.c
index 4c98dbb..75df5ab 100644
--- a/load.c
+++ b/load.c
@@ -18,7 +18,6 @@
 #define IS_DLEXT(e) (strcmp((e), DLEXT) == 0)
 #endif
 
-
 static const char *const loadable_ext[] = {
     ".rb", DLEXT,
 #ifdef DLEXT2
@@ -63,12 +62,110 @@
     return GET_VM()->loaded_features;
 }
 
+static void
+reset_loaded_features_snapshot(void)
+{
+    rb_vm_t *vm = GET_VM();
+    rb_ary_replace(vm->loaded_features_snapshot, vm->loaded_features);
+}
+
+static VALUE
+get_loaded_features_index_raw(void)
+{
+    return GET_VM()->loaded_features_index;
+}
+
 static st_table *
 get_loading_table(void)
 {
     return GET_VM()->loading_table;
 }
 
+static void
+features_index_add_single(VALUE short_feature, VALUE offset)
+{
+    VALUE features_index, this_feature_index;
+    features_index = get_loaded_features_index_raw();
+    if ((this_feature_index = rb_hash_lookup(features_index, short_feature)) == Qnil) {
+	this_feature_index = rb_ary_new();
+	rb_hash_aset(features_index, short_feature, this_feature_index);
+    }
+    rb_ary_push(this_feature_index, offset);
+}
+
+/* Add to the loaded-features index all the required entries for
+   `feature`, located at `offset` in $LOADED_FEATURES.  We add an
+   index entry at each string `short_feature` for which
+     feature == "#{prefix}#{short_feature}#{e}"
+   where `e` is empty or matches %r{^\.[^./]*$}, and `prefix` is empty
+   or ends in '/'.  This maintains the invariant that `rb_feature_p()`
+   relies on for its fast lookup.
+*/
+static void
+features_index_add(VALUE feature, VALUE offset)
+{
+    VALUE short_feature;
+    const char *feature_str, *feature_end, *ext, *p;
+
+    feature_str = StringValuePtr(feature);
+    feature_end = feature_str + RSTRING_LEN(feature);
+
+    for (ext = feature_end; ext > feature_str; ext--)
+      if (*ext == '.' || *ext == '/')
+	break;
+    if (*ext != '.')
+      ext = NULL;
+    /* Now `ext` points to the only string matching %r{^\.[^./]*$} that is
+       at the end of `feature`, or is NULL if there is no such string. */
+
+    p = ext ? ext : feature_end;
+    while (1) {
+	p--;
+	while (p >= feature_str && *p != '/')
+	    p--;
+	if (p < feature_str)
+	    break;
+	/* Now *p == '/'.  We reach this point for every '/' in `feature`. */
+	short_feature = rb_str_substr(feature, p + 1 - feature_str, feature_end - p - 1);
+	features_index_add_single(short_feature, offset);
+	if (ext) {
+	    short_feature = rb_str_substr(feature, p + 1 - feature_str, ext - p - 1);
+	    features_index_add_single(short_feature, offset);
+	}
+    }
+    features_index_add_single(feature, offset);
+    if (ext) {
+	short_feature = rb_str_substr(feature, 0, ext - feature_str);
+	features_index_add_single(short_feature, offset);
+    }
+}
+
+static VALUE
+get_loaded_features_index(void)
+{
+    VALUE features;
+    int i;
+    rb_vm_t *vm = GET_VM();
+
+    if (!rb_ary_shared_with_p(vm->loaded_features_snapshot, vm->loaded_features)) {
+	/* The sharing was broken; something (other than us in rb_provide_feature())
+	   modified loaded_features.  Rebuild the index. */
+	rb_hash_clear(vm->loaded_features_index);
+	features = vm->loaded_features;
+	for (i = 0; i < RARRAY_LEN(features); i++) {
+	    VALUE entry, as_str;
+	    as_str = entry = rb_ary_entry(features, i);
+	    StringValue(as_str);
+	    if (as_str != entry)
+		rb_ary_store(features, i, as_str);
+	    rb_str_freeze(as_str);
+	    features_index_add(as_str, INT2FIX(i));
+	}
+	reset_loaded_features_snapshot();
+    }
+    return vm->loaded_features_index;
+}
+
 /* This searches `load_path` for a value such that
      name == "#{load_path[i]}/#{feature}"
    if `feature` is a suffix of `name`, or otherwise
@@ -142,7 +239,7 @@ struct loaded_feature_searching {
 static int
 rb_feature_p(const char *feature, const char *ext, int rb, int expanded, const char **fn)
 {
-    VALUE v, features, p, load_path = 0;
+    VALUE features, features_index, feature_val, this_feature_index, v, p, load_path = 0;
     const char *f, *e;
     long i, len, elen, n;
     st_table *loading_tbl;
@@ -161,27 +258,39 @@ struct loaded_feature_searching {
 	type = 0;
     }
     features = get_loaded_features();
-    for (i = 0; i < RARRAY_LEN(features); ++i) {
-	/* This loop searches `features` for an entry such that either
-	     "#{features[i]}" == "#{load_path[j]}/#{feature}#{e}"
-	   for some j, or
-	     "#{features[i]}" == "#{feature}#{e}"
-	   Here `e` is an "allowed" extension -- either empty or one
-	   of the extensions accepted by IS_RBEXT, IS_SOEXT, or
-	   IS_DLEXT.  Further, if `ext && rb` then `IS_RBEXT(e)`,
-	   and if `ext && !rb` then `IS_SOEXT(e) || IS_DLEXT(e)`.
-
-	   If `expanded`, then only the latter form (without
-	   load_path[j]) is accepted.  Otherwise either form is
-	   accepted, *unless* `ext` is false and an otherwise-matching
-	   entry of the first form is preceded by an entry of the form
-	     "#{features[i2]}" == "#{load_path[j2]}/#{feature}#{e2}"
-	   where `e2` matches /^\.[^./]*$/ but is not an allowed extension.
-	   After a "distractor" entry of this form, only entries of the
-	   form "#{feature}#{e}" are accepted.
-	*/
-
-	v = RARRAY_PTR(features)[i];
+    features_index = get_loaded_features_index();
+
+    feature_val = rb_str_new(feature, len);
+    this_feature_index = rb_hash_lookup(features_index, feature_val);
+    /* We search `features` for an entry such that either
+         "#{features[i]}" == "#{load_path[j]}/#{feature}#{e}"
+       for some j, or
+         "#{features[i]}" == "#{feature}#{e}"
+       Here `e` is an "allowed" extension -- either empty or one
+       of the extensions accepted by IS_RBEXT, IS_SOEXT, or
+       IS_DLEXT.  Further, if `ext && rb` then `IS_RBEXT(e)`,
+       and if `ext && !rb` then `IS_SOEXT(e) || IS_DLEXT(e)`.
+
+       If `expanded`, then only the latter form (without load_path[j])
+       is accepted.  Otherwise either form is accepted, *unless* `ext`
+       is false and an otherwise-matching entry of the first form is
+       preceded by an entry of the form
+         "#{features[i2]}" == "#{load_path[j2]}/#{feature}#{e2}"
+       where `e2` matches %r{^\.[^./]*$} but is not an allowed extension.
+       After a "distractor" entry of this form, only entries of the
+       form "#{feature}#{e}" are accepted.
+
+       In `rb_provide_feature()` and `get_loaded_features_index()` we
+       maintain an invariant that the array `this_feature_index` will
+       point to every entry in `features` which has the form
+         "#{prefix}#{feature}#{e}"
+       where `e` is empty or matches %r{^\.[^./]*$}, and `prefix` is empty
+       or ends in '/'.  This includes both match forms above, as well
+       as any distractors, so we may ignore all other entries in `features`.
+     */
+    for (i = 0; this_feature_index != Qnil && i < RARRAY_LEN(this_feature_index); i++) {
+	long index = FIX2LONG(rb_ary_entry(this_feature_index, i));
+	v = RARRAY_PTR(features)[index];
 	f = StringValuePtr(v);
 	if ((n = RSTRING_LEN(v)) < len) continue;
 	if (strncmp(f, feature, len) != 0) {
@@ -204,6 +313,7 @@ struct loaded_feature_searching {
 	    return 'r';
 	}
     }
+
     loading_tbl = get_loading_table();
     if (loading_tbl) {
 	f = 0;
@@ -283,11 +393,18 @@ struct loaded_feature_searching {
 static void
 rb_provide_feature(VALUE feature)
 {
-    if (OBJ_FROZEN(get_loaded_features())) {
+    VALUE features;
+
+    features = get_loaded_features();
+    if (OBJ_FROZEN(features)) {
 	rb_raise(rb_eRuntimeError,
 		 "$LOADED_FEATURES is frozen; cannot append feature");
     }
-    rb_ary_push(get_loaded_features(), feature);
+    rb_str_freeze(feature);
+
+    rb_ary_push(features, feature);
+    features_index_add(feature, INT2FIX(RARRAY_LEN(features)-1));
+    reset_loaded_features_snapshot();
 }
 
 void
@@ -828,6 +945,8 @@ struct loaded_feature_searching {
     rb_define_virtual_variable("$\"", get_loaded_features, 0);
     rb_define_virtual_variable("$LOADED_FEATURES", get_loaded_features, 0);
     vm->loaded_features = rb_ary_new();
+    vm->loaded_features_snapshot = rb_ary_new();
+    vm->loaded_features_index = rb_hash_new();
 
     rb_define_global_function("load", rb_f_load, -1);
     rb_define_global_function("require", rb_f_require, 1);
diff --git a/vm.c b/vm.c
index 55ccfe7..5391c2a 100644
--- a/vm.c
+++ b/vm.c
@@ -1501,6 +1501,8 @@
 	RUBY_MARK_UNLESS_NULL(vm->mark_object_ary);
 	RUBY_MARK_UNLESS_NULL(vm->load_path);
 	RUBY_MARK_UNLESS_NULL(vm->loaded_features);
+	RUBY_MARK_UNLESS_NULL(vm->loaded_features_snapshot);
+	RUBY_MARK_UNLESS_NULL(vm->loaded_features_index);
 	RUBY_MARK_UNLESS_NULL(vm->top_self);
 	RUBY_MARK_UNLESS_NULL(vm->coverages);
 	rb_gc_mark_locations(vm->special_exceptions, vm->special_exceptions + ruby_special_error_count);
diff --git a/vm_core.h b/vm_core.h
index 9d776c9..484ac5e 100644
--- a/vm_core.h
+++ b/vm_core.h
@@ -322,6 +322,8 @@ enum ruby_special_exceptions {
     VALUE top_self;
     VALUE load_path;
     VALUE loaded_features;
+    VALUE loaded_features_snapshot;
+    VALUE loaded_features_index;
     struct st_table *loading_table;
 
     /* signal */
diff --git a/load.c b/load.c
index 75df5ab..dfea0ef 100644
--- a/load.c
+++ b/load.c
@@ -33,21 +33,40 @@
     return load_path;
 }
 
-VALUE
-rb_get_expanded_load_path(void)
+static void
+rb_construct_expanded_load_path(void)
 {
-    VALUE load_path = rb_get_load_path();
+    rb_vm_t *vm = GET_VM();
+    VALUE load_path = vm->load_path;
     VALUE ary;
     long i;
 
     ary = rb_ary_new2(RARRAY_LEN(load_path));
     for (i = 0; i < RARRAY_LEN(load_path); ++i) {
-	VALUE path = rb_file_expand_path_fast(RARRAY_PTR(load_path)[i], Qnil);
-	rb_str_freeze(path);
-	rb_ary_push(ary, path);
+	VALUE path, as_str, expanded_path;
+	as_str = path = RARRAY_PTR(load_path)[i];
+	StringValue(as_str);
+	if (as_str != path)
+	    rb_ary_store(load_path, i, as_str);
+	rb_str_freeze(as_str);
+	expanded_path = rb_file_expand_path_fast(as_str, Qnil);
+	rb_str_freeze(expanded_path);
+	rb_ary_push(ary, expanded_path);
     }
     rb_obj_freeze(ary);
-    return ary;
+    vm->expanded_load_path = ary;
+    rb_ary_replace(vm->load_path_snapshot, vm->load_path);
+}
+
+static VALUE
+rb_get_expanded_load_path(void)
+{
+    rb_vm_t *vm = GET_VM();
+    if (!rb_ary_shared_with_p(vm->load_path_snapshot, vm->load_path)) {
+	/* The load path was modified.	Rebuild the expanded load path. */
+	rb_construct_expanded_load_path();
+    }
+    return vm->expanded_load_path;
 }
 
 static VALUE
@@ -941,6 +960,8 @@ struct loaded_feature_searching {
     rb_alias_variable(rb_intern("$-I"), id_load_path);
     rb_alias_variable(rb_intern("$LOAD_PATH"), id_load_path);
     vm->load_path = rb_ary_new();
+    vm->expanded_load_path = rb_ary_new();
+    vm->load_path_snapshot = rb_ary_new();
 
     rb_define_virtual_variable("$\"", get_loaded_features, 0);
     rb_define_virtual_variable("$LOADED_FEATURES", get_loaded_features, 0);
diff --git a/ruby.c b/ruby.c
index 2fbd48f..66b2443 100644
--- a/ruby.c
+++ b/ruby.c
@@ -1377,7 +1377,8 @@ struct cmdline_options {
 	long i;
 	VALUE load_path = GET_VM()->load_path;
 	for (i = 0; i < RARRAY_LEN(load_path); ++i) {
-	    rb_enc_associate(RARRAY_PTR(load_path)[i], lenc);
+	    RARRAY_PTR(load_path)[i] =
+		rb_enc_associate(rb_str_dup(RARRAY_PTR(load_path)[i]), lenc);
 	}
     }
     if (!(opt->disable & DISABLE_BIT(gems))) {
diff --git a/vm.c b/vm.c
index 5391c2a..04466b2 100644
--- a/vm.c
+++ b/vm.c
@@ -1500,6 +1500,8 @@
 	RUBY_MARK_UNLESS_NULL(vm->thgroup_default);
 	RUBY_MARK_UNLESS_NULL(vm->mark_object_ary);
 	RUBY_MARK_UNLESS_NULL(vm->load_path);
+	RUBY_MARK_UNLESS_NULL(vm->load_path_snapshot);
+	RUBY_MARK_UNLESS_NULL(vm->expanded_load_path);
 	RUBY_MARK_UNLESS_NULL(vm->loaded_features);
 	RUBY_MARK_UNLESS_NULL(vm->loaded_features_snapshot);
 	RUBY_MARK_UNLESS_NULL(vm->loaded_features_index);
diff --git a/vm_core.h b/vm_core.h
index 484ac5e..2d4e30e 100644
--- a/vm_core.h
+++ b/vm_core.h
@@ -321,6 +321,8 @@ enum ruby_special_exceptions {
     /* load */
     VALUE top_self;
     VALUE load_path;
+    VALUE load_path_snapshot;
+    VALUE expanded_load_path;
     VALUE loaded_features;
     VALUE loaded_features_snapshot;
     VALUE loaded_features_index;