* include/ruby/ruby.h: embeds the elements of an array into its

	  struct RArray for # of elements <= 3.

	* array.c: ditto.

	* gc.c (gc_mark_children): following the change of struct RArray.

	* ext/tk/tcltklib.c (ip_ruby_cmp): ditto.

	* parse.y (coverage): ditto.

	* proc.c (curry): ditto.

	* .gdbinit: ditto.

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@19723 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

1 files changed, 288 insertions, 129 deletions

diff --git a/array.c b/array.c
index e33c7bc0b1..4aa6dbef07 100644
--- a/array.c
+++ b/array.c
@@ -14,6 +14,7 @@
 #include "ruby/ruby.h"
 #include "ruby/util.h"
 #include "ruby/st.h"
+#include <assert.h>
 
 VALUE rb_cArray;
 
@@ -38,18 +39,120 @@ memfill(register VALUE *mem, register long size, register VALUE val)
     }
 }
 
-#define ARY_SHARED_P(a) FL_TEST(a, ELTS_SHARED)
+# define ARY_SHARED_P(ary) \
+    (assert(!FL_TEST(ary, ELTS_SHARED) || !FL_TEST(ary, RARRAY_EMBED_FLAG)), \
+     FL_TEST(ary,ELTS_SHARED))
+# define ARY_EMBED_P(ary) \
+    (assert(!FL_TEST(ary, ELTS_SHARED) || !FL_TEST(ary, RARRAY_EMBED_FLAG)), \
+     FL_TEST(ary, RARRAY_EMBED_FLAG))
 
+#define ARY_HEAP_PTR(a) (assert(!ARY_EMBED_P(a)), RARRAY(a)->as.heap.ptr)
+#define ARY_HEAP_LEN(a) (assert(!ARY_EMBED_P(a)), RARRAY(a)->as.heap.len)
+#define ARY_EMBED_PTR(a) (assert(ARY_EMBED_P(a)), RARRAY(a)->as.ary)
+#define ARY_EMBED_LEN(a) \
+    (assert(ARY_EMBED_P(a)), \
+     (long)((RBASIC(a)->flags >> RARRAY_EMBED_LEN_SHIFT) & \
+	 (RARRAY_EMBED_LEN_MASK >> RARRAY_EMBED_LEN_SHIFT)))
+
+#define ARY_OWNS_HEAP_P(a) (!FL_TEST(a, ELTS_SHARED|RARRAY_EMBED_FLAG))
+#define FL_SET_EMBED(a) do { \
+    assert(!ARY_SHARED_P(a)); \
+    assert(!OBJ_FROZEN(a)); \
+    FL_SET(a, RARRAY_EMBED_FLAG); \
+} while (0)
+#define FL_UNSET_EMBED(ary) FL_UNSET(ary, RARRAY_EMBED_FLAG|RARRAY_EMBED_LEN_MASK)
+#define FL_SET_SHARED(ary) do { \
+    assert(!ARY_EMBED_P(ary)); \
+    FL_SET(ary, ELTS_SHARED); \
+} while (0)
+#define FL_UNSET_SHARED(ary) FL_UNSET(ary, ELTS_SHARED)
+
+#define ARY_SET_PTR(ary, p) do { \
+    assert(!ARY_EMBED_P(ary)); \
+    assert(!OBJ_FROZEN(ary)); \
+    RARRAY(ary)->as.heap.ptr = (p); \
+} while (0)
+#define ARY_SET_EMBED_LEN(ary, n) do { \
+    long tmp_n = n; \
+    assert(ARY_EMBED_P(ary)); \
+    assert(!OBJ_FROZEN(ary)); \
+    RBASIC(ary)->flags &= ~RARRAY_EMBED_LEN_MASK; \
+    RBASIC(ary)->flags |= (tmp_n) << RARRAY_EMBED_LEN_SHIFT; \
+} while (0)
+#define ARY_SET_HEAP_LEN(ary, n) do { \
+    assert(!ARY_EMBED_P(ary)); \
+    RARRAY(ary)->as.heap.len = n; \
+} while (0)
 #define ARY_SET_LEN(ary, n) do { \
-    RARRAY(ary)->len = (n);\
+    if (ARY_EMBED_P(ary)) { \
+        ARY_SET_EMBED_LEN(ary, n); \
+    } \
+    else { \
+        ARY_SET_HEAP_LEN(ary, n); \
+    } \
+    assert(RARRAY_LEN(ary) == n); \
 } while (0) 
