From: Eric Mahurin Date: 2006-09-25T01:09:10+09:00 Subject: Re: Array shift bug ------=_Part_8280_3446189.1159114147674 Content-Type: multipart/alternative; boundary="----=_Part_8281_5164411.1159114147674" ------=_Part_8281_5164411.1159114147674 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline On 9/24/06, Nobuyoshi Nakada 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? > > > 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 ------=_Part_8281_5164411.1159114147674 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline 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?


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



------=_Part_8281_5164411.1159114147674-- ------=_Part_8280_3446189.1159114147674 Content-Type: application/octet-stream; name=end_test.rb Content-Transfer-Encoding: base64 X-Attachment-Id: f_eshlwxz1 Content-Disposition: attachment; filename="end_test.rb" CnJlcXVpcmUgJ2JlbmNobWFyaycKCiNpbml0IGZpbmFsIGNvZGUgZWxlbWVudC1hc3NlcnRpb24K CnRlc3RzID0gJXd7CgoxICAgMSAgIDsgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaQog ICAgICAgIAoxLjUgMC41IHNoaWZ0ICAgICAgICAgICAgICAgICAgICAgICAgICAgaStuCjEuNSAw LjUgc2hpZnQoMSkgICAgICAgICAgICAgICAgICAgICAgICBpK24KMS41IDAuNSBwb3AgICAgICAg ICAgICAgICAgICAgICAgICAgICAgIGkKMS41IDAuNSBwb3AoMSkgICAgICAgICAgICAgICAgICAg ICAgICAgIGkKMiAgIDAgICBzaGlmdDtwb3AgICAgICAgICAgICAgICAgICAgICAgIG5pbAoyICAg MCAgIHNoaWZ0KDEpO3BvcCgxKSAgICAgICAgICAgICAgICAgbmlsCiAgICAgICAgCjAuNSAxLjUg dW5zaGlmdChpKSAgICAgICAgICAgICAgICAgICAgICAoaT49bikmJihpLW4pfHwobi0xLWkpCjAu NSAxLjUgcHVzaChpKSAgICAgICAgICAgICAgICAgICAgICAgICAoaT49bi8yKSYmKGktbi8yKXx8 aQowICAgMiAgIHVuc2hpZnQoaSk7cHVzaChpKSAgICAgICAgICAgICAgKGk+PW4pJiYoaS1uKXx8 KG4tMS1pKQogICAgICAgIAoxICAgMSAgIHVuc2hpZnQoc2hpZnQpICAgICAgICAgICAgICAgICAg aQoxICAgMSAgIHVuc2hpZnQoKnNoaWZ0KDEpKSAgICAgICAgICAgICAgaQoxICAgMSAgIHB1c2go cG9wKSAgICAgICAgICAgICAgICAgICAgICAgaQoxICAgMSAgIHB1c2goKnBvcCgxKSkgICAgICAg ICAgICAgICAgICAgaQoxICAgMSAgIHB1c2goc2hpZnQpICAgICAgICAgICAgICAgICAgICAgaQox ICAgMSAgIHB1c2goKnNoaWZ0KDEpKSAgICAgICAgICAgICAgICAgaQoxICAgMSAgIHVuc2hpZnQo cG9wKSAgICAgICAgICAgICAgICAgICAgaQoxICAgMSAgIHVuc2hpZnQoKnBvcCgxKSkgICAgICAg ICAgICAgICAgaQogICAgICAgIAoxLjUgMC41IHNsaWNlISgxKSAgICAgICAgICAgICAgICAgICAg ICAgKGk8MSkmJml8fChpK24pCjEuNSAwLjUgZGVsZXRlX2F0KDEpICAgICAgICAgICAgICAgICAg ICAoaTwxKSYmaXx8KGkrbikKMS41IDAuNSBzbGljZSEoMSwxKSAgICAgICAgICAgICAgICAgICAg IChpPDEpJiZpfHwoaStuKQoxLjUgMC41IHNlbGZbMSwxXT1bXSAgICAgICAgICAgICAgICAgICAg KGk8MSkmJml8fChpK24pCjEuNSAwLjUgc2xpY2UhKC0yKSAgICAgICAgICAgICAgICAgICAgICAo aT5uLzItMikmJihpK24pfHxpCjEuNSAwLjUgZGVsZXRlX2F0KC0yKSAgICAgICAgICAgICAgICAg ICAoaT5uLzItMikmJihpK24pfHxpCjEuNSAwLjUgc2xpY2UhKC0yLDEpICAgICAgICAgICAgICAg ICAgICAoaT5uLzItMikmJihpK24pfHxpCjEuNSAwLjUgc2VsZlstMiwxXT1bXSAgICAgICAgICAg ICAgICAgICAoaT5uLzItMikmJihpK24pfHxpCiAgICAgICAgCjAuNSAxLjUgc2VsZlsxLDBdPVtp XSAgICAgICAgICAgICAgICAgICBqPW4taTsoajwwKSYmKGktbil8fChqPj1uKSYmaXx8agowLjUg MS41IGluc2VydCgxLGkpICAgICAgICAgICAgICAgICAgICAgaj1uLWk7KGo8MCkmJihpLW4pfHwo aj49bikmJml8fGoKMC41IDEuNSBzZWxmWy0xLDBdPVtpXSAgICAgICAgICAgICAgICAgIGo9aS1u LzIrMTsoajwwKSYmaXx8KGo+PW4pJiYoaS1uKXx8agowLjUgMS41IGluc2VydCgtMixpKSAgICAg ICAgICAgICAgICAgICAgaj1pLW4vMisxOyhqPDApJiZpfHwoaj49bikmJihpLW4pfHxqCgoxICAg MSAgIHNlbGZbMSwwXT1zbGljZSEoMSwxKSAgICAgICAgICAgaQoxICAgMSAgIGluc2VydCgxLGRl bGV0ZV9hdCgxKSkgICAgICAgICAgaQoxICAgMSAgIHNlbGZbLTEsMF09c2xpY2UhKC0yLDEpICAg ICAgICAgaQoxICAgMSAgIGluc2VydCgtMixkZWxldGVfYXQoLTIpKSAgICAgICAgaQoKMSAgIDEg ICBzZWxmWy0xLDBdPXNsaWNlISgxLDEpICAgICAgICAgICgoaTwxKXx8KGk+PW4tMSkpJiZpfHwo KGkrMSklKG4tMikrMSkKMSAgIDEgICBpbnNlcnQoLTIsZGVsZXRlX2F0KDEpKSAgICAgICAgICgo aTwxKXx8KGk+PW4tMSkpJiZpfHwoKGkrMSklKG4tMikrMSkKMSAgIDEgICBzZWxmWzEsMF09c2xp Y2UhKC0yLDEpICAgICAgICAgICgoaTwxKXx8KGk+PW4tMSkpJiZpfHwoKGktMyklKG4tMikrMSkK MSAgIDEgICBpbnNlcnQoMSxkZWxldGVfYXQoLTIpKSAgICAgICAgICgoaTwxKXx8KGk+PW4tMSkp JiZpfHwoKGktMyklKG4tMikrMSkKCjEgICAxICAgc2VsZltpXT1zZWxmW2ldICAgICAgICAgICAg ICAgICBpCjEgICAxICAgc2VsZltpXT1hdChpKSAgICAgICAgICAgICAgICAgICBpCjEgICAxICAg c2VsZltpLDFdPXNlbGZbaSwxXSAgICAgICAgICAgICBpCjEgICAxICAgc2VsZlstaS0xXT1zZWxm Wy1pLTFdICAgICAgICAgICBpCjEgICAxICAgc2VsZlstaS0xXT1hdCgtaS0xKSAgICAgICAgICAg ICBpCjEgICAxICAgc2VsZlstaS0xLDFdPXNlbGZbLWktMSwxXSAgICAgICBpCjEgICAxICAgc2Vs ZlstaS0xXT1zZWxmW2ldICAgICAgICAgICAgICAoaT49bi8yKSYmKG4tMS1pKXx8aQoxICAgMSAg IHNlbGZbLWktMV09YXQoaSkgICAgICAgICAgICAgICAgKGk+PW4vMikmJihuLTEtaSl8fGkKMSAg IDEgICBzZWxmWy1pLTEsMV09c2VsZltpLDFdICAgICAgICAgIChpPj1uLzIpJiYobi0xLWkpfHxp CjEgICAxICAgc2VsZltpXT1zZWxmWy1pLTFdICAgICAgICAgICAgICAoaT49bi8yKSYmaXx8KG4t MS1pKQoxICAgMSAgIHNlbGZbaV09YXQoLWktMSkgICAgICAgICAgICAgICAgKGk+PW4vMikmJml8 fChuLTEtaSkKMSAgIDEgICBzZWxmW2ksMV09c2VsZlstaS0xLDFdICAgICAgICAgIChpPj1uLzIp JiZpfHwobi0xLWkpCgp9CgpGaWVsZHMgPSA0CgpBUkdWLnJlcGxhY2UoWzEyXSkgaWYgQVJHVi5l bXB0eT8KCkFSR1YuZWFjaCB7IHxleHB8CiAgICBuID0gMSA8PCBleHAudG9faQogICAgcHV0cwog ICAgcHV0cygibiA9ICN7bn0iKQogICAgYW4gPSAoMC4uLihuIDw8IDEpKS50b19hCiAgICAKICAg IHJlc3VsdHMgPSBIYXNoLm5ldzsKICAgIEJlbmNobWFyay5ibWJtIHsgfGJlbmNobWFya3wKICAg ICAgICBlbnRyeSA9IDAgICAKICAgICAgICB3aGlsZSBlbnRyeTx0ZXN0cy5zaXplCiAgICAgICAg ICAgIGluaXQsZmluYWwsY29kZSxhc3NlcnQgPSB0ZXN0c1tlbnRyeSxGaWVsZHNdCiAgICAgICAg ICAgICNwdXRzKGNvZGUpCiAgICAgICAgICAgIGluaXQgPSBpbml0LnRvX2YKICAgICAgICAgICAg ZmluYWwgPSBmaW5hbC50b19mCiAgICAgICAgICAgIGluaXQrZmluYWw9PTIgb3IgcmFpc2UoaW5p dC50b19zKyIrIitmaW5hbC50b19zKyIhPTIiKTsKICAgICAgICAgICAgcmVzdWx0c1tlbnRyeS9G aWVsZHNdID0gZmluYWw9PTAgPyBbXSA6CiAgICAgICAgICAgICAgICBldmFsKCJBcnJheS5uZXco I3sobipmaW5hbCkudG9faX0pIHt8aXwKICAgICAgICAgICAgICAgICAgICAje2Fzc2VydH0KICAg ICAgICAgICAgICAgIH0iKQogICAgICAgICAgICBiZW5jaG1hcmsucmVwb3J0KGNvZGUsJmV2YWwo ImxhbWJkYSB7CiAgICAgICAgICAgICAgICBhID0gYW5bMCwjeyhuKmluaXQpLnRvX2l9XQogICAg ICAgICAgICAgICAgYS5pbnN0YW5jZV9ldmFsIHsje259LnRpbWVzeyB8aXwKICAgICAgICAgICAg ICAgICAgICAje2NvZGV9CiAgICAgICAgICAgICAgICB9fQogICAgICAgICAgICAgICAgcmVzdWx0 ID0gcmVzdWx0c1sje2VudHJ5L0ZpZWxkc31dCiAgICAgICAgICAgICAgICBhPT1yZXN1bHQgb3Ig cmFpc2UoYS5pbnNwZWN0KychPScrcmVzdWx0Lmluc3BlY3QpCiAgICAgICAgICAgIH0iKSkKICAg ICAgICAgICAgZW50cnkgKz0gRmllbGRzCiAgICAgICAgZW5kCiAgICB9Cn0KCgo= ------=_Part_8280_3446189.1159114147674--