diff options
author | nobu <nobu@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2012-11-09 07:08:50 +0000 |
---|---|---|
committer | nobu <nobu@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2012-11-09 07:08:50 +0000 |
commit | fdbd3716781817c840544796d04a7d41b856d9f4 (patch) | |
tree | d0bc269c89f8566d5e228a66d1e738e329371a2a /array.c | |
parent | aaa9cb1ab4dd225113f027d4b725b8bb417e2cb1 (diff) |
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.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@37584 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
Diffstat (limited to 'array.c')
-rw-r--r-- | array.c | 64 |
1 files changed, 55 insertions, 9 deletions
@@ -984,6 +984,55 @@ rb_ary_shift_m(int argc, VALUE *argv, VALUE ary) 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 @@ rb_ary_shift_m(int argc, VALUE *argv, VALUE ary) 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; } |