+#define ARY_INCREASE_PTR(ary, n) do  { \
+    assert(!ARY_EMBED_P(ary)); \
+    assert(!OBJ_FROZEN(ary)); \
+    RARRAY(ary)->as.heap.ptr += n; \
+} while (0)
+#define ARY_INCREASE_LEN(ary, n) do  { \
+    assert(!OBJ_FROZEN(ary)); \
+    if (ARY_EMBED_P(ary)) { \
+        ARY_SET_EMBED_LEN(ary, RARRAY_LEN(ary)+n); \
+    } \
+    else { \
+        RARRAY(ary)->as.heap.len += n; \
+    } \
+} while (0)
+
+#define ARY_CAPA(ary) (ARY_EMBED_P(ary) ? RARRAY_EMBED_LEN_MAX : RARRAY(ary)->as.heap.aux.capa)
+#define ARY_SET_CAPA(ary, n) do { \
+    assert(!ARY_EMBED_P(ary)); \
+    assert(!ARY_SHARED_P(ary)); \
+    assert(!OBJ_FROZEN(ary)); \
+    RARRAY(ary)->as.heap.aux.capa = (n); \
+} while (0)
 
-#define ARY_CAPA(ary) RARRAY(ary)->aux.capa
-#define RESIZE_CAPA(ary,capacity) do {\
-    REALLOC_N(RARRAY(ary)->ptr, VALUE, (capacity));\
-    RARRAY(ary)->aux.capa = (capacity);\
+#define ARY_SHARED(ary) (assert(ARY_SHARED_P(ary)), RARRAY(ary)->as.heap.aux.shared)
+#define ARY_SET_SHARED(ary, value) do { \
+    assert(!ARY_EMBED_P(ary)); \
+    assert(ARY_SHARED_P(ary)); \
+    RARRAY(ary)->as.heap.aux.shared = (value); \
 } while (0)
 
+static void
+RESIZE_CAPA(VALUE ary, long capacity)
+{
+    assert(!OBJ_FROZEN(ary)); 
+    assert(!ARY_SHARED_P(ary)); 
+    if (capacity > RARRAY_EMBED_LEN_MAX) {
+        if (ARY_EMBED_P(ary)) {
+            long len = ARY_EMBED_LEN(ary); 
+            VALUE *ptr = ALLOC_N(VALUE, (capacity));
+            MEMCPY(ptr, ARY_EMBED_PTR(ary), VALUE, len); 
+            FL_UNSET_EMBED(ary); 
+            ARY_SET_PTR(ary, ptr); 
+            ARY_SET_HEAP_LEN(ary, len); 
+        }
+        else { 
+            REALLOC_N(RARRAY(ary)->as.heap.ptr, VALUE, (capacity));
+        }
+        ARY_SET_CAPA(ary, (capacity)); 
+    }
+    else {
+        if (!ARY_EMBED_P(ary)) {
+            long len = RARRAY_LEN(ary); 
+            VALUE *ptr = RARRAY_PTR(ary); 
+            MEMCPY(RARRAY(ary)->as.ary, ptr, VALUE, len); 
+            FL_SET_EMBED(ary); 
+            ARY_SET_LEN(ary, len); 
+            xfree(ptr); 
+        }
+    }
+}
+
 static inline void
 rb_ary_modify_check(VALUE ary)
 {
@@ -61,15 +164,23 @@ rb_ary_modify_check(VALUE ary)
 static void
 rb_ary_modify(VALUE ary)
 {
-    VALUE *ptr;
-
     rb_ary_modify_check(ary);
     if (ARY_SHARED_P(ary)) {
-	ptr = ALLOC_N(VALUE, RARRAY_LEN(ary));
-	FL_UNSET(ary, ELTS_SHARED);
-	RARRAY(ary)->aux.capa = RARRAY_LEN(ary);
-	MEMCPY(ptr, RARRAY_PTR(ary), VALUE, RARRAY_LEN(ary));
-	RARRAY(ary)->ptr = ptr;
+        long len = RARRAY_LEN(ary);
+        if (len <= RARRAY_EMBED_LEN_MAX) {
+            VALUE *ptr = ARY_HEAP_PTR(ary);
+            FL_UNSET_SHARED(ary);
+            FL_SET_EMBED(ary);
+            MEMCPY(ARY_EMBED_PTR(ary), ptr, VALUE, len);
+            ARY_SET_EMBED_LEN(ary, len);
+        }
+        else {
+            VALUE *ptr = ALLOC_N(VALUE, len);
+            FL_UNSET_SHARED(ary);
+            ARY_SET_CAPA(ary, len);
+            MEMCPY(ptr, RARRAY_PTR(ary), VALUE, len);
+            ARY_SET_PTR(ary, ptr);
+        }
     }
 }
 
@@ -99,10 +210,8 @@ ary_alloc(VALUE klass)
 {
     NEWOBJ(ary, struct RArray);
     OBJSETUP(ary, klass, T_ARRAY);
-
-    ary->len = 0;
-    ary->ptr = 0;
-    ary->aux.capa = 0;
+    FL_SET_EMBED((VALUE)ary);
+    ARY_SET_EMBED_LEN((VALUE)ary, 0);
 
     return (VALUE)ary;
 }
@@ -119,9 +228,12 @@ ary_new(VALUE klass, long len)
 	rb_raise(rb_eArgError, "array size too big");
     }
     ary = ary_alloc(klass);
