Yura's array as queue patch

174_mod.patch

From 6ba6eebc2e7dd309c9113ebfbb8c8e0e90542d21 Mon Sep 17 00:00:00 2001
From: Sokolov Yura 'funny-falcon <[email protected]>
Date: Sun, 2 Sep 2012 13:46:17 +0400
Subject: [PATCH 1/4] array.c: steal shared array's container when
 ARY_SHARED_NUM == 1

- Do not allocate new memory in rb_ary_modify when ARY_SHARED_NUM == 1
and length almost same.
- Store ARY_CAPA instead of RARRAY_LEN in ary_make_shared, to make it useful
- Fix rb_ary_sort_bang accordantly
---
 array.c |   23 +++++++++++++++++------
 1 file changed, 17 insertions(+), 6 deletions(-)

diff --git a/array.c b/array.c
index 524553a..b67881b 100644
--- a/array.c
+++ b/array.c
@@ -255,15 +255,24 @@
     rb_ary_modify_check(ary);
     if (ARY_SHARED_P(ary)) {
         long len = RARRAY_LEN(ary);
+	VALUE shared = ARY_SHARED(ary);
         if (len <= RARRAY_EMBED_LEN_MAX) {
             VALUE *ptr = ARY_HEAP_PTR(ary);
-            VALUE shared = ARY_SHARED(ary);
             FL_UNSET_SHARED(ary);
             FL_SET_EMBED(ary);
             MEMCPY(ARY_EMBED_PTR(ary), ptr, VALUE, len);
             rb_ary_decrement_share(shared);
             ARY_SET_EMBED_LEN(ary, len);
         }
+	else if (ARY_SHARED_NUM(shared) == 1 && len > RARRAY_LEN(shared)>>1) {
+	    long shift = RARRAY_PTR(ary) - RARRAY_PTR(shared);
+	    ARY_SET_PTR(ary, RARRAY_PTR(shared));
+	    ARY_SET_CAPA(ary, RARRAY_LEN(shared));
+	    MEMMOVE(RARRAY_PTR(ary), RARRAY_PTR(ary)+shift, VALUE, len);
+	    FL_UNSET_SHARED(ary);
+            FL_SET_EMBED(shared);
+	    rb_ary_decrement_share(shared);
+	}
         else {
             VALUE *ptr = ALLOC_N(VALUE, len);
             MEMCPY(ptr, RARRAY_PTR(ary), VALUE, len);
@@ -440,8 +449,9 @@
 	NEWOBJ_OF(shared, struct RArray, 0, T_ARRAY);
         FL_UNSET_EMBED(shared);
 
-        ARY_SET_LEN((VALUE)shared, RARRAY_LEN(ary));
+        ARY_SET_LEN((VALUE)shared, ARY_CAPA(ary));
         ARY_SET_PTR((VALUE)shared, RARRAY_PTR(ary));
+	rb_mem_clear(RARRAY_PTR(shared) + RARRAY_LEN(ary), ARY_CAPA(ary) - RARRAY_LEN(ary));
 	FL_SET_SHARED_ROOT(shared);
 	ARY_SET_SHARED_NUM((VALUE)shared, 1);
 	FL_SET_SHARED(ary);
@@ -2171,12 +2181,13 @@ enum {
     if (RARRAY_LEN(ary) > 1) {
 	VALUE tmp = ary_make_substitution(ary); /* only ary refers tmp */
 	struct ary_sort_data data;
+	long len = RARRAY_LEN(ary);
 
 	RBASIC(tmp)->klass = 0;
 	data.ary = tmp;
 	data.opt_methods = 0;
 	data.opt_inited = 0;
-	ruby_qsort(RARRAY_PTR(tmp), RARRAY_LEN(tmp), sizeof(VALUE),
+	ruby_qsort(RARRAY_PTR(tmp), len, sizeof(VALUE),
 		   rb_block_given_p()?sort_1:sort_2, &data);
 
         if (ARY_EMBED_P(tmp)) {
@@ -2193,7 +2204,7 @@ enum {
             if (ARY_HEAP_PTR(ary) == ARY_HEAP_PTR(tmp)) {
                 assert(!ARY_EMBED_P(ary));
                 FL_UNSET_SHARED(ary);
-                ARY_SET_CAPA(ary, ARY_CAPA(tmp));
+                ARY_SET_CAPA(ary, RARRAY_LEN(tmp));
             }
             else {
                 assert(!ARY_SHARED_P(tmp));
@@ -2208,8 +2219,8 @@ enum {
                     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));
+                ARY_SET_HEAP_LEN(ary, len);
+                ARY_SET_CAPA(ary, RARRAY_LEN(tmp));
             }
             /* tmp was lost ownership for the ptr */
             FL_UNSET(tmp, FL_FREEZE);
-- 
1.7.10


From 9f43064d479ed0852ae1567464fdee1386b771e7 Mon Sep 17 00:00:00 2001
From: Sokolov Yura 'funny-falcon <[email protected]>
Date: Sun, 2 Sep 2012 13:09:00 +0400
Subject: [PATCH 2/4] array.c : make array really suitable for queue

when array is shared (which happens after Array#shift), and
ARY_SHARED_NUM == 1 (which is very often when array used as
queue), then make rb_ary_push push directly into shared array
---
 array.c |   48 ++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 40 insertions(+), 8 deletions(-)

diff --git a/array.c b/array.c
index b67881b..419de14 100644
--- a/array.c
+++ b/array.c
@@ -283,6 +283,38 @@
     }
 }
 
+static void
+ary_ensure_room_for_push(VALUE ary, long add_len)
+{
+    long new_len = RARRAY_LEN(ary) + add_len;
+    long capa;
+
+    if (ARY_SHARED_P(ary)) {
+        if (new_len > RARRAY_EMBED_LEN_MAX) {
+            VALUE shared = ARY_SHARED(ary);
+            if (ARY_SHARED_NUM(shared) == 1) {
+		if (RARRAY_PTR(ary) - RARRAY_PTR(shared) + new_len <= RARRAY_LEN(shared)) {
+		    rb_ary_modify_check(ary);
+		}
+		else {
+		    /* if array is shared, than it is likely it participate in push/shift pattern */
+		    rb_ary_modify(ary);
+		    capa = ARY_CAPA(ary);
+		    if (new_len > capa - (capa >> 6)) {
+			ary_double_capa(ary, new_len);
+		    }
+		}
+		return;
+            }
+        }
+    }
+    rb_ary_modify(ary);
+    capa = ARY_CAPA(ary);
+    if (new_len > capa) {
+	ary_double_capa(ary, new_len);
+    }
+}
+
 /*
  *  call-seq:
  *      ary.freeze -> ary
@@ -740,8 +772,6 @@ enum ary_take_pos_flags
     return ary_make_partial(ary, rb_cArray, offset, n);
 }
 
-static VALUE rb_ary_push_1(VALUE ary, VALUE item);
-
 /*
  *  call-seq:
  *     ary << obj            -> ary
@@ -758,8 +788,12 @@ enum ary_take_pos_flags
 VALUE
 rb_ary_push(VALUE ary, VALUE item)
 {
-    rb_ary_modify(ary);
-    return rb_ary_push_1(ary, item);
+    long idx = RARRAY_LEN(ary);
+
+    ary_ensure_room_for_push(ary, 1);
+    RARRAY_PTR(ary)[idx] = item;
+    ARY_SET_LEN(ary, idx + 1);
+    return ary;
 }
 
 static VALUE
@@ -778,11 +812,9 @@ enum ary_take_pos_flags
 VALUE
 rb_ary_cat(VALUE ary, const VALUE *ptr, long len)
 {
-    long oldlen;
+    long oldlen = RARRAY_LEN(ary);
 
-    rb_ary_modify(ary);
-    oldlen = RARRAY_LEN(ary);
-    ary_resize_capa(ary, oldlen + len);
+    ary_ensure_room_for_push(ary, len);
     MEMCPY(RARRAY_PTR(ary) + oldlen, ptr, VALUE, len);
     ARY_SET_LEN(ary, oldlen + len);
     return ary;
-- 
1.7.10


From 88d6ab2d9e4c35f9c76c69c34b7cdba01720adb0 Mon Sep 17 00:00:00 2001
From: Sokolov Yura 'funny-falcon <[email protected]>
Date: Sun, 2 Sep 2012 13:09:24 +0400
Subject: [PATCH 3/4] array.c: use shared array in rb_ary_slice

- use ary_ensure_room_for_push when rb_ary_slice used to add at the end of
  array, cause rb_ary_concat use rb_ary_slice
---
 array.c |    6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)

diff --git a/array.c b/array.c
index 419de14..0105143 100644
--- a/array.c
+++ b/array.c
@@ -1374,15 +1374,12 @@ enum ary_take_pos_flags
 	rpl = rb_ary_to_ary(rpl);
 	rlen = RARRAY_LEN(rpl);
     }
-    rb_ary_modify(ary);
     if (beg >= RARRAY_LEN(ary)) {
 	if (beg > ARY_MAX_SIZE - rlen) {
 	    rb_raise(rb_eIndexError, "index %ld too big", beg);
 	}
+	ary_ensure_room_for_push(ary, rlen);
 	len = beg + rlen;
-	if (len >= ARY_CAPA(ary)) {
-	    ary_double_capa(ary, len);
-	}
 	rb_mem_clear(RARRAY_PTR(ary) + RARRAY_LEN(ary), beg - RARRAY_LEN(ary));
 	if (rlen > 0) {
 	    MEMCPY(RARRAY_PTR(ary) + beg, RARRAY_PTR(rpl), VALUE, rlen);
@@ -1392,6 +1389,7 @@ enum ary_take_pos_flags
     else {
 	long alen;
 
+	rb_ary_modify(ary);
 	alen = RARRAY_LEN(ary) + rlen - len;
 	if (alen >= ARY_CAPA(ary)) {
 	    ary_double_capa(ary, alen);
-- 
1.7.10


From a98fa0f868a7b0c7beb667483d214fb6e5f711e5 Mon Sep 17 00:00:00 2001
From: Sokolov Yura 'funny-falcon <[email protected]>
Date: Sun, 2 Sep 2012 13:40:52 +0400
Subject: [PATCH 4/4] array.c : speedup Array#unshift by using space in shared
 array

- when array owns its shared array (ARY_SHARED_NUM == 1),
  and there is enough space then try unshift values directly into shared
  array
- when resulting array is big (~>64 items) then make it shared
  with enough room for future #unshifts, and then insert into shared array
---
 array.c |   64 ++++++++++++++++++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 55 insertions(+), 9 deletions(-)

diff --git a/array.c b/array.c
index 0105143..2a67cef 100644
--- a/array.c
+++ b/array.c
@@ -970,6 +970,55 @@ enum ary_take_pos_flags
     return result;
 }
 
+static void
+ary_ensure_room_for_unshift(VALUE ary, int argc)
+{
+    long len = RARRAY_LEN(ary);
+    long new_len = len + argc;
+    long capa;
+    VALUE *head, *sharedp;
+
+    if (ARY_SHARED_P(ary)) {
+	VALUE shared = ARY_SHARED(ary);
+	capa = RARRAY_LEN(shared);
+	if (ARY_SHARED_NUM(shared) == 1 && capa > new_len) {
+	    head = RARRAY_PTR(ary);
+	    sharedp = RARRAY_PTR(shared);
+	    goto makeroom_if_need;
+	}
+    }
+
+    rb_ary_modify(ary);
+    capa = ARY_CAPA(ary);
+    if (capa - (capa >> 6) <= new_len) {
+	ary_double_capa(ary, new_len);
+    }
+
+    /* use shared array for big "queues" */
+    if (new_len > ARY_DEFAULT_SIZE * 4) {
+	/* make a room for unshifted items */
+	capa = ARY_CAPA(ary);
+	ary_make_shared(ary);
+
+	head = sharedp = RARRAY_PTR(ary);
+	goto makeroom;
+makeroom_if_need:
+	if (head - sharedp < argc) {
+	    long room;
+makeroom:
+	    room = capa - new_len;
+	    room -= room >> 4;
+	    MEMMOVE(sharedp + argc + room, head, VALUE, len);
+	    head = sharedp + argc + room;
+	}
+	ARY_SET_PTR(ary, head - argc);
+    }
+    else {
+	/* sliding items */
+	MEMMOVE(RARRAY_PTR(ary) + argc, RARRAY_PTR(ary), VALUE, len);
+    }
+}
+
 /*
  *  call-seq:
  *     ary.unshift(obj, ...)  -> ary
@@ -985,19 +1034,16 @@ enum ary_take_pos_flags
 static VALUE
 rb_ary_unshift_m(int argc, VALUE *argv, VALUE ary)
 {
-    long len;
+    long len = RARRAY_LEN(ary);
 
-    rb_ary_modify(ary);
-    if (argc == 0) return ary;
-    if (ARY_CAPA(ary) <= (len = RARRAY_LEN(ary)) + argc) {
-	ary_double_capa(ary, len + argc);
+    if (argc == 0) {
+	rb_ary_modify_check(ary);
+	return ary;
     }
 
-    /* sliding items */
-    MEMMOVE(RARRAY_PTR(ary) + argc, RARRAY_PTR(ary), VALUE, len);
+    ary_ensure_room_for_unshift(ary, argc);
     MEMCPY(RARRAY_PTR(ary), argv, VALUE, argc);
-    ARY_INCREASE_LEN(ary, argc);
-
+    ARY_SET_LEN(ary, len + argc);
     return ary;
 }
 
-- 
1.7.10