From: Eric Mahurin Date: 2005-09-22T01:56:21+09:00 Subject: another array patch - performance boosts all over the place --0-698884423-1127321776=:45213 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Content-Id: Content-Disposition: inline Is anybody interested in the patches I'm doing to make arrays (and someday strings) faster? I didn't see a response for my last patch (shift/unshift). Now I have another patch (fastarray.diff - attached) that should help out a lot more code sequences. Here are the results using the attached benchmark (end_test.rb): n = 32768 (2**15) code old new ------------------------- ----- ----- ; 0.01 0.01 shift 0.02 0.02 shift(1) 0.03 0.04 pop 0.02 0.01 pop(1) 0.04 0.05 shift;pop 0.02 0.02 shift(1);pop(1) 0.07 0.08 unshift(i) 2.34 0.02 push(i) 0.02 0.02 unshift(i);push(i) 2.35 0.03 unshift(shift) 17.61 0.03 unshift(*shift(1)) 17.42 0.07 push(pop) 0.04 0.02 push(*pop(1)) 13.83 0.08 push(shift) 14.64 0.03 push(*shift(1)) 15.39 0.08 unshift(pop) 2.33 0.03 unshift(*pop(1)) 16.47 0.08 slice!(1) 2.29 0.03 delete_at(1) 2.30 0.02 slice!(1,1) 12.75 0.05 self[1,1]=[] 2.36 0.05 slice!(-2) 0.02 0.03 delete_at(-2) 0.02 0.02 slice!(-2,1) 10.37 0.05 self[-2,1]=[] 0.04 0.04 self[1,0]=[i] 3.49 0.04 insert(1,i) 3.44 0.04 self[-1,0]=[i] 1.07 0.05 insert(-2,i) 1.02 0.05 self[1,0]=slice!(1,1) 16.40 0.06 insert(1,delete_at(1)) 5.60 0.06 self[-1,0]=slice!(-2,1) 11.92 0.06 insert(-2,delete_at(-2)) 1.00 0.06 self[-1,0]=slice!(1,1) 14.10 0.07 insert(-2,delete_at(1)) 3.29 0.06 self[1,0]=slice!(-2,1) 14.06 0.07 insert(1,delete_at(-2)) 3.30 0.06 self[i]=self[i] 0.03 0.02 self[i]=at(i) 0.03 0.02 self[i,1]=self[i,1] 11.72 0.06 self[-i-1]=self[-i-1] 0.05 0.05 self[-i-1]=at(-i-1) 0.04 0.05 self[-i-1,1]=self[-i-1,1] 11.74 0.07 self[-i-1]=self[i] 0.03 0.03 self[-i-1]=at(i) 0.03 0.04 self[-i-1,1]=self[i,1] 11.67 0.07 self[i]=self[-i-1] 0.04 0.04 self[i]=at(-i-1) 0.03 0.03 self[i,1]=self[-i-1,1] 11.70 0.06 In each of the tests above, it runs the code n times on an array that has an average length of n. The massive performance boosts you see above is because the old (current) code was O(n) in those cases and my patched code is O(1). Here were the changes I made: - added a bit (ELTS_LFREE=FL_USER3) to say whether there is free space to the left of ary->ptr and put the number of free elements in ary->ptr[-1]. - instead of ary->aux.capa, did the same for free space to the right of ary->ptr+ary->len-1 (new flag: ELTS_RFREE=FL_USER3 and amount stored in ary->ptr[ary->len]). This freed up ary->shared for dedicated used (instead of being a union with capa). - instead of shared arrays all pointing to a common frozen array object, put shared arrays in a circular linked list (used ary->shared). The original master array will have ELTS_SHARED=0 and the others will have ELTS_SHARED=1. Unshared arrays will have ELTS_SHARED=0 and ary->shared=0. - when a shared array is to be modified, there are 2 cases: slave - make copy and remove from shared circular linked list; master - make copies of all slaves and terminate sharing between this master and its slaves. When a shared array is to be freed, it operates in a similar way. - during GC, shared arrays are treated independently (master can be freed). This works because of the above mechanism. Before, unused object references would persist because of array sharing (keeping an array slice around would keep references to all objects in the original array). - modified various functions (shift, unshift, delete_at, splice), to insert/delete toward the closest side to minimize the number of elements needed to be moved. Does anybody see a downside to this? The main problem I see is that I don't see the big picture when making these changes (i.e. GC). And this needs to be better tested. Anybody know of something good to do array testing? I just used the self-testing benchmark attached and what's in test/ruby. Eric __________________________________ Yahoo! Mail - PC Magazine Editors' Choice 2005 http://mail.yahoo.com --0-698884423-1127321776=:45213 Content-Type: text/x-patch; name="fastarray.diff" Content-Description: 1280032582-fastarray.diff Content-Disposition: inline; filename="fastarray.diff" Index: array.c =================================================================== RCS file: /src/ruby/array.c,v retrieving revision 1.179 diff -u -r1.179 array.c --- array.c 12 Sep 2005 15:23:54 -0000 1.179 +++ array.c 21 Sep 2005 16:13:02 -0000 @@ -16,6 +16,7 @@ #include "util.h" #include "st.h" #include "node.h" +#include "rubysig.h" VALUE rb_cArray, rb_cValues; @@ -52,20 +53,63 @@ } static void -rb_ary_modify(VALUE ary) +rb_ary_unshare(VALUE ary, int freeit) { + VALUE shared = RARRAY(ary)->shared; + VALUE next = shared; + VALUE cur; VALUE *ptr; - - rb_ary_modify_check(ary); + VALUE *freeptr = 0; if (FL_TEST(ary, ELTS_SHARED)) { - ptr = ALLOC_N(VALUE, RARRAY(ary)->len); + if (freeit) { + RARRAY(ary)->ptr = 0; + } else { + ptr = ALLOC_N(VALUE, RARRAY(ary)->len); + MEMCPY(ptr, RARRAY(ary)->ptr, VALUE, RARRAY(ary)->len); + RARRAY(ary)->ptr = ptr; + } FL_UNSET(ary, ELTS_SHARED); - RARRAY(ary)->aux.capa = RARRAY(ary)->len; - MEMCPY(ptr, RARRAY(ary)->ptr, VALUE, RARRAY(ary)->len); - RARRAY(ary)->ptr = ptr; + RARRAY(ary)->shared = 0; + do { + cur = next; + next = RARRAY(cur)->shared; + } while (next!=ary); + if (cur==shared) { + RARRAY(cur)->shared = 0; + } else { + RARRAY(cur)->shared = shared; + } + } else if (RARRAY(ary)->ptr) { + if (freeit) { + long lfree = FL_TEST(ary,ELTS_LFREE) ? RARRAY(ary)->ptr[-1] : 0; + freeptr = RARRAY(ary)->ptr-lfree; + FL_UNSET(ary, ELTS_LFREE); + FL_UNSET(ary, ELTS_RFREE); + RARRAY(ary)->ptr = 0; + } + if (shared) for (;;) { + RARRAY(ary)->shared = 0; + ary = shared; + shared = RARRAY(ary)->shared; + if (!shared) break; + ptr = ALLOC_N(VALUE, RARRAY(ary)->len); + MEMCPY(ptr, RARRAY(ary)->ptr, VALUE, RARRAY(ary)->len); + FL_UNSET(ary, ELTS_SHARED); + RARRAY(ary)->ptr = ptr; + } + if (freeptr) RUBY_CRITICAL(free(freeptr)); } } +static void +rb_ary_modify(VALUE ary) +{ + VALUE *ptr; + + rb_ary_modify_check(ary); + rb_ary_unshare(ary,0); +} + VALUE rb_ary_freeze(VALUE ary) { @@ -96,7 +140,7 @@ ary->len = 0; ary->ptr = 0; - ary->aux.capa = 0; + ary->shared = 0; return (VALUE)ary; } @@ -116,7 +160,6 @@ ary = ary_alloc(klass); RARRAY(ary)->ptr = ALLOC_N(VALUE, len); - RARRAY(ary)->aux.capa = len; return ary; } @@ -146,7 +189,7 @@ ary = rb_ary_new2(n); va_start(ar, n); - for (i=0; iptr[i] = va_arg(ar, VALUE); } va_end(ar); @@ -196,44 +239,62 @@ if (n > 0 && elts) { RARRAY(val)->len = n; MEMCPY(RARRAY(val)->ptr, elts, VALUE, n); + } else if (n > 0) { + RARRAY(val)->ptr[0] = n; + FL_SET(val,ELTS_RFREE); } return val; } static VALUE -ary_make_shared(VALUE ary) +ary_share(VALUE val, VALUE ary) { + /* if (!FL_TEST(ary, ELTS_SHARED)) { NEWOBJ(shared, struct RArray); OBJSETUP(shared, rb_cArray, T_ARRAY); shared->len = RARRAY(ary)->len; shared->ptr = RARRAY(ary)->ptr; - shared->aux.capa = RARRAY(ary)->aux.capa; - RARRAY(ary)->aux.shared = (VALUE)shared; + if (FL_TEST(ary,ELTS_RFREE)) { + FL_SET(shared,ELTS_RFREE); + FL_UNSET(ary,ELTS_RFREE); + } + if (FL_TEST(ary,ELTS_LFREE)) { + FL_SET(shared,ELTS_LFREE); + FL_UNSET(ary,ELTS_LFREE); + } + RARRAY(ary)->shared = (VALUE)shared; FL_SET(ary, ELTS_SHARED); OBJ_FREEZE(shared); - return (VALUE)shared; } - else { - return RARRAY(ary)->aux.shared; + */ + RARRAY(val)->ptr = RARRAY(ary)->ptr; + RARRAY(val)->len = RARRAY(ary)->len; + if (RARRAY(ary)->shared) { + RARRAY(val)->shared = RARRAY(ary)->shared; + } else { + RARRAY(val)->shared = ary; } + RARRAY(ary)->shared = val; + FL_SET(val, ELTS_SHARED); + return val; } static VALUE ary_shared_array(VALUE klass, VALUE ary) { - VALUE val = ary_alloc(klass); + return ary_share(ary_alloc(klass),ary); +} - ary_make_shared(ary); - RARRAY(val)->ptr = RARRAY(ary)->ptr; - RARRAY(val)->len = RARRAY(ary)->len; - RARRAY(val)->aux.shared = RARRAY(ary)->aux.shared; - FL_SET(val, ELTS_SHARED); - return val; +void +ary_free(VALUE obj) +{ + rb_ary_unshare(obj,1); } + VALUE rb_values_from_ary(VALUE ary) { @@ -315,8 +376,17 @@ { long len; VALUE size, val; + long capa; if (rb_scan_args(argc, argv, "02", &size, &val) == 0) { + if (!FL_TEST(ary,ELTS_SHARED)) { + rb_ary_modify(ary); + capa = RARRAY(ary)->len+(FL_TEST(ary,ELTS_RFREE) ? RARRAY(ary)->ptr[RARRAY(ary)->len] : 0); + if (capa) { + FL_SET(ary,ELTS_RFREE); + RARRAY(ary)->ptr[0] = capa; + } + } RARRAY(ary)->len = 0; if (rb_block_given_p()) { rb_warning("given block not used"); @@ -340,9 +410,13 @@ rb_raise(rb_eArgError, "array size too big"); } rb_ary_modify(ary); - if (len > RARRAY(ary)->aux.capa) { - REALLOC_N(RARRAY(ary)->ptr, VALUE, len); - RARRAY(ary)->aux.capa = len; + capa = RARRAY(ary)->len+(FL_TEST(ary,ELTS_RFREE) ? RARRAY(ary)->ptr[RARRAY(ary)->len] : 0); + if (len > capa) { + long lfree = FL_TEST(ary,ELTS_LFREE) ? RARRAY(ary)->ptr[-1] : 0; + RARRAY(ary)->ptr -= lfree; + REALLOC_N(RARRAY(ary)->ptr, VALUE, len + lfree); + RARRAY(ary)->ptr += lfree; + capa = len; } if (rb_block_given_p()) { long i; @@ -359,6 +433,12 @@ memfill(RARRAY(ary)->ptr, len, val); RARRAY(ary)->len = len; } + if (capa > len) { + FL_SET(ary,ELTS_RFREE); + RARRAY(ary)->ptr[len] = capa-len; + } else { + FL_UNSET(ary,ELTS_RFREE); + } return ary; } @@ -381,7 +461,7 @@ RARRAY(ary)->ptr = ALLOC_N(VALUE, argc); MEMCPY(RARRAY(ary)->ptr, argv, VALUE, argc); } - RARRAY(ary)->len = RARRAY(ary)->aux.capa = argc; + RARRAY(ary)->len = argc; return ary; } @@ -389,6 +469,7 @@ void rb_ary_store(VALUE ary, long idx, VALUE val) { + long capa; if (idx < 0) { idx += RARRAY(ary)->len; if (idx < 0) { @@ -398,8 +479,10 @@ } rb_ary_modify(ary); - if (idx >= RARRAY(ary)->aux.capa) { - long new_capa = RARRAY(ary)->aux.capa / 2; + capa = RARRAY(ary)->len+(FL_TEST(ary,ELTS_RFREE) ? RARRAY(ary)->ptr[RARRAY(ary)->len] : 0); + if (idx >= capa) { + long new_capa = capa / 2; + long lfree = FL_TEST(ary,ELTS_LFREE) ? RARRAY(ary)->ptr[-1] : 0; if (new_capa < ARY_DEFAULT_SIZE) { new_capa = ARY_DEFAULT_SIZE; @@ -408,8 +491,10 @@ if (new_capa * (long)sizeof(VALUE) <= new_capa) { rb_raise(rb_eArgError, "index too big"); } - REALLOC_N(RARRAY(ary)->ptr, VALUE, new_capa); - RARRAY(ary)->aux.capa = new_capa; + RARRAY(ary)->ptr -= lfree; + REALLOC_N(RARRAY(ary)->ptr, VALUE, new_capa + lfree); + RARRAY(ary)->ptr += lfree; + capa = new_capa; } if (idx > RARRAY(ary)->len) { rb_mem_clear(RARRAY(ary)->ptr + RARRAY(ary)->len, @@ -417,7 +502,14 @@ } if (idx >= RARRAY(ary)->len) { - RARRAY(ary)->len = idx + 1; + long len = idx + 1; + RARRAY(ary)->len = len; + if (capa > len) { + FL_SET(ary,ELTS_RFREE); + RARRAY(ary)->ptr[len] = capa-len; + } else { + FL_UNSET(ary,ELTS_RFREE); + } } RARRAY(ary)->ptr[idx] = val; } @@ -495,15 +587,30 @@ VALUE rb_ary_pop(VALUE ary) { - rb_ary_modify_check(ary); + long capa; + VALUE item; + if (!FL_TEST(ary, ELTS_SHARED)) { + rb_ary_modify(ary); + } else { + rb_ary_modify_check(ary); + } if (RARRAY(ary)->len == 0) return Qnil; + capa = RARRAY(ary)->len+(FL_TEST(ary,ELTS_RFREE) ? RARRAY(ary)->ptr[RARRAY(ary)->len] : 0); if (!FL_TEST(ary, ELTS_SHARED) && - RARRAY(ary)->len * 2 < RARRAY(ary)->aux.capa && - RARRAY(ary)->aux.capa > ARY_DEFAULT_SIZE) { - RARRAY(ary)->aux.capa = RARRAY(ary)->len * 2; - REALLOC_N(RARRAY(ary)->ptr, VALUE, RARRAY(ary)->aux.capa); + RARRAY(ary)->len * 2 < capa && + capa > ARY_DEFAULT_SIZE) { + long lfree = FL_TEST(ary,ELTS_LFREE) ? RARRAY(ary)->ptr[-1] : 0; + capa = RARRAY(ary)->len * 2; + RARRAY(ary)->ptr -= lfree; + REALLOC_N(RARRAY(ary)->ptr, VALUE, capa + lfree); + RARRAY(ary)->ptr += lfree; + } + item = RARRAY(ary)->ptr[--RARRAY(ary)->len]; + if (!FL_TEST(ary, ELTS_SHARED)) { + RARRAY(ary)->ptr[RARRAY(ary)->len] = capa-RARRAY(ary)->len; + FL_SET(ary,ELTS_RFREE); } - return RARRAY(ary)->ptr[--RARRAY(ary)->len]; + return item; } /* @@ -523,15 +630,20 @@ rb_ary_pop_m(int argc, VALUE *argv, VALUE ary) { VALUE result; + long n; if (argc == 0) { return rb_ary_pop(ary); } - rb_ary_modify_check(ary); - result = ary_shared_last(argc, argv, ary); - RARRAY(ary)->len -= RARRAY(result)->len; + rb_ary_modify(ary); + n = RARRAY(result)->len; + if (n) { + long rfree = FL_TEST(ary,ELTS_RFREE) ? RARRAY(ary)->ptr[RARRAY(ary)->len] : 0; + RARRAY(ary)->ptr[RARRAY(ary)->len -= n] = rfree+n; + FL_SET(ary,ELTS_RFREE); + } return result; } @@ -540,10 +652,20 @@ { VALUE top; - rb_ary_modify_check(ary); if (RARRAY(ary)->len == 0) return Qnil; top = RARRAY(ary)->ptr[0]; - ary_make_shared(ary); + if (!FL_TEST(ary,ELTS_SHARED)) { + rb_ary_modify(ary); + if (FL_TEST(ary,ELTS_LFREE)) { + RARRAY(ary)->ptr[0] = RARRAY(ary)->ptr[-1]+1; + } else { + FL_SET(ary, ELTS_LFREE); + RARRAY(ary)->ptr[0] = 1; + } + } else { + rb_ary_modify_check(ary); + } + RARRAY(ary)->ptr++; /* shift ptr */ RARRAY(ary)->len--; @@ -577,36 +699,17 @@ return rb_ary_shift(ary); } - rb_ary_modify_check(ary); - result = ary_shared_first(argc, argv, ary); - n = RARRAY(result)->len; - RARRAY(ary)->ptr += n; - RARRAY(ary)->len -= n; - - return result; -} - -VALUE -rb_ary_unshift(VALUE ary, VALUE item) -{ rb_ary_modify(ary); - if (RARRAY(ary)->len == RARRAY(ary)->aux.capa) { - long capa_inc = RARRAY(ary)->aux.capa / 2; - if (capa_inc < ARY_DEFAULT_SIZE) { - capa_inc = ARY_DEFAULT_SIZE; - } - RARRAY(ary)->aux.capa += capa_inc; - REALLOC_N(RARRAY(ary)->ptr, VALUE, RARRAY(ary)->aux.capa); + n = RARRAY(result)->len; + if (n) { + long lfree = FL_TEST(ary,ELTS_LFREE) ? RARRAY(ary)->ptr[-1] : 0; + (RARRAY(ary)->ptr += n)[-1] = lfree+n; + RARRAY(ary)->len -= n; + FL_SET(ary,ELTS_LFREE); } - /* sliding items */ - MEMMOVE(RARRAY(ary)->ptr + 1, RARRAY(ary)->ptr, VALUE, RARRAY(ary)->len); - - RARRAY(ary)->len++; - RARRAY(ary)->ptr[0] = item; - - return ary; + return result; } /* @@ -624,20 +727,50 @@ static VALUE rb_ary_unshift_m(int argc, VALUE *argv, VALUE ary) { - long len = RARRAY(ary)->len; - - if (argc == 0) return ary; - - /* make rooms by setting the last item */ - rb_ary_store(ary, len + argc - 1, Qnil); - - /* sliding items */ - MEMMOVE(RARRAY(ary)->ptr + argc, RARRAY(ary)->ptr, VALUE, len); - MEMCPY(RARRAY(ary)->ptr, argv, VALUE, argc); + long lfree = FL_TEST(ary,ELTS_LFREE) ? RARRAY(ary)->ptr[-1] : 0; + rb_ary_modify_check(ary); + if (lfreelen; + long rfree = (FL_TEST(ary,ELTS_RFREE) ? RARRAY(ary)->ptr[RARRAY(ary)->len] : 0)/2; + long free2 = argc+(RARRAY(ary)->len+argc)/2; + VALUE *ptr; + if (free2 < ARY_DEFAULT_SIZE) { + free2 = ARY_DEFAULT_SIZE; + } + ptr = ALLOC_N(VALUE,len+free2)+(free2-rfree); + MEMMOVE(ptr, RARRAY(ary)->ptr, VALUE, len); + ary_free(ary); + RARRAY(ary)->ptr = ptr; + if (rfree) { + RARRAY(ary)->ptr[len] = rfree; + FL_SET(ary,ELTS_RFREE); + } else { + FL_UNSET(ary,ELTS_RFREE); + } + lfree = free2-rfree; + FL_SET(ary, ELTS_LFREE); + } + + RARRAY(ary)->ptr -= argc; + RARRAY(ary)->len += argc; + lfree -= argc; + if (lfree) { + RARRAY(ary)->ptr[-1] = lfree; + } else { + FL_UNSET(ary, ELTS_LFREE); + } + MEMCPY(RARRAY(ary)->ptr, 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) @@ -661,7 +794,7 @@ static VALUE rb_ary_subseq(VALUE ary, long beg, long len) { - VALUE klass, ary2, shared; + VALUE klass, ary2; VALUE *ptr; if (beg > RARRAY(ary)->len) return Qnil; @@ -675,13 +808,9 @@ klass = rb_obj_class(ary); if (len == 0) return ary_new(klass, 0); - shared = ary_make_shared(ary); - ptr = RARRAY(ary)->ptr; - ary2 = ary_alloc(klass); - RARRAY(ary2)->ptr = ptr + beg; + ary2 = ary_shared_array(klass,ary); + RARRAY(ary2)->ptr += beg; RARRAY(ary2)->len = len; - RARRAY(ary2)->aux.shared = shared; - FL_SET(ary2, ELTS_SHARED); return ary2; } @@ -968,6 +1097,11 @@ rb_ary_splice(VALUE ary, long beg, long len, VALUE rpl) { long rlen; + long alen; + long beg0; + long diff; + VALUE *ptr; + long alen0 = RARRAY(ary)->len; if (len < 0) rb_raise(rb_eIndexError, "negative length (%ld)", len); if (beg < 0) { @@ -977,9 +1111,6 @@ rb_raise(rb_eIndexError, "index %ld out of array", beg); } } - if (beg + len > RARRAY(ary)->len) { - len = RARRAY(ary)->len - beg; - } if (rpl == Qundef) { rlen = 0; @@ -988,41 +1119,100 @@ rpl = rb_ary_to_ary(rpl); rlen = RARRAY(rpl)->len; } + rb_ary_modify(ary); - if (beg >= RARRAY(ary)->len) { - len = beg + rlen; - if (len >= RARRAY(ary)->aux.capa) { - REALLOC_N(RARRAY(ary)->ptr, VALUE, len); - RARRAY(ary)->aux.capa = len; - } - rb_mem_clear(RARRAY(ary)->ptr + RARRAY(ary)->len, beg - RARRAY(ary)->len); - if (rlen > 0) { - MEMCPY(RARRAY(ary)->ptr + beg, RARRAY(rpl)->ptr, VALUE, rlen); - } - RARRAY(ary)->len = len; - } - else { - long alen; + beg0 = beg; + ptr = RARRAY(ary)->ptr; - if (beg + len > RARRAY(ary)->len) { - len = RARRAY(ary)->len - beg; - } + if (beg + len > RARRAY(ary)->len) { + len = RARRAY(ary)->len - beg; + if (len<0) beg0 = beg + len; + } - alen = RARRAY(ary)->len + rlen - len; - if (alen >= RARRAY(ary)->aux.capa) { - REALLOC_N(RARRAY(ary)->ptr, VALUE, alen); - RARRAY(ary)->aux.capa = alen; - } + diff = rlen - len; + alen = alen0 + diff; - if (len != rlen) { - MEMMOVE(RARRAY(ary)->ptr + beg + rlen, RARRAY(ary)->ptr + beg + len, - VALUE, RARRAY(ary)->len - (beg + len)); - RARRAY(ary)->len = alen; - } - if (rlen > 0) { - MEMMOVE(RARRAY(ary)->ptr + beg, RARRAY(rpl)->ptr, VALUE, rlen); - } + if (diff) { + long lfree = FL_TEST(ary,ELTS_LFREE) ? ptr[-1] : 0; + long rfree = FL_TEST(ary,ELTS_RFREE) ? ptr[alen0] : 0; + if (beg>=alen/2) { + rfree -= diff; + if (rfree<0) { + long free2 = alen/2; + if (lfree>free2/2) { + lfree = free2/2; + } + rfree = free2-lfree; + ptr = ALLOC_N(VALUE, alen+free2) + lfree; + MEMCPY(ptr, RARRAY(ary)->ptr, VALUE, beg0); + MEMCPY(ptr+beg+rlen, RARRAY(ary)->ptr+beg+len, VALUE, alen0 - (beg+len)); + if (rlen > 0) { + MEMMOVE(ptr + beg, RARRAY(rpl)->ptr, VALUE, rlen); + } + ary_free(ary); + if (lfree) { + ptr[-1] = lfree; + FL_SET(ary,ELTS_LFREE); + } else { + FL_UNSET(ary,ELTS_LFREE); + } + RARRAY(ary)->ptr = ptr; + } else { + MEMMOVE(ptr+beg+rlen, ptr+beg+len, VALUE, alen0 - (beg+len)); + if (rlen > 0) { + MEMMOVE(ptr + beg, RARRAY(rpl)->ptr, VALUE, rlen); + } + } + if (rfree) { + ptr[alen] = rfree; + FL_SET(ary, ELTS_RFREE); + } else { + FL_UNSET(ary, ELTS_RFREE); + } + } else { + ptr -= diff; + lfree -= diff; + if (lfree<0) { + long free2 = alen/2; + if (rfree>free2/2) { + rfree = free2/2; + } + lfree = free2-rfree; + ptr = ALLOC_N(VALUE, alen+free2) + lfree; + MEMCPY(ptr, RARRAY(ary)->ptr, VALUE, beg0); + MEMCPY(ptr+beg+rlen, RARRAY(ary)->ptr+beg+len, + VALUE, alen0 - (beg+len)); + if (rlen > 0) { + MEMMOVE(ptr + beg, RARRAY(rpl)->ptr, VALUE, rlen); + } + ary_free(ary); + if (rfree) { + ptr[alen] = rfree; + FL_SET(ary,ELTS_RFREE); + } else { + FL_UNSET(ary,ELTS_RFREE); + } + } else { + MEMMOVE(ptr, ptr+diff, VALUE, beg0); + if (rlen > 0) { + MEMMOVE(ptr + beg, RARRAY(rpl)->ptr, VALUE, rlen); + } + } + if (lfree) { + ptr[-1] = lfree; + FL_SET(ary, ELTS_LFREE); + } else { + FL_UNSET(ary, ELTS_LFREE); + } + RARRAY(ary)->ptr = ptr; + } + RARRAY(ary)->len = alen; + } else if (rlen > 0) { + MEMMOVE(ptr + beg, RARRAY(rpl)->ptr, VALUE, rlen); + } + if (len < 0) { + rb_mem_clear(ptr + beg0, -len); } } @@ -1730,6 +1920,7 @@ rb_ary_delete(VALUE ary, VALUE item) { long i1, i2; + long capa; for (i1 = i2 = 0; i1 < RARRAY(ary)->len; i1++) { VALUE e = RARRAY(ary)->ptr[i1]; @@ -1748,13 +1939,23 @@ } rb_ary_modify(ary); + capa = RARRAY(ary)->len+(FL_TEST(ary,ELTS_RFREE) ? RARRAY(ary)->ptr[RARRAY(ary)->len] : 0); if (RARRAY(ary)->len > i2) { RARRAY(ary)->len = i2; - if (i2 * 2 < RARRAY(ary)->aux.capa && - RARRAY(ary)->aux.capa > ARY_DEFAULT_SIZE) { - REALLOC_N(RARRAY(ary)->ptr, VALUE, i2 * 2); - RARRAY(ary)->aux.capa = i2 * 2; - } + if (i2 * 2 < capa && + capa > ARY_DEFAULT_SIZE) { + long lfree = FL_TEST(ary,ELTS_LFREE) ? RARRAY(ary)->ptr[-1] : 0; + RARRAY(ary)->ptr -= lfree; + REALLOC_N(RARRAY(ary)->ptr, VALUE, i2 * 2 + lfree); + RARRAY(ary)->ptr += lfree; + capa = i2 * 2; + } + if (capa>i2) { + RARRAY(ary)->ptr[i2] = capa-i2; + FL_SET(ary,ELTS_RFREE); + } else { + FL_UNSET(ary,ELTS_RFREE); + } } return item; @@ -1763,8 +1964,10 @@ VALUE rb_ary_delete_at(VALUE ary, long pos) { - long i, len = RARRAY(ary)->len; + long len = RARRAY(ary)->len; VALUE del; + long rfree; + VALUE *ptr; if (pos >= len) return Qnil; if (pos < 0) { @@ -1773,11 +1976,27 @@ } rb_ary_modify(ary); - del = RARRAY(ary)->ptr[pos]; - for (i = pos + 1; i < len; i++, pos++) { - RARRAY(ary)->ptr[pos] = RARRAY(ary)->ptr[i]; + ptr = RARRAY(ary)->ptr; + del = ptr[pos]; + if (pos>=len/2) { + VALUE *eptr = ptr+len; + long rfree = FL_TEST(ary,ELTS_RFREE) ? *eptr : 0; + --len; + --eptr; + ptr += pos; + MEMMOVE(ptr, ptr+1, VALUE, len-pos); + RARRAY(ary)->len = len; + *eptr = rfree+1; + FL_SET(ary,ELTS_RFREE); + } else { + long lfree = FL_TEST(ary,ELTS_LFREE) ? ptr[-1] : 0; + --len; + MEMMOVE(ptr+1, ptr, VALUE, pos); + *ptr = lfree+1; + RARRAY(ary)->len = len; + RARRAY(ary)->ptr = ptr+1; + FL_SET(ary,ELTS_LFREE); } - RARRAY(ary)->len = pos; return del; } @@ -1866,9 +2085,11 @@ rb_ary_reject_bang(VALUE ary) { long i1, i2; + long rfree; RETURN_ENUMERATOR(ary, 0, 0); rb_ary_modify(ary); + rfree = FL_TEST(ary,ELTS_RFREE) ? RARRAY(ary)->ptr[RARRAY(ary)->len] : 0; for (i1 = i2 = 0; i1 < RARRAY(ary)->len; i1++) { VALUE v = RARRAY(ary)->ptr[i1]; if (RTEST(rb_yield(v))) continue; @@ -1878,8 +2099,12 @@ i2++; } if (RARRAY(ary)->len == i2) return Qnil; - if (i2 < RARRAY(ary)->len) + if (i2 < RARRAY(ary)->len) { + rfree += RARRAY(ary)->len-i2; + RARRAY(ary)->ptr[i2] = rfree; + FL_SET(ary,ELTS_RFREE); RARRAY(ary)->len = i2; + } return ary; } @@ -2031,18 +2256,11 @@ static VALUE rb_ary_replace(VALUE copy, VALUE orig) { - VALUE shared; - rb_ary_modify(copy); orig = to_ary(orig); if (copy == orig) return copy; - shared = ary_make_shared(orig); - if (RARRAY(copy)->ptr && !FL_TEST(copy, ELTS_SHARED)) - free(RARRAY(copy)->ptr); - RARRAY(copy)->ptr = RARRAY(orig)->ptr; - RARRAY(copy)->len = RARRAY(orig)->len; - RARRAY(copy)->aux.shared = shared; - FL_SET(copy, ELTS_SHARED); + ary_free(copy); + ary_share(copy,orig); return copy; } @@ -2060,12 +2278,19 @@ VALUE rb_ary_clear(VALUE ary) { + long capa; rb_ary_modify(ary); + capa = RARRAY(ary)->len+(FL_TEST(ary,ELTS_RFREE) ? RARRAY(ary)->ptr[RARRAY(ary)->len] : 0); RARRAY(ary)->len = 0; - if (ARY_DEFAULT_SIZE * 2 < RARRAY(ary)->aux.capa) { - REALLOC_N(RARRAY(ary)->ptr, VALUE, ARY_DEFAULT_SIZE * 2); - RARRAY(ary)->aux.capa = ARY_DEFAULT_SIZE * 2; + if (ARY_DEFAULT_SIZE * 2 < capa) { + long lfree = FL_TEST(ary,ELTS_LFREE) ? RARRAY(ary)->ptr[-1] : 0; + RARRAY(ary)->ptr -= lfree; + REALLOC_N(RARRAY(ary)->ptr, VALUE, ARY_DEFAULT_SIZE * 2 + lfree); + RARRAY(ary)->ptr += lfree; + capa = ARY_DEFAULT_SIZE * 2; } + RARRAY(ary)->ptr[0] = capa; + FL_SET(ary,ELTS_RFREE); return ary; } @@ -2131,13 +2356,23 @@ rb_ary_modify(ary); end = beg + len; if (end > RARRAY(ary)->len) { - if (end >= RARRAY(ary)->aux.capa) { - REALLOC_N(RARRAY(ary)->ptr, VALUE, end); - RARRAY(ary)->aux.capa = end; + long capa = RARRAY(ary)->len+(FL_TEST(ary,ELTS_RFREE) ? RARRAY(ary)->ptr[RARRAY(ary)->len] : 0); + if (end >= capa) { + long lfree = FL_TEST(ary,ELTS_LFREE) ? RARRAY(ary)->ptr[-1] : 0; + RARRAY(ary)->ptr -= lfree; + REALLOC_N(RARRAY(ary)->ptr, VALUE, end + lfree); + RARRAY(ary)->ptr += lfree; + capa = end; } if (beg > RARRAY(ary)->len) { rb_mem_clear(RARRAY(ary)->ptr + RARRAY(ary)->len, end - RARRAY(ary)->len); } + if (capa > end) { + RARRAY(ary)->ptr[end] = capa-end; + FL_SET(ary,ELTS_RFREE); + } else { + FL_UNSET(ary,ELTS_RFREE); + } RARRAY(ary)->len = end; } @@ -2611,6 +2846,7 @@ { VALUE hash, v, vv; long i, j; + long capa; hash = ary_make_hash(ary, 0); @@ -2623,7 +2859,14 @@ rb_ary_store(ary, j++, v); } } + capa = RARRAY(ary)->len+(FL_TEST(ary,ELTS_RFREE) ? RARRAY(ary)->ptr[RARRAY(ary)->len] : 0); RARRAY(ary)->len = j; + if (capa > j) { + RARRAY(ary)->ptr[j] = capa-j; + FL_SET(ary,ELTS_RFREE); + } else { + FL_UNSET(ary,ELTS_RFREE); + } return ary; } @@ -2661,6 +2904,7 @@ rb_ary_compact_bang(VALUE ary) { VALUE *p, *t, *end; + long lfree; rb_ary_modify(ary); p = t = RARRAY(ary)->ptr; @@ -2673,8 +2917,12 @@ if (RARRAY(ary)->len == (p - RARRAY(ary)->ptr)) { return Qnil; } - RARRAY(ary)->len = RARRAY(ary)->aux.capa = (p - RARRAY(ary)->ptr); - REALLOC_N(RARRAY(ary)->ptr, VALUE, RARRAY(ary)->len); + RARRAY(ary)->len = (p - RARRAY(ary)->ptr); + lfree = FL_TEST(ary,ELTS_LFREE) ? RARRAY(ary)->ptr[-1] : 0; + RARRAY(ary)->ptr -= lfree; + REALLOC_N(RARRAY(ary)->ptr, VALUE, RARRAY(ary)->len + lfree); + RARRAY(ary)->ptr += lfree; + FL_UNSET(ary,ELTS_RFREE); return ary; } Index: gc.c =================================================================== RCS file: /src/ruby/gc.c,v retrieving revision 1.209 diff -u -r1.209 gc.c --- gc.c 14 Sep 2005 08:30:15 -0000 1.209 +++ gc.c 21 Sep 2005 16:13:05 -0000 @@ -711,7 +711,7 @@ obj->as.basic.flags |= FL_MARK; marking: - if (FL_TEST(obj, FL_EXIVAR)) { + if (FL_TEST(obj, FL_EXIVAR)) { rb_mark_generic_ivar(ptr); } @@ -869,11 +869,7 @@ goto again; case T_ARRAY: - if (FL_TEST(obj, ELTS_SHARED)) { - ptr = obj->as.array.aux.shared; - goto again; - } - else { + { long i, len = obj->as.array.len; VALUE *ptr = obj->as.array.ptr; @@ -1110,9 +1106,7 @@ } break; case T_ARRAY: - if (RANY(obj)->as.array.ptr && !FL_TEST(obj, ELTS_SHARED)) { - RUBY_CRITICAL(free(RANY(obj)->as.array.ptr)); - } + ary_free(obj); break; case T_HASH: if (RANY(obj)->as.hash.tbl) { Index: ruby.h =================================================================== RCS file: /src/ruby/ruby.h,v retrieving revision 1.122 diff -u -r1.122 ruby.h --- ruby.h 14 Sep 2005 13:40:43 -0000 1.122 +++ ruby.h 21 Sep 2005 16:13:05 -0000 @@ -346,7 +346,10 @@ double value; }; +// SHARED implies not (LFREE or RFREE) #define ELTS_SHARED FL_USER2 +#define ELTS_LFREE FL_USER3 +#define ELTS_RFREE FL_USER4 struct RString { struct RBasic basic; @@ -361,10 +364,7 @@ struct RArray { struct RBasic basic; long len; - union { - long capa; VALUE shared; - } aux; VALUE *ptr; }; --0-698884423-1127321776=:45213 Content-Type: application/octet-stream; name="end_test.rb" Content-Transfer-Encoding: base64 Content-Description: 1685833283-end_test.rb Content-Disposition: attachment; filename="end_test.rb" CnJlcXVpcmUgJ2JlbmNobWFyaycKCiNpbml0IGZpbmFsIGNvZGUgZWxlbWVu dC1hc3NlcnRpb24KCnRlc3RzID0gJXd7CgoxICAgMSAgIDsgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgaQogICAgICAgIAoxLjUgMC41IHNoaWZ0 ICAgICAgICAgICAgICAgICAgICAgICAgICAgaStuCjEuNSAwLjUgc2hpZnQo MSkgICAgICAgICAgICAgICAgICAgICAgICBpK24KMS41IDAuNSBwb3AgICAg ICAgICAgICAgICAgICAgICAgICAgICAgIGkKMS41IDAuNSBwb3AoMSkgICAg ICAgICAgICAgICAgICAgICAgICAgIGkKMiAgIDAgICBzaGlmdDtwb3AgICAg ICAgICAgICAgICAgICAgICAgIG5pbAoyICAgMCAgIHNoaWZ0KDEpO3BvcCgx KSAgICAgICAgICAgICAgICAgbmlsCiAgICAgICAgCjAuNSAxLjUgdW5zaGlm dChpKSAgICAgICAgICAgICAgICAgICAgICAoaT49bikmJihpLW4pfHwobi0x LWkpCjAuNSAxLjUgcHVzaChpKSAgICAgICAgICAgICAgICAgICAgICAgICAo aT49bi8yKSYmKGktbi8yKXx8aQowICAgMiAgIHVuc2hpZnQoaSk7cHVzaChp KSAgICAgICAgICAgICAgKGk+PW4pJiYoaS1uKXx8KG4tMS1pKQogICAgICAg IAoxICAgMSAgIHVuc2hpZnQoc2hpZnQpICAgICAgICAgICAgICAgICAgaQox ICAgMSAgIHVuc2hpZnQoKnNoaWZ0KDEpKSAgICAgICAgICAgICAgaQoxICAg MSAgIHB1c2gocG9wKSAgICAgICAgICAgICAgICAgICAgICAgaQoxICAgMSAg IHB1c2goKnBvcCgxKSkgICAgICAgICAgICAgICAgICAgaQoxICAgMSAgIHB1 c2goc2hpZnQpICAgICAgICAgICAgICAgICAgICAgaQoxICAgMSAgIHB1c2go KnNoaWZ0KDEpKSAgICAgICAgICAgICAgICAgaQoxICAgMSAgIHVuc2hpZnQo cG9wKSAgICAgICAgICAgICAgICAgICAgaQoxICAgMSAgIHVuc2hpZnQoKnBv cCgxKSkgICAgICAgICAgICAgICAgaQogICAgICAgIAoxLjUgMC41IHNsaWNl ISgxKSAgICAgICAgICAgICAgICAgICAgICAgKGk8MSkmJml8fChpK24pCjEu NSAwLjUgZGVsZXRlX2F0KDEpICAgICAgICAgICAgICAgICAgICAoaTwxKSYm aXx8KGkrbikKMS41IDAuNSBzbGljZSEoMSwxKSAgICAgICAgICAgICAgICAg ICAgIChpPDEpJiZpfHwoaStuKQoxLjUgMC41IHNlbGZbMSwxXT1bXSAgICAg ICAgICAgICAgICAgICAgKGk8MSkmJml8fChpK24pCjEuNSAwLjUgc2xpY2Uh KC0yKSAgICAgICAgICAgICAgICAgICAgICAoaT5uLzItMikmJihpK24pfHxp CjEuNSAwLjUgZGVsZXRlX2F0KC0yKSAgICAgICAgICAgICAgICAgICAoaT5u LzItMikmJihpK24pfHxpCjEuNSAwLjUgc2xpY2UhKC0yLDEpICAgICAgICAg ICAgICAgICAgICAoaT5uLzItMikmJihpK24pfHxpCjEuNSAwLjUgc2VsZlst MiwxXT1bXSAgICAgICAgICAgICAgICAgICAoaT5uLzItMikmJihpK24pfHxp CiAgICAgICAgCjAuNSAxLjUgc2VsZlsxLDBdPVtpXSAgICAgICAgICAgICAg ICAgICBqPW4taTsoajwwKSYmKGktbil8fChqPj1uKSYmaXx8agowLjUgMS41 IGluc2VydCgxLGkpICAgICAgICAgICAgICAgICAgICAgaj1uLWk7KGo8MCkm JihpLW4pfHwoaj49bikmJml8fGoKMC41IDEuNSBzZWxmWy0xLDBdPVtpXSAg ICAgICAgICAgICAgICAgIGo9aS1uLzIrMTsoajwwKSYmaXx8KGo+PW4pJiYo aS1uKXx8agowLjUgMS41IGluc2VydCgtMixpKSAgICAgICAgICAgICAgICAg ICAgaj1pLW4vMisxOyhqPDApJiZpfHwoaj49bikmJihpLW4pfHxqCgoxICAg MSAgIHNlbGZbMSwwXT1zbGljZSEoMSwxKSAgICAgICAgICAgaQoxICAgMSAg IGluc2VydCgxLGRlbGV0ZV9hdCgxKSkgICAgICAgICAgaQoxICAgMSAgIHNl bGZbLTEsMF09c2xpY2UhKC0yLDEpICAgICAgICAgaQoxICAgMSAgIGluc2Vy dCgtMixkZWxldGVfYXQoLTIpKSAgICAgICAgaQoKMSAgIDEgICBzZWxmWy0x LDBdPXNsaWNlISgxLDEpICAgICAgICAgICgoaTwxKXx8KGk+PW4tMSkpJiZp fHwoKGkrMSklKG4tMikrMSkKMSAgIDEgICBpbnNlcnQoLTIsZGVsZXRlX2F0 KDEpKSAgICAgICAgICgoaTwxKXx8KGk+PW4tMSkpJiZpfHwoKGkrMSklKG4t MikrMSkKMSAgIDEgICBzZWxmWzEsMF09c2xpY2UhKC0yLDEpICAgICAgICAg ICgoaTwxKXx8KGk+PW4tMSkpJiZpfHwoKGktMyklKG4tMikrMSkKMSAgIDEg ICBpbnNlcnQoMSxkZWxldGVfYXQoLTIpKSAgICAgICAgICgoaTwxKXx8KGk+ PW4tMSkpJiZpfHwoKGktMyklKG4tMikrMSkKCjEgICAxICAgc2VsZltpXT1z ZWxmW2ldICAgICAgICAgICAgICAgICBpCjEgICAxICAgc2VsZltpXT1hdChp KSAgICAgICAgICAgICAgICAgICBpCjEgICAxICAgc2VsZltpLDFdPXNlbGZb aSwxXSAgICAgICAgICAgICBpCjEgICAxICAgc2VsZlstaS0xXT1zZWxmWy1p LTFdICAgICAgICAgICBpCjEgICAxICAgc2VsZlstaS0xXT1hdCgtaS0xKSAg ICAgICAgICAgICBpCjEgICAxICAgc2VsZlstaS0xLDFdPXNlbGZbLWktMSwx XSAgICAgICBpCjEgICAxICAgc2VsZlstaS0xXT1zZWxmW2ldICAgICAgICAg ICAgICAoaT49bi8yKSYmKG4tMS1pKXx8aQoxICAgMSAgIHNlbGZbLWktMV09 YXQoaSkgICAgICAgICAgICAgICAgKGk+PW4vMikmJihuLTEtaSl8fGkKMSAg IDEgICBzZWxmWy1pLTEsMV09c2VsZltpLDFdICAgICAgICAgIChpPj1uLzIp JiYobi0xLWkpfHxpCjEgICAxICAgc2VsZltpXT1zZWxmWy1pLTFdICAgICAg ICAgICAgICAoaT49bi8yKSYmaXx8KG4tMS1pKQoxICAgMSAgIHNlbGZbaV09 YXQoLWktMSkgICAgICAgICAgICAgICAgKGk+PW4vMikmJml8fChuLTEtaSkK MSAgIDEgICBzZWxmW2ksMV09c2VsZlstaS0xLDFdICAgICAgICAgIChpPj1u LzIpJiZpfHwobi0xLWkpCgp9CgpGaWVsZHMgPSA0CgpBUkdWLnJlcGxhY2Uo WzEyXSkgaWYgQVJHVi5lbXB0eT8KCkFSR1YuZWFjaCB7IHxleHB8CiAgICBu ID0gMSA8PCBleHAudG9faQogICAgcHV0cwogICAgcHV0cygibiA9ICN7bn0i KQogICAgYW4gPSAoMC4uLihuIDw8IDEpKS50b19hCiAgICAKICAgIHJlc3Vs dHMgPSBIYXNoLm5ldzsKICAgIEJlbmNobWFyay5ibWJtIHsgfGJlbmNobWFy a3wKICAgICAgICBlbnRyeSA9IDAgICAKICAgICAgICB3aGlsZSBlbnRyeTx0 ZXN0cy5zaXplCiAgICAgICAgICAgIGluaXQsZmluYWwsY29kZSxhc3NlcnQg PSB0ZXN0c1tlbnRyeSxGaWVsZHNdCiAgICAgICAgICAgICNwdXRzKGNvZGUp CiAgICAgICAgICAgIGluaXQgPSBpbml0LnRvX2YKICAgICAgICAgICAgZmlu YWwgPSBmaW5hbC50b19mCiAgICAgICAgICAgIGluaXQrZmluYWw9PTIgb3Ig cmFpc2UoaW5pdC50b19zKyIrIitmaW5hbC50b19zKyIhPTIiKTsKICAgICAg ICAgICAgcmVzdWx0c1tlbnRyeS9GaWVsZHNdID0gZmluYWw9PTAgPyBbXSA6 CiAgICAgICAgICAgICAgICBldmFsKCJBcnJheS5uZXcoI3sobipmaW5hbCku dG9faX0pIHt8aXwKICAgICAgICAgICAgICAgICAgICAje2Fzc2VydH0KICAg ICAgICAgICAgICAgIH0iKQogICAgICAgICAgICBiZW5jaG1hcmsucmVwb3J0 KGNvZGUsJmV2YWwoImxhbWJkYSB7CiAgICAgICAgICAgICAgICBhID0gYW5b MCwjeyhuKmluaXQpLnRvX2l9XQogICAgICAgICAgICAgICAgYS5pbnN0YW5j ZV9ldmFsIHsje259LnRpbWVzeyB8aXwKICAgICAgICAgICAgICAgICAgICAj e2NvZGV9CiAgICAgICAgICAgICAgICB9fQogICAgICAgICAgICAgICAgcmVz dWx0ID0gcmVzdWx0c1sje2VudHJ5L0ZpZWxkc31dCiAgICAgICAgICAgICAg ICBhPT1yZXN1bHQgb3IgcmFpc2UoYS5pbnNwZWN0KychPScrcmVzdWx0Lmlu c3BlY3QpCiAgICAgICAgICAgIH0iKSkKICAgICAgICAgICAgZW50cnkgKz0g RmllbGRzCiAgICAgICAgZW5kCiAgICB9Cn0KCgo= --0-698884423-1127321776=:45213--