pop/push, shift/unshift

R

Robert Dober

On 10/24/07 said:
Can someone explain -- with the code above -- why tmp does in fact
_not_ take on NilClass? I think it would be good info for newbies.
Click to expand...

In the above code, the shift method, through an involved but hidden
technique implemented by Ruby, arranges for the 0th element of the
list to 'disappear', for the original @list[1] to become @list[0] and
so on, for the array size to be reduced by one, and returns the
original @list[0].

So, tmp 'remembers' the original @list[0]. The '@list[0] = nil'
removes the reference to what is now in tmp,
Click to expand...
I believe that this is not true, imagine the GC freeing all objects
that are nil!
Seems very strange to me.

R.
 
R

Robert Dober

Sorry for replying to my own post, can somebody confirm please that
the following code proves that Array#shift does not leak?
Thx in advance
def count
i = 0
ObjectSpace.each_object{ i += 1 }
i
end

a = []
10.times do
10_000.times do
a << "a"
a.shift
end
ObjectSpace.garbage_collect
p count
end
381
382
382
382
382
382
382
382
382
382

Robert
 
D

David A. Black

Hi --

On 24-Oct-07, at 9:03 AM, Todd Benson wrote:

def dequeue
@list.shift
end

Save yourself some grief, do it this way:

def dequeue
tmp = @list[0]
@list[0] = nil
@list.shift
tmp
end

Cheers,
Bob
Click to expand...

Bob, I can only guess that the grief you are talking about has
something to do with memory management, but I don't see it.

Can someone explain -- with the code above -- why tmp does in fact
_not_ take on NilClass? I think it would be good info for newbies.

Todd
Click to expand...

Okay, I guess I can answer my own question. Binding is resolved when
an operator like '=' is interpreted, especially with immutable objects
(like Fixnum).

a = 1,2,3
puts a[0].__id__
#output => 3
b = a
puts b.__id__
#output => 3
a[0] = 7
puts a[0].__id__
#output => 15
puts b.__id__
#output => 3

For the newbies out there, keep this in mind. The name b put on
a[0]'s shoes and kept them on. Somebody correct me if I'm wrong.
Click to expand...

I'm not seeing what you're seeing:

irb(main):014:0> a = 1,2,3
=> [1, 2, 3]
irb(main):015:0> a[0].__id__
=> 3
irb(main):016:0> b = a
=> [1, 2, 3]
irb(main):017:0> b.__id__
=> 1669980 # Are you really seeing 3 here?
irb(main):018:0> a[0] = 7
=> 7
irb(main):019:0> a[0].__id__
=> 15
irb(main):020:0> b.__id__
=> 1669980 # And here?

When you do b = a, you're binding b to the same object as a. I don't
know why b would think you had bound it to a[0].


David

--
Upcoming training by David A. Black/Ruby Power and Light, LLC:
* Advancing With Rails, Edison, NJ, November 6-9
* Advancing With Rails, Berlin, Germany, November 19-22
* Intro to Rails, London, UK, December 3-6 (by Skills Matter)
See http://www.rubypal.com for details!
 
T

Todd Benson

Hi --

Okay, I guess I can answer my own question. Binding is resolved when
an operator like '=' is interpreted, especially with immutable objects
(like Fixnum).

a = 1,2,3
puts a[0].__id__
#output => 3
b = a
puts b.__id__
#output => 3
a[0] = 7
puts a[0].__id__
#output => 15
puts b.__id__
#output => 3

For the newbies out there, keep this in mind. The name b put on
a[0]'s shoes and kept them on. Somebody correct me if I'm wrong.
Click to expand...

I'm not seeing what you're seeing:

irb(main):014:0> a = 1,2,3
=> [1, 2, 3]
irb(main):015:0> a[0].__id__
=> 3
irb(main):016:0> b = a
=> [1, 2, 3]
irb(main):017:0> b.__id__
=> 1669980 # Are you really seeing 3 here?
irb(main):018:0> a[0] = 7
=> 7
irb(main):019:0> a[0].__id__
=> 15
irb(main):020:0> b.__id__
=> 1669980 # And here?

When you do b = a, you're binding b to the same object as a. I don't
know why b would think you had bound it to a[0].


David
Click to expand...

You're right David. That was supposed to be b = a[0] and _not_ b = a.

Todd
 
B

Bob Hutchison

Hi,

Sorry for replying to my own post, can somebody confirm please that
the following code proves that Array#shift does not leak?
Thx in advance
def count
i = 0
ObjectSpace.each_object{ i += 1 }
i
end

