From: Nobuyoshi Nakada <nobu@...>
Date: 2008-01-23T15:54:57+09:00
Subject: [ruby-dev:33308] Re: [ruby-cvs:22386] Ruby:r15149 (trunk): * string.c (rb_str_each_char): move forward.

なかだです。

At Mon, 21 Jan 2008 21:05:33 +0900,
Yukihiro Matsumoto wrote in [ruby-dev:33254]:
> |> 変更がないことが確認できればそのほうがいいんですけどね。
> |
> |freezeしたコピーを作っておいて、変更の影響を受けないようにすると
> |いうのを思い付きました。当然のことながら格段に速くなるようです。
> 
> んじゃ、この線でコミットしてください。

もうひとつ思い付きました。

rb_str_modify()がsharedをクリアすることを利用して、ある時点以降
に変更されたか(正確には変更しようとされたか)チェックできそうです。


Index: string.c
===================================================================
--- string.c	(revision 15180)
+++ string.c	(working copy)
@@ -394,9 +394,9 @@ rb_str_new4(VALUE orig)
     if (OBJ_FROZEN(orig)) return orig;
     klass = rb_obj_class(orig);
-    if (STR_SHARED_P(orig) && (str = RSTRING(orig)->as.heap.aux.shared)
-	&& klass == RBASIC(str)->klass) {
+    if (STR_SHARED_P(orig) && (str = RSTRING(orig)->as.heap.aux.shared)) {
 	long ofs;
 	ofs = RSTRING_LEN(str) - RSTRING_LEN(orig);
-	if ((ofs > 0) || (!OBJ_TAINTED(str) && OBJ_TAINTED(orig))) {
+	if ((ofs > 0) || (klass != RBASIC(str)->klass) ||
+	    (!OBJ_TAINTED(str) && OBJ_TAINTED(orig))) {
 	    str = str_new3(klass, str);
 	    RSTRING(str)->as.heap.ptr += ofs;
@@ -980,4 +980,58 @@ rb_str_dup_frozen(VALUE str)
 }
 
+static VALUE
+str_snapshot(VALUE str)
+{
+    VALUE snap;
+
+    if (STR_ASSOC_P(str)) {
+	snap = str_alloc(rb_obj_class(str));
+	FL_SET(str, STR_ASSOC);
+	RSTRING(snap)->as.heap.aux.shared = RSTRING(str)->as.heap.aux.shared;
+	rb_enc_copy(snap, str);
+	OBJ_INFECT(snap, str);
+    }
+    else {
+	snap = rb_str_new4(str);
+    }
+    return snap;
+}
+
+static int
+str_modified_since(VALUE str, VALUE snap)
+{
+    /*
+     * encodings must be same, and snapshot of assocated is also
+     * assocated but unasscociated when to be modified.
+     */
+    const long invariant_bits = STR_ASSOC|ENCODING_MASK;
+    const long strf = RBASIC(str)->flags;
+    const long diff = strf ^ RBASIC(snap)->flags;
+
+    if (diff & invariant_bits) return 1;
+    if (!(strf & STR_NOEMBED)) {
+	/* check first since embeded strings are small */
+	long len = (strf & RSTRING_EMBED_LEN_MASK) >> RSTRING_EMBED_LEN_SHIFT;
+	if (diff & (STR_NOEMBED|RSTRING_EMBED_LEN_MASK))
+	    return 1;
+	if (memcmp(RSTRING(str)->as.ary, RSTRING(snap)->as.ary, len))
+	    return 1;
+    }
+    if (ENCODING_GET_INLINED(str) == ENCODING_INLINE_MAX &&
+	rb_enc_internal_get_index(str) != rb_enc_internal_get_index(snap)) {
+	return 1;
+    }
+    if (strf & STR_ASSOC) {
+	snap = RSTRING(snap)->as.heap.aux.shared;
+    }
+    else if (!(strf & STR_NOEMBED)) {
+	return 0;
+    }
+    else if (!(strf & STR_SHARED)) {
+	return 1;
+    }
+    return RSTRING(str)->as.heap.aux.shared != snap;
+}
+
 VALUE
 rb_str_locktmp(VALUE str)
@@ -4469,10 +4523,9 @@ rb_str_each_line(int argc, VALUE *argv, 
 {
     rb_encoding *enc;
-    VALUE rs;
+    VALUE rs, line;
+    volatile VALUE snapshot;
     int newline;
-    char *p = RSTRING_PTR(str), *pend = p + RSTRING_LEN(str), *s = p;
-    char *ptr = p;
-    long len = RSTRING_LEN(str), rslen;
-    VALUE line;
+    const char *ptr, *pend, *p, *s;
+    long i, len, rslen;
     int n;
 
@@ -4486,8 +4539,14 @@ rb_str_each_line(int argc, VALUE *argv, 
 	return str;
     }
-    StringValue(rs);
+
+    ptr = s = p = RSTRING_PTR(str);
+    len = RSTRING_LEN(str);
+    pend = p + len;
+    snapshot = str_snapshot(str);
+
+    rs = rb_str_new4(StringValue(rs));
     enc = rb_enc_check(str, rs);
     if (rs == rb_default_rs) {
-	while (p < pend) {
+	for (i = 0; p < pend; i++) {
 	    n = rb_enc_mbclen(p, pend, enc);
 	    if (rb_enc_is_newline(p, pend, enc)) {
@@ -4496,5 +4555,14 @@ rb_str_each_line(int argc, VALUE *argv, 
 		rb_enc_copy(line, str);
 		rb_yield(line);
-		str_mod_check(str, ptr, len);
+		if (str_modified_since(str, snapshot)) {
+		    ptr = RSTRING_PTR(str);
+		    len = RSTRING_LEN(str);
+		    pend = ptr + len;
+		    snapshot = str_snapshot(str);
+		    enc = rb_enc_get(str);
+		    p = str_nth(ptr, pend, i, enc, single_byte_optimizable(str));
+		    if (!p) break;
+		    n = rb_enc_mbclen(p, pend, enc);
+		}
 		s = p + n;
 	    }
@@ -4512,5 +4580,5 @@ rb_str_each_line(int argc, VALUE *argv, 
     }
 
-    while (p < pend) {
+    for (i = 0; p < pend; i++) {
 	int c = rb_enc_codepoint(p, pend, enc);
 
@@ -4519,6 +4587,8 @@ rb_str_each_line(int argc, VALUE *argv, 
 	    while (p < pend && rb_enc_codepoint(p, pend, enc) == newline) {
 		p += n;
+		i++;
 	    }
 	    p -= n;
+	    i--;
 	}
 	if (c == newline &&
@@ -4528,5 +4598,15 @@ rb_str_each_line(int argc, VALUE *argv, 
 	    rb_enc_copy(line, str);
 	    rb_yield(line);
-	    str_mod_check(str, ptr, len);
+	    if (str_modified_since(str, snapshot)) {
+		enc = rb_enc_check(str, rs); /* may be forced encoding */
+		ptr = RSTRING_PTR(str);
+		len = RSTRING_LEN(str);
+		pend = ptr + len;
+		snapshot = str_snapshot(str);
+		p = str_nth(ptr, pend, i, rb_enc_get(str),
+			    single_byte_optimizable(str));
+		if (!p) break;
+		n = rb_enc_mbclen(p, pend, enc);
+	    }
 	    s = p + (rslen ? rslen : n);
 	}
@@ -4615,16 +4695,24 @@ static VALUE
 rb_str_each_char(VALUE str)
 {
-    int i, len, n;
-    const char *ptr;
+    long i, n;
+    const char *ptr, *pend, *p;
     rb_encoding *enc;
+    volatile VALUE snapshot;
 
     RETURN_ENUMERATOR(str, 0, 0);
-    str = rb_str_new4(str);
-    ptr = RSTRING_PTR(str);
-    len = RSTRING_LEN(str);
+    snapshot = str_snapshot(str);
+    pend = (ptr = RSTRING_PTR(str)) + RSTRING_LEN(str);
     enc = rb_enc_get(str);
-    for (i = 0; i < len; i += n) {
-	n = rb_enc_mbclen(ptr + i, ptr + len, enc);
-	rb_yield(rb_str_subseq(str, i, n));
+    for (i = 0, p = ptr; p < pend; i++, p += n) {
+	n = rb_enc_mbclen(p, pend, enc);
+	rb_yield(rb_str_subseq(str, p - ptr, n));
+	if (str_modified_since(str, snapshot)) {
+	    snapshot = str_snapshot(str);
+	    pend = (ptr = RSTRING_PTR(str)) + RSTRING_LEN(str);
+	    enc = rb_enc_get(str);
+	    p = str_nth(ptr, pend, i, enc, single_byte_optimizable(str));
+	    if (!p) break;
+	    n = rb_enc_mbclen(p, pend, enc);
+	}
     }
     return str;


-- 
--- 僕の前にBugはない。
--- 僕の後ろにBugはできる。
    中田 伸悦