Asp Forum - Array shift bug

Bob Hutchison

9/24/2006 12:37:00 AM

A short article describing a problem in the implementation of array
shift in Ruby 1.8.4 with a simple one-line fix in the C code is here:

<http://recursive.ca/hutch/index.php...

This is the source of the problem Mongrel had experienced with the
Mutex.

Cheers,
Bob

----
Bob Hutchison -- blogs at <http://www.rec...
hutch/>
Recursive Design Inc. -- <http://www.rec...>
Raconteur -- <http://www.raconteur...
xampl for Ruby -- <http://rubyforge.org/projects/...

9 Answers

Devin Mullins

9/24/2006 2:52:00 AM

Bob Hutchison wrote:
> A short article describing a problem in the implementation of array
> shift in Ruby 1.8.4 with a simple one-line fix in the C code is here:
That's half a fix. If you're using shift and push to manage a queue, you
still have an ever-growing buffer.*

Devin
*I Might Be Wrong.

Nobuyoshi Nakada

9/24/2006 7:55:00 AM

Hi,

At Sun, 24 Sep 2006 11:52:27 +0900,
Devin Mullins wrote in [ruby-talk:216068]:
>
> Bob Hutchison wrote:
> > A short article describing a problem in the implementation of array
> > shift in Ruby 1.8.4 with a simple one-line fix in the C code is here:
> That's half a fix. If you're using shift and push to manage a queue, you
> still have an ever-growing buffer.*

Does this patch fix it?

