[ruby-dev:34173] Re: Array#shift/unshift の高速化

ワナベです。

08/03/28 に Nobuyoshi Nakada<[e-mail]> さんは書きました:
> RArrayにはもう空きがないので、全オブジェクトのサイズが1word増え
>  てしまう、というのは悩ましいですね。

元のパッチと同じく、前方に空きメモリがあるかどうかのフラグを新設して
空きがあるときだけRARRAY_PTR(ary)[-1]にサイズを書き込むようにしてみました。


Index: array.c
===================================================================
--- array.c	(revision 15844)
+++ array.c	(working copy)
@@ -20,6 +20,7 @@
 static ID id_cmp;

 #define ARY_DEFAULT_SIZE 16
+#define ARY_DEFAULT_LCAPA 4

 void
 rb_mem_clear(register VALUE *mem, register long size)
@@ -45,11 +46,65 @@

 #define ARY_CAPA(ary) RARRAY(ary)->aux.capa
 #define RESIZE_CAPA(ary,capacity) do {\
-    REALLOC_N(RARRAY(ary)->ptr, VALUE, (capacity));\
+    long lcapacity = ARY_LCAPA(ary);\
+    RARRAY(ary)->ptr -= lcapacity;\
+    REALLOC_N(RARRAY(ary)->ptr, VALUE, (capacity) + lcapacity);\
+    RARRAY(ary)->ptr += lcapacity;\
     RARRAY(ary)->aux.capa = (capacity);\
 } while (0)

+#define ARY_LCAPA(ary)\
+  (FL_TEST(ary, RARRAY_LFREE) ? (long)RARRAY_PTR(ary)[-1] : 0)
+#define RARRAY_TOP_PTR(ary) (RARRAY_PTR(ary) - ARY_LCAPA(ary))
+
 static inline void
+rb_ary_copy_lcapa(VALUE dst, VALUE src)
+{
+    if (FL_TEST(src, RARRAY_LFREE)) {
+	FL_SET(dst, RARRAY_LFREE);
+	RARRAY_PTR(dst)[-1] = RARRAY_PTR(src)[-1];
+    } else {
+	FL_UNSET(dst, RARRAY_LFREE);
+    }
+}
+
+static inline void
+rb_ary_set_lcapa_val(VALUE ary, long lcapacity)
+{
+    if (lcapacity != 0) {
+	FL_SET(ary, RARRAY_LFREE);
+	RARRAY_PTR(ary)[-1] = lcapacity;
+    } else {
+	FL_UNSET(ary, RARRAY_LFREE);
+    }
+}
+
+static inline void
+rb_ary_slide_capa_vals(VALUE ary, long offset)
+{
+    if (offset < 0) {
+	rb_raise(rb_eNotImpError, "[BUG] array negative shift"); /* todo? */
+    } else {
+	RARRAY_PTR(ary)[offset - 1] = offset + ARY_LCAPA(ary);
+	FL_SET(ary, RARRAY_LFREE);
+    }
+    RARRAY(ary)->aux.capa -= offset;
+}
+
+static inline void
+rb_ary_resize_lcapa(VALUE ary, long lcapacity)
+{
+    long offset = lcapacity - ARY_LCAPA(ary);
+    if (lcapacity < 0 || offset > RARRAY(ary)->aux.capa - RARRAY_LEN(ary)) {
+	rb_raise(rb_eIndexError, "[BUG] invalid left-capacity");
+    }
+    RARRAY_PTR(ary) += offset;
+    MEMMOVE(RARRAY_PTR(ary), RARRAY_PTR(ary) - offset, VALUE, RARRAY_LEN(ary));
+    RARRAY(ary)->aux.capa -= offset;
+    rb_ary_set_lcapa_val(ary,lcapacity);
+}
+
+static inline void
 rb_ary_modify_check(VALUE ary)
 {
     if (OBJ_FROZEN(ary)) rb_error_frozen("array");
@@ -67,6 +122,7 @@
 	ptr = ALLOC_N(VALUE, RARRAY_LEN(ary));
 	FL_UNSET(ary, ELTS_SHARED);
 	RARRAY(ary)->aux.capa = RARRAY_LEN(ary);
+	FL_UNSET(ary, RARRAY_LFREE);
 	MEMCPY(ptr, RARRAY_PTR(ary), VALUE, RARRAY_LEN(ary));
 	RARRAY(ary)->ptr = ptr;
     }
@@ -102,6 +158,7 @@
     ary->len = 0;
     ary->ptr = 0;
     ary->aux.capa = 0;
+    FL_UNSET(ary, RARRAY_LFREE);

     return (VALUE)ary;
 }
@@ -121,6 +178,7 @@
     if (len == 0) len++;
     RARRAY(ary)->ptr = ALLOC_N(VALUE, len);
     RARRAY(ary)->aux.capa = len;
+    FL_UNSET(RARRAY(ary), RARRAY_LFREE);

     return ary;
 }
@@ -135,7 +193,14 @@
 VALUE
 rb_ary_new(void)
 {
-    return rb_ary_new2(ARY_DEFAULT_SIZE);
+    VALUE ary = rb_ary_new2(ARY_DEFAULT_SIZE + ARY_DEFAULT_LCAPA);
+#if ARY_DEFAULT_LCAPA != 0
+    FL_SET(ary, RARRAY_LFREE);
+    RARRAY(ary)->ptr += ARY_DEFAULT_LCAPA;
+    RARRAY_PTR(ary)[-1] = ARY_DEFAULT_LCAPA;
+#endif
+    RARRAY(ary)->aux.capa = ARY_DEFAULT_SIZE;
+    return ary;
 }

 #include <stdarg.h>