a = []
10.times do
10_000.times do
a << "a"
a.shift
end
ObjectSpace.garbage_collect
p count
end
381
382
382
382
382
382
382
382
382
382

Robert
Click to expand...


Try it this way:

class Thing
end

def count
i = 0
ObjectSpace.each_object(Thing){ i += 1 }
i
end

a = []
10.times do
10_000.times do
a << Thing.new
end
ObjectSpace.garbage_collect
10_000.times do
a.shift
end
ObjectSpace.garbage_collect
puts "count(1): #{count} size: #{a.size}"
a.push(nil).pop
ObjectSpace.garbage_collect
puts "count(2): #{count} size: #{a.size}"

10_000.times do
a << Thing.new
end
ObjectSpace.garbage_collect
10_000.times do
a[0] = nil # <<<<<< !!!!
a.shift
end
ObjectSpace.garbage_collect
puts "count(3): #{count} size: #{a.size}"
end

count(1): 10000 size: 0
count(2): 0 size: 0
count(3): 0 size: 0
count(1): 10000 size: 0
count(2): 0 size: 0
count(3): 0 size: 0
count(1): 10000 size: 0
count(2): 0 size: 0
count(3): 0 size: 0
count(1): 10000 size: 0
count(2): 0 size: 0
count(3): 0 size: 0
count(1): 10000 size: 0
count(2): 0 size: 0
count(3): 0 size: 0
count(1): 10000 size: 0
count(2): 0 size: 0
count(3): 0 size: 0
count(1): 10000 size: 0
count(2): 0 size: 0
count(3): 0 size: 0
count(1): 10000 size: 0
count(2): 0 size: 0
count(3): 0 size: 0
count(1): 10000 size: 0
count(2): 0 size: 0
count(3): 0 size: 0
count(1): 10000 size: 0
count(2): 0 size: 0
count(3): 0 size: 0

----
Bob Hutchison -- tumblelog at http://
www.recursive.ca/so/
Recursive Design Inc. -- weblog at http://www.recursive.ca/
hutch
http://www.recursive.ca/ -- works on http://www.raconteur.info/
cms-for-static-content/home/
 
R

Robert Dober

Hi,

Sorry for replying to my own post, can somebody confirm please that
the following code proves that Array#shift does not leak?
Thx in advance
def count
i = 0
ObjectSpace.each_object{ i += 1 }
i
end

a = []
10.times do
10_000.times do
a << "a"
a.shift
end
ObjectSpace.garbage_collect
p count
end
381
382
382
382
382
382
382
382
382
382

Robert
Click to expand...


Try it this way:

class Thing
end

def count
i = 0
ObjectSpace.each_object(Thing){ i += 1 }
i
end

a = []
10.times do
10_000.times do
a << Thing.new
end
ObjectSpace.garbage_collect
10_000.times do
a.shift
end
ObjectSpace.garbage_collect
puts "count(1): #{count} size: #{a.size}"
a.push(nil).pop
ObjectSpace.garbage_collect
puts "count(2): #{count} size: #{a.size}"

10_000.times do
a << Thing.new
end
ObjectSpace.garbage_collect
10_000.times do
a[0] = nil # <<<<<< !!!!
a.shift
end
ObjectSpace.garbage_collect
puts "count(3): #{count} size: #{a.size}"
end

count(1): 10000 size: 0
count(2): 0 size: 0
count(3): 0 size: 0
count(1): 10000 size: 0
count(2): 0 size: 0
count(3): 0 size: 0
count(1): 10000 size: 0
count(2): 0 size: 0
count(3): 0 size: 0
count(1): 10000 size: 0
count(2): 0 size: 0
count(3): 0 size: 0
count(1): 10000 size: 0
count(2): 0 size: 0
count(3): 0 size: 0
count(1): 10000 size: 0
count(2): 0 size: 0
count(3): 0 size: 0
count(1): 10000 size: 0
count(2): 0 size: 0
count(3): 0 size: 0
count(1): 10000 size: 0
count(2): 0 size: 0
count(3): 0 size: 0
count(1): 10000 size: 0
count(2): 0 size: 0
count(3): 0 size: 0
count(1): 10000 size: 0
count(2): 0 size: 0
count(3): 0 size: 0

----
Bob Hutchison -- tumblelog at http://
www.recursive.ca/so/
Recursive Design Inc. -- weblog at http://www.recursive.ca/
hutch
http://www.recursive.ca/ -- works on http://www.raconteur.info/
cms-for-static-content/home/
Click to expand...
Amazing Bob,
it has nothing to do with nil though, but with the assignment to a[0]
change a[0] = nil to a[0]=42, you get the same results.
You can even do the following