-    if (len == 0) len++;
-    RARRAY(ary)->ptr = ALLOC_N(VALUE, len);
-    RARRAY(ary)->aux.capa = len;
+    if (len > RARRAY_EMBED_LEN_MAX) {
+        FL_UNSET_EMBED(ary);
+        ARY_SET_PTR(ary, ALLOC_N(VALUE, len));
+        ARY_SET_CAPA(ary, len);
+        ARY_SET_HEAP_LEN(ary, 0);
+    }
 
     return ary;
 }
@@ -136,7 +248,7 @@ rb_ary_new2(long len)
 VALUE
 rb_ary_new(void)
 {
-    return rb_ary_new2(ARY_DEFAULT_SIZE);
+    return rb_ary_new2(RARRAY_EMBED_LEN_MAX);
 }
 
 #include <stdarg.h>
@@ -156,7 +268,7 @@ rb_ary_new3(long n, ...)
     }
     va_end(ar);
 
-    RARRAY(ary)->len = n;
+    ARY_SET_LEN(ary, n);
     return ary;
 }
 
@@ -168,7 +280,7 @@ rb_ary_new4(long n, const VALUE *elts)
     ary = rb_ary_new2(n);
     if (n > 0 && elts) {
 	MEMCPY(RARRAY_PTR(ary), elts, VALUE, n);
-	RARRAY(ary)->len = n;
+	ARY_SET_LEN(ary, n);
     }
 
     return ary;
