pop/push, shift/unshift

[Bob Hutchison]

I understand your explanation, but this sounds like a bug to me. I
understand the optimization part of not shifting everything in the
shift method, but if that's a desired way of working I suppose it
should be warned for the users of Array. In light of this then, the
recommended approach for queue semantics would be to use unshift and
pop?

unshift/pop seems to me to be a possibility. I think it'll have to be =20=

tested though. One can easily imagine that ruby does not release =20
allocated space in an array, as an optimisation. If this is the case =20
then the queue will continue to grow unbound but after the end of the =20=

array instead before the start.

Maybe a linked list?

Cheers,
Bob

Thanks,

Jesus.

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

 

[Bob Hutchison]

I understand your explanation, but this sounds like a bug to me. I
understand the optimization part of not shifting everything in the
shift method, but if that's a desired way of working I suppose it
should be warned for the users of Array. In light of this then, the
recommended approach for queue semantics would be to use unshift and
pop?

I just did a quick test. It looks as though Ruby is now handling both =20=

the unshift/pop and push/shift properly. I know when I reported it in =20=

Ruby 1.8.4 there was a discussion about how to deal with this, and it =20=

looks as though 1.8.5 has it working (or I've patched my version of =20
Ruby and have forgotten about it).

So maybe not a problem, or too big of a problem. Just don't forget =20
about the cells holding references, that is definitely there in 1.8.5.

Cheers,
Bob

Thanks,

Jesus.

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

 

[Bob Hutchison]

I just did a quick test. It looks as though Ruby is now handling =20
both the unshift/pop and push/shift properly. I know when I =20
reported it in Ruby 1.8.4 there was a discussion about how to deal =20
with this, and it looks as though 1.8.5 has it working (or I've =20
patched my version of Ruby and have forgotten about it).

So maybe not a problem, or too big of a problem. Just don't forget =20
about the cells holding references, that is definitely there in 1.8.5.

I just wrote a little test script. It looks as though push will =20
cleanup the empty space left by shift. So your queue should be okay =20
on *average* either way you implement it. Though you'll be growing =20
the array until push is called (and at the same time there will be =20
invisible references to objects)... generally working but with =20
potentially subtle bugginess.

Cheers,
Bob

Cheers,
Bob

hutch
http://www.recursive.ca/ -- works on http://=20
www.raconteur.info/cms-for-static-content/home/

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

 

[Jesús Gabriel y Galán]

I just wrote a little test script. It looks as though push will
cleanup the empty space left by shift. So your queue should be okay
on *average* either way you implement it. Though you'll be growing
the array until push is called (and at the same time there will be
invisible references to objects)... generally working but with
potentially subtle bugginess.

Thanks, it's good to know.

Kind regards,

Jesus.

 

[Randy Kramer]

Have a look at #shift and #unshift.

Thanks! (I did notice those later.)

Randy Kramer

 

[bbiker]

On 23-Oct-07, at 10:02 AM, Jesús Gabriel y Galán wrote:

Hi,

On 10/23/07, (e-mail address removed) <[email protected]>
wrote:

I like this:

class Array
alias :enqueue ush
alias :dequeue :shift
end

Then you get Queue semantics and the start of the queue is the first
element in the Array . (you could do enqueue --> unshift, dequeue
--> pop if you rather have the first element of the queue the last in
the array).

You have to be really careful here. Push/pop and shift/unshift are
not the same functions working on opposite ends of the array, no
matter what it sounds like from the documentation.

There is an issue with shift that I think amounts to a bug. Shift/
unshift work at the beginning of the array, so shift conceptually
requires moving array elements around. Ruby (and other programming
languages too, specifically some implementations of Common Lisp)
optimise shift so as to not have to actually move anything in memory.
What it does is, more or less, to move the start of the array 'right'
-- so no movement but there is now some part of the array before the
start of the array. The bug is that Ruby doesn't stomp on the cell of
the array that is being shifted before the start, and so that cell
still contains a reference to some object (and IT IS INVISIBLE).

You say this will never happen? or rarely? Well, it's not 'never' for
sure, and 'rarely' doesn't help much when you get caught by it. How
did I find out about it? Implementing a cache (the uncached stuff was
hanging around in memory, intermittently since unshift will re-use
the parts of the array before the start). I also found (and reported,
maybe even supplied a patch for) a problem in Mongrel's thread
management code that was using shift. How did I debug it the first
time? Don't ask.

