From: Bob Hutchison <hutch@...>
Date: 2007-10-23T23:43:22+09:00
Subject: Re: pop/push, shift/unshift


On 23-Oct-07, at 10:32 AM, Bob Hutchison wrote:

>
> On 23-Oct-07, at 10:02 AM, Jesús Gabriel y Galán wrote:
>
> Hi,
>
>> On 10/23/07, richard.j.dale@gmail.com <richard.j.dale@gmail.com>  
>> wrote:
>>
>>> Maybe 'enque' and 'deque' could be used as names for methods to put
>>> items on the front of a Queue and remove items from the back  
>>> somewhere
>>> in Ruby - then you wouldn't need push/pop and shift/unshift  
>>> depending
>>> on which end of the queue you were operating on.
>>
>> I like this:
>>
>> class Array
>>    alias :enqueue :push
>>    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.

Of course I forgot to mention the specific problem for your scheme.  
My previous email outlines how un/shift works (see below, I left it  
quoted).

In your scheme you are using unshift to remove from the front, and  
push to add to the back. As I mentioned shift moves the start point  
of the array. Every time you use shift you 'loose' a cell of your  
array before the start of the array. Unshift will re-use those lost  
cells (Ruby might be doing something clever with these but I wouldn't  
count on it). Push will never reuse them since it is adding to the  
end of the array. Consequently the Array used for the queue will get  
larger and larger.

I guess this is just reinforcing David's comment.

Cheers,
Bob

>
> 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 at http://www.recursive.ca/ 
> hutch
> http://www.recursive.ca/       -- works on http:// 
> www.raconteur.info/cms-for-static-content/home/
>
>
>
>

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