@@ -183,31 +295,48 @@ rb_ary_tmp_new(long len)
 void
 rb_ary_free(VALUE ary)
 {
-    if (!ARY_SHARED_P(ary)) {
-	xfree(RARRAY(ary)->ptr);
+    if (ARY_OWNS_HEAP_P(ary)) {
+	xfree(RARRAY_PTR(ary));
     }
 }
 
 static VALUE
 ary_make_shared(VALUE ary)
 {
+    assert(!ARY_EMBED_P(ary));
     if (ARY_SHARED_P(ary)) {
-	return RARRAY(ary)->aux.shared;
+	return ARY_SHARED(ary);
     }
     else {
 	NEWOBJ(shared, struct RArray);
 	OBJSETUP(shared, 0, T_ARRAY);
+        FL_UNSET_EMBED(shared);
 
-	shared->len = RARRAY(ary)->len;
-	shared->ptr = RARRAY(ary)->ptr;
-	shared->aux.capa = RARRAY(ary)->aux.capa;
-	RARRAY(ary)->aux.shared = (VALUE)shared;
-	FL_SET(ary, ELTS_SHARED);
+        ARY_SET_LEN((VALUE)shared, RARRAY_LEN(ary));
+        ARY_SET_PTR((VALUE)shared, RARRAY_PTR(ary));
+        ARY_SET_CAPA((VALUE)shared, ARY_CAPA(ary));
+	FL_SET_SHARED(ary);
+	ARY_SET_SHARED(ary, (VALUE)shared);
 	OBJ_FREEZE(shared);
 	return (VALUE)shared;
     }
 }
 
+
+static VALUE
+ary_make_substitution(VALUE ary)
+{
+    if (RARRAY_LEN(ary) <= RARRAY_EMBED_LEN_MAX) {
+        VALUE subst = rb_ary_new2(RARRAY_LEN(ary));
+        MEMCPY(ARY_EMBED_PTR(subst), RARRAY_PTR(ary), VALUE, RARRAY_LEN(ary));
+        ARY_SET_EMBED_LEN(subst, RARRAY_LEN(ary));
+        return subst;
+    }
+    else {
+        return ary_make_shared(ary);
+    }
+}
+
 VALUE
 rb_assoc_new(VALUE car, VALUE cdr)
 {
@@ -298,10 +427,12 @@ rb_ary_initialize(int argc, VALUE *argv, VALUE ary)
 
     rb_ary_modify(ary);
     if (argc ==  0) {
-	if (RARRAY_PTR(ary) && !ARY_SHARED_P(ary)) {
-	    xfree(RARRAY(ary)->ptr);
+	if (ARY_OWNS_HEAP_P(ary) && RARRAY_PTR(ary)) {
+	    xfree(RARRAY_PTR(ary));
 	}
-	RARRAY(ary)->len = 0;
+        FL_UNSET_SHARED(ary);
+        FL_SET_EMBED(ary);
+	ARY_SET_EMBED_LEN(ary, 0);
 	if (rb_block_given_p()) {
 	    rb_warning("given block not used");
 	}
@@ -333,12 +464,12 @@ rb_ary_initialize(int argc, VALUE *argv, VALUE ary)
 	}
 	for (i=0; i<len; i++) {
 	    rb_ary_store(ary, i, rb_yield(LONG2NUM(i)));
-	    RARRAY(ary)->len = i + 1;
+	    ARY_SET_LEN(ary, i + 1);
 	}
     }
     else {
 	memfill(RARRAY_PTR(ary), len, val);
-	RARRAY(ary)->len = len;
+	ARY_SET_LEN(ary, len);
     }
     return ary;
 }
@@ -355,15 +486,11 @@ rb_ary_initialize(int argc, VALUE *argv, VALUE ary)
 static VALUE
 rb_ary_s_create(int argc, VALUE *argv, VALUE klass)
 {
-    VALUE ary = ary_alloc(klass);
-
-    if (argc < 0) {
-	rb_raise(rb_eArgError, "negative array size");
+    VALUE ary = ary_new(klass, argc);
+    if (argc > 0 && argv) {
+        MEMCPY(RARRAY_PTR(ary), argv, VALUE, argc);
+        ARY_SET_LEN(ary, argc);
     }
-    RARRAY(ary)->ptr = ALLOC_N(VALUE, argc);
-    RARRAY(ary)->aux.capa = argc;
-    MEMCPY(RARRAY_PTR(ary), argv, VALUE, argc);
-    RARRAY(ary)->len = argc;
 
     return ary;
 }
@@ -401,28 +528,41 @@ rb_ary_store(VALUE ary, long idx, VALUE val)
     }
 
     if (idx >= RARRAY_LEN(ary)) {
-	RARRAY(ary)->len = idx + 1;
+	ARY_SET_LEN(ary, idx + 1);
     }
     RARRAY_PTR(ary)[idx] = val;
 }
 
 static VALUE
-ary_shared_array(VALUE klass, VALUE ary)
+ary_make_partial0(VALUE ary, long offset, long len)
 {
-    VALUE val = ary_alloc(klass);
+    assert(offset >= 0);
+    assert(len >= 0);
+    assert(offset+len <= RARRAY_LEN(ary));
 
-    ary_make_shared(ary);
-    RARRAY(val)->ptr = RARRAY(ary)->ptr;
-    RARRAY(val)->len = RARRAY(ary)->len;
-    RARRAY(val)->aux.shared = RARRAY(ary)->aux.shared;
-    FL_SET(val, ELTS_SHARED);
-    return val;
+    if (len <= RARRAY_EMBED_LEN_MAX) {
+        return rb_ary_new4(len, RARRAY_PTR(ary) + offset);
+    }
+    else {
+        VALUE shared, result = ary_alloc(rb_obj_class(ary));
+        FL_UNSET_EMBED(result);
+
+        shared = ary_make_shared(ary);
+        ARY_SET_PTR(result, RARRAY_PTR(ary));
+        ARY_SET_LEN(result, RARRAY_LEN(ary));
+        FL_SET_SHARED(result);
+        ARY_SET_SHARED(result, shared);
+
+        ARY_INCREASE_PTR(result, offset);
+        ARY_SET_LEN(result, len);
+        return result;
+    }
 }
 
 static VALUE
