From 1113d54edecb68eaa55aa07996dec3b6fd8422f6 Mon Sep 17 00:00:00 2001 From: matz Date: Tue, 26 Sep 2006 22:46:16 +0000 Subject: * array.c (rb_ary_shift): shift/unshift performance boost patch, based on the patch from Eric Mahurin . [ruby-core:05861] * array.c (rb_ary_unshift_m): ditto. * array.c (ary_make_shared): ditto. * array.c (RESIZE_CAPA): ditto. * array.c (rb_ary_free): new function to free memory. code moved from gc.c. * string.c (rb_str_free): ditto. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@11038 b2dd03c8-39d4-4d8f-98ff-823fe69b080e --- array.c | 131 ++++++++++++++++++++++++++++++++++++++++++++++------------------ 1 file changed, 95 insertions(+), 36 deletions(-) (limited to 'array.c') diff --git a/array.c b/array.c index 4896ed24fb..a60df5d432 100644 --- a/array.c +++ b/array.c @@ -64,6 +64,11 @@ memfill(register VALUE *mem, register long size, register VALUE val) }\ } while (0) +#define ARY_LFREE FL_USER6 +#define ARY_LFREE_P(ary) FL_TEST(ary, ARY_LFREE) +#define LFREE_SIZE(ary) RARRAY(ary)->as.heap.ptr[-1] +#define LFREE_CAPA(ary) (LFREE_SIZE(ary)+RARRAY(ary)->as.heap.aux.capa) + #define ARY_CAPA(ary) ((ARY_EMBED_P(ary)) ? RARRAY_EMBED_LEN_MAX : RARRAY(ary)->as.heap.aux.capa) #define RESIZE_CAPA(ary,capacity) do {\ if (ARY_EMBED_P(ary)) {\ @@ -77,6 +82,21 @@ memfill(register VALUE *mem, register long size, register VALUE val) RARRAY(ary)->as.heap.aux.capa = (capacity);\ }\ }\ + else if (ARY_LFREE_P(ary)) {\ + VALUE *ptr = RARRAY(ary)->as.heap.ptr - LFREE_SIZE(ary);\ + if (LFREE_CAPA(ary) >= (capacity)) {\ + RARRAY(ary)->as.heap.aux.capa = LFREE_CAPA(ary);\ + MEMMOVE(ptr, RARRAY(ary)->as.heap.ptr, VALUE, RARRAY_LEN(ary));\ + FL_UNSET(ary, ARY_LFREE);\ + RARRAY(ary)->as.heap.ptr = ptr;\ + }\ + else {\ + long offset = LFREE_SIZE(ary);\ + REALLOC_N(ptr, VALUE, offset+(capacity));\ + RARRAY(ary)->as.heap.aux.capa = (capacity);\ + RARRAY(ary)->as.heap.ptr = ptr + offset;\ + }\ + }\ else {\ REALLOC_N(RARRAY(ary)->as.heap.ptr, VALUE, (capacity));\ RARRAY(ary)->as.heap.aux.capa = (capacity);\ @@ -223,6 +243,19 @@ rb_ary_new4(long n, const VALUE *elts) return ary; } +void +rb_ary_free(VALUE ary) +{ + if (!ARY_SHARED_P(ary) && !ARY_EMBED_P(ary)) { + if (ARY_LFREE_P(ary)) { + xfree(RARRAY(ary)->as.heap.ptr - RARRAY(ary)->as.heap.ptr[-1]); + } + else { + xfree(RARRAY(ary)->as.heap.ptr); + } + } +} + static VALUE ary_make_shared(VALUE ary) { @@ -238,6 +271,10 @@ ary_make_shared(VALUE ary) shared->as.heap.len = RARRAY(ary)->as.heap.len; shared->as.heap.ptr = RARRAY(ary)->as.heap.ptr; shared->as.heap.aux.capa = RARRAY(ary)->as.heap.aux.capa; + if (ARY_LFREE_P(ary)) { + FL_SET(shared,ARY_LFREE); + FL_UNSET(ary,ARY_LFREE); + } RARRAY(ary)->as.heap.aux.shared = (VALUE)shared; FL_SET(ary, ELTS_SHARED); OBJ_FREEZE(shared); @@ -578,18 +615,23 @@ rb_ary_shift(VALUE ary) rb_ary_modify_check(ary); if (RARRAY_LEN(ary) == 0) return Qnil; top = RARRAY_PTR(ary)[0]; - if (RARRAY_LEN(ary) < ARY_DEFAULT_SIZE && !FL_TEST(ary, ELTS_SHARED)) { + if (ARY_EMBED_P(ary)) { MEMMOVE(RARRAY_PTR(ary), RARRAY_PTR(ary)+1, VALUE, RARRAY_LEN(ary)); - ARY_SET_LEN(ary, RARRAY_LEN(ary)-1); + ARY_SET_EMBED_LEN(ary, RARRAY_LEN(ary)-1); + return top; } - else { - if (!FL_TEST(ary, ELTS_SHARED)) { - RARRAY_PTR(ary)[0] = Qnil; + if (!ARY_SHARED_P(ary)) { + if (ARY_LFREE_P(ary)) { + RARRAY(ary)->as.heap.ptr[0] = RARRAY(ary)->as.heap.ptr[-1]+1; + } + else { + FL_SET(ary, ARY_LFREE); + RARRAY(ary)->as.heap.ptr[0] = 1; } - ary_make_shared(ary); - RARRAY(ary)->as.heap.ptr++; /* shift ptr */ - RARRAY(ary)->as.heap.len--; + RARRAY(ary)->as.heap.aux.capa--; } + RARRAY(ary)->as.heap.ptr++; /* shift ptr */ + RARRAY(ary)->as.heap.len--; return top; } @@ -640,26 +682,6 @@ rb_ary_shift_m(int argc, VALUE *argv, VALUE ary) return result; } -VALUE -rb_ary_unshift(VALUE ary, VALUE item) -{ - rb_ary_modify(ary); - if (RARRAY_LEN(ary) == ARY_CAPA(ary)) { - long capa_inc = ARY_CAPA(ary) / 2; - if (capa_inc < ARY_DEFAULT_SIZE) { - capa_inc = ARY_DEFAULT_SIZE; - } - RESIZE_CAPA(ary, ARY_CAPA(ary)+capa_inc); - } - - /* sliding items */ - MEMMOVE(RARRAY_PTR(ary) + 1, RARRAY_PTR(ary), VALUE, RARRAY_LEN(ary)); - ARY_SET_LEN(ary, RARRAY_LEN(ary)+1); - RARRAY_PTR(ary)[0] = item; - - return ary; -} - /* * call-seq: * array.unshift(obj, ...) -> array @@ -675,20 +697,57 @@ rb_ary_unshift(VALUE ary, VALUE item) static VALUE rb_ary_unshift_m(int argc, VALUE *argv, VALUE ary) { - long len = RARRAY_LEN(ary); - + long lfree = ARY_LFREE_P(ary) ? RARRAY_PTR(ary)[-1] : 0; + + rb_ary_modify_check(ary); if (argc == 0) return ary; - /* make rooms by setting the last item */ - rb_ary_store(ary, len + argc - 1, Qnil); - - /* sliding items */ - MEMMOVE(RARRAY_PTR(ary) + argc, RARRAY_PTR(ary), VALUE, len); + if (lfree < argc) { + int shared = ARY_SHARED_P(ary); + long len = RARRAY_LEN(ary); + long rfree = shared ? 0 : (ARY_CAPA(ary)-len)/2; + long free2 = argc+(RARRAY_LEN(ary)+argc)/2; + VALUE *ptr; + if (free2 < ARY_DEFAULT_SIZE) { + free2 = ARY_DEFAULT_SIZE; + } + ptr = ALLOC_N(VALUE,len+free2)+(free2-rfree); + MEMCPY(ptr, RARRAY_PTR(ary), VALUE, len); + if (shared) { + FL_UNSET(ary, ELTS_SHARED); + } + else if (ARY_EMBED_P(ary)) { + ARY_SET_NOEMBED(ary); + } + else { + free(RARRAY_PTR(ary)-lfree); + } + RARRAY(ary)->as.heap.ptr = ptr; + RARRAY(ary)->as.heap.len = len; + RARRAY(ary)->as.heap.aux.capa = len+rfree; + lfree = free2-rfree; + FL_SET(ary, ARY_LFREE); + } + RARRAY(ary)->as.heap.ptr -= argc; + RARRAY(ary)->as.heap.len += argc; + RARRAY(ary)->as.heap.aux.capa += argc; + lfree -= argc; + if (lfree > 0) { + RARRAY(ary)->as.heap.ptr[-1] = lfree; + } else { + FL_UNSET(ary, ARY_LFREE); + } MEMCPY(RARRAY_PTR(ary), argv, VALUE, argc); - + return ary; } +VALUE +rb_ary_unshift(VALUE ary, VALUE item) +{ + return rb_ary_unshift_m(1,&item,ary); +} + /* faster version - use this if you don't need to treat negative offset */ static inline VALUE rb_ary_elt(VALUE ary, long offset) -- cgit v1.2.3