@@ -177,7 +242,7 @@
 rb_ary_free(VALUE ary)
 {
     if (!ARY_SHARED_P(ary)) {
-	xfree(RARRAY(ary)->ptr);
+	xfree(RARRAY_TOP_PTR(ary));
     }
 }

@@ -194,6 +259,9 @@
 	shared->len = RARRAY(ary)->len;
 	shared->ptr = RARRAY(ary)->ptr;
 	shared->aux.capa = RARRAY(ary)->aux.capa;
+	if(FL_TEST(shared, RARRAY_LFREE)) {
+	    FL_SET(ary, RARRAY_LFREE);
+	}
 	RARRAY(ary)->aux.shared = (VALUE)shared;
 	FL_SET(ary, ELTS_SHARED);
 	OBJ_FREEZE(shared);
@@ -292,7 +360,7 @@
     rb_ary_modify(ary);
     if (argc ==  0) {
 	if (RARRAY_PTR(ary) && !ARY_SHARED_P(ary)) {
-	    free(RARRAY(ary)->ptr);
+	    free(RARRAY_TOP_PTR(ary));
 	}
 	RARRAY(ary)->len = 0;
 	if (rb_block_given_p()) {
@@ -355,6 +423,7 @@
     }
     RARRAY(ary)->ptr = ALLOC_N(VALUE, argc);
     RARRAY(ary)->aux.capa = argc;
+    FL_UNSET(RARRAY(ary), RARRAY_LFREE);
     MEMCPY(RARRAY_PTR(ary), argv, VALUE, argc);
     RARRAY(ary)->len = argc;

@@ -533,13 +602,10 @@
     if (RARRAY_LEN(ary) == 0) return Qnil;
     top = RARRAY_PTR(ary)[0];
     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--;
-	    return top;
+	if (RARRAY_LEN(ary) * 2 < ARY_LCAPA(ary)) {
+	    rb_ary_resize_lcapa(ary, RARRAY_LEN(ary));
 	}
-	RARRAY_PTR(ary)[0] = Qnil;
-	ary_make_shared(ary);
+	rb_ary_slide_capa_vals(ary, 1);
     }
     RARRAY(ary)->ptr++;		/* shift ptr */
     RARRAY(ary)->len--;
@@ -577,14 +643,11 @@
     rb_ary_modify_check(ary);
     result = ary_shared_first(argc, argv, ary, Qfalse);
     n = RARRAY_LEN(result);
-    if (ARY_SHARED_P(ary)) {
-	RARRAY(ary)->ptr += n;
-	RARRAY(ary)->len -= n;
-	}
-    else {
-	MEMMOVE(RARRAY_PTR(ary), RARRAY_PTR(ary)+n, VALUE, RARRAY_LEN(ary)-n);
-	RARRAY(ary)->len -= n;
+    if (!ARY_SHARED_P(ary)) {
+	rb_ary_slide_capa_vals(ary, n);
     }
+    RARRAY(ary)->ptr += n;
+    RARRAY(ary)->len -= n;

     return result;
 }
@@ -605,16 +668,25 @@
 rb_ary_unshift_m(int argc, VALUE *argv, VALUE ary)
 {
     long len;
+    long lcapa;

     if (argc == 0) return ary;
     rb_ary_modify(ary);
-    if (RARRAY(ary)->aux.capa <= (len = RARRAY(ary)->len) + argc) {
-	RESIZE_CAPA(ary, len + argc + ARY_DEFAULT_SIZE);
+    lcapa = ARY_LCAPA(ary);
+    if (lcapa < argc) {
+	long add_capa = ARY_DEFAULT_SIZE;
+	long add_lcapa = argc + ARY_DEFAULT_LCAPA;
+	if (RARRAY(ary)->aux.capa <= (len = RARRAY(ary)->len) + add_lcapa) {
+	    RESIZE_CAPA(ary, len + add_capa + add_lcapa);
+	}
+	lcapa += add_lcapa;
+	rb_ary_resize_lcapa(ary, lcapa);
     }

-    /* sliding items */
-    MEMMOVE(RARRAY(ary)->ptr + argc, RARRAY(ary)->ptr, VALUE, len);
+    RARRAY(ary)->ptr -= argc;
+    RARRAY(ary)->aux.capa += argc;
     MEMCPY(RARRAY(ary)->ptr, argv, VALUE, argc);
+    rb_ary_set_lcapa_val(ary, lcapa - argc);
     RARRAY(ary)->len += argc;

     return ary;
@@ -1494,6 +1566,7 @@
 	RARRAY(ary)->ptr = RARRAY(tmp)->ptr;
 	RARRAY(ary)->len = RARRAY(tmp)->len;
 	RARRAY(ary)->aux.capa = RARRAY(tmp)->aux.capa;
+	rb_ary_copy_lcapa(ary, tmp);
 	FL_UNSET(ary, ELTS_SHARED);
 	rb_gc_force_recycle(tmp);
     }
@@ -2019,7 +2092,7 @@
     if (copy == orig) return copy;
     shared = ary_make_shared(orig);
     if (!ARY_SHARED_P(copy)) {
-	ptr = RARRAY(copy)->ptr;
+	ptr = RARRAY_TOP_PTR(copy);
 	xfree(ptr);
     }
     RARRAY(copy)->ptr = RARRAY(orig)->ptr;
Index: include/ruby/ruby.h
===================================================================
--- include/ruby/ruby.h	(revision 15844)
+++ include/ruby/ruby.h	(working copy)
@@ -499,6 +499,8 @@
     } aux;
     VALUE *ptr;
 };
+
+#define RARRAY_LFREE FL_USER3
 #define RARRAY_LEN(a) RARRAY(a)->len
 #define RARRAY_PTR(a) RARRAY(a)->ptr


-- 
ワナベ