Array shift bug

[Bob Hutchison]

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?p=361>

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

Cheers,
Bob

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

 

[Devin Mullins]

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]

Hi,

At Sun, 24 Sep 2006 11:52:27 +0900,
Devin Mullins wrote in [ruby-talk:216068]:

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);

 

[Nobuyoshi Nakada]

Hi,

At Sun, 24 Sep 2006 16:54:53 +0900,
Nobuyoshi Nakada wrote in [ruby-talk:216087]:

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);

 

[Devin Mullins]

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]

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?

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-core/5861

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).

 

[Hal Fulton]

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 Fulton]

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]

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?

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-core/5861

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 Fulton]

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