-ary_shared_first(int argc, VALUE *argv, VALUE ary, int last)
+ary_make_partial(int argc, VALUE *argv, VALUE ary, int last)
 {
-    VALUE nv, result;
+    VALUE nv;
     long n;
     long offset = 0;
 
@@ -437,11 +577,7 @@ ary_shared_first(int argc, VALUE *argv, VALUE ary, int last)
     if (last) {
 	offset = RARRAY_LEN(ary) - n;
     }
-    result = ary_shared_array(rb_cArray, ary);
-    RARRAY(result)->ptr += offset;
-    RARRAY(result)->len = n;
-
-    return result;
+    return ary_make_partial0(ary, offset, n);
 }
 
 /*
@@ -492,14 +628,14 @@ rb_ary_pop(VALUE ary)
     long n;
     rb_ary_modify_check(ary);
     if (RARRAY_LEN(ary) == 0) return Qnil;
-    if (!ARY_SHARED_P(ary) &&
+    if (ARY_OWNS_HEAP_P(ary) &&
 	RARRAY_LEN(ary) * 3 < ARY_CAPA(ary) &&
 	ARY_CAPA(ary) > ARY_DEFAULT_SIZE)
     {
 	RESIZE_CAPA(ary, RARRAY_LEN(ary) * 2);
     }
     n = RARRAY_LEN(ary)-1;
-    RARRAY(ary)->len = n;
+    ARY_SET_LEN(ary, n);
     return RARRAY_PTR(ary)[n];
 }
 
@@ -530,8 +666,8 @@ rb_ary_pop_m(int argc, VALUE *argv, VALUE ary)
     }
 
     rb_ary_modify_check(ary);
-    result = ary_shared_first(argc, argv, ary, Qtrue);
-    RARRAY(ary)->len -= RARRAY_LEN(result);
+    result = ary_make_partial(argc, argv, ary, Qtrue);
+    ARY_INCREASE_LEN(ary, -RARRAY_LEN(result));
     return result;
 }
 
@@ -546,14 +682,16 @@ rb_ary_shift(VALUE ary)
     if (!ARY_SHARED_P(ary)) {
 	if (RARRAY_LEN(ary) < ARY_DEFAULT_SIZE) {
 	    MEMMOVE(RARRAY_PTR(ary), RARRAY_PTR(ary)+1, VALUE, RARRAY_LEN(ary)-1);
-	    RARRAY(ary)->len--;
+            ARY_INCREASE_LEN(ary, -1);
 	    return top;
 	}
+        assert(!ARY_EMBED_P(ary)); /* ARY_EMBED_LEN_MAX < ARY_DEFAULT_SIZE */
+
 	RARRAY_PTR(ary)[0] = Qnil;
 	ary_make_shared(ary);
     }
-    RARRAY(ary)->ptr++;		/* shift ptr */
-    RARRAY(ary)->len--;
+    ARY_INCREASE_PTR(ary, 1);		/* shift ptr */
+    ARY_INCREASE_LEN(ary, -1);
 
     return top;
 }
@@ -590,16 +728,15 @@ rb_ary_shift_m(int argc, VALUE *argv, VALUE ary)
     }
 
     rb_ary_modify_check(ary);
-    result = ary_shared_first(argc, argv, ary, Qfalse);
+    result = ary_make_partial(argc, argv, ary, Qfalse);
     n = RARRAY_LEN(result);
     if (ARY_SHARED_P(ary)) {
-	RARRAY(ary)->ptr += n;
-	RARRAY(ary)->len -= n;
-	}
+        ARY_INCREASE_PTR(ary, n);
+    }
     else {
 	MEMMOVE(RARRAY_PTR(ary), RARRAY_PTR(ary)+n, VALUE, RARRAY_LEN(ary)-n);
-	RARRAY(ary)->len -= n;
     }
+    ARY_INCREASE_LEN(ary, -n);
 
     return result;
 }
@@ -623,14 +760,14 @@ rb_ary_unshift_m(int argc, VALUE *argv, VALUE ary)
 
     if (argc == 0) return ary;
     rb_ary_modify(ary);
-    if (RARRAY(ary)->aux.capa <= (len = RARRAY(ary)->len) + argc) {
+    if (ARY_CAPA(ary) <= (len = RARRAY_LEN(ary)) + argc) {
 	RESIZE_CAPA(ary, len + argc + ARY_DEFAULT_SIZE);
     }
 
     /* sliding items */
-    MEMMOVE(RARRAY(ary)->ptr + argc, RARRAY(ary)->ptr, VALUE, len);
-    MEMCPY(RARRAY(ary)->ptr, argv, VALUE, argc);
-    RARRAY(ary)->len += argc;
+    MEMMOVE(RARRAY_PTR(ary) + argc, RARRAY_PTR(ary), VALUE, len);
+    MEMCPY(RARRAY_PTR(ary), argv, VALUE, argc);
+    ARY_INCREASE_LEN(ary, argc);
     
     return ary;
 }