I believe/hope that this will be fixed in some future version of Ruby.

This monkey patch fixes the problem, if this is how you want to solve
it...

class Array
alias :clingy_shift :shift

def shift
self[0] = nil
clingy_shift
end
end

Cheers,
Bob

Jesus.

----
Bob Hutchison -- tumblelog at http://www.recursive.ca/so/
Recursive Design Inc. -- weblog athttp://www.recursive.ca/
hutchhttp://www.recursive.ca/ -- works onhttp://www.raconteur.info/
cms-for-static-content/home/- Hide quoted text -

- Show quoted text -

It was my understanding that unshift was the leaky method. There was a
monkey patch but I have lost the reference to that thread.

 

[Thufir]

I'm not sure what exactly you mean. #push and #pop just work as one
would expect from a LIFO.

Perhaps he means to work with a FIFO?

"Head or tail first

Authors and users of FIFO queue software should consider carefully the
use of the terms "head" and "tail" to refer to the two ends of the queue.
To many people, items should enter a queue at the tail, remain in the
queue until they reach the head and leave the queue from there. This
point of view is justified by analogy with queues of people waiting for
some kind of service and parallels the use of "front" and "back" in the
above example. 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>




-Thufir

 

[Thufir]

Implementing a cache (the uncached stuff was hanging around in memory,
intermittently since unshift will re-use the parts of the array before
the start). I also found (and reported, maybe even supplied a patch for)
a problem in Mongrel's thread management code that was using shift. How
did I debug it the first time? Don't ask.

Could this lead to a security problem down the road?


-Thufir

 

[Todd Benson]

Hi --



No thanks. #shift/#unshift are fine, and certainly I don't want to
have to figure out what people have aliased enqueue and dequeue to
before I can understand their code.

Not only that, but enqueue and dequeue return different objects.
Enqueue returns an array, and dequeue returns the object that was
shifted from the stack.

Todd

 

[Todd Benson]

Not only that, but enqueue and dequeue return different objects.
Enqueue returns an array, and dequeue returns the object that was
shifted from the stack.

Todd

Hmm. I guess shift/unshift are like that too. Sorry for the noise.

I'm surprised, though, that this thread has received so much
attention. I don't really have a problem with the terminology, or the
behavior of the methods pop/push/shift/unshift. In fact, the
shift/unshift methods were two of many things that attracted me to
Ruby. I know they exist in other languages, but I haven't experienced
the others in depth yet.

Todd

 

[Jesús Gabriel y Galán]

I'm surprised, though, that this thread has received so much
attention. I don't really have a problem with the terminology, or the
behavior of the methods pop/push/shift/unshift. In fact, the
shift/unshift methods were two of many things that attracted me to
Ruby. I know they exist in other languages, but I haven't experienced
the others in depth yet.

Well, I answered to this thread not because I had any problem with the
terminology, but to comment on the fact that pop/push is stack
semantics, and I would like also queue semantics. After thinking about
what David and I were discussing about how to make this happen, I'm
settled on the following if I ever want queue/stack semantics :

class Queue
def initialize
@buffer = []
end

def enqueue(element)
@buffer.unshift(element)
end

def dequeue
@buffer.pop
end

def empty?
@buffer.empty?
end
end

But, there's already a Queue implementation in ruby core, so I would
use that, although that class is aimed at synchronizing threads so I
might implement a simple queue like the above at some point if I need
simple queue semantics.
I would corresponding class for Stack, with push/pop being delegated
to array's push and pop . Or just use an array if the fact of
having more methods than a stack is not a problem .

Jesus.

 

[Bob Hutchison]

Hmm. I guess shift/unshift are like that too. Sorry for the noise.

I'm surprised, though, that this thread has received so much
attention. I don't really have a problem with the terminology, or the
behavior of the methods pop/push/shift/unshift. In fact, the
shift/unshift methods were two of many things that attracted me to
Ruby. I know they exist in other languages, but I haven't experienced
the others in depth yet.

