Patch against ruby-1.9.3-p0 to futher improve load.c

load.c.patch

diff --git a/load.c b/load.c
index 0ff4b60..019ccb9 100644
--- a/load.c
+++ b/load.c
@@ -18,6 +18,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,
@@ -129,12 +130,16 @@ 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 feature_basename_length(const char *, long);
+
 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;
     const char *f, *e;
-    long i, len, elen, n;
+    long i, len, elen, n, flen;
     st_table *loading_tbl;
     st_data_t data;
     int type;
@@ -151,8 +156,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 +183,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 +258,174 @@ 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;
+	for (ext = feature + (flen - 1); ext >= feature; ext--) {
+	    if (*ext == '.') return ext - feature;
+	    if (*ext == '/') return flen;
+	}
+	return 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 +433,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
@@ -776,7 +954,7 @@ Init_load()
 
     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);

Is there a version of the patch for 1.8.7? I have a much larger 1.8.7 app.

@skaes I made same patch for 1.8.7 but it gains no improvement cause ruby 1.8.7 do much less work on each iteration of checking file loop.

now it is configurable with RUBY_LOADED_FEATURES_SORTED environment variable: RUBY_LOADED_FEATURES_SORTED=0 turns behaviour to similar with unpatched ruby.

getting corrupt patch when trying git apply on ruby_1_9_3

C:\Users\Jon\Documents\RubyDev\ruby-git>git log -3 --oneline
8f29ff7 * 2011-10-30
2c1d1fb Bump version
14c3e60 Skip too heavy test.

C:\Users\Jon\Documents\RubyDev\ruby-git>git apply --check --verbose load.c.patch
fatal: corrupt patch at line 248

@jonforums issue were in a newline character only. fixed.

I have a report from one man (@saks) about it's application startup time with and without patch:

$ time ./bin/rails runner 'puts'

1.9.3-p0 without patch:
real 0m22.683s
user 0m21.417s
sys 0m0.956s

with patch:
real 0m17.806s
user 0m16.633s
sys 0m0.892s

thanks. looks fine.

git diff --check can't wait to meet you ;)

C:\Users\Jon\Documents\RubyDev\ruby-git>git apply --verbose load.c.patch
load.c.patch:92: trailing whitespace.
/* used to find when equal features run out */
Checking patch load.c...
Applied patch load.c cleanly.
warning: 1 line adds whitespace errors.

Aaaa ok, another trailing space... fixed

$ git checkout load.c
$ wget https://gist.github.com/raw/1272991/02bea3fef4ac3ff0eac1e8571225399842205acc/load.c.patch
--2011-11-03 09:41:13--  https://gist.github.com/raw/1272991/02bea3fef4ac3ff0eac1e8571225399842205acc/load.c.patch
Resolving gist.github.com... 207.97.227.243
Connecting to gist.github.com|207.97.227.243|:443... connected.
HTTP request sent, awaiting response... 302 Found
Location: https://raw.github.com/gist/1272991/02bea3fef4ac3ff0eac1e8571225399842205acc/load.c.patch [following]
--2011-11-03 09:41:14--  https://raw.github.com/gist/1272991/02bea3fef4ac3ff0eac1e8571225399842205acc/load.c.patch
Resolving raw.github.com... 207.97.227.243
Connecting to raw.github.com|207.97.227.243|:443... connected.
HTTP request sent, awaiting response... 200 OK
Length: 7159 (7,0K) [text/plain]
Saving to: `load.c.patch'

100%[===================================================================================================================>] 7 159       --.-K/s   in 0s      

2011-11-03 09:41:15 (173 MB/s) - `load.c.patch' saved [7159/7159]

$ git apply --verbose load.c.patch
Checking patch load.c...
Applied patch load.c cleanly.

@skaes

I measured the effect on a rails application using 'rails runner 1'.
Got only a tiny improvement: down to 1.63 seconds from 1.67 seconds.
Doesn't seem to justify the extra complexity introduced by the patch.
I just retest patch against 1.9.2-p260 on clear rails application (rails new test_load) I've got following results (ubuntu 11.04 AthlonX2 on 2.1GHz):
Before 06-keep-loaded-features-sorted.patch

$ time rails runner 'puts $LOADED_FEATURES.size'
579

real    0m3.077s
user    0m2.660s
sys 0m0.420s

After patch

$ time rails runner 'puts $LOADED_FEATURES.size'
579

real    0m2.834s
user    0m2.436s
sys 0m0.400s

It seems that difference should be at least 8% on such small application. How did you get only 2.5% percent difference?

install it under rvm:

rvm install ruby-1.9.3-p0 --patch load.c.patch -n patched

Fixed bug, which prevents gem update --system.
Actually, I think this is hidden bug in stock ruby. I filled pull request ruby/ruby#63 and ticket in redmine http://redmine.ruby-lang.org/issues/5727 .

Cumulative patch: this and "cached expanded load path" https://gist.github.com/1484985