@@ -664,8 +801,7 @@ rb_ary_entry(VALUE ary, long offset)
 VALUE
 rb_ary_subseq(VALUE ary, long beg, long len)
 {
-    VALUE klass, ary2, shared;
-    VALUE *ptr;
+    VALUE klass;
 
     if (beg > RARRAY_LEN(ary)) return Qnil;
     if (beg < 0 || len < 0) return Qnil;
@@ -676,15 +812,7 @@ rb_ary_subseq(VALUE ary, long beg, long len)
     klass = rb_obj_class(ary);
     if (len == 0) return ary_new(klass, 0);
 
-    shared = ary_make_shared(ary);
-    ptr = RARRAY_PTR(ary);
-    ary2 = ary_alloc(klass);
-    RARRAY(ary2)->ptr = ptr + beg;
-    RARRAY(ary2)->len = len;
-    RARRAY(ary2)->aux.shared = shared;
-    FL_SET(ary2, ELTS_SHARED);
-
-    return ary2;
+    return ary_make_partial0(ary, beg, len);
 }
 
 /* 
@@ -794,7 +922,7 @@ rb_ary_first(int argc, VALUE *argv, VALUE ary)
 	return RARRAY_PTR(ary)[0];
     }
     else {
-	return ary_shared_first(argc, argv, ary, Qfalse);
+	return ary_make_partial(argc, argv, ary, Qfalse);
     }
 }
 
@@ -819,7 +947,7 @@ rb_ary_last(int argc, VALUE *argv, VALUE ary)
 	return RARRAY_PTR(ary)[RARRAY_LEN(ary)-1];
     }
     else {
-	return ary_shared_first(argc, argv, ary, Qtrue);
+	return ary_make_partial(argc, argv, ary, Qtrue);
     }
 }
 
@@ -1003,7 +1131,7 @@ rb_ary_splice(VALUE ary, long beg, long len, VALUE rpl)
 	if (rlen > 0) {
 	    MEMCPY(RARRAY_PTR(ary) + beg, RARRAY_PTR(rpl), VALUE, rlen);
 	}
-	RARRAY(ary)->len = len;
+	ARY_SET_LEN(ary, len);
     }
     else {
 	long alen;
@@ -1020,7 +1148,7 @@ rb_ary_splice(VALUE ary, long beg, long len, VALUE rpl)
 	if (len != rlen) {
 	    MEMMOVE(RARRAY_PTR(ary) + beg + rlen, RARRAY_PTR(ary) + beg + len,
 		    VALUE, RARRAY_LEN(ary) - (beg + len));
-	    RARRAY(ary)->len = alen;
+	    ARY_SET_LEN(ary, alen);
 	}
 	if (rlen > 0) {
 	    MEMMOVE(RARRAY_PTR(ary) + beg, RARRAY_PTR(rpl), VALUE, rlen);
@@ -1238,10 +1366,11 @@ VALUE
 rb_ary_dup(VALUE ary)
 {
     VALUE dup = rb_ary_new2(RARRAY_LEN(ary));
-
+    int is_embed = ARY_EMBED_P(dup);
     DUPSETUP(dup, ary);
+    if (is_embed) FL_SET_EMBED(dup);
     MEMCPY(RARRAY_PTR(dup), RARRAY_PTR(ary), VALUE, RARRAY_LEN(ary));
-    RARRAY(dup)->len = RARRAY_LEN(ary);
+    ARY_SET_LEN(dup, RARRAY_LEN(ary));
 
     return dup;
 }
@@ -1548,8 +1677,9 @@ VALUE
 rb_ary_sort_bang(VALUE ary)
 {
     rb_ary_modify(ary);
+    assert(!ARY_SHARED_P(ary));
     if (RARRAY_LEN(ary) > 1) {
-	VALUE tmp = ary_make_shared(ary);
+	VALUE tmp = ary_make_substitution(ary); /* only ary refers tmp */
 	struct ary_sort_data data;
 
 	RBASIC(tmp)->klass = 0;
@@ -1558,18 +1688,39 @@ rb_ary_sort_bang(VALUE ary)
 	data.opt_inited = 0;
 	ruby_qsort(RARRAY_PTR(tmp), RARRAY_LEN(tmp), sizeof(VALUE),
 		   rb_block_given_p()?sort_1:sort_2, &data);
