ruby-changes:25527
From: nobu <ko1@a...>
Date: Fri, 9 Nov 2012 16:08:59 +0900 (JST)
Subject: [ruby-changes:25527] nobu:r37584 (trunk): array.c: speedup Array#unshift by using space in shared array
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/