def count
i = 0
ObjectSpace.each_object{ i += 1 }
i
end

a = []
10_000.times do
a << Object.new
end
ObjectSpace.garbage_collect
10_000.times do
a.shift
end
ObjectSpace.garbage_collect
puts "count(1): #{count} size: #{a.size}"
a.push(nil).pop
ObjectSpace.garbage_collect
puts "count(2): #{count} size: #{a.size}"

10_000.times do
a << Object.new
end
ObjectSpace.garbage_collect
10_000.times do
a[0] = Object.new
a.shift
end
ObjectSpace.garbage_collect
puts "count(3): #{count} size: #{a.size}"

count(1): 10386 size: 0
count(2): 389 size: 0
count(3): 392 size: 0

There remains one thing to be clarified, is this really a bug?
I do not think so, I just ran this until I got 200 points on my terminal :-0

a = []
loop do
a << Array.new( 1_000_000){ Object.new }
a.shift
$stdout.print "."
$stdout.flush
end

on my Zenwalk box memory is allocated and released regualrely, I doubt
if ObjectSpace is the right tool to use.


Anyway forgive me to be blunt but everybody should just use Array#shift.

Cheers
Robert
 
B

Bob Hutchison

There remains one thing to be clarified, is this really a bug?
I do not think so, I just ran this until I got 200 points on my
terminal :-0

a = []
loop do
a << Array.new( 1_000_000){ Object.new }
a.shift
$stdout.print "."
$stdout.flush
end
Click to expand...

The code in Ruby that deals with the stuff before the start of the
array is non-trivial. The push(nil).pop thing I did, or the use of <<
you did triggers a cleanup. If you do your latest example without
interleaving the << and shift you'll have a problem (change the
implementation of the Thing class in my example to allocate the
million element array and see what happens -- well DON'T actually,
you won't like what it does to your machine).

The trouble here is that the normal use of queues involves filling
them up then emptying them. If you use an Array and Array.shift to
empty the queue there's going to be at least one element 'stuck' in
front of the array, likely more than 1. This might not matter but it
might. It mattered to my cache implementation, and it mattered to
Mongrel's task management.

Cheers,
Bob

----
Bob Hutchison -- tumblelog at http://
www.recursive.ca/so/
Recursive Design Inc. -- weblog at http://www.recursive.ca/
hutch
http://www.recursive.ca/ -- works on http://www.raconteur.info/
cms-for-static-content/home/
 
R

Robert Dober

There remains one thing to be clarified, is this really a bug?
I do not think so, I just ran this until I got 200 points on my
terminal :-0

a = []
loop do
a << Array.new( 1_000_000){ Object.new }
a.shift
$stdout.print "."
$stdout.flush
end
Click to expand...

The code in Ruby that deals with the stuff before the start of the
array is non-trivial. The push(nil).pop thing I did, or the use of <<
you did triggers a cleanup. If you do your latest example without
interleaving the << and shift you'll have a problem (change the
implementation of the Thing class in my example to allocate the
million element array and see what happens -- well DON'T actually,
you won't like what it does to your machine).

The trouble here is that the normal use of queues involves filling
them up then emptying them. If you use an Array and Array.shift to
empty the queue there's going to be at least one element 'stuck' in
front of the array, likely more than 1. This might not matter but it
might. It mattered to my cache implementation, and it mattered to
Mongrel's task management.
Click to expand...
Well I guess I have to believe you, but I would *love* to reproduce it
if I do
times do
<<
end
times do
shift
end
it will leak?

R.
 
G

Giles Bowkett

Other people, however, believe that you enter a queue at
the head and leave at the tail, in the manner of food passing through a
snake. Queues written in that way appear in places that might be
considered authoritiative, such as the GNU/Linux operating system, making
the point of view hard to dismiss however repugnant you find the idea of
getting your data from a snake's rear-end."

<http://en.wikipedia.org/wiki/FIFO>
Click to expand...

Repugnant is definitely the word. I don't like the idea of getting my
information from a snake's asshole. If I wanted to do that, I'd talk
to Steven Ballmer.

--
Giles Bowkett

Blog: http://gilesbowkett.blogspot.com
Portfolio: http://www.gilesgoatboy.org
Tumblelog: http://giles.tumblr.com/
 
B

Bob Hutchison