-	if (RARRAY(ary)->ptr != RARRAY(tmp)->ptr) {
-	    if (!ARY_SHARED_P(ary)) xfree(RARRAY(ary)->ptr);
-	    RARRAY(ary)->ptr = RARRAY(tmp)->ptr;
-	    RARRAY(ary)->len = RARRAY(tmp)->len;
-	    RARRAY(ary)->aux.capa = RARRAY(tmp)->aux.capa;
-	    FL_SET(ary, ELTS_SHARED);
-	};
-	FL_UNSET(ary, ELTS_SHARED);
-	RARRAY(tmp)->ptr = 0;
-	RARRAY(tmp)->len = 0;
-	RARRAY(tmp)->aux.capa = 0;
-	RBASIC(tmp)->klass = rb_cArray;
+
+        if (ARY_EMBED_P(ary) || ARY_EMBED_P(tmp)) {
+            assert(ARY_EMBED_P(tmp));
+            MEMCPY(RARRAY_PTR(ary), ARY_EMBED_PTR(tmp), VALUE, ARY_EMBED_LEN(tmp));
+            ARY_SET_LEN(ary, ARY_EMBED_LEN(tmp));
+        }
+        else {
+            assert(!ARY_EMBED_P(ary));
+            assert(!ARY_EMBED_P(tmp));
+            if (RARRAY_PTR(ary) != RARRAY_PTR(tmp)) {
+                assert(!ARY_SHARED_P(tmp));
+                if (ARY_SHARED_P(ary)) {
+                    FL_UNSET_SHARED(ary);
+                }
+                else {
+                    xfree(ARY_HEAP_PTR(ary));
+                }
+                ARY_SET_PTR(ary, RARRAY_PTR(tmp));
+                ARY_SET_HEAP_LEN(ary, RARRAY_LEN(tmp));
+                ARY_SET_CAPA(ary, ARY_CAPA(tmp));
+            } 
+            else {
+                FL_UNSET_SHARED(ary);
+                ARY_SET_CAPA(ary, ARY_CAPA(tmp));
+            }
+            /* tmp was lost ownership for the ptr */
+            FL_UNSET(tmp, FL_FREEZE);
+            FL_SET_EMBED(tmp);
+            ARY_SET_EMBED_LEN(tmp, 0);
+            FL_SET(tmp, FL_FREEZE);
+	}
+        /* tmp will be GC'ed. */
+        RBASIC(tmp)->klass = rb_cArray;
     }
     return ary;
 }
@@ -1778,7 +1929,7 @@ rb_ary_delete(VALUE ary, VALUE item)
 
     rb_ary_modify(ary);
     if (RARRAY_LEN(ary) > i2) {
-	RARRAY(ary)->len = i2;
+	ARY_SET_LEN(ary, i2);
 	if (i2 * 2 < ARY_CAPA(ary) &&
 	    ARY_CAPA(ary) > ARY_DEFAULT_SIZE) {
 	    RESIZE_CAPA(ary, i2*2);
@@ -1804,7 +1955,7 @@ rb_ary_delete_at(VALUE ary, long pos)
     del = RARRAY_PTR(ary)[pos];
     MEMMOVE(RARRAY_PTR(ary)+pos, RARRAY_PTR(ary)+pos+1, VALUE,
 	    RARRAY_LEN(ary)-pos-1);
-    RARRAY(ary)->len--;
+    ARY_INCREASE_LEN(ary, -1);
 
     return del;
 }
@@ -1921,7 +2072,7 @@ rb_ary_reject_bang(VALUE ary)
 
     if (RARRAY_LEN(ary) == i2) return Qnil;
     if (i2 < RARRAY_LEN(ary))
-	RARRAY(ary)->len = i2;
+	ARY_SET_LEN(ary, i2);
     return ary;
 }
 
@@ -2089,22 +2240,30 @@ rb_ary_transpose(VALUE ary)
 VALUE
 rb_ary_replace(VALUE copy, VALUE orig)
 {
-    VALUE shared;
-    VALUE *ptr;
-
     orig = to_ary(orig);
     rb_ary_modify_check(copy);
     if (copy == orig) return copy;
-    shared = ary_make_shared(orig);
-    if (!ARY_SHARED_P(copy)) {
-	ptr = RARRAY(copy)->ptr;
-	xfree(ptr);
-    }
-    RARRAY(copy)->ptr = RARRAY(orig)->ptr;
-    RARRAY(copy)->len = RARRAY(orig)->len;
-    RARRAY(copy)->aux.shared = shared;
-    FL_SET(copy, ELTS_SHARED);
 
+    if (RARRAY_LEN(orig) <= RARRAY_EMBED_LEN_MAX) {
+        VALUE *ptr;
+        if (ARY_OWNS_HEAP_P(copy)) xfree(RARRAY_PTR(copy));
+        FL_UNSET_SHARED(copy);
+        FL_SET_EMBED(copy);
+        ptr = RARRAY_PTR(orig);
+        MEMCPY(RARRAY_PTR(copy), ptr, VALUE, RARRAY_LEN(orig));
+        ARY_SET_LEN(copy, RARRAY_LEN(orig));
+    }
+    else {
+        VALUE shared = ary_make_shared(orig);
+        if (ARY_OWNS_HEAP_P(copy)) {
+            xfree(RARRAY_PTR(copy));
+        }
+        FL_UNSET_EMBED(copy);
+        FL_SET_SHARED(copy);
+        ARY_SET_PTR(copy, RARRAY_PTR(orig));
+        ARY_SET_LEN(copy, RARRAY_LEN(orig));
+        ARY_SET_SHARED(copy, shared);
+    }
     return copy;
 }
 
