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 H. – 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/
Bob H. 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.
Hi,
At Sun, 24 Sep 2006 11:52:27 +0900,
Devin M. wrote in [ruby-talk:216068]:
Bob H. 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?
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) (\
#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)) {
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;
rb_ary_modify(ary);
On 9/24/06, Nobuyoshi N. [email protected] wrote:
still have an ever-growing buffer.*
Does this patch fix it?
Index: array.c
RCS file: /cvs/ruby/src/ruby/array.c,v
Nobu,
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.
Would you mind running the benchmark I have attached? It has cases with
run-time and memory performance issues (but this benchmark is only
measuring
run-time). You may need to delete some of the tests that use a count
with
shift/pop. The 1.9 a year ago that I was patching against could take a
count for shift and pop. I’m not sure if the current 1.9 still does or
not. This benchmark takes one argument - the binary power for the
number of
elements/iterations (15 : 2**15 elements/iterations).
Here were the improvements I had with my patch. Many went from O(n) to
O(1).
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
Nobuyoshi N. 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
Hi,
At Sun, 24 Sep 2006 16:54:53 +0900,
Nobuyoshi N. 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.
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;
{
+static void
+rb_ary_modify(ary)
+static void
+rb_ary_limit_shared(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;
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;
@@ -2162,9 +2184,9 @@ rb_ary_replace(copy, orig)
if (copy == orig) return copy;
shared = ary_make_shared(orig);
On Mon, 25 Sep 2006 01:09:10 +0900
“Eric M.” [email protected] 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?
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).
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
On 9/24/06, Zed A. Shaw [email protected] wrote:
> 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?
And than he discovered that life was not perfect, he still has not
recovered
compeletely yet.
So we hesitate to show him the rest 
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).
Open source is not perfect either, and after all you do have the
satisfaction that you were right, can you tell me how that feels BTW;)
Look at my nice little sig I’ll translate it for once, believe me this
sig
applies to myself it is not there to insult anybody.
–
Zed A. Shaw, MUDCRAP-CE Master Black Belt Sifu
http://www.zedshaw.com/
http://mongrel.rubyforge.org/
http://www.lingr.com/room/3yXhqKbfPy8 – Come get help.
Two things are infinite, universe and human stupidity, for what regards
the
universe I am not yet completely sure.
–
Deux choses sont infinies : l’univers et la bêtise humaine ; en ce qui
concerne l’univers, je n’en ai pas acquis la certitude absolue.
Eric M. wrote:
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
Zed A. Shaw wrote:
Bob H. wrote:
http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/5861
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!
On 9/24/06, Hal F. [email protected] wrote:
bothered to apply?
FWIW, I’ve never denied the problem or called you a liar. I’m simply
unfamiliar with the problem.
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
#
On my patched ruby 1.9 from a year ago, it gives me this:
VmSize: 3632 kB
#
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.
Jeremy K. 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
On 9/24/06, Hal F. [email protected] wrote:
That sounds like a performance issue, but this thread title
says ‘bug.’ Is there really a bug or not?
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.
jeremy
On 9/24/06, Jeremy K. [email protected] wrote:
His algorithmic improvements are cool & welcome but are only related to
this
bug inasmuch as they were introduced in the same patch.jeremy
Yep. I’d call something that takes O(n**2) memory to hold O(n) items a
memory leak, but some may argue. The problem is the copy-on-write
algorithm that is used currently. You can easily make it so that a
small
slice of a few elements can reference a large (O(n) size) array where
none
of the other elements are used anymore.
too many changes. As soon as I made datastructure changes, it required
a
lot of changes.
The same techniques could be applied to strings.
Hi,
In message “Re: Array shift bug”
on Mon, 25 Sep 2006 01:09:10 +0900, “Eric M.”
[email protected] writes:
|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
I have somehow missed to check your patch. Let me consider the pro
and cons of your modification.
matz.
On 9/24/06, Yukihiro M. [email protected] wrote:
I have somehow missed to check your patch. Let me consider the pro
and cons of your modification.matz.
Here is a quick summary of what I did:
used 2 unused flag bits for designating whether there is free space
before
and after the array data. Then, the first positions outside of the used
data will be a count of the excess capacity in that direction. I’m sure
there are other ways to do this, but this was the only way I could think
of
that wouldn’t use any more memory than is used now. And, it also freed
up
ary->shared for dedicated use (union with ary->capa not needed anymore).
used ary->shared to put master and slave (slice of master) arrays in a
circular linked list so that the master could access all slaves and any
slave could access the master (and other slaves). The master will have
ELTS_SHARED=0 and the slave will have ELTS_SHARED=1. Again, there may
be
better ways to do this, but this way gives the same memory footprint.
Before a slave is modified, its data is copied and sharing with its
master
data ceases. Before a master is modified (or freed), the data for all
of
its slaves are copied and the sharing ceases. In the current ruby (last
I
checked), the master data is copied before being modified instead. The
slave(s) continue sharing with the original data. I would consider that
implementation “leaky”, because the majority of that original data is
not
used anymore (just a slice of it).
made various functions that insert or delete (shift, unshift, insert,
delete_at, slice, etc) do so toward the closest side of the array.
Inserting or deleting on the first half of the array would use or add
capacity in the space before the array data. On the second half
capacity
after the array data would be modified. Also, when extra capacity is
needed
on either side, the array is reallocated with the new capacity on that
side
being relative to the current array size. This makes all insert delete
operations near either end of the array amoritized O(1) operations.
The primary cons I know for these changes are:
C extensions will need to be recompiled in the array structure
changed.
risk. These are significant changes. There may be hidden bugs.
I haven’t looked at this stuff in a while. I haven’t checked out ruby
1.9since about a year ago. If you are interested, I can try making a
patch for
the current ruby 1.9 or 1.8.5.
These same techniques (or something like them) could be applied to
String
also.
Hi,
In message “Re: Array shift bug”
on Mon, 25 Sep 2006 12:37:20 +0900, “Eric M.”
[email protected] writes:
|Here is a quick summary of what I did:
I just submitted a patch based on yours to the HEAD. Thank you!
It is fairly complex, so that I won’t submit it to the stable (1.8).
|These same techniques (or something like them) could be applied to String
|also.
Since strings have no shift nor unshift, I am not going to add it to
the strings, until it is really needed.
Thank you again. And I apologize that I left your patch ignored for a
full year.
matz.
On 9/26/06, Yukihiro M. [email protected] wrote:
full year.
matz.
Thanks matz,
I tried out the code and it looks better in a few spots, but it also got
worse in a few (but not as common). You can still use enormous amounts
of
memory because of the copy-on-write mechanism. I am attaching a
testbench
for testing runtime and memory (sorry, linux only) performance for a
bunch
of array operations that can be O(1). It also includes some new tests
at
the end (didn’t have these before) that show O(n**2) memory when it
should
be O(n). All of those performance (memory and runtime) issues were
fixed in
my patch.
Here are the results (for just 2^12=4096 iterations/elements):
code 2006-09-01 2006-09-26 eric’s-patch
sec kB sec kB sec kB
---- ---- ---- ---- ---- ----
; 0.01 132 0.00 0 0.01 136
shift 0.01 148 0.00 132 0.00 144
shift(1) 0.01 152 0.13- 136 0.01 152
pop 0.01 128 0.01 132 0.01 144
pop(1) 0.01 152 0.00 136 0.01 152
shift;pop 0.01 132 0.01 136 0.01 156
shift(1);pop(1) 0.01 136 0.14- 140 0.01 164
unshift(i) 0.13 132 0.01+ 140 0.00 132
push(i) 0.01 132 0.01 0 0.01 132
unshift(i);push(i) 0.14 0 0.00+ 200 0.01 208
unshift(shift) 0.59 4816 0.00+ 0 0.01 140
unshift(shift(1)) 0.60 4816 0.13 68 0.01 148
push(pop) 0.01 132 0.00 0 0.01 140
push(*pop(1)) 0.38 4816 0.00+ 8 0.01 148
push(shift) 0.45 4816 0.00+ 0 0.01 140
push(shift(1)) 0.45 4816 0.14 8 0.01 148
unshift(pop) 0.14 132 0.00+ 60 0.01 140
unshift(pop(1)) 0.51 4816 0.01+ 68 0.01 148
slice!(1) 0.13 148 0.56-- 132 0.00 144
delete_at(1) 0.14 148 0.55-- 132 0.00 144
slice!(1,1) 0.58 8124 0.58- 8264 0.01 152
self[1,1]=[] 0.14 552 0.13- 536 0.01 548
slice!(-2) 0.00 148 0.00 132 0.00 144
delete_at(-2) 0.00 148 0.00 132 0.00 144
slice!(-2,1) 0.45 8120 0.46- 8260 0.01 148
self[-2,1]=[] 0.01 544 0.01 528 0.00 544
self[1,0]=[i] 0.16 140 0.14- 4 0.00 304
insert(1,i) 0.16 136 0.14- 0 0.00 304
self[-1,0]=[i] 0.02 136 0.01 4 0.01 308
insert(-2,i) 0.02 132 0.01 0 0.01 308
self[1,0]=slice!(1,1) 0.76 4056 0.77- 3956 0.01 144
insert(1,delete_at(1)) 0.27 136 0.81-- 4 0.01 144
self[-1,0]=slice!(-2,1) 0.56 4056 0.58 3956 0.02 144
insert(-2,delete_at(-2)) 0.01 136 0.01 4 0.01 144
self[-1,0]=slice!(1,1) 0.73 4052 0.69- 3952 0.01 276
insert(-2,delete_at(1)) 0.13 132 0.63-- 0 0.01 276
self[1,0]=slice!(-2,1) 0.72 4052 0.74- 3952 0.01 212
insert(1,delete_at(-2)) 0.17 132 0.17- 0 0.01 212
self[i]=self[i] 0.00 136 0.00 4 0.01 140
self[i]=at(i) 0.00 136 0.01 4 0.00 140
self[i,1]=self[i,1] 0.50 3960 0.50- 3952 0.01 144
self[-i-1]=self[-i-1] 0.01 140 0.01 8 0.02 144
self[-i-1]=at(-i-1) 0.02 140 0.01 8 0.01 144
self[-i-1,1]=self[-i-1,1] 0.49 4056 0.50- 3956 0.01 144
self[-i-1]=self[i] 0.01 132 0.01 0 0.01 136
self[-i-1]=at(i) 0.01 132 0.01 0 0.01 136
self[-i-1,1]=self[i,1] 0.57 4044 0.59- 3948 0.01 140
self[i]=self[-i-1] 0.01 136 0.01 4 0.01 140
self[i]=at(-i-1) 0.01 136 0.01 4 0.01 140
self[i,1]=self[-i-1,1] 0.56 4048 0.59- 3952 0.02 140
push(shift(1)) 8.15 393900 0.24 4 0.02 312
unshift(pop(1)) 4.80 393920 0.01+ 60 0.02 308
insert(-1,slice!(0,1)) 6.05 262964 36.24- 262836 0.04 404
insert(0,slice!(-1,1)) 2.71 262980 73.98- 262852 0.03 304
self[i]=self[i,1] 9.84 262924 18.77- 262832 0.02 268
self[-i-1]=self[-i-1,1] 8.36 262976 39.82- 262820 0.03 272
self[-i-1]=self[i,1] 5.94 262840 38.00- 262816 0.03 132
self[i]=self[-i-1,1] 0.90 262824 19.97- 262800 0.03 136
Notice how bad the memory and runtime is for these last ones. And this
is
only for 4096 elements/iterations!
I think the rest of array.c should be overhauled just like I had to do
in my
original patch.
I still would like to see the same done for String sometime. The same
issues exist. You’ll find many deficiencies even without shift/unshift
(but
with the equivalent functionality). I’d like the extra performance to
build
a fast character FIFO with a String.
Eric
On 9/27/06, Yukihiro M. wrote:
I will examine your patch again. But I am afraid I was looking at the
old one. Could you show me your patch again?
Hi matz,
Would you check your email at matz at ruby dash lang dot org? I was not
able to post the patch here because of the size. Let me know if there
is a
better address to send this.
Thanks,
Eric
This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.
Sponsor our Newsletter | Privacy Policy | Terms of Service | Remote Ruby Jobs