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

ワナベと申します。

[ruby-core:5861]のパッチに興味があったので、
RARRAY_PTR(ary) より前方に空きメモリを保持するようにする、というアイディアを真似して
shift/unshift の高速化をするパッチを書いてみました。
長くなりそうだったので rb_ary_splice には触っていません。

元のパッチと比較すると、短いのでチェック・テストはしやすくなっていると思います。
とりあえず test_array.rb は通ることを確認しました。

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,9 +46,21 @@

 #define ARY_CAPA(ary) RARRAY(ary)->aux.capa
 #define RESIZE_CAPA(ary,capacity) do {\
-    REALLOC_N(RARRAY(ary)->ptr, VALUE, (capacity));\
+    RARRAY(ary)->ptr -= RARRAY(ary)->lcapa;\
+    REALLOC_N(RARRAY(ary)->ptr, VALUE, (capacity) + RARRAY(ary)->lcapa);\
+    RARRAY(ary)->ptr += RARRAY(ary)->lcapa;\
     RARRAY(ary)->aux.capa = (capacity);\
 } while (0)
+#define RESIZE_LCAPA(ary,lcapacity) do {\
+    long offset = (lcapacity) - RARRAY(ary)->lcapa;\
+    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;\
+    RARRAY(ary)->lcapa = (lcapacity);\
+} while (0)

 static inline void
 rb_ary_modify_check(VALUE ary)
@@ -67,6 +80,7 @@
 	ptr = ALLOC_N(VALUE, RARRAY_LEN(ary));
 	FL_UNSET(ary, ELTS_SHARED);
 	RARRAY(ary)->aux.capa = RARRAY_LEN(ary);
+	RARRAY(ary)->lcapa = 0;
 	MEMCPY(ptr, RARRAY_PTR(ary), VALUE, RARRAY_LEN(ary));
 	RARRAY(ary)->ptr = ptr;
     }
@@ -102,6 +116,7 @@
     ary->len = 0;
     ary->ptr = 0;
     ary->aux.capa = 0;
+    ary->lcapa = 0;

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

     return ary;
 }
@@ -135,7 +151,11 @@
 VALUE
 rb_ary_new(void)
 {
-    return rb_ary_new2(ARY_DEFAULT_SIZE);
+    VALUE ary = rb_ary_new2(ARY_DEFAULT_SIZE + ARY_DEFAULT_LCAPA);
+    RARRAY(ary)->ptr += ARY_DEFAULT_LCAPA;
+    RARRAY(ary)->lcapa = ARY_DEFAULT_LCAPA;
+    RARRAY(ary)->aux.capa = ARY_DEFAULT_SIZE;
+    return ary;
 }

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

@@ -194,6 +214,7 @@
 	shared->len = RARRAY(ary)->len;
 	shared->ptr = RARRAY(ary)->ptr;
 	shared->aux.capa = RARRAY(ary)->aux.capa;
+	shared->lcapa = RARRAY(ary)->lcapa;
 	RARRAY(ary)->aux.shared = (VALUE)shared;
 	FL_SET(ary, ELTS_SHARED);
 	OBJ_FREEZE(shared);
@@ -292,7 +313,7 @@
     rb_ary_modify(ary);
     if (argc ==  0) {
 	if (RARRAY_PTR(ary) && !ARY_SHARED_P(ary)) {
-	    free(RARRAY(ary)->ptr);
+	    free(RARRAY(ary)->ptr - RARRAY(ary)->lcapa);
 	}
 	RARRAY(ary)->len = 0;
 	if (rb_block_given_p()) {
@@ -355,6 +376,7 @@
     }
     RARRAY(ary)->ptr = ALLOC_N(VALUE, argc);
     RARRAY(ary)->aux.capa = argc;
+    RARRAY(ary)->lcapa = 0;
     MEMCPY(RARRAY_PTR(ary), argv, VALUE, argc);
     RARRAY(ary)->len = argc;

@@ -533,13 +555,11 @@
     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 < RARRAY(ary)->lcapa) {
+	    RESIZE_LCAPA(ary, RARRAY_LEN(ary));
 	}
-	RARRAY_PTR(ary)[0] = Qnil;
-	ary_make_shared(ary);
+	RARRAY(ary)->lcapa++;
+	RARRAY(ary)->aux.capa--;
     }
     RARRAY(ary)->ptr++;		/* shift ptr */
     RARRAY(ary)->len--;
@@ -577,14 +597,12 @@
     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)) {
+	RARRAY(ary)->lcapa += n;
+	RARRAY(ary)->aux.capa -= n;
     }
+    RARRAY(ary)->ptr += n;
+    RARRAY(ary)->len -= n;

     return result;
 }
@@ -608,12 +626,18 @@

     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);
+    if (RARRAY(ary)->lcapa < argc) {
+	long add_capa = ARY_DEFAULT_SIZE;
+	long add_lcapa = ARY_DEFAULT_LCAPA;
+	if (RARRAY(ary)->aux.capa <= (len = RARRAY(ary)->len) + argc + add_lcapa) {
+	    RESIZE_CAPA(ary, len + argc + add_capa + add_lcapa);
+	}
+	RESIZE_LCAPA(ary, RARRAY(ary)->lcapa + argc + add_lcapa);
     }

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

@@ -1494,6 +1518,7 @@
 	RARRAY(ary)->ptr = RARRAY(tmp)->ptr;
 	RARRAY(ary)->len = RARRAY(tmp)->len;
 	RARRAY(ary)->aux.capa = RARRAY(tmp)->aux.capa;
+	RARRAY(ary)->lcapa = RARRAY(tmp)->lcapa;
 	FL_UNSET(ary, ELTS_SHARED);
 	rb_gc_force_recycle(tmp);
     }
@@ -2019,7 +2044,7 @@
     if (copy == orig) return copy;
     shared = ary_make_shared(orig);
     if (!ARY_SHARED_P(copy)) {
-	ptr = RARRAY(copy)->ptr;
+	ptr = RARRAY(copy)->ptr - RARRAY(copy)->lcapa;
 	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)
@@ -498,6 +498,7 @@
 	VALUE shared;
     } aux;
     VALUE *ptr;
+    long lcapa;
 };
 #define RARRAY_LEN(a) RARRAY(a)->len
 #define RARRAY_PTR(a) RARRAY(a)->ptr

-- 
ワナベ