I agree with you. I don't have any problem with the terminology, and
I certainly appreciate the implementation. The only problem I have is
the two specific deficiencies in the optimisation of un/shift. With
some release after 1.8.5 this should be completely resolved, it is
much better in 1.8.5 than in 1.8.4 I think.

Cheers,
Bob

Todd

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

 

[Bob Hutchison]

Could this lead to a security problem down the road?

I don't think so in the cases I mentioned. The objects in front of
the array are not accessible using Ruby. I suppose you could write
some C code easily enough to get at them.

Cheers,
Bob

-Thufir

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

 

[Todd Benson]

class Queue
def initialize
@buffer =3D []
end

def enqueue(element)
@buffer.unshift(element)
end

def dequeue
@buffer.pop
end

def empty?
@buffer.empty?
end
end

But, there's already a Queue implementation in ruby core, so I would
use that, although that class is aimed at synchronizing threads so I
might implement a simple queue like the above at some point if I need
simple queue semantics.
I would corresponding class for Stack, with push/pop being delegated
to array's push and pop . Or just use an array if the fact of
having more methods than a stack is not a problem .

Jesus.

You want to -- as mentioned elsewhere in this thread -- push it in the
front and take it out the back. Interesting. I guess it all comes
down to what direction you want to go. I like to see the procession
moving towards the zeroth position and not to some indexth position.

If I was going to queue, it would be more like...

class Queue
def initialize enum
@list =3D enum if enum.is_a? Enumerable
end
def enqueue object
@list << object
#haven't looked at C code, but
#I think this is the same as #push
end
def dequeue
@list.shift
end
def cut_in_line object
@list.unshift object
end
def bouncer_removes_last_guy
@list.pop
end

end


Todd

 

[Bob Hutchison]

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

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

 

[Robert Dober]

push/pop.

I always liked that visualization. The problem for me (and I'm not the OP) is
that in Ruby you have to lift all the plates off, put the new plate on the
bottom, and then put all the plates back. (Likewise when you want to "pop"
that plate.) ;-) (Because Ruby uses push and pop on the end of the array
instead of the beginning.)

Get on your feet again, no need to stand on your hands all the time .
R.

 

[Todd Benson]

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

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

 

[Todd Benson]

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

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

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.

Todd

 

[Jesús Gabriel y Galán]

class Queue
def initialize
@buffer =3D []
end

def enqueue(element)
@buffer.unshift(element)
end

def dequeue
@buffer.pop
end

def empty?
@buffer.empty?
end
end

But, there's already a Queue implementation in ruby core, so I would
use that, although that class is aimed at synchronizing threads so I
might implement a simple queue like the above at some point if I need
simple queue semantics.
I would corresponding class for Stack, with push/pop being delegated
to array's push and pop . Or just use an array if the fact of
having more methods than a stack is not a problem .

Jesus.

You want to -- as mentioned elsewhere in this thread -- push it in the
front and take it out the back. Interesting. I guess it all comes
down to what direction you want to go. I like to see the procession
moving towards the zeroth position and not to some indexth position.

The truth is that I don't mind in which direction to go, because I
only want queue semantics, and that would be part of an implementation
detail. I changed in my example to unshift/pop because of the
recommendations made above in this thread about not using shift, but
other than that I wouldn't mind.

Jesus.

 

[Bob Hutchison]

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

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.

It has to do with an optimisation in the implementation of shift
(there's a series of posts regarding this earlier in this thread). In
brief, shift optimises itself by 'shifting' the start of the array
rather than shifting the contents of the array. The effect is that
using shift leaves an old part of the array in front of the start of
the array (but you cannot access it). The problem is that the shift
implementation doesn't 'clear' the original 0th element, so it is
still in memory, is not accessible, but the garbage collector can see
it. In effect, the object referenced isn't collected because there is
a reference. This is a memory leak. Sooner or later it'll get fixed
up, but sometimes it really is later.

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.

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, and @list.shift makes
the original @list[0] 'disappear', and the last reference to tmp
returns it as the result of the method.

Unfortunately it isn't as simple as everyone would like it to be.
But, as I've mentioned elsewhere, this will all go away in some
future version of Ruby. Already Ruby 1.8.5 is much better than 1.8.4

Cheers,
Bob

Todd

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