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;
 

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