Hi,

Well I guess I have to believe you, but I would *love* to reproduce it
if I do
times do
<<
end
times do
shift
end
it will leak?
Click to expand...

How else would you describe the 10k Things left in memory after the
shifts in the modified version of your test case?

Cheers,
Bob
R.
Click to expand...

----
Bob Hutchison -- tumblelog at http://
www.recursive.ca/so/
Recursive Design Inc. -- weblog at http://www.recursive.ca/
hutch
http://www.recursive.ca/ -- works on http://www.raconteur.info/
cms-for-static-content/home/
 
R

Robert Dober

Hi,



How else would you describe the 10k Things left in memory after the
shifts in the modified version of your test case?
Click to expand...
But that is assuming that the ObjectSpace tools tell the truth, it
does however not look like that on my box.
I have therefore no reason to believe that the above structure of the
code will leak, and have asked you if it will.
I will kill my box tonight ;) (or not).
R.
 
B

Bob Hutchison

But that is assuming that the ObjectSpace tools tell the truth, it
does however not look like that on my box.
I have therefore no reason to believe that the above structure of the
code will leak, and have asked you if it will.
I will kill my box tonight ;) (or not).
Click to expand...

I guess you'll have to convince your self :)

Cheers,
Bob
R.
Click to expand...

----
Bob Hutchison -- tumblelog at http://
www.recursive.ca/so/
Recursive Design Inc. -- weblog at http://www.recursive.ca/
hutch
http://www.recursive.ca/ -- works on http://www.raconteur.info/
cms-for-static-content/home/
 
E

Eric Mahurin

Hi,



How else would you describe the 10k Things left in memory after the
shifts in the modified version of your test case?
Click to expand...


The problem is that Ruby's COW (copy-on-write) scheme is messed up for
arrays. I've found much worse cases performance and memory-wise. Try
doing a small #slice on a big array a bunch and modify the small
slices. I made a 1.9 patch a couple years ago that fixed the problem
and made ALL operations near the front just as fast as the operations
on the back. Unfortunately, it never made it in. The way I did it
might be unique, not sure. I thought C++ deque does something
similiar, but it doesn't. When I find time, I'll try to do the fix
again.
 
R

Robert Dober

I guess you'll have to convince your self :)
Click to expand...
yes I have because it just did not happen,

526/28 > uname -a && ruby -v
Linux zenwalk 2.6.18.1 #1 SMP PREEMPT Mon Oct 30 15:32:27 CET 2006
i686 athlon-4 i386 GNU/Linux
ruby 1.8.6 (2007-03-13 patchlevel 0) [i686-linux]

the program was
N = 1000
M = 1000
a = []
loop do
N.times do
a << Array.new( M ){ Object.new }
end
N.times do
a.shift
end
end

Ruby allocated up to 43M and then decided to release 3M regularly,
seems a very reasonable strategy to me.
I feel that it would be nice to show the exact leaking code so that I
can run it.

Cheers
Robert
 
B

Bob Hutchison

The problem is that Ruby's COW (copy-on-write) scheme is messed up for
arrays. I've found much worse cases performance and memory-wise. Try
doing a small #slice on a big array a bunch and modify the small
slices. I made a 1.9 patch a couple years ago that fixed the problem
and made ALL operations near the front just as fast as the operations
on the back. Unfortunately, it never made it in. The way I did it
might be unique, not sure. I thought C++ deque does something
similiar, but it doesn't. When I find time, I'll try to do the fix
again.
Click to expand...

Eric, thanks for the information.

Cheers,
Bob

----
Bob Hutchison -- tumblelog at http://
www.recursive.ca/so/
Recursive Design Inc. -- weblog at http://www.recursive.ca/
hutch
http://www.recursive.ca/ -- works on http://www.raconteur.info/
cms-for-static-content/home/
 
R

Robert Dober

Eric, thanks for the information.
Click to expand...
Now this is all very great but could you share with us what is going
on, right now I just see people complaining that it is broken, no
reference to a bug report, no test code, I feel that this is highly
unfair to Ruby.

Whatever I am not going to try to reproduce an error that might not
even be there.
I have not found any reference to this on Ruby core, could you please
give a pointer to your patch Eric?

Robert
 
B

Bob Hutchison

I guess you'll have to convince your self :)
Click to expand...
yes I have because it just did not happen,

526/28 > uname -a && ruby -v
Linux zenwalk 2.6.18.1 #1 SMP PREEMPT Mon Oct 30 15:32:27 CET 2006
i686 athlon-4 i386 GNU/Linux
ruby 1.8.6 (2007-03-13 patchlevel 0) [i686-linux]

