nobu	2012-11-09 16:08:50 +0900 (Fri, 09 Nov 2012)

  New Revision: 37584

  http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=37584

  Log:
    array.c: speedup Array#unshift by using space in shared array
    
    * array.c: speedup Array#unshift by using space in shared array.
      [Feature #6638]
      - 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.

  Modified files:
    trunk/ChangeLog
    trunk/array.c

Index: array.c
===================================================================
--- array.c	(revision 37583)
+++ array.c	(revision 37584)
@@ -984,6 +984,55 @@
     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
@@ -999,19 +1048,16 @@
 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;
 }
 
Index: ChangeLog
===================================================================
--- ChangeLog	(revision 37583)
+++ ChangeLog	(revision 37584)
@@ -1,5 +1,14 @@
-Fri Nov  9 16:08:43 2012  Sokolov Yura funny-falcon  <funny.falcon@g...>
+Fri Nov  9 16:08:46 2012  Sokolov Yura funny-falcon  <funny.falcon@g...>
 
+	* array.c: speedup Array#unshift by using space in shared array.
+	  [Feature #6638]
+	  - 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 (rb_ary_splice): use shared array in rb_ary_slice.
 	  [Feature #6638]
 	  - use ary_ensure_room_for_push when rb_ary_slice used to add at the

--
ML: ruby-changes@q...
Info: http://www.atdot.net/~ko1/quickml/