@@ -2122,7 +2281,7 @@ VALUE
 rb_ary_clear(VALUE ary)
 {
     rb_ary_modify(ary);
-    RARRAY(ary)->len = 0;
+    ARY_SET_LEN(ary, 0);
     if (ARY_DEFAULT_SIZE * 2 < ARY_CAPA(ary)) {
 	RESIZE_CAPA(ary, ARY_DEFAULT_SIZE * 2);
     }
@@ -2201,7 +2360,7 @@ rb_ary_fill(int argc, VALUE *argv, VALUE ary)
 	    RESIZE_CAPA(ary, end);
 	}
 	rb_mem_clear(RARRAY_PTR(ary) + RARRAY_LEN(ary), end - RARRAY_LEN(ary));
-	RARRAY(ary)->len = end;
+	ARY_SET_LEN(ary, end);
     }
 
     if (block_p) {
@@ -2245,7 +2404,7 @@ rb_ary_plus(VALUE x, VALUE y)
     z = rb_ary_new2(len);
     MEMCPY(RARRAY_PTR(z), RARRAY_PTR(x), VALUE, RARRAY_LEN(x));
     MEMCPY(RARRAY_PTR(z) + RARRAY_LEN(x), RARRAY_PTR(y), VALUE, RARRAY_LEN(y));
-    RARRAY(z)->len = len;
+    ARY_SET_LEN(z, len);
     return z;
 }
 
@@ -2307,7 +2466,7 @@ rb_ary_times(VALUE ary, VALUE times)
     len *= RARRAY_LEN(ary);
 
     ary2 = ary_new(rb_obj_class(ary), len);
-    RARRAY(ary2)->len = len;
+    ARY_SET_LEN(ary2, len);
 
     for (i=0; i<len; i+=RARRAY_LEN(ary)) {
 	MEMCPY(RARRAY_PTR(ary2)+i, RARRAY_PTR(ary), VALUE, RARRAY_LEN(ary));
@@ -2716,7 +2875,7 @@ rb_ary_uniq_bang(VALUE ary)
 	    rb_ary_store(ary, j++, v);
 	}
     }
-    RARRAY(ary)->len = j;
+    ARY_SET_LEN(ary, j);
 
     return ary;
 }
@@ -2771,7 +2930,7 @@ rb_ary_compact_bang(VALUE ary)
     if (n * 2 < ARY_CAPA(ary) && ARY_DEFAULT_SIZE * 2 < ARY_CAPA(ary)) {
 	RESIZE_CAPA(ary, n * 2);
     }
-    RARRAY(ary)->len = n;
+    ARY_SET_LEN(ary, n);
 
     return ary;
 }
@@ -3168,7 +3327,7 @@ permute0(long n, long r, long *p, long index, int *used, VALUE values)
 		const VALUE *values_array = RARRAY_PTR(values);
 
 		for (j = 0; j < r; j++) result_array[j] = values_array[p[j]];
-		RARRAY(result)->len = r;
+		ARY_SET_LEN(result, r);
 		rb_yield(result);
 	    }
 	}
@@ -3228,7 +3387,7 @@ rb_ary_permutation(int argc, VALUE *argv, VALUE ary)
 	long *p = (long*)RSTRING_PTR(t0);
 	volatile VALUE t1 = tmpbuf(n,sizeof(int));
 	int *used = (int*)RSTRING_PTR(t1);
-	VALUE ary0 = ary_make_shared(ary); /* private defensive copy of ary */
+	VALUE ary0 = ary_make_substitution(ary); /* private defensive copy of ary */
 
 	for (i = 0; i < n; i++) used[i] = 0; /* initialize array */