the program was
N = 1000
M = 1000
a = []
loop do
N.times do
a << Array.new( M ){ Object.new }
end
N.times do
a.shift
end
end

Ruby allocated up to 43M and then decided to release 3M regularly,
seems a very reasonable strategy to me.
I feel that it would be nice to show the exact leaking code so that I
can run it.
Click to expand...

You need to be careful what it is you are testing.

Try the tiny variation I've supplied below as it is, it'll execute
relatively benignly. Then comment out the crucial line indicated by
the comment. If you dare. BTW, if you run this make sure you keep on
top of things and kill it before it starts screwing up your machine.
Make sure you don't have anything important unsaved.

Why don't we keep all the 'a' arrays we generate? Shouldn't cause a
problem right? If fact if you don't comment out the crucial line
memory use will grow relatively slowly. If you do comment it out,
then, well, it *is* your machine.

BTW, the *only* thing special about nil is that there is only one of
them. You could use a symbol, true/false, a number -- just don't
create a new object.

What happens if you comment out the whole second N.times loop? I get
strangely similar behaviour to just commenting out the crucial line.
Why's that? Because, in neither case, none of the arrays of Object is
being collected.

If you get the behaviour I'm getting, how do you explain it other
than as a leak?

Innocent bystanders: if you comment out that crucial line before
running the program PAY ATTENTION AND BE READY TO KILL THE PROCESS
BEFORE IT LOCKS UP YOUR MACHINE (very bad on OS X, it is an abrupt
lockup of the system after about 20s on my machine, Ctrl-C won't
work, get either your activity monitor up and visible or the force
quit dialog).

N = 1000
M = 1000

as = []
loop do
a = []
N.times do
a << Array.new( M ){ Object.new }
end
N.times do
a[0] = nil # <<< the crucial line
a.shift
end

as << a

GC.start
STDERR << '.'
end

Cheers,
Bob
Cheers
Robert
Click to expand...

----
Bob Hutchison -- tumblelog at http://
www.recursive.ca/so/
Recursive Design Inc. -- weblog at http://www.recursive.ca/
hutch
http://www.recursive.ca/ -- works on http://www.raconteur.info/
cms-for-static-content/home/
 
B

Bob Hutchison

Now this is all very great but could you share with us what is going
on, right now I just see people complaining that it is broken, no
reference to a bug report, no test code, I feel that this is highly
unfair to Ruby.

Whatever I am not going to try to reproduce an error that might not
even be there.
I have not found any reference to this on Ruby core, could you please
give a pointer to your patch Eric?
Click to expand...

Robert, I've provided several pieces of code to illustrate this problem.

I'm afraid this thread has the potential to degenerate very very
quickly. I'm sorry I'm involved, and I'd very much like to be
uninvolved as of now.

Cheers,
Bob
Robert
Click to expand...

----
Bob Hutchison -- tumblelog at http://
www.recursive.ca/so/
Recursive Design Inc. -- weblog at http://www.recursive.ca/
hutch
http://www.recursive.ca/ -- works on http://www.raconteur.info/
cms-for-static-content/home/
 
E

Eric Mahurin

Now this is all very great but could you share with us what is going
on, right now I just see people complaining that it is broken, no
reference to a bug report, no test code, I feel that this is highly
unfair to Ruby.

Whatever I am not going to try to reproduce an error that might not
even be there.
I have not found any reference to this on Ruby core, could you please
give a pointer to your patch Eric?

Robert
Click to expand...

Here it is from over 2 years ago:

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/5861

I believe matz tried incorporating it about a year ago, but there were
too many changes in the code since I patched it. You might find a
discussion from then.

The message above also has a testbench (for some reason it is
base-64). Last I tried it, there were some improvements, but there
were still some tests that looked clearly leaky and/or slow.

Eric
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Why are "Array#push" and "pop" not "push!" and "pop!"? 27
Push and Pop on a Priority Queue appears to change nature of Array 5
shift vs. slice!(0) and others 11
push and pop - stacks 6
FAQ 4.46 How do I handle linked lists? 0
Multiprocessing: don't push the pedal to the metal? 5
shift, signed unsigned 5
pop up error 4

Members online

Total: 27 (members: 3, guests: 24)
Robots: 152

Forum statistics

Threads
473,777
Messages
2,569,604
Members
45,234
Latest member
SkyeWeems

Latest Threads

Top