Cumulative: Sorted loaded features + Cached load path (against 1.9.3-p0)

cached_lp_sorted_lf.patch

diff --git a/file.c b/file.c
index 81f28ff..6aad4b0 100644
--- a/file.c
+++ b/file.c
@@ -2819,6 +2819,20 @@ ntfs_tail(const char *path)
     buflen = RSTRING_LEN(result),\
     pend = p + buflen)
 
+#define EXPAND_PATH()\
+    if ( !(abs_mode & FEP_DIR_EXPANDED) ) { \
+	file_expand_path(dname, Qnil, abs_mode, result); \
+    } \
+    else { \
+	size_t dlen = RSTRING_LEN(dname); \
+	BUFCHECK(dlen > buflen); \
+	strncpy(buf, RSTRING_PTR(dname), dlen + 1); \
+	rb_str_set_len(result, dlen); \
+	rb_enc_associate(result, rb_enc_check(result, dname)); \
+	ENC_CODERANGE_CLEAR(result); \
+    }
+
+
 VALUE
 rb_home_dir(const char *user, VALUE result)
 {
@@ -2863,6 +2877,8 @@ rb_home_dir(const char *user, VALUE result)
     return result;
 }
 
+#define FEP_FILE_ABSOLUTE 1
+#define FEP_DIR_EXPANDED 2
 static VALUE
 file_expand_path(VALUE fname, VALUE dname, int abs_mode, VALUE result)
 {
@@ -2875,7 +2891,7 @@ file_expand_path(VALUE fname, VALUE dname, int abs_mode, VALUE result)
     BUFINIT();
     tainted = OBJ_TAINTED(fname);
 
-    if (s[0] == '~' && abs_mode == 0) {      /* execute only if NOT absolute_path() */
+    if (s[0] == '~' && !(abs_mode & FEP_FILE_ABSOLUTE)) {      /* execute only if NOT absolute_path() */
 	long userlen = 0;
 	tainted = 1;
 	if (isdirsep(s[1]) || s[1] == '\0') {
@@ -2923,7 +2939,7 @@ file_expand_path(VALUE fname, VALUE dname, int abs_mode, VALUE result)
 	    /* specified drive, but not full path */
 	    int same = 0;
 	    if (!NIL_P(dname) && !not_same_drive(dname, s[0])) {
-		file_expand_path(dname, Qnil, abs_mode, result);
+		EXPAND_PATH();
 		BUFINIT();
 		if (has_drive_letter(p) && TOLOWER(p[0]) == TOLOWER(s[0])) {
 		    /* ok, same drive */
@@ -2949,7 +2965,7 @@ file_expand_path(VALUE fname, VALUE dname, int abs_mode, VALUE result)
 #endif
     else if (!rb_is_absolute_path(s)) {
 	if (!NIL_P(dname)) {
-	    file_expand_path(dname, Qnil, abs_mode, result);
+	    EXPAND_PATH();
 	    BUFINIT();
 	    rb_enc_associate(result, rb_enc_check(result, fname));
 	}
@@ -3232,7 +3248,7 @@ VALUE
 rb_file_absolute_path(VALUE fname, VALUE dname)
 {
     check_expand_path_args(fname, dname);
-    return file_expand_path(fname, dname, 1, EXPAND_PATH_BUFFER());
+    return file_expand_path(fname, dname, FEP_FILE_ABSOLUTE, EXPAND_PATH_BUFFER());
 }
 
 /*
@@ -5103,13 +5119,23 @@ rb_find_file_ext(VALUE *filep, const char *const *ext)
     return rb_find_file_ext_safe(filep, ext, rb_safe_level());
 }
 
+#define GET_LOAD_PATH() \
+    if (cached_expanded_load_path) { \
+	RB_GC_GUARD(load_path) = rb_get_expanded_load_path(); \
+	dirs_mode = FEP_DIR_EXPANDED; \
+    } \
+    else { \
+	RB_GC_GUARD(load_path) = rb_get_load_path(); \
+	dirs_mode = 0; \
+    }
+
 int
 rb_find_file_ext_safe(VALUE *filep, const char *const *ext, int safe_level)
 {
     const char *f = StringValueCStr(*filep);
     VALUE fname = *filep, load_path, tmp;
     long i, j, fnlen;
-    int expanded = 0;
+    int expanded = 0, dirs_mode;
 
     if (!ext[0]) return 0;
 
@@ -5144,7 +5170,7 @@ rb_find_file_ext_safe(VALUE *filep, const char *const *ext, int safe_level)
 	rb_raise(rb_eSecurityError, "loading from non-absolute path %s", f);
     }
 
-    RB_GC_GUARD(load_path) = rb_get_load_path();
+    GET_LOAD_PATH();
     if (!load_path) return 0;
 
     fname = rb_str_dup(*filep);
@@ -5158,7 +5184,7 @@ rb_find_file_ext_safe(VALUE *filep, const char *const *ext, int safe_level)
 
 	    RB_GC_GUARD(str) = rb_get_path_check(str, safe_level);
 	    if (RSTRING_LEN(str) == 0) continue;
-	    file_expand_path(fname, str, 0, tmp);
+	    file_expand_path(fname, str, dirs_mode, tmp);
 	    if (file_load_ok(RSTRING_PTR(tmp))) {
 		*filep = copy_path_class(tmp, *filep);
 		return (int)(j+1);
@@ -5182,7 +5208,7 @@ rb_find_file_safe(VALUE path, int safe_level)
 {
     VALUE tmp, load_path;
     const char *f = StringValueCStr(path);
-    int expanded = 0;
+    int expanded = 0, dirs_mode;
 
     if (f[0] == '~') {
 	tmp = file_expand_path_1(path);
@@ -5208,7 +5234,7 @@ rb_find_file_safe(VALUE path, int safe_level)
 	rb_raise(rb_eSecurityError, "loading from non-absolute path %s", f);
     }
 
-    RB_GC_GUARD(load_path) = rb_get_load_path();
+    GET_LOAD_PATH();
     if (load_path) {
 	long i;
 
@@ -5217,7 +5243,7 @@ rb_find_file_safe(VALUE path, int safe_level)
 	    VALUE str = RARRAY_PTR(load_path)[i];
 	    RB_GC_GUARD(str) = rb_get_path_check(str, safe_level);
 	    if (RSTRING_LEN(str) > 0) {
-		file_expand_path(path, str, 0, tmp);
+		file_expand_path(path, str, dirs_mode, tmp);
 		f = RSTRING_PTR(tmp);
 		if (file_load_ok(f)) goto found;
 	    }
diff --git a/internal.h b/internal.h
index 172e7f4..447557f 100644
--- a/internal.h
+++ b/internal.h
@@ -108,6 +108,10 @@ VALUE rb_iseq_clone(VALUE iseqval, VALUE newcbase);
 
 /* load.c */
 VALUE rb_get_load_path(void);
+VALUE rb_get_expanded_load_path(void);
+void rb_reset_expanded_cache();
+void rb_load_path_ary_push(VALUE path);
+extern int cached_expanded_load_path;
 
 /* math.c */
 VALUE rb_math_atan2(VALUE, VALUE);
diff --git a/load.c b/load.c
index 0ff4b60..eac1863 100644
--- a/load.c
+++ b/load.c
@@ -4,6 +4,7 @@
 
 #include "ruby/ruby.h"
 #include "ruby/util.h"
+#include "ruby/encoding.h"
 #include "internal.h"
 #include "dln.h"
 #include "eval_intern.h"
@@ -18,6 +19,7 @@ VALUE ruby_dln_librefs;
 #define IS_DLEXT(e) (strcmp((e), DLEXT) == 0)
 #endif
 
+static int sorted_loaded_features = 1;
 
 static const char *const loadable_ext[] = {
     ".rb", DLEXT,
@@ -34,21 +36,34 @@ rb_get_load_path(void)
     return load_path;
 }
 
+static VALUE rb_checked_expanded_cache(int*);
+static void rb_set_expanded_cache(VALUE, int);
+static VALUE rb_expand_load_paths(int, VALUE*, int*);
+int cached_expanded_load_path = 1;
+
 VALUE
 rb_get_expanded_load_path(void)
 {
-    VALUE load_path = rb_get_load_path();
-    VALUE ary;
-    long i;
+    VALUE expanded = rb_checked_expanded_cache(NULL);
 
-    ary = rb_ary_new2(RARRAY_LEN(load_path));
-    for (i = 0; i < RARRAY_LEN(load_path); ++i) {
-	VALUE path = rb_file_expand_path(RARRAY_PTR(load_path)[i], Qnil);
-	rb_str_freeze(path);
-	rb_ary_push(ary, path);
+    if ( !RTEST(expanded) ) {
+	VALUE load_path = rb_get_load_path();
+	int has_relative = 0;
+
+	if (!load_path) return 0;
+
+	expanded = rb_expand_load_paths(
+			RARRAY_LEN(load_path), RARRAY_PTR(load_path),
+			&has_relative);
+	RB_GC_GUARD(load_path);
+
+	if (cached_expanded_load_path) {
+	    rb_set_expanded_cache(expanded, has_relative);
+	}
+    } else {
+	expanded = rb_ary_dup(expanded);
     }
-    rb_obj_freeze(ary);
-    return ary;
+    return expanded;
 }
 
 static VALUE
@@ -129,6 +144,9 @@ loaded_feature_path_i(st_data_t v, st_data_t b, st_data_t f)
     return ST_STOP;
 }
 
+static int rb_feature_first_equal_or_greater(VALUE, const char *, long);
+static int rb_stop_search_feature(VALUE, const char *, long);
+
 static int
 rb_feature_p(const char *feature, const char *ext, int rb, int expanded, const char **fn)
 {
@@ -151,8 +169,10 @@ rb_feature_p(const char *feature, const char *ext, int rb, int expanded, const c
 	type = 0;
     }
     features = get_loaded_features();
-    for (i = 0; i < RARRAY_LEN(features); ++i) {
+    i = rb_feature_first_equal_or_greater(features, feature, len);
+    for (; i < RARRAY_LEN(features); ++i) {
 	v = RARRAY_PTR(features)[i];
+	if (rb_stop_search_feature(v, feature, len)) break;
 	f = StringValuePtr(v);
 	if ((n = RSTRING_LEN(v)) < len) continue;
 	if (strncmp(f, feature, len) != 0) {
@@ -176,14 +196,14 @@ rb_feature_p(const char *feature, const char *ext, int rb, int expanded, const c
 	}
     }
     loading_tbl = get_loading_table();
-    if (loading_tbl) {
+    if (loading_tbl && loading_tbl->num_entries > 0) {
 	f = 0;
 	if (!expanded) {
 	    struct loaded_feature_searching fs;
 	    fs.name = feature;
 	    fs.len = len;
 	    fs.type = type;
-	    fs.load_path = load_path ? load_path : rb_get_load_path();
+	    fs.load_path = load_path ? load_path : rb_get_expanded_load_path();
 	    fs.result = 0;
 	    st_foreach(loading_tbl, loaded_feature_path_i, (st_data_t)&fs);
 	    if ((f = fs.result) != 0) {
@@ -251,6 +271,170 @@ rb_feature_provided(const char *feature, const char **loading)
     return FALSE;
 }
 
+static int
+feature_basename_length(const char *feature, long flen)
+{
+    if (sorted_loaded_features) {
+	const char *ext = strrchr(feature, '.');
+	return ext && !strchr(ext, '/') ? ext - feature : flen;
+    } else {
+	return 0;
+    }
+}
+
+static int
+compare_feature_name(const char *left, long llen, const char *right, long rlen)
+{
+    int diff = 0;
+    while (llen-- && rlen--) {
+	diff = left[llen] - right[rlen];
+	if (diff) break;
+	if (left[llen] == '/') break;
+    }
+    return diff;
+}
+
+static int
+rb_compare_feature_name(VALUE loaded, const char *feature, long flen)
+{
+    const char *loaded_name = StringValuePtr(loaded);
+    long loaded_len = feature_basename_length(loaded_name, RSTRING_LEN(loaded));
+    return compare_feature_name(loaded_name, loaded_len, feature, flen);
+}
+
+/* used to find when equal features run out */
+static int
+rb_stop_search_feature(VALUE loaded, const char *feature, long flen)
+{
+    if (sorted_loaded_features)
+	return rb_compare_feature_name(loaded, feature, flen) > 0;
+    else
+	return FALSE;
+}
+
+/* returns first position to search feature from */
+static int
+rb_feature_first_equal_or_greater(VALUE features, const char *feature, long flen)
+{
+    if (sorted_loaded_features) {
+	int before = 0, first = RARRAY_LEN(features);
+	VALUE *values = RARRAY_PTR(features);
+	if (first == 0)
+	    return 0;
+	if (rb_compare_feature_name(values[0], feature, flen) >= 0)
+	    return 0;
+
+	while (first - before > 1) {
+	    int mid = (first + before) / 2;
+	    int cmp = rb_compare_feature_name(values[mid], feature, flen);
+	    if (cmp >= 0)
+		first = mid;
+	    else
+		before = mid;
+	}
+	return first;
+    } else {
+	return 0;
+    }
+}
+
+/* returns position to insert new feature in */
+static int
+rb_feature_first_greater(VALUE features, const char *feature, long flen)
+{
+    if (sorted_loaded_features) {
+	int before = 0, first = RARRAY_LEN(features);
+	VALUE *values = RARRAY_PTR(features);
+	if (first == 0)
+	    return 0;
+	if (rb_compare_feature_name(values[0], feature, flen) > 0)
+	    return 0;
+	if (rb_compare_feature_name(values[first-1], feature, flen) <= 0)
+	    return first;
+
+	while (first - before > 1) {
+	    int mid = (first + before) / 2;
+	    int cmp = rb_compare_feature_name(values[mid], feature, flen);
+	    if (cmp > 0)
+		first = mid;
+	    else
+		before = mid;
+	}
+	return first;
+    } else {
+	return RARRAY_LEN(features);
+    }
+}
+
+
+static VALUE
+rb_push_feature_1(VALUE features, VALUE feature)
+{
+    const char *fname = StringValuePtr(feature);
+    long flen = feature_basename_length(fname, RSTRING_LEN(feature));
+    int i = rb_feature_first_greater(features, fname, flen);
+    rb_ary_push(features, feature);
+    if ( i < RARRAY_LEN(features) - 1 ) {
+	MEMMOVE(RARRAY_PTR(features) + i + 1, RARRAY_PTR(features) + i,
+		VALUE, RARRAY_LEN(features) - i - 1);
+	RARRAY_PTR(features)[i] = feature;
+    }
+    return features;
+}
+
+static VALUE
+rb_push_feature_m(int argc, VALUE *argv, VALUE features)
+{
+    while (argc--) {
+	rb_push_feature_1(features, *argv++);
+    }
+    return features;
+}
+
+static VALUE
+rb_concat_features(VALUE features, VALUE add)
+{
+    add = rb_convert_type(add, T_ARRAY, "Array", "to_ary");
+    if (RARRAY_LEN(add)) {
+	rb_push_feature_m(RARRAY_LEN(add), RARRAY_PTR(add), features);
+    }
+    return features;
+}
+static const char *load_features_undefined_methods[] = {
+    "[]=", "reverse!", "rotate!", "sort!", "sort_by!",
+    "collect!", "map!", "shuffle!", "fill", "insert",
+    NULL
+};
+
+static VALUE
+rb_loaded_features_init(void)
+{
+    char *sorted_flag;
+    const char **name;
+    VALUE loaded_features = rb_ary_new();
+    VALUE loaded_features_c = rb_singleton_class(loaded_features);
+
+    sorted_flag = getenv("RUBY_LOADED_FEATURES_SORTED");
+    if (sorted_flag != NULL) {
+	int sorted_set = atoi(sorted_flag);
+	if (RTEST(ruby_verbose))
+	    fprintf(stderr, "sorted_loaded_features=%d (%d)\n", sorted_set, sorted_loaded_features);
+	sorted_loaded_features = sorted_set;
+    }
+
+    for(name = load_features_undefined_methods; *name; name++) {
+	rb_undef_method(loaded_features_c, *name);
+    }
+
+    if (sorted_loaded_features) {
+	rb_define_method(loaded_features_c, "<<", rb_push_feature_1, 1);
+	rb_define_method(loaded_features_c, "push", rb_push_feature_m, -1);
+	rb_define_method(loaded_features_c, "concat", rb_concat_features, 1);
+	rb_define_method(loaded_features_c, "unshift", rb_push_feature_m, -1);
+    }
+    return loaded_features;
+}
+
 static void
 rb_provide_feature(VALUE feature)
 {
@@ -258,7 +442,10 @@ rb_provide_feature(VALUE feature)
 	rb_raise(rb_eRuntimeError,
 		 "$LOADED_FEATURES is frozen; cannot append feature");
     }
-    rb_ary_push(get_loaded_features(), feature);
+    if (sorted_loaded_features)
+	rb_push_feature_1(get_loaded_features(), feature);
+    else
+	rb_ary_push(get_loaded_features(), feature);
 }
 
 void
@@ -760,6 +947,223 @@ rb_f_autoload_p(VALUE obj, VALUE sym)
     return rb_mod_autoload_p(klass, sym);
 }
 
+// $LOAD_PATH methods which invalidates cache
+static const char *load_path_reset_cache_methods[] = {
+    "[]=", "collect!", "compact!", "delete",
+    "delete_if", "fill", "flatten!", "insert", "keep_if",
+    "map!", "reject!", "replace", "select!", "shuffle!",
+    "sort!", "sort_by!", "uniq!", NULL
+};
+
+// $LOAD_PATH methods which sends also to cache
+static const char *load_path_apply_to_cache_methods[] = {
+    "clear", "delete_at", "pop", "reverse!", "rotate!",
+    "shift", "slice!", NULL
+};
+
+// $LOAD_PATH methods which sends to cache whith expanded arguments
+static const char *load_path_apply_expanded_methods[] = {
+    "<<", "push", "unshift", NULL
+};
+
+void
+rb_reset_expanded_cache()
+{
+    GET_VM()->load_path_expanded_cache = 0;
+}
+
+static VALUE
+rb_load_path_expanded_cache()
+{
+    VALUE cache = GET_VM()->load_path_expanded_cache;
+    VALUE expanded = Qnil;
+    if (RTEST(cache)) {
+	expanded = RARRAY_PTR(cache)[2];
+    }
+    return expanded;
+}
+
+// Return cache only if we still in the same working directory
+// and filesystem_encoding didn't change
+// Invalidate cache otherwise
+static VALUE
+rb_checked_expanded_cache(int *has_relative)
+{
+    VALUE cache = GET_VM()->load_path_expanded_cache;
+    VALUE expanded = Qnil;
+    if (RTEST(cache)) {
+	VALUE curwd = RARRAY_PTR(cache)[0];
+	VALUE encindex = RARRAY_PTR(cache)[1];
+	int cache_valid = rb_filesystem_encindex() == FIX2INT(encindex);
+
+	if ( cache_valid ) {
+	    cache_valid = curwd == Qtrue;
+	    if (has_relative) {
+		*has_relative = cache_valid;
+	    }
+	    if (!cache_valid ) {
+		char *cwd = my_getcwd();
+		cache_valid = !strcmp(RSTRING_PTR(curwd), cwd);
+		xfree(cwd);
+	    }
+	}
+
+	if ( !cache_valid ) {
+	    rb_reset_expanded_cache();
+	} else {
+	    expanded = RARRAY_PTR(cache)[2];
+	}
+    }
+    RB_GC_GUARD(cache);
+    return expanded;
+}
+
+static void
+rb_set_expanded_cache(VALUE expanded, int has_relative)
+{
+    VALUE cache = rb_ary_new2(2);
+
+    if (has_relative) {
+	char *cwd = my_getcwd();
+	rb_ary_push(cache, rb_str_new_cstr(cwd));
+	xfree(cwd);
+    } else {
+	rb_ary_push(cache, Qtrue);
+    }
+
+    rb_ary_push(cache, INT2FIX(rb_filesystem_encindex()));
+    rb_ary_push(cache, rb_ary_dup(expanded));
+    GET_VM()->load_path_expanded_cache = cache;
+}
+
+static VALUE
+rb_expand_load_paths(int pathc, VALUE* paths, int *has_relative)
+{
+    int i;
+    const char *p;
+    VALUE path, expanded = rb_ary_new2(pathc);
+
+    for(i = 0; i < pathc; i++) {
+	path = rb_get_path(paths[i]);
+	p = RSTRING_PTR(path);
+	*has_relative = *has_relative || !rb_is_absolute_path(p);
+	path = rb_file_expand_path(path, Qnil);
+	rb_str_freeze(path);
+	rb_ary_push(expanded, path);
+    }
+
+    return expanded;
+}
+
+// Invalidating $LOAD_PATH methods implementation
+static VALUE
+rb_load_path_reset_cache_method(int argc, VALUE *argv, VALUE self)
+{
+    rb_reset_expanded_cache();
+    return rb_call_super(argc, argv);
+}
+
+// Proxying $LOAD_PATH methods implementation
+static VALUE
+rb_load_path_apply_to_cache_method(int argc, VALUE *argv, VALUE self)
+{
+    VALUE load_path_expanded = rb_load_path_expanded_cache();
+    if (RTEST(load_path_expanded)) {
+	ID func = rb_frame_this_func();
+	rb_funcall2(load_path_expanded, func, argc, argv);
+    }
+    return rb_call_super(argc, argv);
+}
+
+// Proxying with expansion $LOAD_PATH methods implementation
+static VALUE
+rb_load_path_apply_expanded_method(int argc, VALUE *argv, VALUE self)
+{
+    int old_has_relative = 0;
+    // We call methods on cache only if we still in the same working directory
+    VALUE load_path_expanded = rb_checked_expanded_cache(&old_has_relative);
+    if (RTEST(load_path_expanded)) {
+	int has_relative = 0;
+	ID func = rb_frame_this_func();
+	VALUE expanded = rb_expand_load_paths(argc, argv, &has_relative);
+
+	rb_funcall2(load_path_expanded, func, argc, RARRAY_PTR(expanded));
+
+	if (!old_has_relative && has_relative) {
+	    rb_set_expanded_cache(load_path_expanded, has_relative);
+	}
+	RB_GC_GUARD(expanded);
+    }
+    return rb_call_super(argc, argv);
+}
+// $LOAD_PATH.concat(ary) - special, we call push(*ary) instead
+// cause I'm lazy a bit and wish not to rewrite method above second time :)
+static VALUE
+rb_load_path_concat(VALUE self, VALUE ary)
+{
+    ID push;
+    CONST_ID(push, "push");
+    RB_GC_GUARD(ary);
+    return rb_funcall2(self, push, RARRAY_LEN(ary), RARRAY_PTR(ary));
+}
+
+void
+rb_load_path_ary_push(VALUE path)
+{
+    int old_has_relative = 0;
+    VALUE load_path_expanded = rb_checked_expanded_cache(&old_has_relative);
+    if (RTEST(load_path_expanded)) {
+	int has_relative = 0;
+	VALUE expanded = rb_expand_load_paths(1, &path, &has_relative);
+
+	rb_ary_push(load_path_expanded, RARRAY_PTR(expanded)[0]);
+
+	if (!old_has_relative && has_relative) {
+	    rb_set_expanded_cache(load_path_expanded, has_relative);
+	}
+	RB_GC_GUARD(expanded);
+    }
+
+    rb_ary_push(rb_get_load_path(), path);
+}
+
+static VALUE
+rb_load_path_init(void)
+{
+    const char **name;
+    VALUE load_path = rb_ary_new();
+    char *cached_flag;
+
+    cached_flag = getenv("RUBY_CACHED_LOAD_PATH");
+    if (cached_flag != NULL) {
+	cached_expanded_load_path = atoi(cached_flag);
+    }
+
+    // Do all the magick if user did not disable it
+    // with RUBY_CACHED_LOAD_PATH=0 environment variable
+    if (cached_expanded_load_path) {
+	VALUE load_path_c = rb_singleton_class(load_path);
+
+	for(name = load_path_reset_cache_methods; *name; name++ ) {
+	    rb_define_method(load_path_c, *name, rb_load_path_reset_cache_method, -1);
+	}
+
+	for(name = load_path_apply_to_cache_methods; *name; name++ ) {
+	    rb_define_method(load_path_c, *name, rb_load_path_apply_to_cache_method, -1);
+	}
+
+	for(name = load_path_apply_expanded_methods; *name; name++ ) {
+	    rb_define_method(load_path_c, *name, rb_load_path_apply_expanded_method, -1);
+	}
+
+	rb_define_method(load_path_c, "concat", rb_load_path_concat, 1);
+    }
+
+    rb_reset_expanded_cache();
+
+    return load_path;
+}
+
 void
 Init_load()
 {
@@ -772,11 +1176,11 @@ Init_load()
     rb_define_hooked_variable(var_load_path, (VALUE*)vm, load_path_getter, rb_gvar_readonly_setter);
     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->load_path = rb_load_path_init();
 
     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 = rb_loaded_features_init();
 
     rb_define_global_function("load", rb_f_load, -1);
     rb_define_global_function("require", rb_f_require, 1);
diff --git a/ruby.c b/ruby.c
index b53784f..0897400 100644
--- a/ruby.c
+++ b/ruby.c
@@ -209,7 +209,6 @@ push_include(const char *path, VALUE (*filter)(VALUE))
 {
     const char sep = PATH_SEP_CHAR;
     const char *p, *s;
-    VALUE load_path = GET_VM()->load_path;
 
     p = path;
     while (*p) {
@@ -217,7 +216,7 @@ push_include(const char *path, VALUE (*filter)(VALUE))
 	    p++;
 	if (!*p) break;
 	for (s = p; *s && *s != sep; s = CharNext(s));
-	rb_ary_push(load_path, (*filter)(rubylib_mangled_path(p, s - p)));
+	rb_load_path_ary_push((*filter)(rubylib_mangled_path(p, s - p)));
 	p = s;
     }
 }
@@ -338,7 +337,6 @@ ruby_init_loadpath(void)
 void
 ruby_init_loadpath_safe(int safe_level)
 {
-    VALUE load_path;
     ID id_initial_load_path_mark;
     extern const char ruby_initial_load_paths[];
     const char *paths = ruby_initial_load_paths;
@@ -438,7 +436,6 @@ ruby_init_loadpath_safe(int safe_level)
 #define RUBY_RELATIVE(path, len) rubylib_mangled_path((path), (len))
 #define PREFIX_PATH() RUBY_RELATIVE(exec_prefix, sizeof(exec_prefix)-1)
 #endif
-    load_path = GET_VM()->load_path;
 
     if (safe_level == 0) {
 #ifdef MANGLED_PATH
@@ -452,7 +449,7 @@ ruby_init_loadpath_safe(int safe_level)
 	size_t len = strlen(paths);
 	VALUE path = RUBY_RELATIVE(paths, len);
 	rb_ivar_set(path, id_initial_load_path_mark, path);
-	rb_ary_push(load_path, path);
+	rb_load_path_ary_push(path);
 	paths += len + 1;
     }
 
@@ -1349,6 +1346,7 @@ process_options(int argc, char **argv, struct cmdline_options *opt)
 	for (i = 0; i < RARRAY_LEN(load_path); ++i) {
 	    rb_enc_associate(RARRAY_PTR(load_path)[i], lenc);
 	}
+	rb_reset_expanded_cache();
     }
     if (!(opt->disable & DISABLE_BIT(gems))) {
 #if defined DISABLE_RUBYGEMS && DISABLE_RUBYGEMS
diff --git a/vm.c b/vm.c
index 2d7e15c..d1fe744 100644
--- a/vm.c
+++ b/vm.c
@@ -1575,6 +1575,7 @@ rb_vm_mark(void *ptr)
 	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_expanded_cache);
 	RUBY_MARK_UNLESS_NULL(vm->loaded_features);
 	RUBY_MARK_UNLESS_NULL(vm->top_self);
 	RUBY_MARK_UNLESS_NULL(vm->coverages);
diff --git a/vm_core.h b/vm_core.h
index 0dda1c4..f4dc58a 100644
--- a/vm_core.h
+++ b/vm_core.h
@@ -298,6 +298,7 @@ typedef struct rb_vm_struct {
     /* load */
     VALUE top_self;
     VALUE load_path;
+    VALUE load_path_expanded_cache;
     VALUE loaded_features;
     struct st_table *loading_table;
 

$ rvm 1.9.3-p0,sorted_loaded_features_and_cached_load_path,sorted_loaded_features_and_cached_load_path_and_optimized_hash do bash -c 'rvm current; for i in {1..5}; do /usr/bin/time -l rake test 2>&1 | egrep "real|maximum"; done; echo'
ruby-1.9.3-p0
        8.90 real         5.76 user         0.64 sys
  72765440  maximum resident set size
        8.64 real         5.74 user         0.61 sys
  73023488  maximum resident set size
        8.68 real         5.77 user         0.61 sys
  73445376  maximum resident set size
        8.46 real         5.72 user         0.58 sys
  73777152  maximum resident set size
        8.57 real         5.75 user         0.58 sys
  72044544  maximum resident set size

ruby-1.9.3-p0-patched
        7.97 real         4.95 user         0.59 sys
  65732608  maximum resident set size
        7.66 real         4.95 user         0.55 sys
  64376832  maximum resident set size
        7.64 real         4.92 user         0.55 sys
  63041536  maximum resident set size
        7.72 real         4.94 user         0.57 sys
  63700992  maximum resident set size
        7.64 real         4.93 user         0.55 sys
  64958464  maximum resident set size

ruby-1.9.3-p0-patched2
        7.99 real         4.82 user         0.61 sys
  65138688  maximum resident set size
        7.63 real         4.83 user         0.57 sys
  66949120  maximum resident set size
        7.81 real         4.86 user         0.57 sys
  66711552  maximum resident set size
        7.64 real         4.82 user         0.57 sys
  67518464  maximum resident set size
        7.65 real         4.87 user         0.56 sys
  66207744  maximum resident set size

Btw, I think, travis-ci guys can be persuaded to check out this patches in production and share resulting stats. @michaelklishin is that possible?

rvm 1.9.3-p0,sorted_loaded_features_and_cached_load_path,sorted_loaded_features_and_cached_load_path_and_optimized_hash do bash -c 'rvm current; for i in {1..5}; do /usr/bin/time -l rails r "" 2>&1 | egrep "real|maximum"; done; echo' 
ruby-1.9.3-p0
        2.64 real         2.31 user         0.31 sys
  56811520  maximum resident set size
        2.63 real         2.30 user         0.31 sys
  55255040  maximum resident set size
        2.70 real         2.34 user         0.30 sys
  52371456  maximum resident set size
        2.63 real         2.31 user         0.30 sys
  56295424  maximum resident set size
        2.71 real         2.33 user         0.31 sys
  54337536  maximum resident set size

ruby-1.9.3-p0-patched
        2.20 real         1.85 user         0.30 sys
  38674432  maximum resident set size
        2.10 real         1.80 user         0.28 sys
  38678528  maximum resident set size
        2.17 real         1.84 user         0.28 sys
  38866944  maximum resident set size
        2.20 real         1.87 user         0.29 sys
  39174144  maximum resident set size
        2.11 real         1.82 user         0.28 sys
  39358464  maximum resident set size

ruby-1.9.3-p0-patched2
        2.03 real         1.68 user         0.30 sys
  41226240  maximum resident set size
        1.97 real         1.67 user         0.28 sys
  41050112  maximum resident set size
        1.93 real         1.64 user         0.28 sys
  40411136  maximum resident set size
        2.01 real         1.69 user         0.29 sys
  41975808  maximum resident set size
        2.09 real         1.74 user         0.29 sys
  40308736  maximum resident set size

I have updated hash_optimize patch, so that it should be more space effective and faster.

If you find patches useful, please vote on them:
hash-optimize patches
cache expanded load path patch
sorted loaded features patch

New results – https://gist.github.com/1656693
Thanks for the patches! I'm not sure if +1 is appropriate for ruby-core, so I dont know how would I vote there :(

@funny-falcon, can you make new cumulative patch with (hash-optimize, cache expanded load path and sorted loded features) ? I will use this patch in on local machine for development.

@yury , @brainopia here is united patch: https://gist.github.com/1658360
(for some reason, load time could be a bit worse than when this two patches applied separately, cause I remove patching file.c .
But it is still faster than stock ruby-1.9.3-p0)

@funny-falcon, thanks