Index: array.c
===================================================================
RCS file: /cvs/ruby/src/ruby/array.c,v
retrieving revision 1.195
diff -p -U 2 -r1.195 array.c
--- array.c 16 Sep 2006 02:24:58 -0000 1.195
+++ array.c 24 Sep 2006 07:53:48 -0000
@@ -43,4 +43,11 @@ memfill(register VALUE *mem, register lo
#define ARY_NOEMBED FL_USER3
#define ARY_SHARED_P(a) FL_TEST(a, ELTS_SHARED)
+#define ARY_SHARED_ARY(a) RARRAY(a)->as.heap.aux.shared
+#define ARY_SHARED_LIMIT(a) (+ (RARRAY(a)->as.heap.ptr - + RARRAY(ARY_SHARED_ARY(a))->as.heap.ptr > + ARY_DEFAULT_SIZE) && + (RARRAY(a)->as.heap.len < + RARRAY(ARY_SHARED_ARY(a))->as.heap.len / 2))

#define ARY_SET_NOEMBED(ary) do {@@ -229,5 +236,5 @@ ary_make_shared(VALUE ary)
if (ARY_EMBED_P(ary)) abort();
if (ARY_SHARED_P(ary)) {
- return RARRAY(ary)->as.heap.aux.shared;
+ return ARY_SHARED_ARY(ary);
}
else {
@@ -239,5 +246,5 @@ ary_make_shared(VALUE ary)
shared->as.heap.ptr = RARRAY(ary)->as.heap.ptr;
shared->as.heap.aux.capa = RARRAY(ary)->as.heap.aux.capa;
- RARRAY(ary)->as.heap.aux.shared = (VALUE)shared;
+ ARY_SHARED_ARY(ary) = (VALUE)shared;
FL_SET(ary, ELTS_SHARED);
OBJ_FREEZE(shared);
@@ -452,5 +459,5 @@ ary_shared_array(VALUE klass, VALUE ary)
RARRAY(val)->as.heap.ptr = RARRAY(ary)->as.heap.ptr;
RARRAY(val)->as.heap.len = RARRAY(ary)->as.heap.len;
- RARRAY(val)->as.heap.aux.shared = RARRAY(ary)->as.heap.aux.shared;
+ ARY_SHARED_ARY(val) = ARY_SHARED_ARY(ary);
FL_SET(val, ELTS_SHARED);
return val;
@@ -533,5 +540,5 @@ rb_ary_pop(VALUE ary)
rb_ary_modify_check(ary);
if (RARRAY_LEN(ary) == 0) return Qnil;
- if (!FL_TEST(ary, ELTS_SHARED) &&
+ if (!ARY_SHARED_P(ary, ELTS_SHARED) &&
RARRAY_LEN(ary) * 3 < ARY_CAPA(ary) &&
ARY_CAPA(ary) > ARY_DEFAULT_SIZE) {
@@ -587,4 +594,7 @@ rb_ary_shift(VALUE ary)
RARRAY(ary)->as.heap.ptr++; /* shift ptr */
RARRAY(ary)->as.heap.len--;
+ if (ARY_SHARED_LIMIT(ary)) {
+ rb_ary_modify(ary);
+ }
}

@@ -620,7 +630,4 @@ rb_ary_shift_m(int argc, VALUE *argv, VA

rb_ary_modify_check(ary);
- if (ARY_EMBED_P(ary)) {
-
- }

result = ary_shared_first(argc, argv, ary, Qfalse);
@@ -629,4 +636,7 @@ rb_ary_shift_m(int argc, VALUE *argv, VA
RARRAY(ary)->as.heap.ptr += n;
RARRAY(ary)->as.heap.len -= n;
+ if (ARY_SHARED_LIMIT(ary)) {
+ rb_ary_modify(ary);
+ }
}
else {
@@ -734,5 +744,5 @@ rb_ary_subseq(VALUE ary, long beg, long
RARRAY(ary2)->as.heap.ptr = ptr + beg;
RARRAY(ary2)->as.heap.len = len;
- RARRAY(ary2)->as.heap.aux.shared = shared;
+ ARY_SHARED_ARY(ary2) = shared;
FL_SET(ary2, ELTS_SHARED);
return ary2;
@@ -2093,5 +2103,5 @@ rb_ary_replace(VALUE copy, VALUE orig)
RARRAY(copy)->as.heap.ptr = RARRAY(shared)->as.heap.ptr;
RARRAY(copy)->as.heap.len = RARRAY(shared)->as.heap.len;
- RARRAY(copy)->as.heap.aux.shared = shared;
+ ARY_SHARED_ARY(copy) = shared;
FL_SET(copy, ELTS_SHARED);

--
Nobu Nakada

Nobuyoshi Nakada

9/24/2006 1:12:00 PM

Hi,

At Sun, 24 Sep 2006 16:54:53 +0900,
Nobuyoshi Nakada wrote in [ruby-talk:216087]:
> > > A short article describing a problem in the implementation of array
> > > shift in Ruby 1.8.4 with a simple one-line fix in the C code is here:
> > That's half a fix. If you're using shift and push to manage a queue, you
> > still have an ever-growing buffer.*
>
> Does this patch fix it?

It was for 1.9.

The patch for 1.8 is following.

Index: array.c
===================================================================
RCS file: /cvs/ruby/src/ruby/array.c,v
retrieving revision 1.137.2.33
diff -p -U 2 -r1.137.2.33 array.c
--- array.c 24 Jun 2006 14:53:36 -0000 1.137.2.33
+++ array.c 24 Sep 2006 13:09:32 -0000
@@ -44,4 +44,6 @@ memfill(mem, size, val)

#define ARY_TMPLOCK FL_USER1
+#define ARY_SHARED_P(a) FL_TEST(a, ELTS_SHARED)
+#define ARY_SHARED_ARY(a) RARRAY(a)->aux.shared

static inline void
@@ -57,12 +59,10 @@ rb_ary_modify_check(ary)

static void
-rb_ary_modify(ary)
+rb_ary_make_independent(ary)
VALUE ary;
{
- VALUE *ptr;
+ if (ARY_SHARED_P(ary)) {
+ VALUE *ptr = ALLOC_N(VALUE, RARRAY(ary)->len);

- rb_ary_modify_check(ary);
- if (FL_TEST(ary, ELTS_SHARED)) {
- ptr = ALLOC_N(VALUE, RARRAY(ary)->len);
FL_UNSET(ary, ELTS_SHARED);
RARRAY(ary)->aux.capa = RARRAY(ary)->len;
@@ -72,4 +72,25 @@ rb_ary_modify(ary)
}

+static void
+rb_ary_modify(ary)
+ VALUE ary;
+{
+ rb_ary_modify_check(ary);
+ rb_ary_make_independent(ary);
+}
+
+static void
+rb_ary_limit_shared(ary)
+ VALUE ary;
+{
+ VALUE shared;
+
+ if (!ARY_SHARED_P(ary)) return;
+ shared = ARY_SHARED_ARY(ary);
+ if (RARRAY(ary)->ptr - RARRAY(shared)->ptr < ARY_DEFAULT_SIZE) return;
+ if (RARRAY(ary)->len > RARRAY(shared)->len / 2) return;
+ rb_ary_make_independent(ary);
+}
+
VALUE
rb_ary_freeze(ary)
@@ -450,5 +471,5 @@ rb_ary_pop(ary)
rb_ary_modify_check(ary);
if (RARRAY(ary)->len == 0) return Qnil;
- if (!FL_TEST(ary, ELTS_SHARED) &&
+ if (!ARY_SHARED_P(ary) &&
RARRAY(ary)->len * 2 < RARRAY(ary)->aux.capa &&
RARRAY(ary)->aux.capa > ARY_DEFAULT_SIZE) {
@@ -463,5 +484,5 @@ ary_make_shared(ary)
VALUE ary;
{
- if (!FL_TEST(ary, ELTS_SHARED)) {
+ if (!ARY_SHARED_P(ary)) {
NEWOBJ(shared, struct RArray);
OBJSETUP(shared, rb_cArray, T_ARRAY);
@@ -470,5 +491,5 @@ ary_make_shared(ary)
shared->ptr = RARRAY(ary)->ptr;
shared->aux.capa = RARRAY(ary)->aux.capa;
- RARRAY(ary)->aux.shared = (VALUE)shared;
+ ARY_SHARED_ARY(ary) = (VALUE)shared;
FL_SET(ary, ELTS_SHARED);
OBJ_FREEZE(shared);
@@ -476,5 +497,5 @@ ary_make_shared(ary)
}
else {
- return RARRAY(ary)->aux.shared;
+ return ARY_SHARED_ARY(ary);
}
}
@@ -505,4 +526,5 @@ rb_ary_shift(ary)
RARRAY(ary)->ptr++; /* shift ptr */
RARRAY(ary)->len--;
+ rb_ary_limit_shared(ary);

return top;
@@ -612,5 +634,5 @@ rb_ary_subseq(ary, beg, len)
RARRAY(ary2)->ptr = ptr + beg;
RARRAY(ary2)->len = len;
- RARRAY(ary2)->aux.shared = shared;
+ ARY_SHARED_ARY(ary2) = shared;
FL_SET(ary2, ELTS_SHARED);

@@ -2162,9 +2184,9 @@ rb_ary_replace(copy, orig)
if (copy == orig) return copy;
shared = ary_make_shared(orig);
- if (RARRAY(copy)->ptr && !FL_TEST(copy, ELTS_SHARED))
+ if (RARRAY(copy)->ptr && !ARY_SHARED_P(copy))
free(RARRAY(copy)->ptr);
RARRAY(copy)->ptr = RARRAY(orig)->ptr;
RARRAY(copy)->len = RARRAY(orig)->len;
- RARRAY(copy)->aux.shared = shared;
+ ARY_SHARED_ARY(copy) = shared;
FL_SET(copy, ELTS_SHARED);

--
Nobu Nakada

Devin Mullins

9/24/2006 6:12:00 PM

Nobuyoshi Nakada wrote:
>>That's half a fix. If you're using shift and push to manage a queue, you
>>still have an ever-growing buffer.*
> Does this patch fix it?
Nobu, your Ruby-fu surpasses mine muchly. It'll take me a little while
to process this. In the meanwhile, go with your gut. :)

Devin

Zed A. Shaw

9/24/2006 8:06:00 PM

On Mon, 25 Sep 2006 01:09:10 +0900
"Eric Mahurin" <eric.mahurin@gmail.com> wrote:

> On 9/24/06, Nobuyoshi Nakada <nobu@ruby-lang.org> wrote:
> >
> > Hi,
> >
> > At Sun, 24 Sep 2006 11:52:27 +0900,
> > Devin Mullins wrote in [ruby-talk:216068]:
> > >
> > > Bob Hutchison wrote:
> > > > A short article describing a problem in the implementation of array
> > > > shift in Ruby 1.8.4 with a simple one-line fix in the C code is here:
> > > That's half a fix. If you're using shift and push to manage a queue, you
> > > still have an ever-growing buffer.*
> >
> > Does this patch fix it?
<snip>
>
> This was one of the issues I was addressing in a patch I made a year ago:
>
> http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby...
>
> In addition to this memory issue with element sharing, I also made
> performance for operating at either end of the array symmetrical (i.e.
> shift/unshift same performance as pop/push). From my testing of perl, it
> has this now.

A *year* ago? A whole year? You mean, I've been having this problem, people have denied it was a problem, they've insulted me, they've told me I'm full of it for a full on month, called me a liar, large production operations have been crashing over it, countless hours were wasted trying to fix it...

and someone posted a patch over a year ago to fix it that nobody bothered to apply?

Not only that but Eric improved the performance *and* had a test case that demonstrated the performance enhancement *and* Perl has these changes?

Please, someone tell me it slipped through the cracks or that Eric is wrong (doesn't look like it).

--
Zed A. Shaw, MUDCRAP-CE Master Black Belt Sifu
http://www.ze...
http://mongrel.ruby...
http://www.lingr.com/room/3... -- Come get help.

Hal E. Fulton

9/24/2006 8:27:00 PM

Zed A. Shaw wrote:
>
> A *year* ago? A whole year? You mean, I've been having this problem, people have denied it was a problem, they've insulted me, they've told me I'm full of it for a full on month, called me a liar, large production operations have been crashing over it, countless hours were wasted trying to fix it...
>
> and someone posted a patch over a year ago to fix it that nobody bothered to apply?
>
> Not only that but Eric improved the performance *and* had a test case that demonstrated the performance enhancement *and* Perl has these changes?
>
> Please, someone tell me it slipped through the cracks or that Eric is wrong (doesn't look like it).
>

I overlooked this whole thing. Do you mind summarizing what it's all
about?

FWIW, I've never denied the problem or called you a liar. I'm simply
unfamiliar with the problem.

Hal

Hal E. Fulton

9/24/2006 10:23:00 PM

Eric Mahurin wrote:
>
> Take a look at the thread I mentioned on ruby-core from a year ago. It
> gives a lot of details. If you want to see an extreme example of the
> problem, try this (sorry, linux only for memory measurements):
>
> n=2**14
> a=(0...n).to_a
> (n-1).times{ a[0,2] = [a[0,2]] }
> IO.readlines("/proc/#{Process.pid}/status").grep(/VmSize/).display
> puts(Process.times)
>
> In ruby 1.8.4, the above gives me this:
>
> VmSize: 528236 kB
> #<struct Struct::Tms utime=37.77, stime=1.38, cutime=0.0, cstime=0.0>
>
> On my patched ruby 1.9 from a year ago, it gives me this:
>
> VmSize: 3632 kB
> #<struct Struct::Tms utime=0.03, stime=0.0, cutime=0.0, cstime=0.0>
>
> If you try this with different values of n, you'll see O(n**2) memory and
> runtime, whereas my patch gives O(n) memory and runtime.
>
> The end_test.rb I posted gives a bunch of cases that should have O(n)
> memory
> and runtime IMHO, but don't always on ruby 1.8 and 1.9. You'll need to
> delete some tests for ruby 1.8, because they have some 1.9-only stuff.
>

That sounds like a performance issue, but this thread title
says 'bug.' Is there really a bug or not?

Hal

Daniel Berger

9/24/2006 10:37:00 PM

Zed A. Shaw wrote:
> On Mon, 25 Sep 2006 01:09:10 +0900
> "Eric Mahurin" <eric.mahurin@gmail.com> wrote:
>
> > On 9/24/06, Nobuyoshi Nakada <nobu@ruby-lang.org> wrote:
> > >
> > > Hi,
> > >
> > > At Sun, 24 Sep 2006 11:52:27 +0900,
> > > Devin Mullins wrote in [ruby-talk:216068]:
> > > >
> > > > Bob Hutchison wrote:
> > > > > A short article describing a problem in the implementation of array
> > > > > shift in Ruby 1.8.4 with a simple one-line fix in the C code is here:
> > > > That's half a fix. If you're using shift and push to manage a queue, you
> > > > still have an ever-growing buffer.*
> > >
> > > Does this patch fix it?
> <snip>
> >
> > This was one of the issues I was addressing in a patch I made a year ago:
> >
> > http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby...
> >
> > In addition to this memory issue with element sharing, I also made
> > performance for operating at either end of the array symmetrical (i.e.
> > shift/unshift same performance as pop/push). From my testing of perl, it
> > has this now.
>
> A *year* ago? A whole year? You mean, I've been having this problem, people have denied it was a problem, they've insulted me, they've told me I'm full of it for a full on month, called me a liar, large production operations have been crashing over it, countless hours were wasted trying to fix it...
>
> and someone posted a patch over a year ago to fix it that nobody bothered to apply?
>
> Not only that but Eric improved the performance *and* had a test case that demonstrated the performance enhancement *and* Perl has these changes?
>
> Please, someone tell me it slipped through the cracks or that Eric is wrong (doesn't look like it).

I could be wrong but I'm pretty sure the patch was against 1.9 only.
Although, it probably could have been backported.

ruby-core: 5861 and 5869

Regards,

Dan

PS - We love you Zed!

Hal E. Fulton

9/24/2006 11:29:00 PM

Jeremy Kemper wrote:
>
> Eric demonstrated a memory leak in code that shouldn't. Terminology-wise, I
> think that safely falls under the 'bug' rubric.
>
> His algorithmic improvements are cool & welcome but are only related to
> this
> bug inasmuch as they were introduced in the same patch.

I follow you now. I do agree a true memory leak is a bug.
I was trying to figure out how the algo changes were related
to the bug fix, but I guess as you say they are tangential.

Hal

comp.lang.ruby

Array shift bug

Bob Hutchison

Devin Mullins

Nobuyoshi Nakada

Nobuyoshi Nakada

Devin Mullins

Zed A. Shaw

Hal E. Fulton

Hal E. Fulton

Daniel Berger

Hal E. Fulton

x Login to ForumsZone